容量約束的車輛路徑問題研究現狀綜述*

靳康飛，閆 軍，梁云濤

（蘭州交通大學 機電技術研究所，甘肅 蘭州 730070）

0 引言

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

CVRP問題在實際生活和理論研究中具有廣泛的應用。比如在實際的物流配送中，牛奶的收集與配送，煤炭物流中生產資料的運輸問題，垃圾的回收與處理，運輸車輛能耗的綠色車輛路徑問題，飲料行業的配送問題，抗震救災中的物資配送等現實情況的應用。CVRP問題是VRP問題的基本類型，因為它是VRP問題最基本的衍生問題，也很容易與VRP的其他衍生問題相結合，因此VRP也是學者研究最多的問題。在新能源車輛能源補充站數量有限的情況，由于新能源車輛的行駛距離有限，研究考慮新能源車輛運載能力綠色車輛路徑問題［2］。文章主要對物流運輸領域的CVRP發表的文獻進行簡要的總結和分析，CVRP的基本類型和衍生類型的研究進展進行分類綜述，并分析了CVRP未來的研究發展趨勢。

1 CVRP問題研究現狀

1.1 CVRP問題文獻研究現狀

文章從Web of science和ScienceDirect以“Capaci?tated Vehicle Routing Problems”檢索了公開發表的文獻，對檢索的文獻進行人工刪選，剔除了不相關的文獻（會議摘要，評論和已撤銷的出版物），并做了客觀的分析。研究CVRP問題的文獻最早發表在1997年，隨后眾多學者的研究逐漸增多。從1997～2021年發表的有關研究CVRP問題的文獻數量，如圖1所示。從2012年開始，CVRP問題研究逐漸增多，2015年文獻數量增長較快，而最近5年來發表的文獻數量較多。可見，CVRP問題已經逐漸成為近年來研究的熱點。

圖1 1997～2021年CVRP領域發表文獻數量

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

表1 發表CVRP論文的主要期刊

圖2 各國研究CVRP情況

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

圖3 發表CVRP論文期刊的數量和影響因子

1.2 CVRP研究進展

1.2.1 CVRP研究內涵

CVRP是指在物流的配送網絡中，有一個分撥中心，多個需求量不同的客戶和多臺配送車輛，在不超過車輛容量的前提下，合理的規劃車輛的配送路徑，使得總的配送費用最低的目標。CVRP是VRP的最基本類型。此問題中，客戶的信息是確定的，（如客戶的需求量，車輛的數量，客戶的位置等），客戶的服務類型單純為取送貨物，配送中心車輛的類型相同且車輛的約束也相同，客戶的需求量不大于車輛的容量，每個客戶的需求量不能被分割（即每個客戶僅由一輛車服務），配送車輛都是從分撥中心出發，完成配送任務后返回分撥中心，使問題的目標最小化。

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

1.2.2 CVRP相關算法研究現狀

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

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

2 CVRP衍生類型研究現狀

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

2.1 裝載限制的CVRP

具有二維裝載約束的容量限制的車輛路徑問題（2L-CVRP）是CVRP的拓展問題，2L-CVRP的目標是通過路徑調度優化和裝載優化兩方面的問題，使配送車輛的總路徑最小。在2L-CVRP問題中，貨車的車廂被抽象為一個長為L、寬為W的二維長矩形，則S=L*W為貨物的總裝載面積，而所有的貨物被抽象為矩形的底面。而根據貨物裝載的情況，2L-CVRP可分為有序無方向、有序有方向、無序無方向、無序有方向［8］。裝載與路徑的聯合優化的求解，事實上并不是兩個優化問題的簡單疊加或集成，這兩個問題是相互結合并且是錯綜復雜的。2005年，Iori［9］首先提出了2L-CVRP模型，并求解了規模為35個客戶，90多個實例。2008年，Gendreau［10］提出了可以解決大規模2L-CVRP的禁忌搜索算法。隨后，越來越多的優化算法被應用到了求解2L-CVRP。2017年，對考慮二維裝箱約束的多車場時間窗車輛路徑問題（Two-Dimensional Loading Capaci?tated Vehicle Routing Problems with Multi-depots and Time window，2L-CVRP-MDTW），顏瑞［11］提出了由量子粒子群算法和引導式局部搜索算法組成的混合算法進行求解。2021年，針對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），是三維裝箱配載和路徑調度的組合優化問題。裝載貨物時，必須考慮貨物的特性（易碎、不可擠壓），能否進行配載，還需考慮貨品的體積和重量不能超過車廂的可承受范圍。車輛行駛路徑是否可行依賴于貨物能否全部裝車，反過來貨品的裝載次序同樣會影響配送路徑的方案，因此兩者是相互緊密聯系的，必須綜合考慮。Koch將車廂分區，從而解決同時取送貨的3L-CVRP［13］。2015年，顏瑞針對3L-CVRP問題，提出模糊遺傳算法和引導式局部算法相結合的GLSFGA算法［14］。2016年，顏瑞在3L-CVRP的基礎上，考慮多配送中心，利用GLSFGA求解考慮三維裝箱約束多配送中心車輛路徑問題（Three-Dimensional Load?ing Multi-Depots Capacitated Constrains Vehicle Routing Problem）［15］。國內外的學者還考慮了分倉運輸、生鮮農產品、貨物的多層車廂配送、貨物不能混裝的3L-CVRP問題。

2.2 帶時間窗的CVRP

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

2.3 隨機需求的CVRP

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

2.4 大規模的CVRP

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

3 結語與展望

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

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

設計和開發新的解決方案，比如優化模擬技術、智能優化的算法、機器學習。目前好多算法在解決特定的車輛路徑優化問題表現出良好的性能，如何設計通用的算法來求解CVRP問題。精確算法只能求解小規模CVRP和啟發式算法容易陷入局部最優，而機器學習具有求解高效、穩定的特點，已有學者將機器學習（無監督學習、強化學習）的方式應用到車輛路徑優化問題。未來的研究中可以加大對機器學習的探索，從而使得求解CVRP更加穩定和高效。

多行程優化的車輛路徑問題引起了學者的關注。配送車輛在完成配送任務時只能從配送中心出發一次，而多行程優化問題配送車輛可以返回配送中心補貨后繼續執行配送任務。關于時間窗的模糊需求的多行程優化問題，同時考慮車隊規模和組合的復雜性、不同車型多車廂的限制，是CVRP問題未來面臨的新挑戰。