容量約束的車輛路徑問題研究現(xiàn)狀綜述*

靳康飛，閆 軍，梁云濤

（蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州 730070）

0 引言

如何有效地分配物流資源、降低運(yùn)輸?shù)某杀?，車輛路徑問題（Vehicle Routing Problems，VRP）是近年來交通運(yùn)輸和物流研究領(lǐng)域的熱門問題。VRP問題被提出后，影響VRP問題的因素被重點(diǎn)研究，如車輛容量的變化，與時(shí)間有關(guān)的限制，是否取送貨的限制。容量約束的車輛路徑問題（Capacitated Vehicle Routing Problems，CVRP）是車輛路徑問題的拓展問題，最初由Dantzig和Ramser提出［1］，根據(jù)他們的定義，在一個(gè)中心倉庫中具有相同容量或不同容量的車隊(duì)，為一組需求量不同、位置信息不同的客戶完成配送任務(wù)。在配送的過程中，從總的旅行時(shí)間、物流成本和配送時(shí)間等幾個(gè)方面確定最優(yōu)的路線。CVRP自從被提出后，國內(nèi)外學(xué)者做了大量的研究。

CVRP問題在實(shí)際生活和理論研究中具有廣泛的應(yīng)用。比如在實(shí)際的物流配送中，牛奶的收集與配送，煤炭物流中生產(chǎn)資料的運(yùn)輸問題，垃圾的回收與處理，運(yùn)輸車輛能耗的綠色車輛路徑問題，飲料行業(yè)的配送問題，抗震救災(zāi)中的物資配送等現(xiàn)實(shí)情況的應(yīng)用。CVRP問題是VRP問題的基本類型，因?yàn)樗荲RP問題最基本的衍生問題，也很容易與VRP的其他衍生問題相結(jié)合，因此VRP也是學(xué)者研究最多的問題。在新能源車輛能源補(bǔ)充站數(shù)量有限的情況，由于新能源車輛的行駛距離有限，研究考慮新能源車輛運(yùn)載能力綠色車輛路徑問題［2］。文章主要對(duì)物流運(yùn)輸領(lǐng)域的CVRP發(fā)表的文獻(xiàn)進(jìn)行簡要的總結(jié)和分析，CVRP的基本類型和衍生類型的研究進(jìn)展進(jìn)行分類綜述，并分析了CVRP未來的研究發(fā)展趨勢。

1 CVRP問題研究現(xiàn)狀

1.1 CVRP問題文獻(xiàn)研究現(xiàn)狀

文章從Web of science和ScienceDirect以“Capaci?tated Vehicle Routing Problems”檢索了公開發(fā)表的文獻(xiàn)，對(duì)檢索的文獻(xiàn)進(jìn)行人工刪選，剔除了不相關(guān)的文獻(xiàn)（會(huì)議摘要，評(píng)論和已撤銷的出版物），并做了客觀的分析。研究CVRP問題的文獻(xiàn)最早發(fā)表在1997年，隨后眾多學(xué)者的研究逐漸增多。從1997～2021年發(fā)表的有關(guān)研究CVRP問題的文獻(xiàn)數(shù)量，如圖1所示。從2012年開始，CVRP問題研究逐漸增多，2015年文獻(xiàn)數(shù)量增長較快，而最近5年來發(fā)表的文獻(xiàn)數(shù)量較多?？梢姡珻VRP問題已經(jīng)逐漸成為近年來研究的熱點(diǎn)。

圖1 1997～2021年CVRP領(lǐng)域發(fā)表文獻(xiàn)數(shù)量

統(tǒng)計(jì)發(fā)表在SCI上發(fā)表的CVRP的文獻(xiàn)。由表1可知，根據(jù)JCR分區(qū)，發(fā)表在Q1/Q2的文章居多（發(fā)表論文數(shù)量超過3篇的期刊）。圖2表示的是發(fā)表CVRP期刊所屬的國家情況：英國占比最多（32%），荷蘭（29%）和美國（17%）次之。

表1 發(fā)表CVRP論文的主要期刊

圖2 各國研究CVRP情況

通過分析現(xiàn)有發(fā)表的CVRP論文，其中發(fā)表在《Eu?ropean Journal Of Operational Research》中的一篇文獻(xiàn)，被引了133次，發(fā)表CVRP問題最多的期刊是《Com?puters&Operations Research》。表1統(tǒng)計(jì)了1997～2021年發(fā)表CVRP論文的主要期刊（發(fā)表論文數(shù)量超過3篇的期刊）。圖3表示了發(fā)表CVRP論文的數(shù)量和影響因子（圖中期刊名稱為簡稱）。

