車輛路徑問題及其優化算法研究綜述

畢國通

摘 要：車輛路徑問題是物流管理與運輸組織優化中的核心問題，是運籌學中一類經典的組合優化問題。文章比較系統地總結了常見的VRP問題的分類和基本的數學模型，并通過查閱學者們的研究狀況，總結了求解VRP問題常用和高效的啟發式算法及相應的研究現狀；最后總結了研究存在的問題，并對今后VRP問題的研究和求解方法進行了展望。

關鍵詞：車輛路徑問題；啟發式算法；優化

中圖分類號：U116.2 文獻標識碼：A

Abstract： Vehicle routing problem is the core problem in logistics management and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars' research situation， summarized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems.

Key words： vehicle routing problem； heuristic algorithm； optimization

0 引 言

隨著科技的進步和電子商務的飛速發展，作為國民經濟中一個重要行業的物流產業已成為拉動國家經濟發展與提高居民生活水平的重要動力源泉，而物流行業中的車輛路徑問題（Vehicle Routing Problem， VRP）是制約物流行業發展的一個關鍵要素，其研究也受到人們的廣泛關注。車輛路徑問題是物流管理與運輸組織優化中的核心問題之一，是指在滿足一定的約束條件（如時間限制、車載容量限制、交通限制等）下，通過對一系列收貨點與發貨點客戶合理安排行車路線，在客戶的需求得到滿足的前提下，達到配送車輛最少、配送時間最短、配送成本最低、配送路程最短等目標。該問題由Dantzig和Ramser[1]于1959年在優化亞特蘭大煉油廠的運輸路徑問題時首次提出，現已成為運籌學中一類經典的組合優化問題，是典型的NP-難題。

企業通過選取恰當的配送路徑，對運輸車輛進行優化調度，可以明顯提高配送效率，有效減少車輛的空駛率和行駛距離，降低運輸成本，加快響應客戶的速度從而提高客戶服務質量，提高企業的核心競爭力。VRP作為物流系統優化環節中關鍵的一環，其研究成果已經應用到快遞和報紙配送連鎖商店線路優化以及城市綠化車線路優化等社會實際問題中，因而車輛路徑問題的優化研究具有很好的現實意義。

1 車輛路徑問題的分類與基本模型

VRP的構成要素通常包括車輛、客戶點、貨物、配送中心（車場）、道路網絡、目標函數和約束條件等，根據側重點的不同，VRP可以分為不同的類型。根據運輸車輛載貨狀況分類可分為非滿載車輛路徑問題和滿載車輛路徑問題；根據任務特征可分為僅裝貨、僅卸貨和裝卸混合的車輛路徑問題；根據優化目標的數量可分為單目標車輛路徑問題和多目標車輛路徑問題；根據配送車輛是否相同可分為同型車輛路徑問題和異型車輛路徑問題；根據客戶對貨物接收與發送有無時間窗約束可分為不帶時間窗的車輛路徑問題和帶時間窗的車輛路徑問題；根據客戶需求是否可拆分可分為需求可拆分車輛路徑問題和需求不可拆分車輛路徑問題；根據客戶是否優先可分為優先約束車輛路徑問題和無優先約束車輛路徑問題；根據配送與取貨完成后車輛是否需要返回出發點可分為開放式車輛路徑問題和閉合式車輛路徑問題；還可以將上述兩個或更多約束條件結合起來，構成一些更復雜的車輛路徑問題。

由于VRP的約束條件不同引起了其分類多種多樣，而不同類型的VRP其模型構造及求解算法有很大差別。VRP的一般數學模型為：

在上述模型中，式（1）表示目標函數，式（2）表示約束條件。其他VRP模型大致都是在此模型的基礎上根據約束條件完善形成的。

2 VRP的求解算法與研究現狀

VRP的求解方法，基本上可分為精確算法和啟發式算法兩大類。由于精確算法的計算難度與計算量隨著客戶點的增多呈指數級增加，在實際中應用范圍有限，而啟發式算法則具有全局搜索能力強、求解效率高的特點，求出的解也具有較好的參考性，因此，目前大部分研究者們主要把精力集中在如何構造高質量的啟發式算法上，本文也主要討論一些近年來研究比較多的啟發式優化算法。針對VRP問題目前已提出了大量的啟發式算法，其中研究較多的主要包括以下算法：

