車輛路徑問題的發(fā)展及其應用

卞晨++趙建東

摘要：車輛路徑問題作為運籌學和組合優(yōu)化領域的熱點問題，與現(xiàn)實生活息息相關。隨著對車輛路徑問題的不斷深入研究，各類新型的啟發(fā)式算法被運用到解決這類問題之中。文對具有各類約束條件的車輛路徑問題進行了調查、分析和總結，并對國內(nèi)外相關研究成果進行了提煉，在該基礎之上，闡述了車輛路徑問題的研究綜述。基于當前多樣的分類標準，討論并分析了經(jīng)典車輛路徑問題，并在此基礎之上綜述了求解各類型車輛路徑問題的基本方法和現(xiàn)代啟發(fā)式算法。

關鍵詞：車輛路徑問題；啟發(fā)式算法；多配送中心；帶時間窗；集送貨一體化

中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2016）26-0079-02

Development and Application of Vehicle Routing Problem

BIAN Chen， ZHAO Jian-dong

（School of Computer Science and Engineering， Anhui University of Science & Technology， Huainan 232001， China）

Abstract： As a hotspot in the field of operational research and combinatorial optimization， vehicle routing problem is closely related to real life.As long as the deepening study of vehicle routing problem， various kinds of new types of heuristic algorithm is applied to solve such problems.The vehicle routing problem with various constraint were investigated， analysis and summary in this paper， and the related domestic and foreign research results were reviewed and refined， on this basis， this paper summarizes the research of vehicle routing problem. Based on the current various standard of classification， this paper discusses and analyzes the classical vehicle routing problem firstly， and summarized the basic methods and modern heuristic algorithm on this basis.

Key words： vehicle routing problem； heuristic algorithm； hybrid；multi-depots； time window； pickup and delivery

1 背景

車輛路徑問題（Vehicle Routing Problem，VRP ）是由 Dantzig等人在1959 年提出的一個經(jīng)典的NP-hard問題[1]。是指對于一系列的裝貨點及卸貨點，規(guī)劃合理的配送路徑，在滿足了約束條件之下，載貨車輛按照規(guī)劃的路線依次訪問，能夠滿足一定的需求或達到某些目標。其研究成果已廣泛地應用于各個學科之中。VRP已經(jīng)不止是單純的理論研究，現(xiàn)實世界中，國內(nèi)外學者的研究經(jīng)歷了其從最早期無車輛約束的TSP問題發(fā)展為對車輛運載能力、車輛行駛里程、客戶服務數(shù)量進行限制的經(jīng)典VRP，而后依據(jù)客戶需求的改變和客戶對配送要求的提高，從服務無時限向有時限（也稱為時間窗問題）以及從純送貨問題或者純?nèi)∝泦栴}向混合取送問題（也稱為集貨送貨一體化）的變化的VRP問題。為了不斷滿足現(xiàn)實要求，當前針對VRP的大部分研究，集中在對其動態(tài)性的討論上，即從配送過程中信息的確定性向動態(tài)接受客戶需求（也稱為不確定性）的變化。

隨著現(xiàn)代物流行業(yè)的崛起，企業(yè)為了降低運輸成本，越來越重視對VRP問題的探究，新型的VRP不斷地涌現(xiàn)，使得其更有研究價值和現(xiàn)實意義。

2車輛路徑問題研究現(xiàn)狀及評述

本文根據(jù)現(xiàn)有對VRP問題研究的成果，從綜合的角度分析車輛路徑路徑問題，目前國內(nèi)外針對車輛路徑問題的研究主要集中在其擴展問題上。

2.1 多配送中心的車輛路徑問題

根據(jù)配送中心數(shù)目的多少，配送車輛調度問題可以分為單配送中心車輛調度問題和多中心車輛調度問題，在整個物流管理的體系中，配送地一般都存在多個中心，因此對多配送中心車輛調度問題的研究更加具有現(xiàn)實意義。目前國內(nèi)對于多配送中心車輛調度問題的研究還是處于一個有限的階段。

在多配中心車輛路徑問題中，車輛路徑的安排需要滿足以下四點條件：

1）每一輛車都從一個配送中心駛出，并在服務了一定數(shù)量的客戶后返回初始的配送中心；

2）每一個客戶每次只能被一輛車服務；

3）車輛不能夠在兩個配送中心之間進行運輸，并且行駛路徑不能夠出現(xiàn)回路；

4）車輛的運載量不能夠超出容量限制，并且每一個配送中心提供的客戶服務數(shù)量是有限的。

