韓娟娟，李永先

（遼寧師范大學(xué)，遼寧 大連116029）

1 引言

車輛路徑問題（Vehicle Routing Problems，VRP）是一類具有重要實用價值的組合優(yōu)化問題。VRP是指對安排適當(dāng)?shù)能囕v路徑，使車輛在滿足約束條件下，經(jīng)過一系列的發(fā)貨點和（或）供貨點并達到一定的目標(biāo)。如果在車輛、時間、人員、顧客需求等信息都確定的情況下安排車輛路徑，這類問題屬于靜態(tài)車輛路徑問題。但在現(xiàn)實世界中，信息大多是不確定的，比如顧客需求、交通狀況、天氣狀況、人員、車輛等信息的不確定，有些信息還會處在不斷變動的狀態(tài)，這對安排車輛路徑造成了很大的困擾，需要根據(jù)不斷更新的系統(tǒng)信息動態(tài)地安排車輛路徑，這類問題屬于動態(tài)車輛路徑問題（DVRP）。根據(jù)動態(tài)信息的隨機性和模糊性，動態(tài)車輛路徑問題可以分為隨機車輛路徑問題和模糊車輛路徑問題。如果可以根據(jù)歷史資料或市場調(diào)查得到信息（顧客需求、車輛行駛時間、服務(wù)時間等）的概率分布或信息服從的某種變化規(guī)律，路徑制定者根據(jù)信息的規(guī)律及得到的新的系統(tǒng)信息實時地規(guī)劃車輛路徑，這類問題就是隨機車輛路徑問題。但是，當(dāng)需要的信息沒有長期積累，不能獲得信息的分布規(guī)律（如企業(yè)開辟新市場時，顧客的需求信息就是模糊的）或者信息不能清晰的被描述，這類問題就是模糊車輛路徑問題。由于動態(tài)VRP更接近于實際的車輛配送情況，對于現(xiàn)實中的物流更具有應(yīng)用價值，因此，動態(tài)VRP已經(jīng)成為車輛配送領(lǐng)域研究的重點。

動態(tài)車輛路徑問題是近年來國內(nèi)外學(xué)術(shù)界研究的一個熱點問題。本文對動態(tài)車輛路徑問題的研究進行評述，分析了動態(tài)車輛路徑問題在模型、算法、仿真方面的主要研究成果及存在的問題，提出了動態(tài)車輛路徑問題的進一步發(fā)展方向。

2 動態(tài)車輛路徑問題的研究進展

Wilson在20世紀70年代研究了動態(tài)VRP中的dial－a－ride問題，使得動態(tài)VRP受到關(guān)注。后來，Powell、Psaraftis、Gendreau等都對動態(tài)VRP的特征進行了研究，總結(jié)了動態(tài)車輛路徑問題的特點。雖然動態(tài)車輛路徑問題研究的歷史不長，但是在靜態(tài)車輛路徑問題研究的基礎(chǔ)上對動態(tài)車輛路徑問題的研究還是取得了不小的進展，本文從模型、算法、仿真3個方面對動態(tài)車輛路徑問題進行了綜述。

2.1 動態(tài)VRP模型的研究進展

基于動態(tài)VRP實時性和復(fù)雜性的特點，動態(tài)VRP需要與之對應(yīng)的新的模型和理論，一些學(xué)者在靜態(tài)VRP研究的基礎(chǔ)上，提出了一些新的模型來解決動態(tài)VRP。

Bertsimas等［1］研究了多車輛有容量約束的DVRP和動態(tài)旅行修理員問題，并提出了解決該問題的排隊論模型。排隊論模型成為研究動態(tài)車輛路徑問題的一個重要的模型。Minkoff［2］提出了馬爾可夫模型，但只能求解10個需求的小規(guī)模DVRP。Tillmar［3］在研究隨機需求的車輛路徑問題時，提出了一種懲罰模型，該模型規(guī)定當(dāng)車的容量滿足不了顧客服務(wù)要求時要按照一定的策略給予懲罰，這種模型有效地解決了路徑失敗的問題，對以后的研究有很好的借鑒作用。Stewart和Golden［4］提出了基于機會約束機制理論與二元可能性理論下的VRPSD的模型，這兩個理論在以后的研究中應(yīng)用的比較廣泛。謝如鶴等［5］在對隨機需求的VRP求解時，利用了一種基于車輛剩余能力的插入準(zhǔn)則。葛顯龍［6］研究了跨區(qū)域多配送中心動態(tài)需求的開放式VRP問題，提出了配送車輛共享和聯(lián)合配送策略并建立符合實際的車輛路徑優(yōu)化模型，并利用云模型理論改進遺傳算法對模型求解，得到了較好的結(jié)果。