2.1 遺傳算法（Genetic Algorithm，GA）

GA是一種通過模擬生物進化過程來搜索最優解的方法，該方法通過對群體進行選擇、交叉和變異等操作，產生代表新的解集的種群，根據個體適應度大小選擇個體，通過迭代逐步使群體進化到近似最優解狀態。但是該算法具有搜索速度慢、易早熟、總體可行解質量不高等缺點。

采用遺傳算法研究VRP問題的研究現狀包括：蔣波[2]設計了遺傳算法求解以配送總成本最小為目標函數和帶有懲罰函數的VRPTW模型；趙辰[3]基于遺傳算法求解了從生產中心到倉庫之間的路徑優化問題，設計了配送路徑優化決策；張群和顏瑞[4]建立了多配送中心、多車型車輛路徑問題混合模型，并采用一種新的模糊遺傳算法求解該問題。

2.2 模擬退火算法（Simulated Annealing，SA）

SA同禁忌搜索算法一樣，也屬于局部搜素算法，但是模擬退火算法是模仿金屬加工中退火的過程，通過一個溫度函數作為目標函數，使其趨于最小值，是一種基于概率的算法。

采用模擬退火算法研究VRP問題的研究現狀包括：郎茂祥[5]研究了裝卸混合車輛路徑問題，并構造了模擬退火算法求解該問題；穆東等[6]提出了一種并行模擬退火算法，并將該算法的應用領域擴展到其他車輛路徑問題和組合優化問題；魏江寧和夏唐斌[7]以模擬退火算法為基礎，研究了單個集散點與多個客戶之間的運輸問題；Mirabi和Fatemi Ghomi等[8]提出了一種基于模擬退火思想的三步啟發式算法求解最小化配送時間的多配送中心VRP模型。

2.3 蟻群算法（Ant Colony Optimization，ACO）

蟻群算法是人們受螞蟻可以快速找到食物的自然現象啟發提出的。蟻群算法所建立的機制，主要包括螞蟻的記憶、螞蟻利用信息素進行交互通信及螞蟻的集群活動三個方面。單個螞蟻缺乏智能，但整個蟻群則表現為一種有效的智能行為。通過這種群體智能行為建立的路徑選擇機制可使蟻群算法的搜索向最優解靠近。

采用蟻群算法研究VRP問題的研究現狀包括：馬建華等[9]研究了基于動態規劃方法的多車場最快完成車輛路徑問題的變異蟻群算法；辛穎[10]通過對MMAS蟻群算法進行了三種策略的改造，指出蟻群算法可以找到相對較好的解和很強的魯棒性；陳迎欣[11]針對蟻群算法的缺點，分別對信息素更新策略、啟發因子進行改進，引入搜索熱區機制，有效解決車輛路徑優化問題；段征宇等[12]通過最小成本的最鄰近法生成蟻群算法和局部搜索操作設計了一種求解TDVRP問題的改進蟻群算法。

2.4 粒子群算法（Particle Swarm Optimization，PSO）

PSO算法是通過對鳥群覓食行為的研究而得出的一種群體并行優化算法，它從隨機解出發，通過迭代尋找最優解。蟻群算法具有容易實現、收斂速度快、精度高等優點，在多種優化問題上均取得了較好的效果。但是由于PSO算法是通過粒子之間的相互作用來尋找最優解，缺乏像遺傳算法那樣的變異機制，因而PSO算法容易陷入局部最優。

采用粒子群算法研究VRP問題的研究現狀包括：馬炫等[13]提出了一種基于粒子交換原理的整數粒子更新方法求解有時間窗約束的車輛路徑問題；吳耀華和張念志[14]以處理集貨或送貨非滿載帶時間窗車輛路徑優化問題為背景，提出了帶自調節機制的局部近鄰粒子群算法解決VRP問題。

2.5 蝙蝠算法（Bat Algorithm，BA）

蝙蝠算法是劍橋大學學者Yang[15]于2010年提出的一種新型群智能進化算法，模擬自然界中蝙蝠通過超聲波搜索、捕食獵物的生物學特性，是一種基于種群的隨機尋優算法。截至目前，蝙蝠算法主要用于求解連續域的函數優化問題，只有少數學者將其用來求解離散型問題，具有很好的研究前景。