對配送中心的車輛路徑問題一般可以如下的描述：在整個物流配送系統(tǒng)中，存在著多個服務中心為多個客戶進行服務，需要制定一條配送行車路徑使得所有客戶的需求被滿足的前提之下，配送成本降至最低。多配送中心的VRP是一個NP難度組合優(yōu)化問題，因此一般求解是很難得到最優(yōu)解的。當前，國內(nèi)外學者普遍采用多階段的辦法來解決此類問題，一般先將多配送中心問題轉化為單配送中心問題，再利用啟發(fā)式算法進行求解。崔文[2]通過多階段的啟發(fā)式算法，將此類問題通過聚合—求解—優(yōu)化的步驟逐步求解出最優(yōu)路徑，提出了通過啟發(fā)式算法在短時間生成最初的有效路徑來代替Lin-Kemighan算法中采用的隨機路徑作為初始路徑。

2.2 開放式車輛路徑問題

開放式車輛路徑問題（OVRP）是現(xiàn)代運輸運籌學中的一個新型研究課題，與經(jīng)典VRP問題相比較，他的一個顯著特點是車輛在完成運輸服務后可以將其他的配送中心點選為終點。OVRP一般可以簡化為忽視了回程約束的帶容量約束車輛路徑問題（CVRP），其求解目標是構建一個哈密頓通路以滿足所有顧客的需求。在現(xiàn)實中，物流公司可能通過雇傭車輛來完成配送任務，那么車輛是否回到出發(fā)點并不受到關注，這段路程的費用也將不計。

OVRP是配送運輸管理中廣泛存在的問題，在現(xiàn)實生活中有很多應用，特別是在具有外包業(yè)務特點的配送服務中具有較大的應用價值，例如校園班車問題、牛奶配送、報紙配送等，在這類問題中，由于企業(yè)沒有自己的車輛，所以將其配送業(yè)務外包給其他的車輛或車隊，而且企業(yè)并不要求車輛在服務完客戶后回到車場點。OVRP問題的首要優(yōu)化目標一般都是最少車輛數(shù)，在此基礎上優(yōu)化行駛距離。在過去的十幾年里，盡管學者們通過禁忌搜索，確定性退火技術，大規(guī)模領域搜索方法，分枝切面法等多種方法為OVRP問題提供了基本的解決辦法，但面對大規(guī)模的數(shù)據(jù)處理，OVRP問題仍然存在著一定的求解難度。Sariklis[6]等人通過兩階段啟發(fā)式算法來進行求解，第一階段是先生成客戶群，然后在每一個客戶群中安排路線，進行局部優(yōu)化，第二階段將OVRP問題轉化為最小生成樹問題并求解。Brandao[7]在求解時，通過最近鄰居法和最小K度生成樹來劃分客戶群，并最終用禁忌搜索法優(yōu)化路徑。

2.3 時間窗口約束的車輛路徑問題

帶時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）作為物流管理問題中一個重要的分支，他基于以下假設：1.需要必不可少的通信設備，使得顧客和服務中心之間，服務中心和貨運車輛之間的信息能夠快速便捷的傳遞；2.配送的計劃中，存在預約服務的客戶。服務車輛必須在客戶規(guī)定的時間窗[[Ai，Bi]]對其進行服務，其中[Ai]是客戶[i]的允許最早開始時間，[Bi]是其所允許的最遲開始時間。如果車輛到達客戶的時間早于[Ai]，那么車輛只得等待直至到達服務的最早時間點，其系統(tǒng)優(yōu)化目標是最小化客戶的平均等待時間。

近年來，對于求解帶時間窗車輛路徑問題取得較好效果的是啟發(fā)式算法。Gold等人最早綜述了VRPTW的研究狀況。上世紀80-90年代，對VRPTW的研究開展綜述的是Solomon等人[10]。隨后Braysy等人[11]綜述了經(jīng)典啟發(fā)式、智能啟發(fā)式算法并提出了展望。最近，Raúl Ba?os[12]等人提出了一種針對多目標VRPTW問題的混合現(xiàn)代啟發(fā)式算法，得到優(yōu)化解決方案。

2.4 帶集貨送貨需求的車輛路徑問題

車輛調度領域之內(nèi)的問題一般可以按如下區(qū)分為兩大類：一種是純裝貨或者純卸貨問題，另一種是帶裝貨卸貨一體化的車輛調度問題（VRPSPD），而后者更是包括了先送貨后取貨的車輛路徑問題，同時集貨送貨的車輛路徑問題以及混合集貨送貨的車輛路徑問題。

VRPSPD的提出最早可以追溯到1989年，由Min提出的在解決了車輛數(shù)量一定并且車輛運載能力有限的情況下，一個中心配送點和22個地方圖書館之間的書籍配送問題。VRPSPD問題可描述為：某一個倉庫為其用戶群體進行貨運服務，任意用戶可能同時需要送貨和集貨服務，并且某一客戶的送取貨的需求之和不能大于車輛總運載能力Q。