Teodorovic和Pavkovic［7］最早研究了模糊顧客需求的VRP，顧客的信息和決策者的偏好用模糊數(shù)來表示，并建立了以傾向度為基礎(chǔ)的模糊判定準(zhǔn)則。Pavone［8］在動態(tài)車輛路徑問題中首先考慮了顧客等待的耐心因素。祝祟雋［9］以模糊可能性分布，建立了車輛路徑問題的基于置信度的三下標(biāo)流模型，并提出了基于可能性分布的2－opt算法。陸琳等［10］考慮到配送者的經(jīng)驗對現(xiàn)實中的車輛路徑制定的顯著作用，建立了包含配送者經(jīng)驗的知識系統(tǒng)的FVRP模型，使模型不單純理論化而更具現(xiàn)實應(yīng)用意義。

雖然動態(tài)車輛路徑的模型有了進一步的發(fā)展，但還是存在許多不足，比如這些模型大多是只考慮了一種或者兩種不確定信息存在的情況，但是實際系統(tǒng)中有很多類型的不確定信息，對于這種情況還沒有相應(yīng)的模型，而且對不同信息之間的聯(lián)系也沒有建立對應(yīng)的數(shù)學(xué)模型?？紤]到多車輛多車型的動態(tài)VRP的模型還比較少，還不成熟。

2.2 動態(tài)VRP算法的研究進展

VRP是NP－h(huán)ard問題，由于其約束條件多，節(jié)點規(guī)模大，難以用精確算法求解，所以對這類問題的求解一般要用啟發(fā)式算法獲得其滿意解。常用的啟發(fā)式算法有遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法等，目前兩種或者多種算法結(jié)合形成的混合算法經(jīng)常被用來解決車輛路徑問題。啟發(fā)式算法的發(fā)展為解決VRP提供了新的思路，可以解決問題規(guī)模比較大、結(jié)構(gòu)比較復(fù)雜的車輛路徑問題。人們?yōu)榱私鉀Q動態(tài)VRP，對啟發(fā)式算法進行了改進。

1989年 Min［11］最早提出了 VRPSDP，采用先對顧客聚類，然后解決每一類顧客群體的TSP。在此基礎(chǔ)上，對不可行路徑進行補償，從而優(yōu)化各TSP路徑。Chen和Gen［12］提出了一種利用推－碰－擲過程改進的混合遺傳算法解決模糊車輛路徑問題。Gendreau等求解動態(tài)車輛路徑問題時，構(gòu)造了一種具有自適應(yīng)性的禁忌搜索算法，首先利用禁忌搜索算法求解，當(dāng)新的需求出現(xiàn)時，停止運行禁忌搜索算法，并將當(dāng)前的最優(yōu)解存儲到自適應(yīng)存儲單元，然后利用插入法將新的需求插入到自適應(yīng)存儲單元的所有解中，再繼續(xù)使用禁忌搜索算法對加入了新的需求點后的動態(tài)車輛路徑問題進行優(yōu)化。Pureza［13］研究動態(tài)車輛路徑問題時，不是按照新需求出現(xiàn)的順序依次對應(yīng)進行服務(wù)，而是設(shè)置一定的新需求點緩存區(qū)，在達到一定數(shù)量的新需求后再根據(jù)緊急程度安排車輛服務(wù)，這種方法更符合了實際情況。Liao［14］等將動態(tài)車輛路徑問題分為兩階段處理，首先采用掃描法確定使用的車輛數(shù)量，再根據(jù)接受到的實時信息采用禁忌搜索算法優(yōu)化路徑。

