車輛路徑問(wèn)題及其優(yōu)化算法研究綜述

畢國(guó)通

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

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

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

1 車輛路徑問(wèn)題的分類與基本模型

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

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

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

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

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

2.1 遺傳算法（Genetic Algorithm，GA）

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

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

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

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

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

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

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

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

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

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

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

2.5 蝙蝠算法（Bat Algorithm，BA）

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

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

3 總結(jié)與展望

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫(kù)存路徑問(wèn)題研究[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] 馬建華，房勇，袁杰. 多車場(chǎng)多車型最快完成車輛路徑問(wèn)題的變異蟻群算法[J]. 系統(tǒng)工程理論與實(shí)踐，2011，31（8）：1508

-1516.

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

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

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

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

[14] 吳耀華，張念志. 帶時(shí)間窗車輛路徑問(wèn)題的改進(jìn)粒子群算法研究[J]. 計(jì)算機(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)化問(wèn)題中的應(yīng)用[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2015，45（24）：80-86.