楊其芝

((重慶交通大學，重慶 400074)

引言

我國經(jīng)歷了40年的改革開放，市場經(jīng)濟不斷繁榮，公路網(wǎng)的基本全面覆蓋。物流配送的費用、時間等直接影響著生產(chǎn)的成本和企業(yè)的發(fā)展。配送的路徑優(yōu)化是物流配送中的重要環(huán)節(jié)，它直接影響著物流配送的效率及質(zhì)量。所以路徑優(yōu)化問題是當前物流研究的重要內(nèi)容。

車輛路徑問題(VRP)問題最早于1959年由Dantzig和Fulkerson提出。路徑優(yōu)化問題在早期主要研究的是確定性問題，確定性問題就是指所有的信息如：客戶信息、交通狀況、車輛信息都是確定的。在這些確定的信息下對路徑進行優(yōu)化，得到滿足這些信息的最優(yōu)解或者滿意解。

然而，實際問題中，路徑優(yōu)化中的信息存在很大的不確定性。因此，人們把研究方向轉(zhuǎn)向了隨機性路徑優(yōu)化問題。本文主要從隨機客戶需求，隨機時間和隨機用戶三個方面進行路徑優(yōu)化綜述。

1 隨機客戶需求

1992年Bertsimas以車輛行駛距離最短為目標，進行了不確定客戶需求的研究，其中假設(shè)客戶的需求按照一定的概率分布[1]。Lei在2011年提出了有時間約束的不確定需求的車輛路徑優(yōu)化問題。并用啟發(fā)式算法對問題進行求解，并通過實驗證實算法的準確性。Yang在2000年討論了在運輸途中有補貨點的問題，車輛如果缺貨可以提前在途中的補貨點進行補給，不需要再返回出發(fā)點補給，這是一種帶有中途補貨的客戶隨機需求問題。作者使用啟發(fā)式算法以運輸成本最小為目標進行了求解最優(yōu)路徑。

國內(nèi)對不確定客戶需求問題也有許多的研究。2015年，管峰，鐘銘等，基于隨機顧客需求，采用魯棒優(yōu)化模型解決有容量限制的車輛路徑優(yōu)化問題。實例證明該模型能夠保證路徑再需求波動下的可行性。2016年，薛祥，朱小林探究危險品運輸終端需求不確定對運輸總成本和安全性的影響，結(jié)果顯示對路徑運輸穩(wěn)定性有影響。

2 隨機時間

運輸車輛行駛過程中的不確定性，導致車輛的旅行時間和對客戶的服務時間是不確定的。1992年，Laporet對于含有不確定旅行時間和不確定服務時間的路徑優(yōu)化問題進行了研究。提出了三種模型,并設(shè)計了一種適合三種模型的branch-and-cut算法，并通過實驗驗證了可行性[2]。2003年Kenyon和Morton對上述問題也進行了研究，提出了兩種數(shù)學模型。2013年，Tas就討論了關(guān)于軟時間窗和隨機旅行時間的路徑優(yōu)化，并且通過以成本最小為目的建立了數(shù)學模型，通過禁忌搜索算法進行求解，并不斷改進優(yōu)化結(jié)果。

國內(nèi)也有不少學者進行了相應的研究。2006年，張建勇，李軍創(chuàng)建了具有模糊行駛時間的VRP問題的數(shù)學模型，并通過一種混合遺傳算法對該模型進行求解[3]。2009年，李相勇和田澎研究了帶時間窗的隨機時間問題，建立了模型并用啟發(fā)式算法進行求解。同年，俞峰考慮了時間以及網(wǎng)絡(luò)狀態(tài)的最短路徑問題，并對影響算法化簡結(jié)果的一些因素以及算法的復雜性進行了分析[4]。2011年，張濤等建立了同時去送貨的不確定時間路徑優(yōu)化問題，并用分散搜索的方法進行求解。2014年，李鋒，魏瑩綜合考慮車輛在運輸過程中的時間和距離，通過多目標混合遺傳算法對該問題求解，通過求解驗證了算法的有效性[5]。

3 隨機客戶

1988年，Bertsimas對概率性路徑問題進行了研究，其中討論了概率最小生成樹問題，概率性旅行商問題以及對應的選址問題。次年，Waters假設(shè)客戶對服務的需求存在一定的概率.1995年,Gendreau對隨機需求和隨機用戶同時存在的問題進行研究，作者通過精確算法進行了求解。2004年，Bent和Van Hentenryck研究了動態(tài)的具有隨機客戶和時間窗的問題，目標為最大服務客戶量。2006年，Hvattum研究了客戶信息未知的動態(tài)、隨機的車輛路徑優(yōu)化問題，提出了解決該問題的啟發(fā)式算法。

2012年，曾華在其博士論文中探討了客戶需求存在性和需求量為不確定因素時的概率優(yōu)化問題，并建立了隨機顧客和需求的車輛路徑問題的數(shù)學模型，分析模型數(shù)學特征，給出解決該模型的啟發(fā)式算法。

4 結(jié)論

針對上述研究，可以看出在隨機性路徑優(yōu)化研究方面國內(nèi)外都取得了顯著的成果。不過還存在著下述不足：

(1)對不確定性信息的隨機路徑優(yōu)化中考慮的不確定性信息比較單一。

(2)雖然通過建立的模型能夠求出車輛的最優(yōu)路徑，但是隨著路網(wǎng)規(guī)模的不斷擴大，對問題的求解會變得困難。

(3)缺少對車輛的動態(tài)管理和處理運輸過程中出現(xiàn)異常信息的快速反應機制的研究。

參考文獻：

[1] Bertsimas DJ.A vehicle routing problem with stochastic demand[J].Operation Research,1992,40(3):574-585.

[2] Laporte G.1992.The vehicle routing problem:An overview of exact and approximate algorithms[J].European journal of operational Research,59(3):345-358.

[3] 張建勇,李軍.具有模糊旅行時間的VRP的一種混合遺傳算法[J].管理工程學報,2006,20(4):13-16.

[4] 李相勇,田澎.帶時間窗和隨機時間車輛路徑問題:模型和算法[J].系統(tǒng)工程理論與實踐,2009,29(8),81-90.

[5] 李鋒,魏瑩.求解隨機旅行時間的CVRP問題的混合遺傳算法[J].系統(tǒng)管理學報.2014,23(6):819-825.