甘勤濤等［15］利用禁忌搜索算法求解模糊需求VRP，郎茂祥等［16］研究了車輛多次巡回配送和考慮車輛故障的DVRP，利用兩階段策略求解該問題，第一階段用禁忌搜索算法安排車輛路徑，第二階段當(dāng)新的信息出現(xiàn)時采用局部搜索算法進行局部優(yōu)化。謝秉磊等［17］研究了一類隨機顧客和隨機需求的車輛路徑問題，需求的隨機性增加了決策的復(fù)雜性和難度，首先提出了多回路策略，并設(shè)計了具有不同鄰域結(jié)構(gòu)的模擬退火算法。劉霞［18］把計劃周期分片，將動態(tài)車輛路徑問題轉(zhuǎn)換成一系列的靜態(tài)車輛路徑問題，并用最大最小蟻群算法對一系列的靜態(tài)車輛路徑問題進行求解，根據(jù)數(shù)據(jù)集的特點采用并行法或順序法構(gòu)建路線。王連鋒等［19］針對具有多重模糊性的模糊車輛路徑問題，依據(jù)模糊可信性理論建立了模糊期望值模型，并基于MOPSO提出了自適應(yīng)混合多目標(biāo)粒子群優(yōu)化算法。

雖然動態(tài)車輛路徑問題在算法上有所改進，但是由于動態(tài)VRP的參數(shù)復(fù)雜，約束條件多，數(shù)學(xué)模型復(fù)雜，所以啟發(fā)式算法也很難比較理想地解決現(xiàn)實中的動態(tài)車輛路徑問題。

2.3 動態(tài)VRP仿真優(yōu)化的研究進展

仿真是建立數(shù)學(xué)邏輯模型并在計算機上運行該模型進行實驗的過程，仿真建模是模仿真實系統(tǒng)的行為，仿真是決策者用于車輛路徑安排的最有力的工具之一。目前，仿真已經(jīng)成為管理科學(xué)與運籌學(xué)領(lǐng)域應(yīng)用最廣泛的技術(shù)手段之一。近年來，隨著許多仿真軟件的開發(fā)和應(yīng)用，各種仿真建模方法應(yīng)用到了解決動態(tài)VRP問題中，通過仿真建模和仿真分析可以將現(xiàn)實配送系統(tǒng)中的各種不確定因素考慮進來。所以將仿真與優(yōu)化方法結(jié)合起來是解決復(fù)雜的車輛調(diào)度問題的一個非常有效的方法。

Alkhamis［20］討論了車輛路徑問題中約束條件帶有隨機性函數(shù)的情況，文中使用粒子群優(yōu)化求解，用幾次仿真的均值來估計約束中的函數(shù)值，即用仿真方法對隨機性的約束進行了有效處理。Taniguchi等［21］提出了一個有時間窗的車輛路徑問題和動態(tài)交通仿真的集成模型。李永先［22］提出了用仿真的方法求解隨機約束條件下車輛路徑問題的新思路，建立了在需求量及行駛速度隨機變動情況下的有時間窗的車輛路徑的數(shù)學(xué)模型，并基于物流系統(tǒng)仿真平臺eM－Plant設(shè)計了隨機約束條件下VRP的仿真模型，而且實現(xiàn)了對該問題的求解。孫中悅［23］在其博士論文中討論了動態(tài)車輛路徑問題的求解方法。針對車輛在實際配送過程中經(jīng)常出現(xiàn)不確定信息情況，提出了基于定時觸發(fā)的動態(tài)仿真方法，該仿真的推進依靠真實時長的定時器觸發(fā)，而不是依賴虛擬時鐘，在新信息發(fā)生后，使得仿真過程和實際配送過程同步，并根據(jù)智能決策的優(yōu)化方法進行調(diào)整得到新問題的仿真優(yōu)化結(jié)果，確保在出現(xiàn)新的信息后車輛能夠得到優(yōu)化的配送路線。

仿真在物流系統(tǒng)領(lǐng)域的研究較少，現(xiàn)有的研究還存在一些不足，在解決動態(tài)車輛問題方面還存在算法效率不高、智能化程度不高等不足，還沒有解決現(xiàn)實中的大規(guī)模的路徑安排問題的能力。

3 動態(tài)車輛路徑問題未來的研究方向

國內(nèi)外學(xué)者在動態(tài)車輛路徑問題理論和實踐中都取得了一些研究成果，但是在動態(tài)車輛路徑問題建模、信息處理和應(yīng)用領(lǐng)域方面尚存在一些問題有待改進和提高，例如建模方法尚不完善，一些復(fù)雜的問題尚無法建立準(zhǔn)確的模型來求解；不確定信息的處理還不成熟；動態(tài)車輛路徑問題在新的物流模型（綠色物流，冷鏈物流等）中還沒有得到很好的應(yīng)用。動態(tài)車輛路徑問題應(yīng)在以下幾個方面進行進一步的研究。

3.1 多約束多目標(biāo)模型