圖3 發(fā)表CVRP論文期刊的數(shù)量和影響因子

1.2 CVRP研究進(jìn)展

1.2.1 CVRP研究內(nèi)涵

CVRP是指在物流的配送網(wǎng)絡(luò)中，有一個(gè)分撥中心，多個(gè)需求量不同的客戶和多臺(tái)配送車輛，在不超過車輛容量的前提下，合理的規(guī)劃車輛的配送路徑，使得總的配送費(fèi)用最低的目標(biāo)。CVRP是VRP的最基本類型。此問題中，客戶的信息是確定的，（如客戶的需求量，車輛的數(shù)量，客戶的位置等），客戶的服務(wù)類型單純?yōu)槿∷拓浳?，配送中心車輛的類型相同且車輛的約束也相同，客戶的需求量不大于車輛的容量，每個(gè)客戶的需求量不能被分割（即每個(gè)客戶僅由一輛車服務(wù)），配送車輛都是從分撥中心出發(fā)，完成配送任務(wù)后返回分撥中心，使問題的目標(biāo)最小化。

CVRP可描述為假設(shè)某配送區(qū)域內(nèi)有n個(gè)客戶，分撥中心有m輛車，配送車輛從分撥中心出發(fā)，完成配送任務(wù)后返回分撥中心。CVRP問題做出以下假設(shè)：（1）配送中心或分撥中心和客戶的位置點(diǎn)已知，且客戶的需求量已知，車輛行駛的起點(diǎn)和終點(diǎn)都為配送中心；（2）每一條子路徑必須至少有一個(gè)客戶，每一條配送線路的子路徑客戶的總需求量不超過車輛的最大容量約束，配送中心可同時(shí)派出多輛車服務(wù)；（3）每輛車的單位時(shí)間的花費(fèi)成本都相同，每輛車的載重量，性能都已知；（4）每個(gè)客戶都有確定的需求，確保每個(gè)客戶都被服務(wù)。

1.2.2 CVRP相關(guān)算法研究現(xiàn)狀

CVRP屬于NP-hard問題。CVRP問題是在VRP的基礎(chǔ)上增加了車輛容量的約束條件，則在求解過程中必須同時(shí)考慮客戶的需求量、貨品的分配、車輛的數(shù)量和路徑規(guī)劃；CVRP的解是一組車輛路徑規(guī)劃的集合。CVRP求解時(shí)路徑問題和排序子問題是車輛調(diào)度需要解決的兩個(gè)子問題。路徑子問題是指每一個(gè)客戶必須有可供選擇的車輛，即必須保證每個(gè)客戶被服務(wù)。排序的子問題所有的客戶被服務(wù)后，對(duì)所有的客戶的服務(wù)順序利用算法規(guī)劃合適的路線。所以通常求解CVRP問題時(shí)一般有兩種方法：一是分別考慮路徑子問題和排序子問題；二是同時(shí)考慮兩個(gè)子問題一起求解。

求解CVRP的算法一般可分為：精確算法、啟發(fā)式算法和元啟發(fā)式算法。精確算法指求出最優(yōu)解的算法，在面對(duì)小規(guī)模的NP-hard問題時(shí)，求解效果優(yōu)于啟發(fā)式算法。精確算法可分為：動(dòng)態(tài)規(guī)劃算法、列生成法、切面法、分支定界算法和整數(shù)線性規(guī)劃算法。Hokama提出一種分切割算法求解二維裝載約束的CVRP問題［3］。在求解大規(guī)模CVRP問題時(shí)，精確算法容易陷入局部最優(yōu)，從而影響其求解效果；而啟發(fā)式算法和元啟發(fā)式算法求解大規(guī)模的CVRP問題表現(xiàn)出很好的性能。啟發(fā)式算法有：節(jié)約法、C-W節(jié)約算法、兩階段算法。元啟發(fā)式算法又稱智能優(yōu)化算法：模擬退火算法、禁忌搜索算法、遺傳算法、蜂群算法、粒子群算法、變領(lǐng)域搜索算法。近年來，為提高算法的求解性能，多種改進(jìn)的優(yōu)化算法和混合的優(yōu)化算法被越來越多的學(xué)者提出。尚正陽利用回火操作，解決了全局搜索與局部搜索不平衡的問題；通過隨機(jī)鄰域變換策略，提高多約束條件下的新解生成質(zhì)量，提出回火操作的改進(jìn)模擬退火算法［4］。黃戈文［5］用自適應(yīng)的遺傳灰狼優(yōu)化算法，蔣海青［6］在遺傳算法的基礎(chǔ)上應(yīng)用化學(xué)優(yōu)化算法，李陽［7］用混合變鄰域生物共棲搜索算法求解CVRP問題。