VRPSDP的難點在于服務車輛的裝載量難以控制易發(fā)生溢出。當每一個客戶的送貨需求是已知的時候，依據(jù)車輛的剩余裝載能力來定義插入準則，。

2.5 動態(tài)車輛路徑問題

依據(jù)物流信息在配送之前是否完全可知，VRP按新的分類方式分為靜態(tài)VRP和動態(tài)VRP。動態(tài)車輛路徑問題的首次完全提出要歸功于Wilson和Colvin[13]，當時他們研究的單一車輛問題描述了客戶旅程的需求，從始發(fā)地到目的地的旅程是動態(tài)變化，并通過啟發(fā)式算法來提升計算效率。車輛路徑問題中動態(tài)信息最常見的來源就是客戶需求的在線到達。具體來說，需求可以是針對貨物的調整也可以是是服務需求的變化。

一般認為動態(tài)車輛路徑問題和靜態(tài)車輛路徑問題的區(qū)別在于信息的確定性與未知性，而前者在配送服務過程中，會出現(xiàn)不同類型的動態(tài)信息。

動態(tài)車輛路徑問題一般具有的特征如下：

1）安排配送路徑和車輛執(zhí)行計劃的過程中新客戶信息能夠實時的傳達。

2）任何新傳達的信息都允許是不精確的。

3）新信息需要被快速的響應。

4）與靜態(tài)VRP問題相比求解的目標函數(shù)更為繁雜。

任何動態(tài)車輛路徑問題仍是基于靜態(tài)車輛路徑問題提出的，目前針對動態(tài)車輛路徑問題的求解辦法，仍然需要借鑒處理靜態(tài)車輛路徑問題的各類算法，其中大部分算法為元啟發(fā)算法。

動態(tài)車輛路徑問題首先要明確需要響應哪些動態(tài)信息，并以客戶需求變化為依據(jù)，選擇需要優(yōu)化的目標函數(shù)，例如將配送車輛的總行程作為目標函數(shù)進行優(yōu)化，然后再設置額外的約束條件，例如設定單車最大行程為約束條件。借助各類啟發(fā)式算法如蟻群優(yōu)化算法等進行優(yōu)化，在整個配送過程中，不再是單一直接地插入顧客需求，通過最大熵法分布估計算法計算出具有發(fā)展?jié)摿Φ目蛻羧后w和區(qū)域。在=當需求發(fā)生沖突時衡量各個客戶需求的利益，通過懲罰措施來降低費用。

3 結束語

車輛路徑問題因其不可預估的經(jīng)濟效益和其在現(xiàn)代物流中的所占據(jù)的重要地位已經(jīng)引起了國內(nèi)外學者的高度關注，并依據(jù)實際需求不斷引入新的約束。在理論與應用上，各類精確算法、啟發(fā)式算法被廣泛地應用于解決車輛路徑問題，并已經(jīng)取得了長足的進步。然而，同樣被關注的是，從現(xiàn)有的各類研究成果看來，雖然新型約束條件下的VRP模型更加完善也更符合現(xiàn)代物流實際需求，但實際求解算法卻很難在精度和效率上做到兩全，簡化算法測率需要得到更多的重視，特別是，各類啟發(fā)式算法在求解時的弊端也愈加明顯，需要取長補短發(fā)揮其他算法的優(yōu)勢。

參考文獻：

[1] Dantzing G，Ramser J. The truck dispatching problem[J]. Management Science， 1959， 10（6）： 80-91.

[2]崔西.大規(guī)模多配送中心車輛路徑問題研究[D]. 濟南： 山東大學， 2009.

[3]Sariklis D， Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational ResearchSociety，2000，51： 564-573.

[4] Branda～o J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research， 2004，157：552-564.

[5] Desrochers M， Lenstra J K， Savelsbergh M W，et al. Vehicle Routing With Time Windows： Optimization and Approximation[M]. Amsterdam， The Netherlands： Elsevier Science Publishers， 1988.

[6] Braysy， Gendreau. Vehicle Routing Problem With Time Windows，Part I：Route Construction and Local Search Algorithms[J]. Transportation Science， 2005（39）： 104-118.

[7] Raul Banos， Julio Ortega， Consolacion Gil， et al. A Hybrid Meta-heuristic for Multi objective Vehicle Routing Problems with Time Windows[J]. Computers & Industrial Engineering， 2013， 65： 286-296.

[8] Wilson N，Colvin N.Computer control of the Rochester dial-a-ride system[Z]. Cambridge，Massachusetts，1977.