時變網(wǎng)絡(luò)中跨時段運行的動態(tài)規(guī)劃啟發(fā)式算法

時變網(wǎng)絡(luò)中跨時段運行的動態(tài)規(guī)劃啟發(fā)式算法

1tdrsp問題的時變處理時間變網(wǎng)絡(luò)車輛規(guī)劃問題是一個靜態(tài)網(wǎng)絡(luò)的類似問題。在靜態(tài)網(wǎng)絡(luò)的梁啟超問題中，車輛行駛時間只與節(jié)點之間的距離有關(guān)，不隨著時間的推移而改變。然而，在當前的交通網(wǎng)絡(luò)中，車輛的行駛速度總是受到交通、交通流量、交通事故、交通高峰和其他因素的影響，車輛的行駛時間會不斷變化。對于trvp，您通常每天分為幾個周期。車輛和兩個節(jié)點之間的相應(yīng)步行時間是不同的。在駕駛過程中，車輛通常從一個周期過渡到另一個周期（或多個周期）。時間變特性處理的關(guān)鍵是時間變異征處理[1、2、3、4、5、6、7、8、9、10、11]。目前文獻關(guān)于TDVRP問題時變處理,主要包括以下幾種方式.Malandraki等將不同時段的行駛時間表示為階段函數(shù),但沒有考慮跨時段時對應(yīng)行駛時間的變化,這是最常見的一種時變處理方式,魏航等采用這種方法對有害物品運輸問題和有宵禁限制的最短路問題進行了研究.Hill和Benton提出基于旅行速度階段函數(shù)的處理方法,以避免旅行時間在跨時段時產(chǎn)生跳躍.以上兩種方法均不滿足先入先出(first-infirst-out,簡寫FIFO)準則,即存在先出發(fā)的車后到這種現(xiàn)象.Ichoua等對跨時段時車輛行駛速度進行調(diào)整,該假設(shè)是對實際問題的一種合理假設(shè),且滿足FIFO準則,但其行駛時間計算方法非常復雜,需要每時段的行駛速度、行駛距離等數(shù)據(jù).Haghani等、Donati等沿用了該方法.李妍峰等對時變旅行商問題提出一種滿足FIFO準則的跨時段處理方法,直接推導出旅行商在行走過程中跨單時段和多時段對應(yīng)的旅行時間.VanWoensel等采用排隊模型模擬交通擁擠情形下的行駛速度,從而得到車輛行駛時間.由于VRP問題是NP難題,若再考慮時變的車輛行駛時間,問題求解變得非常困難.目前文獻中關(guān)于TDVRP問題的求解算法研究很少.最優(yōu)化算法只能求解某些小規(guī)模問題,啟發(fā)式算法成為求解這類問題的有力工具.相關(guān)文獻中涉及TDVRP問題求解算法主要包括最近鄰算法、禁忌搜索算法、遺傳算法和蟻群算法.在鄰域搜索領(lǐng)域,Malandraki和Daskin提出最近鄰算法求解了10-25個顧客的TDVRP問題.該方法求解問題規(guī)模很小,并且沒有考慮車輛行駛時間在跨時段時的變化,問題不滿足FIFO準則,很難應(yīng)用于實際問題.本文在文獻的基礎(chǔ)上對TDVRP問題提出一種滿足FIFO準則的時變處理方法,考慮跨單時段和多時段兩種情形.在此基礎(chǔ)上建立問題數(shù)學模型,并構(gòu)造動態(tài)規(guī)劃啟發(fā)式算法求解該問題,通過實驗仿真與最近鄰算法進行性能比較.2處理間隔內(nèi)的事件2.1不同+a+b假設(shè)車輛行駛路段(i,j)只跨越1個時段.路段(i,j)長度為d,由于跨時段被分為d1和d2,分別為車輛于1時段和2時段內(nèi)行駛的距離.cij1和cij2分別為車輛于1時段和2時段行駛完路段(i,j)所用時間(不考慮跨時段),B2為兩時段的分界時刻,如圖1所示.車輛于時刻ti從節(jié)點i出發(fā),若ti<B2-cij1,則在1時段內(nèi)行駛完該路段,對應(yīng)行駛時間為cij1;若ti≥B2,則整個行駛過程在2時段內(nèi)完成,對應(yīng)行駛時間為cij2;只有當B2-cij1≤ti<B2時才會跨時段,對應(yīng)行駛時間為,顯然,在1時段車輛行駛d1的時間為B2-ti,在2時段車輛行駛d2的時間為,其中,則在2時段車輛行駛d2的時間可整理為,因此車輛在路段(i,j)的總行駛時間為,則到達節(jié)點j的時刻,經(jīng)整理得由式(1)可知,到達節(jié)點j的時刻tj為車輛從節(jié)點i出發(fā)時刻ti的增函數(shù),因此滿足FIFO準則.在該式中,不涉及兩節(jié)點間的距離和車輛的行駛速度,處理更簡便.2.2車輛行駛dki,j的需求計算假設(shè)一天被分為P個時段,[Bp,Bp+1]表示時段p(p∈[1,P])的區(qū)域.車輛行駛路段(i,j)需跨越K個時段,在l時段內(nèi)行駛距離為dl,滿足.在不考慮跨時段情況下,車輛于第l(l=1,2,…,K+1)時段行駛路段(i,j)需要時間cijl.設(shè)車輛于ti時刻(ti∈[B1,B2])從節(jié)點i出發(fā),總行駛時間為.在第1時段走完d1所用時間為B2-ti,在第l(l∈[2,K])時段行駛dl所用時間為Bl+1-Bl,則,車輛在第K+1時段行駛dK+1所用時間為,則車輛在路段(i,j)的總行駛時間為經(jīng)整理得因此到達節(jié)點j的時刻經(jīng)整理得車輛到達節(jié)點j的時刻tj同樣也為從節(jié)點i出發(fā)時刻ti的增函數(shù),滿足FIFO準則.特別地,當K=1時,,該式變?yōu)榭鐔螘r段情形,有,式(2)變?yōu)槭?1).3模型建立和約束在TDVRP問題中,假設(shè)相同類型的M輛車需要去服務(wù)N個顧客.每輛車具有相同的裝載能力,每個顧客有一確定的需求量.每輛車從車場出發(fā),并返回到車場.每個顧客只能由一輛車服務(wù).車輛裝載量不能超過車的裝載能力.該問題目標為找到一組能服務(wù)所有顧客的最短行駛時間車輛路線.假設(shè)所有車輛在同一時刻從車場出發(fā),目標可轉(zhuǎn)換為最小化所有車輛服務(wù)完顧客后返回車場的時刻.在模型建立過程中,需要用到如下參數(shù)和變量:參數(shù):N:顧客數(shù)目;M:車輛數(shù)目;0:車場編號;di:顧客i的需求量;Q:每輛車的裝載能力;t0:所有車輛從車場出發(fā)的時刻;L:非常大的正數(shù).變量:tN+m:第m輛車返回車場的時刻;tj:到達節(jié)點j的時刻(不考慮在顧客處停留,也為從節(jié)點j出發(fā)的時刻);TDVRP問題數(shù)學模型可表示為:目標函數(shù)(3)為最小化所有車輛訪問完所有顧客之后返回車場的時刻.約束(4)保證在任一時段節(jié)點j緊前只有一個節(jié)點.約束(5)保證在任一時段節(jié)點i緊后只有一個節(jié)點.約束(6)計算到達節(jié)點j的時刻.若xijp=1,約束(7)應(yīng)取“=”號,此時tj=Sijp;若xijp=0,約束(7)應(yīng)取“>”號.約束(7)分別考慮了跨時段與不跨時段兩種情況計算Sijp.約束(8)保證每個顧客只能被某一輛車訪問,而車場則被所有車輛訪問.約束(9)為車的能力約束.約束(10)保證路徑的連續(xù)性.約束(11)保證車輛到達節(jié)點i的時刻非負.4動態(tài)規(guī)劃啟發(fā)式算法為了更好地描述動態(tài)規(guī)劃啟發(fā)式算法,在此先給出求解TDVRP問題的動態(tài)規(guī)劃精確算法.為了描述方便,時變處理只考慮跨單時段情形(跨多時段情形可類推).S表示車輛訪問的節(jié)點(顧客+車場)集合.若所有車輛從車場出發(fā),訪問完所有顧客,并回到車場,則S可表示為{0,s1,0,s2,0,…,0,sM,0},其中sl(l∈[1,M])表示第l輛車訪問的全部顧客集合,0的個數(shù)為M+1,因此|S|=N+M+1.階段數(shù):N+M+1.狀態(tài)(S,h):S={0,s1,0,s2,0,…,0;sl-1,0,ul,h}表示目前已安排了l-1輛車的路徑,且第l(l≤M)輛車訪問了部分顧客集合ul后到達節(jié)點h,.指標函數(shù)F(S,h):表示前l(fā)-1輛車的總到達時刻與第l輛車訪問了部分顧客集合ul后到達節(jié)點h的時刻之和最小值.初始條件:|S|=1:S={0},S中只有車場.|S|=2:對第一輛可供使用的車,有對|S|>2,S={0,.s1,0,s2,0,…,0,ul,q,h},考慮第l輛車訪問了節(jié)點q后立即訪問節(jié)點h,對所有h∈{0,1,…,N},有如下遞歸方程:其中,f(m)(m∈[1,l-1])為第m輛車的最早返回車場時刻.最后階段|S|=N+M+1:考慮第M輛車訪問了顧客q后返回車場,則所有車輛返回車場的總最早到達時刻為動態(tài)規(guī)劃啟發(fā)式算法在動態(tài)規(guī)劃精確算法的基礎(chǔ)上,每階段保留前H(或小于H,當每階段所有的子路徑數(shù)目小于H時)個最優(yōu)子路徑,H是一個可被設(shè)定的參數(shù).假設(shè)在第i階段(|S|=i)得到前H個最優(yōu)子路徑,則第i+1階段(|S|=i+1),在這H個最優(yōu)子路徑后加上一節(jié)點(若為顧客,則之前一定未被訪問),同樣在該階段選擇前H個最優(yōu)子路徑.特別地,當H=1時,該算法變?yōu)镸alandraki和Daskin提出的最近鄰算法.動態(tài)規(guī)劃啟發(fā)式算法是動態(tài)規(guī)劃精確算法與最近鄰算法的折中,在保證滿意解的情況下能夠較大幅度地減少運算時間和存儲空間.算法步驟如下:Step3對正被安排的車,通過對上階段前H(或小于H)個最優(yōu)子路徑加上一個剩余未被訪問的顧客,若滿足該車能力約束,則計算在當前階段到達該顧客的時刻,轉(zhuǎn)Step5;否則,轉(zhuǎn)Step4.Step4對正被安排的車返回車場,計算返回車場的到達時刻,另安排下一輛車.轉(zhuǎn)Step5.Step5當前階段保留前H(或小于H)個最優(yōu)子路徑.Step6第M輛車對應(yīng)的前H個最優(yōu)子路徑均返回車場.在H個方案中,找到最早到達車場時刻,并回溯找到最優(yōu)路徑.算法停止.5算法仿真結(jié)果文中用隨機產(chǎn)生的10組不同規(guī)模數(shù)據(jù)分別測試動態(tài)規(guī)劃啟發(fā)式算法和最近鄰算法,考慮跨單時段情形.隨機數(shù)據(jù)包括顧客數(shù)、車輛數(shù)和在不同時段節(jié)點間的車輛行駛時間.所有程序均用C++編寫,并在PentiumIV主頻1.6GHz的計算機上進行實驗仿真.表1記錄了兩類算法的實驗結(jié)果,其中包括了目標函數(shù)值(單位:h)和算法運行時間(單位:s).從表1,可以得到如下結(jié)論:1)隨著TDVRP問題規(guī)模的擴大,即顧客數(shù)和車輛數(shù)不斷增加,兩類算法的運行時間隨之增加.當顧客數(shù)為250、車輛數(shù)為40時,以上兩類算法均不能求解.2)隨著H的增加,即每階段選取狀態(tài)數(shù)越多,所得目標函數(shù)值越好.H=2對應(yīng)的目標函數(shù)值比H=1對應(yīng)的目標函數(shù)值改進11%,H=3時目標函數(shù)值比H=1時目標函數(shù)值改進17%.3)隨著H的增加,算法運行時間也隨之增加,但增加幅度不大.當H=1時平均運算時間為0.86s,H=2時平均運算時間為1.34s,H=3時平均運算時間為1.58s.在平均運算時間不到2s的情況下,動態(tài)規(guī)劃啟發(fā)式算法能較好地改進最近鄰算法(H=1)的目標函數(shù)值.6仿真實驗與結(jié)果分析本文對TDVRP問題提出一類滿足FIFO準則的跨時段處理方法,建立相應(yīng)的數(shù)學模型,并構(gòu)造動態(tài)規(guī)劃啟發(fā)式算法求解該問題.通過設(shè)置算法參數(shù)H平衡求解質(zhì)量和算法運行時間,使得算法運用更加靈活.H越大(小),求解質(zhì)量更好(差),算法運行時間越長(短).當H設(shè)置為每階段子路徑數(shù)目時,算法變?yōu)閯討B(tài)規(guī)劃精確算法;當H=1時,算法變?yōu)樽罱徦惴?文中對10組隨機數(shù)據(jù)進行測試,結(jié)果表明,動態(tài)規(guī)劃啟發(fā)式算法能在非常短的時間內(nèi)得到比最近鄰算法更好的解.該算法也能在運行時間和存儲空間允許的情況下求解更大規(guī)模的問題得到滿意解,為實際物流企業(yè)配送