2 CVRP衍生類型研究現(xiàn)狀

在CVRP基礎(chǔ)上，增加不同約束的可拓展為不同的子問題，主要有4個(gè)方面，包括：增加裝載限制約束時(shí)，CVRP可拓 展 為2L-CVRP（Vehicle Routing Problems with Two-Dimensional Loading Constrain）和3L-CVRP（Vehicle Routing Problems with Three-Dimensional Load?ing Constrains）；增加時(shí)間窗的約束時(shí)，CVRP可以拓展為帶時(shí)間窗的容量約束的車輛路徑問題（Capacitated Vehicle Routing Problem with Time Window，CVRPTW）。當(dāng)客戶的需求量信息變化時(shí)，CVRP可拓展為客戶點(diǎn)需求量信息具有隨機(jī)分布特點(diǎn)的隨機(jī)需求車輛路徑問題（Vehicle Routing Problem With Stochastic Demand，VRPSD）；隨著客戶規(guī)模的不斷增加，國內(nèi)外的學(xué)者也開始研究大規(guī)模的CVRP問題。

2.1 裝載限制的CVRP

具有二維裝載約束的容量限制的車輛路徑問題（2L-CVRP）是CVRP的拓展問題，2L-CVRP的目標(biāo)是通過路徑調(diào)度優(yōu)化和裝載優(yōu)化兩方面的問題，使配送車輛的總路徑最小。在2L-CVRP問題中，貨車的車廂被抽象為一個(gè)長為L、寬為W的二維長矩形，則S=L*W為貨物的總裝載面積，而所有的貨物被抽象為矩形的底面。而根據(jù)貨物裝載的情況，2L-CVRP可分為有序無方向、有序有方向、無序無方向、無序有方向［8］。裝載與路徑的聯(lián)合優(yōu)化的求解，事實(shí)上并不是兩個(gè)優(yōu)化問題的簡單疊加或集成，這兩個(gè)問題是相互結(jié)合并且是錯(cuò)綜復(fù)雜的。2005年，Iori［9］首先提出了2L-CVRP模型，并求解了規(guī)模為35個(gè)客戶，90多個(gè)實(shí)例。2008年，Gendreau［10］提出了可以解決大規(guī)模2L-CVRP的禁忌搜索算法。隨后，越來越多的優(yōu)化算法被應(yīng)用到了求解2L-CVRP。2017年，對(duì)考慮二維裝箱約束的多車場時(shí)間窗車輛路徑問題（Two-Dimensional Loading Capaci?tated Vehicle Routing Problems with Multi-depots and Time window，2L-CVRP-MDTW），顏瑞［11］提出了由量子粒子群算法和引導(dǎo)式局部搜索算法組成的混合算法進(jìn)行求解。2021年，針對(duì)LIFO約束下的2L-CVRP問題，尚正陽［12］提出了ISA-LOS算法（Improved Simulated An?nealing，ISA，Least Open Space，LOS）。

三維裝載約束的容量限制的車輛路徑問題（Vehi?cle Routing Problems with Three-Dimensional Loading Constrains，3L-CVRP），是三維裝箱配載和路徑調(diào)度的組合優(yōu)化問題。裝載貨物時(shí)，必須考慮貨物的特性（易碎、不可擠壓），能否進(jìn)行配載，還需考慮貨品的體積和重量不能超過車廂的可承受范圍。車輛行駛路徑是否可行依賴于貨物能否全部裝車，反過來貨品的裝載次序同樣會(huì)影響配送路徑的方案，因此兩者是相互緊密聯(lián)系的，必須綜合考慮。Koch將車廂分區(qū)，從而解決同時(shí)取送貨的3L-CVRP［13］。2015年，顏瑞針對(duì)3L-CVRP問題，提出模糊遺傳算法和引導(dǎo)式局部算法相結(jié)合的GLSFGA算法［14］。2016年，顏瑞在3L-CVRP的基礎(chǔ)上，考慮多配送中心，利用GLSFGA求解考慮三維裝箱約束多配送中心車輛路徑問題（Three-Dimensional Load?ing Multi-Depots Capacitated Constrains Vehicle Routing Problem）［15］。國內(nèi)外的學(xué)者還考慮了分倉運(yùn)輸、生鮮農(nóng)產(chǎn)品、貨物的多層車廂配送、貨物不能混裝的3L-CVRP問題。

