畢國通

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

關(guān)鍵詞：車輛路徑問題；啟發(fā)式算法；優(yōu)化

中圖分類號：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 引 言

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

企業(yè)通過選取恰當?shù)呐渌吐窂?，對運輸車輛進行優(yōu)化調(diào)度，可以明顯提高配送效率，有效減少車輛的空駛率和行駛距離，降低運輸成本，加快響應(yīng)客戶的速度從而提高客戶服務(wù)質(zhì)量，提高企業(yè)的核心競爭力。VRP作為物流系統(tǒng)優(yōu)化環(huán)節(jié)中關(guān)鍵的一環(huán)，其研究成果已經(jīng)應(yīng)用到快遞和報紙配送連鎖商店線路優(yōu)化以及城市綠化車線路優(yōu)化等社會實際問題中，因而車輛路徑問題的優(yōu)化研究具有很好的現(xiàn)實意義。

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

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

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

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

2 VRP的求解算法與研究現(xiàn)狀

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

2.1 遺傳算法（Genetic Algorithm，GA）

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

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

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

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

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

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

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

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

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

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

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

2.5 蝙蝠算法（Bat Algorithm，BA）

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

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

3 總結(jié)與展望

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

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

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

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

參考文獻：

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

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

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

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

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

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

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業(yè)工程與管理，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]. 系統(tǒng)工程理論與實踐，2011，31（8）：1508

-1516.

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

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

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

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

[14] 吳耀華，張念志. 帶時間窗車輛路徑問題的改進粒子群算法研究[J]. 計算機工程與應(yīng)用，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] 馬祥麗，張惠珍，馬良. 蝙蝠算法在物流配送車輛路徑優(yōu)化問題中的應(yīng)用[J]. 數(shù)學(xué)的實踐與認識，2015，45（24）：80-86.