目前，人們對模糊車輛路徑問題研究的很少，而且對其研究主要集中在模糊需求的研究上，雖然對隨機車輛路徑問題研究的相對比較多，但是其研究方向也是主要集中于對隨機需求的研究上，進一步的研究方向應(yīng)從隨機和模糊的預(yù)約時間、費用、顧客、車輛數(shù)、交通堵塞等方面進行。

人們研究動態(tài)車輛問題時，一般是單獨研究隨機車輛路徑問題和模糊車輛路徑問題，但是實際的物流系統(tǒng)中，往往是既存在隨機信息又存在模糊信息，將這兩種信息結(jié)合起來放到一個模型中解決物流配送問題將是未來的一個研究方向。

動態(tài)車輛路徑問題與靜態(tài)車輛路徑問題一個重要的區(qū)別在于系統(tǒng)信息，動態(tài)車輛路徑問題中的信息具有不確定性，所以信息多種多樣但信息之間又有關(guān)聯(lián)，如何將各種信息聯(lián)系起來系統(tǒng)的分析車輛路徑問題也是一個值得研究的方向。

因此，隨著對動態(tài)車輛路徑問題研究的深入，為了使物流配送和車輛調(diào)度問題更加符合實際情況，多約束多目標(biāo)的動態(tài)車輛路徑問題模型將是未來研究的趨勢。

3.2 分布估計算法的應(yīng)用

分布估計算法是最近幾年新興起的一種啟發(fā)式算法，分布估計算法的概念是在1999年提出的，在遺傳算法的基礎(chǔ)上提出了一種全新的進化模型，并迅速成為計算進化領(lǐng)域的研究熱點和解決工程問題的有效方法。分布估計算法是遺傳算法和統(tǒng)計學(xué)習(xí)相結(jié)合的思想，其基本方法是通過統(tǒng)計學(xué)習(xí)的手段建立解空間內(nèi)個體分布的概率模型，然后對概率模型隨機采樣產(chǎn)生新的群體，如此反復(fù)，實現(xiàn)群體的進化。由于分布估計算法是基于概率模型的進化，更能適應(yīng)動態(tài)VRP的優(yōu)化。目前，利用分布估計算法研究動態(tài)VRP還很少，這將是未來的一個研究方向。

3.3 研究領(lǐng)域的擴展

綠色物流是一種新的物流模型，綠色物流是指在物流過程中抑制物流對環(huán)境造成危害的同時，實現(xiàn)對物流環(huán)境的凈化，使物流資源得到充分利用。綠色物流包括集約資源、綠色運輸、綠色倉儲、綠色包裝和逆向物流。其中綠色運輸要求對貨運點、配送中心的設(shè)置做合理布局與規(guī)劃，并通過縮短車輛路徑和降低空載率，實現(xiàn)節(jié)能減排的目標(biāo)。綠色物流中的綠色運輸是一種動態(tài)車輛路徑問題，由于綠色物流順應(yīng)了世界發(fā)展的潮流，因此如何將綠色物流中的一些參數(shù)融合到動態(tài)車輛路徑問題模型中來解決綠色物流問題是一個值得研究的問題。

冷鏈物流是指冷藏冷凍類食品從原料、生產(chǎn)、加工、儲藏、運輸、銷售直到消費前的各個環(huán)節(jié)始終處于規(guī)定的低溫環(huán)境，以保證食品質(zhì)量、減少食品損耗的一項系統(tǒng)工程。由于冷藏冷凍類食品易變質(zhì)易腐爛，因此冷藏冷凍類食品在運輸過程中較其他物流對時間的要求更苛刻。在冷鏈物流中不僅包括了一般的車輛安排中存在的不確定信息，還有冷藏冷凍類食品隨時間變質(zhì)的情況，如何將冷鏈物流的這一特性與動態(tài)車輛路徑安排結(jié)合，減少食品損耗和運輸時間將是未來研究的一個熱點。

4 結(jié)語

動態(tài)車輛路徑問題的研究對解決現(xiàn)實中的即使配送、第三方物流、交通擁擠、智能運輸、綠色物流等問題有非常重大的意義。動態(tài)車輛路徑問題取得了一定的研究成果，但是其研究的深度還不夠，一般只考慮含一種或者兩種約束條件的模型，多約束多目標(biāo)的動態(tài)車輛路徑問題的模型研究還很少。對動態(tài)信息處理的研究不成熟，解決實際問題的能力還比較差。目前的啟發(fā)式算法對引入了動態(tài)信息的復(fù)雜的動態(tài)車輛路徑問題有一定的局限，利用分布估計算法解決動態(tài)VRP是一個值得研究的方向。動態(tài)車輛問題還應(yīng)該在其多約束多目標(biāo)建模、研究領(lǐng)域的擴展、啟發(fā)式算法的改進等方面做進一步的研究。