采用蝙蝠算法研究VRP問題的研究現狀包括：馬祥麗等[16]將蝙蝠算法應用于求解VRP問題，在蝙蝠速度更新公式中引入了慣性權重，對基本蝙蝠算法進行了改進，克服了基本蝙蝠算法的不足之處；馬祥麗等[16]針對VRPTW問題的具體特性重新定義了蝙蝠算法的操作算子，設計了求解VRPTW 問題的蝙蝠算法，并采用罰函數的方式對目標函數進行了簡化求解。

3 總結與展望

車輛路徑問題由于約束條件的不同其分類多種多樣，數學模型與求解算法也層出不窮。本文總結了近幾年一些相關學者對VRP問題的研究和求解算法，通過較為系統地總結VRP問題，本文總結出以下當前研究存在的問題和今后可能的研究方向：

（1）研究目標太過理想化。目前學者研究VRP的研究過于注重成本最小和路徑最短，大部分是單目標優化，而在實際應用中，配送的駕駛員也可能會因許多原因耽誤計劃的行程，顧客的需求各異甚至沖突，顧客滿意度與企業成本最小化目標之間存在效益悖反的矛盾。今后的研究可以將成本、路程、駕駛員休息、顧客滿意度等多個目標聯合起來進行研究，并可以通過線性加權的方式進行綜合求解。

（2）單個約束的VRP問題由于研究時間較長，現在已經研究的較為成熟，而且其應用局限也比較大，應該考慮將多個約束條件結合起來，建立符合實際的多約束條件的車輛路徑問題，更好地解決企業的配送優化。

（3）雖然啟發式算法具有全局搜索能力強，運算方便等優點，但是也存在著局部搜索能力差、收斂時間過長、易陷于局部最優等問題。使用單一的群智能算法不是求解VRP的最有效算法，將兩種和多種群智能算法結合起來研究車輛路徑問題，取長補短，是今后應該考慮的問題；同時，應考慮尋求更多的智能優化算法來求解VRP問題。

參考文獻：

[1] GB. Dantzig， JK. Ramser. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 蔣波. 基于遺傳算法的帶時間窗車輛路徑優化問題研究[D]. 北京：北京交通大學（碩士學位論文），2010.

[3] 趙辰. 基于遺傳算法的車輛路徑優化問題研究[D]. 天津：天津大學（碩士學位論文），2012.

[4] 張群，顏瑞. 基于改進遺傳算法的混合車輛路徑問題[J]. 中國管理科學，2012，20（2）：121-128.

[5] 郎茂祥. 裝卸混合車輛路徑問題的模擬退火算法研究[J]. 系統工程學報，2005，20（5）：485-491.

[6] 穆東，王超，王勝春，等. 基于并行模擬退火算法求解時間依懶型車輛路徑問題[J]. 計算機集成制造系統，2015，21（6）：1626

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業工程與管理，2015，20（3）：1-8.

[8] M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing， 2010，26（6）：564-569.

[9] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統工程理論與實踐，2011，31（8）：1508

-1516.

[10] 辛穎. 基于蟻群算法的車輛路徑規劃問題求解研究[D]. 長春：吉林大學（碩士學位論文），2015.

[11] 陳迎欣. 基于改進蟻群算法的車輛路徑優化問題研究[J]. 計算機應用研究，2012，29（6）：2031-2034.

[12] 段征宇，楊東援，王上. 時間依賴型車輛路徑問題的一種改進蟻群算法[J]. 控制理論與應用，2010，27（11）：1557-1563.

[13] 馬炫，彭芃，劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應用，2009，45（27）：200-204.

[14] 吳耀華，張念志. 帶時間窗車輛路徑問題的改進粒子群算法研究[J]. 計算機工程與應用，2010，46（15）：230-235.

[15] Yang X S. A new metaheuristic bat-inspired algorithm[C] // Nature-Inspired Coopreative Strategies for Optimization， 2010：65

-74.

[16] 馬祥麗，張惠珍，馬良. 蝙蝠算法在物流配送車輛路徑優化問題中的應用[J]. 數學的實踐與認識，2015，45（24）：80-86.