2.2 帶時(shí)間窗的CVRP

帶時(shí)間窗的容量約束車輛路徑問題（CVRPTW），指每一個(gè)客戶都有一個(gè)服務(wù)的時(shí)間窗口，這個(gè)時(shí)間窗口是指服務(wù)客戶所用的時(shí)間，車輛的配送任務(wù)必須在這個(gè)時(shí)間窗口開始和結(jié)束的時(shí)間內(nèi)為客戶服務(wù)。González［16］提出了一種特殊的車輛路徑問題，即累積容量約束問題帶時(shí)間窗約束的車輛路徑問題（the Cumu?lative Capacitated Vehicle Routing Problem with Timewindow Constraints，Cum CVRPTW）。問題描述為：有一組地理位置分散的客戶，客戶的要求是在一個(gè)固定的時(shí)間窗內(nèi)完成配送任務(wù)，目標(biāo)的成本計(jì)算為所有客戶的到達(dá)時(shí)間之和；并用大領(lǐng)域搜索算法和遺傳算法相結(jié)合的算法求解此問題。同時(shí)具有三維裝載約束和時(shí)間窗約束的車輛路徑問題（Capacitated Vehicle Routing Problem With Three-Dimensional Loading Constraints with Time Windows，3L-CVRPTW），Pace［17］用局部搜索算法和模擬退火算法相結(jié)合的算法，王超［18］用多階段算法與兩層算法相結(jié)合的算法分別求解了此問題。

2.3 隨機(jī)需求的CVRP

在實(shí)際的快遞物流過程中，零售商（快遞和物流行業(yè)的客戶）的貨物數(shù)量事先不知道，快遞和物流行業(yè)就得將客戶需求的隨機(jī)信息考慮進(jìn)來，從而可以降低物流的成本。客戶點(diǎn)需求量隨機(jī)分布，且假設(shè)在規(guī)劃每個(gè)客戶的概率發(fā)布已知的車輛路徑問題，稱為隨機(jī)需求的車輛路徑問題（Capacitated Vehicle Routing Problem With Stochastic Demand，CVRPSD）。Christian［19］用分支定價(jià)算法求解隨機(jī)需求的車輛路徑問題。Wang［20］研究隨機(jī)需求的兩級(jí)有容量約束的車輛路徑問題，首先用隨機(jī)規(guī)劃描述了此問題，并基于遺傳算法求解2ECVRPSD問題。李陽［21］通過構(gòu)建CVRPSD的隨機(jī)機(jī)會(huì)約束的模型，設(shè)計(jì)兩階段的混合變領(lǐng)域搜索算法，減少對(duì)人工和車輛的占用。

2.4 大規(guī)模的CVRP

