楊其芝

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

引言

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

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

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

1 隨機(jī)客戶(hù)需求

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

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

2 隨機(jī)時(shí)間

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

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

3 隨機(jī)客戶(hù)

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

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

4 結(jié)論

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

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

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

(3)缺少對(duì)車(chē)輛的動(dòng)態(tài)管理和處理運(yùn)輸過(guò)程中出現(xiàn)異常信息的快速反應(yīng)機(jī)制的研究。

參考文獻(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] 張建勇,李軍.具有模糊旅行時(shí)間的VRP的一種混合遺傳算法[J].管理工程學(xué)報(bào),2006,20(4):13-16.

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

[5] 李鋒,魏瑩.求解隨機(jī)旅行時(shí)間的CVRP問(wèn)題的混合遺傳算法[J].系統(tǒng)管理學(xué)報(bào).2014,23(6):819-825.