［1］Bertsimas D J，Ryzin G V.A stochastic and dynamic vehicle routing problems in the euclidean plane［J］.Operations Research，1991（39）：601～615.

［2］Minkoff A S.A markov decision mode land decomposition heuristic for dynamics algorithms，addressing uncertainty［J］.Operations Research，1993（41）：77～90.

［3］Tillman F.The multiple terminal delivery problem with probabilistic demands［J］.Transportation Science，1969，3（3）：192～204.

［4］Stewart W，Golden B.Stochastic vehicle routing：a comprehensive approach［J］.European Journal of Operational Research，1983，14（4）：371～385.

［5］謝如鶴，劉 霆，邱祝強.基于剩余裝載能力的逆向物流車輛路徑問題［J］.系統(tǒng)工程，2004（10）：20～23.

［6］葛顯龍，王 旭，鄧 蕾.基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究［J］.管理工程學(xué)報，2013（3）：60～68.

［7］Teodorovic D，Radivojevic G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain［J］.Fuzzy Sets and Systems，1996（82）：307～317.

［8］Pavone M，Bisnik N，F(xiàn)razzoli E，et al.A stochastic and dynamic vehicle routing problem with time windows and customer impatience［J］.Mobile Networks＆Applications，2009，14（3）：350～364.

［9］祝崇雋，劉 民，吳 澄，等.針對模糊需求的兩種2－opt算法［J］.電子學(xué)報，2001（8）：1035～1037.

［10］路 琳.不確定信息車輛路徑問題及其算法研究［D］.南京：南京航空航天大學(xué)，2007.

［11］Min H.The multiple vehicle routing problem with simultaneous delivery and pick－up points［J］.Transportation Research A，1989（23）：377～386.

［12］Chen R，Gen M.Vehicle routing problem with fuzzy due－time using genetic algorithms［J］.Japanese Journal of Fuzzy Theory and Systems，1995，7（5）：1050～1061.

［13］Pureza V，Laporte G.Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows［J］.Information Systems and Operational Research，2008，46（3）：165～175.

［14］Liao T Y，Hu T Y.An object－oriented evaluation framework for dynamic vehicle routing problems under real－time information［J］.Expert Systems with Applications，2011，38（10）：12548～12558.

［15］甘勤濤，陽平華，童鐘靈.模糊需求車輛路徑問題的禁忌搜索算法研究［J］.長春理工大學(xué)學(xué)報，2006（1）：84～86.

［16］朗茂祥，胡思繼.車輛路徑問題的禁忌搜索算法研究［J］.北方交通大學(xué)學(xué)報，2004（2）：81～84.

［17］謝秉磊.隨機車輛路徑問題的多回路優(yōu)化策略［J］.系統(tǒng)工程理論與實踐，2007（2）：167～171.

［18］劉 霞.基于最大最小螞蟻系統(tǒng)的動態(tài)車輛路徑問題研究［J］.計算機工程與科學(xué)，2013，35（1）：130～136.

［19］王連鋒，宋建社，曹繼平，等.帶硬時間窗模糊車輛路徑問題的多目標(biāo)優(yōu)化［J］.計算機工程，2013，39（4）：9～17.

［20］Talal M.Alkhamis，Mohamed A.Ahmed.Simulatin－based optimization for repairable systems using particles swarm algorithm［C］//Proceedings of the 37th conference on Winter simulation.Orlando，F(xiàn)lorida.2005：857～861.

［21］Taniguchi E，Yamada T，Hosokawa T.Dynamic traffic simula－tion with optimal truck routing and scheduling［A］.Transporation and Traffic，Abbreviated Presentation Sessions of the 14th International symposium on Transportation and Traffic Theory［C］.Jerusalem，1999：419～439.

［22］李永先.車輛路徑問題的仿真模型及優(yōu)化方法研究［D］.大連：大連理工大學(xué)，2007.

［23］孫中悅.車輛路徑問題的仿真優(yōu)化方法研究［D］.北京：北京交通大學(xué)，2012.