容量約束車輛路徑問題（CVRP）由于其在各種現(xiàn)實(shí)場景中的應(yīng)用，近年來得到了廣泛的研究。通常對(duì)CVRP的研究是對(duì)標(biāo)準(zhǔn)算例庫，其規(guī)模主要是從幾十到幾百個(gè)客戶點(diǎn)，而隨著科技的發(fā)展，CVRP中的客戶通常會(huì)上升到一定的規(guī)模，因此LSCVRP研究就很有必要。然而，對(duì)于大多數(shù)現(xiàn)有算法來說，解決大規(guī)模CVRP仍然是一個(gè)非常具有挑戰(zhàn)性的問題，即擁有數(shù)百或數(shù)千個(gè)客戶的CVRP。在解決中小規(guī)模的CVRP問題（一般指服務(wù)的客戶不到500人）時(shí)，啟發(fā)式算法和數(shù)學(xué)規(guī)劃算法有很高的效率；然而，這兩種方法在處理LSCVRP時(shí)的可拓展性較差。上述2類算法在解決中小規(guī)模的CVRP問題（通常需要服務(wù)的客戶不到500人）時(shí)都表現(xiàn)出了很高的效率。然而，它們中的大多數(shù)對(duì)大規(guī)模CVRP（LSCVRP）的可擴(kuò)展性較差，尤其是對(duì)于擁有1000多個(gè)客戶的客戶。Teymourian［22］通過利用智能水滴和布谷鳥搜索方法在探索解決方案空間方面的優(yōu)點(diǎn)，提出2種混合啟發(fā)式算法，該算法在解決50～483個(gè)客戶的CVRP問題有很高的效率。Mester［23］將進(jìn)化策略和引導(dǎo)式局部搜索結(jié)合到一個(gè)迭代的兩階段過程中，對(duì)50～1200個(gè)客戶的CVRP，實(shí)驗(yàn)結(jié)果表明該算法有較好的可拓展性。Xiao［24］提出可變領(lǐng)域的模擬搜索算法，并在1200個(gè)CVRP客戶的基礎(chǔ)上驗(yàn)證此算法的優(yōu)越性。Armas［25］討論時(shí)間容量限制的弧路徑問題（Capacitated Vehicle Arc Routing Problem，CARP），并介紹了一種啟發(fā)式和亞啟發(fā)式算法解決此問題。

3 結(jié)語與展望

CVRP問題的研究對(duì)物流配送車輛的路徑的優(yōu)化有重要的生活應(yīng)用和理論研究價(jià)值。通過對(duì)配送車輛的容量約束，優(yōu)化裝貨方案和確定最優(yōu)的路徑方案可以降低車輛配送中的行駛成本，從而降低整體的物流成本。文章對(duì)CVRP研究進(jìn)展做了簡要的歸納和總結(jié)，包括CVRP的基本類型和衍生問題。基于CVRP研究現(xiàn)狀綜述，得出CVRP未來的研究方向和趨勢，希望可以為交通運(yùn)輸、物流配送領(lǐng)域的學(xué)者提供一些見解和啟示。

為減少對(duì)環(huán)境的影響和新能源車輛的使用，綠色車輛路徑問題逐漸成為未來研究的熱點(diǎn)。考慮實(shí)時(shí)的交通信息，比如道路狀況和停車位的可用性，配送車輛可以被規(guī)劃到不太擁擠的路線，可以減少配送的服務(wù)時(shí)間；通過規(guī)劃使車輛以最佳的速度行駛，就可以使配送過程更加環(huán)保，從而減少污染。將日常交通擁堵的真實(shí)模式參考進(jìn)來，如規(guī)劃的范圍、倉庫的位置、車隊(duì)規(guī)模和組合、出發(fā)的時(shí)間、客戶的需求以及時(shí)間窗口的設(shè)置，這有助于更好地了解城市物流系統(tǒng)的運(yùn)行，從而更好地處理能源消耗的變化。

設(shè)計(jì)和開發(fā)新的解決方案，比如優(yōu)化模擬技術(shù)、智能優(yōu)化的算法、機(jī)器學(xué)習(xí)。目前好多算法在解決特定的車輛路徑優(yōu)化問題表現(xiàn)出良好的性能，如何設(shè)計(jì)通用的算法來求解CVRP問題。精確算法只能求解小規(guī)模CVRP和啟發(fā)式算法容易陷入局部最優(yōu)，而機(jī)器學(xué)習(xí)具有求解高效、穩(wěn)定的特點(diǎn)，已有學(xué)者將機(jī)器學(xué)習(xí)（無監(jiān)督學(xué)習(xí)、強(qiáng)化學(xué)習(xí)）的方式應(yīng)用到車輛路徑優(yōu)化問題。未來的研究中可以加大對(duì)機(jī)器學(xué)習(xí)的探索，從而使得求解CVRP更加穩(wěn)定和高效。

多行程優(yōu)化的車輛路徑問題引起了學(xué)者的關(guān)注。配送車輛在完成配送任務(wù)時(shí)只能從配送中心出發(fā)一次，而多行程優(yōu)化問題配送車輛可以返回配送中心補(bǔ)貨后繼續(xù)執(zhí)行配送任務(wù)。關(guān)于時(shí)間窗的模糊需求的多行程優(yōu)化問題，同時(shí)考慮車隊(duì)規(guī)模和組合的復(fù)雜性、不同車型多車廂的限制，是CVRP問題未來面臨的新挑戰(zhàn)。