基于索套啟發(fā)式的物流中心路線規(guī)劃模型

基于索套啟發(fā)式的物流中心路線規(guī)劃模型

在物流中心團(tuán)隊(duì)的實(shí)際運(yùn)營計(jì)劃過程中，服務(wù)對象包括用于支付交通需求的車輛路線規(guī)劃，以及用于返回交通需求的車輛路線規(guī)劃，即混合運(yùn)輸需求車隊(duì)的線路規(guī)劃問題。由于客戶的需求、返回需求和車輛運(yùn)輸能力的限制，混合運(yùn)輸需求車隊(duì)的線路規(guī)劃問題不能使用經(jīng)典的旅行商業(yè)問題解決方案。為了找到這個問題的滿意的解，使用之前的團(tuán)隊(duì)法和線性法，并根據(jù)使用客戶分布模型來區(qū)分客戶子集的模型，提出每個節(jié)點(diǎn)可以訪問一次或兩次的消息啟動方法。集類開發(fā)的語法解與用附近搜索法獲得的規(guī)律成本進(jìn)行比較。集類開發(fā)教育法解釋的路徑方案的成本比用附近搜索法獲得的殼成本低。1最短路徑劃分在有混合運(yùn)輸需求的n-1個客戶中,以i=1代表配送中心,i=2,3,…,n代表第i個客戶,di和pi各代表第i個客戶的投遞和回投需求,用k輛車向這(n-1)個客戶提供運(yùn)輸服務(wù),L(1)為初始載運(yùn)量,Pk為車輛k的走行路線,L(1)=∑i∈Pkdi?cd(ik)=∑i=2ikdi?cp(ik)=∑i=2ikpi?L(1)=∑i∈Ρkdi?cd(ik)=∑i=2ikdi?cp(ik)=∑i=2ikpi?式中:ik為第k輛車沿走行路線Pk的當(dāng)前所在點(diǎn);cd(ik)為沿路線Pk的累計(jì)投遞需求量;cp(ik)為沿路線Pk的累計(jì)回投需求量.在所有的客戶i運(yùn)輸需求滿足di≥pi或di≤pi(i=2,3…n)的情況下,用需求值較大的值作為參數(shù)給車隊(duì)車輛分配客戶子集,化為經(jīng)典旅行商問題,即可得到各車輛的最優(yōu)線路.而當(dāng)有的客戶di≥pi,有的di<pi時,最短的哈密爾頓回路可能是不可行的,在任一節(jié)點(diǎn)ik都可能使載運(yùn)量L(ik)=L(1)?cd(ik)+cp(ik)L(ik)=L(1)-cd(ik)+cp(ik)大于車輛載運(yùn)容量R.雖然可以將di≥pi的客戶劃分為一個子集s1,將di<pi的客戶劃分為一個子集s2,先對s1中的客戶進(jìn)行服務(wù)再對s2中的客戶進(jìn)行服務(wù),但很明顯這必定使運(yùn)輸總距離大大拉長,成本也同時上升.可行的最短路徑的值必然在最短哈密爾頓路徑和劃分為兩種需求子集下最短路徑之間.假定物流中心的所有車輛有相同的載運(yùn)容量R,服務(wù)(n-1)個有混合運(yùn)輸需求的客戶,所需要的最少車輛數(shù)k=max???????ent????∑i=2ndiR????+1,ent????∑i=2npiR????+1???????.(1)k=max{ent(∑i=2ndiR)+1,ent(∑i=2npiR)+1}.(1)一輛車對應(yīng)一條索套路線,選定k個離配送中心最遠(yuǎn)的點(diǎn)為種子節(jié)點(diǎn),記為sv(v=1,2,…,k),一個節(jié)點(diǎn)指定給一輛車,把剩下的(n-1-k)個節(jié)點(diǎn)按以下客戶子集分配模型進(jìn)行劃分.min∑i=2n∑v=1kfivwiv,(2)s.t.∑i=2ndiwiv≤R,?v；i≠1,i∈sˉv;(3)∑i=2npiwiv≤R,?v；i≠1,i∈sˉv;(4)∑v=1kwiv=1,?v；i≠1,i∈sˉv.(5)min∑i=2n∑v=1kfivwiv,(2)s.t.∑i=2ndiwiv≤R,?v；i≠1,i∈sˉv;(3)∑i=2npiwiv≤R,?v；i≠1,i∈sˉv;(4)∑v=1kwiv=1,?v；i≠1,i∈sˉv.(5)wiv=1表示車輛v訪問i節(jié)點(diǎn),wiv=0表示車輛v不訪問i節(jié)點(diǎn).因子fiv由下式計(jì)算fiv=C1i+Cisv?C1sv,(6)fiv=C1i+Cisv-C1sv,(6)式中:fiv為將i指定給第v輛車(v個種子結(jié)點(diǎn))車輛旅行費(fèi)用的增加值;C1i為第v輛車從物流中心到第i個客戶的旅行費(fèi)用;Cisv為第v輛車從第i個客戶到種子節(jié)點(diǎn)sv的旅行費(fèi)用,C1sv為第v輛車從物流中心到種子節(jié)點(diǎn)sv的旅行費(fèi)用.通過以上模型使得指定給每一輛車的客戶子集相互鄰近,且使客戶分配到各子集后增加的成本之和最小,并且每一個子集的投遞運(yùn)輸需求之和與回投運(yùn)輸需求之和都小于車輛裝載容量.2哈密爾頓近鄰搜索模型在通過上文給每一輛車分配了客戶子集后,在客戶子集中的路線選擇模型如下:min∑cijxij,(7)s.t.L(ik)≤R,(8)∑j=1nxij≤2,i=1,2,?,n,(9)∑i=1nxij≤2,j=1,2,?,n,(10)xij∈{0,1,2},i,j=1,2,?,n,i≠j.(11)min∑cijxij,(7)s.t.L(ik)≤R,(8)∑j=1nxij≤2,i=1,2,?,n,(9)∑i=1nxij≤2,j=1,2,?,n,(10)xij∈{0,1,2},i,j=1,2,?,n,i≠j.(11)該模型的索套啟發(fā)式解法步驟如下:(1)在客戶子集中用近鄰搜索算法尋找出1條最短的哈密爾頓回路S,沿配送中心順該路搜尋ik點(diǎn),使得L(ik)≤R且L(ik+1)>R.對任意j<k,L(ij)≤R,如果沒有這樣的節(jié)點(diǎn),停止搜索,該路線即是最優(yōu)路線;如果找到這樣的節(jié)點(diǎn),將第1個索環(huán)節(jié)點(diǎn)i1置為索把結(jié)點(diǎn),即第1次訪問i1時只投遞不回投,離開i1時的載運(yùn)量為L(1)+cp(ik)-cd(ik)-pi1,i1變?yōu)樗鹘Y(jié),i1后面的所有節(jié)點(diǎn)構(gòu)成新的索環(huán).轉(zhuǎn)向(2).(2)繼續(xù)沿回路S,尋找滿足L(ik)≤R且L(ik+1)>R(對任意j<k,L(ij)≤R)的節(jié)點(diǎn)ik.將第1個索環(huán)節(jié)點(diǎn)置為索把結(jié)點(diǎn),第1次訪問該節(jié)點(diǎn)時只投遞不回投,離開該點(diǎn)的載運(yùn)量為L(1)-cd(ik)+cp(ik)-pik-pi1.(3)重復(fù)步驟(2)直到路徑包括所有的節(jié)點(diǎn).如所有節(jié)點(diǎn)都滿足判別式L(ik)≤R,且cd(ik)≤R,cp(ik)≤R,停止.連接路徑的最后1個節(jié)點(diǎn)和最后一個創(chuàng)建的索把節(jié)點(diǎn),最后一個創(chuàng)建的索把節(jié)點(diǎn)即索結(jié),索把節(jié)點(diǎn)第1次訪問該節(jié)點(diǎn)時只投遞不回投,第2次訪問時再回投,該索套回路即模型的滿意解.如不滿足3個判別式,則轉(zhuǎn)至步驟(2),直到滿足3個約束條件為止.3客戶結(jié)論分配以下以成都某啤酒廠配送中心的啤酒配送和空瓶回收為例.有13個銷售點(diǎn)有混合運(yùn)輸需求,該啤酒廠配送中心有2輛載運(yùn)容量為150箱的車,各銷售點(diǎn)間車輛的運(yùn)行成本見表1,各銷售點(diǎn)的混合運(yùn)輸需求見表2.首先,用近鄰搜索法得到3條回路:S1:1-14-13-9-10-11-4-1,其成本為32.7元,L(1)=130箱;S2:1-12-3-2-6-5-7-1,其成本為58.3元,L(1)=130箱;S3:1-8-1,其成本為31.8元,L(1)=30箱.S1沿反方向行走,則3條路線都為可行路線.配送S1和S2的車輛在配送作業(yè)完成后,其中一輛繼續(xù)進(jìn)行S3的作業(yè),總成本為122.8元.將表1中的數(shù)據(jù)代入客戶子集分配模型,以5和8作為種子節(jié)點(diǎn),得出2個分配子集:s1{1,2,5,6,10,13,14}和s2{1,3,4,7,8,9,11,12}.s1中總投遞需求量為145箱,總回投需求量為150箱;s2中總投遞需求量為145箱,總回投需求量為145箱.s1中最小成本的哈密爾頓回路為S1:1-14-13-10-6-5-2-1,其成本為45.8元.由于L(1)=145箱,當(dāng)?shù)?4點(diǎn)時,如果既進(jìn)行投遞又進(jìn)行回投作業(yè)的話,其載運(yùn)量達(dá)到145+30-20=155箱.因此該路線不可行.可行的最小成本的哈密爾頓回路為S2:1-5-6-10-12-14-2-1,其成本為51.8元.圖1為最終索套解圖,1~14為索把,節(jié)點(diǎn)14為索結(jié)并被訪問2次,節(jié)點(diǎn)13,10,6,5,2和索結(jié)14構(gòu)成索環(huán).該索套路徑的成本為49.8元.s2中最小成本的哈密爾頓回路為S3:1-3-4-11-7-8-9-12-1,該回路滿足在各節(jié)點(diǎn)載運(yùn)量都小于車輛載運(yùn)容量的約束,是可行回路.因此S3即最優(yōu)解,其成本為49.3元.綜上所述,車隊(duì)總成本為49.8+49.3=99.1元.用本文中陳述的客戶子集分配模型和索套啟發(fā)式解法比用近鄰搜索法的成本節(jié)約額為122.8-99.1=23.7元.4混合運(yùn)輸需求情況近鄰搜索法(或Sweep算法等采用先定線路,再分組的啟發(fā)式算法)得到的是最短路徑的哈密爾頓回路,最短路徑的哈密爾頓回路由于受L(ik)≤R,cd(ik)≤R,cp(ik)≤R這3個條件的約束,有可能是不可行的回路,而索套啟發(fā)式解法是在近鄰搜索法基礎(chǔ)上的改進(jìn),采用先分組,后定線路的方法,有效保證了混合運(yùn)輸情況下的3個約束條件,即保證其解必然是可行解.在最短路徑的哈密爾頓回路不可行的情況下,近鄰搜索法方法必然尋求卸貨量大于裝載量的點(diǎn)先進(jìn)行作業(yè),這勢必使走行距離變長,費(fèi)用增加,而索套啟發(fā)式解法對最短徑的哈密爾頓回路不可行的點(diǎn)實(shí)施先卸貨,等把其它的點(diǎn)的作業(yè)完成后再來裝該點(diǎn)的貨,節(jié)約了里程,有效地降低了有混合運(yùn)輸需求情況下的運(yùn)行總成本,為解決混合運(yùn)輸需求情況下的車隊(duì)計(jì)劃提供了一種解決方案.參考文獻(xiàn):郭耀煌.運(yùn)籌學(xué)原理與方法[M].成都:西南交通大學(xué)出版社,1994:153-154.MosheiovG.Vehicleroutingwithpick-upanddeliverytour-partitioningheuristics[J].Computersand.Eng.1998;34(3):669-684.Brenninger-GotheM.Twovehicleroutingproblems—ma