解決車輛路徑問題及其變體的混合粒子群算法綜述

楊觀富 蔡延光

特約論文

解決車輛路徑問題及其變體的混合粒子群算法綜述

楊觀富 蔡延光

（廣東工業大學自動化學院，廣東 廣州 510006）

通過對車輛路徑問題的分析總結，得出啟發式算法在解決車輛路徑問題具有優越性的結論，并以混合粒子群算法為代表，詳細闡述混合粒子群在不同車輛路徑變形問題中的應用。最后指出車輛路徑問題和混合粒子群算法研究的不足與趨勢，強調該問題與算法具良好的擴展性，在物流領域有廣闊的應用前景。

車輛路徑；啟發式算法；混合粒子群

0 引言

21世紀以來，隨著科學技術與電子商務的快速發展，物流行業已逐漸成為國家經濟增長的重要支柱，也成為提高人民生活水平與生活質量的重要保障。同時，物流行業發展的瓶頸——車輛路徑問題（vehicle routing problem, VRP）備受研究人員關注。VRP由DANTZING和RAMSER于1959年提出[1]，本意是優化亞特蘭大煉油廠的運輸路徑。經過60多年的發展與歷代研究人員的研究，其研究目的、對象和限制條件等都有極大擴充。目前，VRP已從最初的簡單車輛安排調度逐步演變為運籌學中一類經典的組合優化問題，是物流管理與運輸組織優化中的核心問題，也是一個典型的NP難題。

隨著VRP復雜程度不斷增加，傳統的優化方法在解決該問題時捉襟見肘。研究人員從自然界的一些現象得到啟發，利用自然界的規律設置算法，形成一系列的啟發式算法，如粒子群算法、人工魚群算法和共生生物算法等。這些算法結構相對簡單，不需要研究人員具備太多相關的專業知識，調節參數較少，容易實現。但也存在計算效率低、通用性差或全局搜索能力不足等問題。隨著VRP模型規模越來越大，約束條件越來越多，將算法合并得到的新算法，能較好解決這類問題，且具有較好的魯棒性、智能性、適應性以及良好的全局搜索能力?；旌狭Ｗ尤核惴ň褪瞧渲械馁?。

啟發式算法被提出來后受到了各國研究人員的廣泛關注。本文對近年來的VRP文獻進行分析總結，歸納出VRP及其變形模型；對解決各模型的算法進行歸納，著重分析混合粒子群算法目前的研究進度，并從中推斷出混合粒子群算法今后的研究方向。

1 VRP及其變形

基本的車輛路徑問題也稱為容量限制車輛路徑問題（capacitated VRP, CVRP），是指所有車輛都在中央倉庫開始和結束的條件限制下，為一組相同車輛尋找到能夠滿足所有需求且總路線成本最小的路線集?？删唧w理解為若干顧客隨機分布在不同區域，一組車隊從倉庫出發，有且僅有一次經過所有顧客位置，最后回到出發點。在這期間，每輛車不能超過最大裝載能力，不能超過車輛最大行駛距離，也不能對貨物進行分批配送。VRP有很多變形，下面對近年來VRP的變形進行分析總結。

帶時間窗的車輛路徑問題（the VRP with time windows, VRPTW）在基本VRP的基礎上添加了時間限制，即強制每輛車都必須在特定的時間間隔內交付貨物給顧客或從顧客處取走貨物。該問題又分為帶軟時間窗的車輛路徑問題（VRP with soft time window ,VRPSTW）、帶硬時間窗的車輛路徑問題（VRP with hard time window, VRPHTW）和混合時間窗的車輛路徑問題（VRP with mixing time window, VRPMTW）3類。其中，VRPHTW不允許有任何的時間延遲，如Yan等[2]根據城市物流特點，建立具有困難時段的城市冷鏈物流兩階段配送選址路由模型；VRPSTW允許有時間上的延遲或提前，但會有相應懲罰，如李博威等[3]以軟時間窗為基礎，綜合考慮違反時間窗、客戶滿意度等問題構建混合整數非線性規劃模型（mixed integer nonlinear programming, MINLP）；VRPMTW允許車輛以給定的公差偏離客戶時間窗，可分別在最早和最近的時間范圍之前和之后為客戶提供服務，節省運營成本，如丁建立等[4]考慮到航班到達的不確定性，建立地面特種作業車輛的混合時間窗車輛路徑模型，有利于機場實際運營。

取貨與運送問題（the pickup and delivery problem, PDP）是指貨物需要從某些取貨地點轉移到其他交貨地點。因此，根據取貨與運貨的回程和交接、取貨與運送問題也可細分為5個部分，如表1所示。

隨機車輛路徑問題（the stochastic VRP, SVRP）不是單純的車輛路徑問題，而是車輛問題中的一個或者幾個問題的組成，具有較大不確定性。具體分類如表2所示。

表1 PDP延伸領域

表2 SVRP分類

除上述一些常見的VRP及其變形外，還存在一些相對不常用的變形。不常用VRP及變形部分是研究人員在特定情況下提出的，即這些變形沒有普適性，僅是針對相應的場景建立模型從而提出解決方法，如定期車輛路徑問題、開放式車輛路徑問題等，如表3所示。

表3 不常用車輛路徑問題匯總表

2 混合粒子群算法

VRP的求解方法主要分為精確解法和啟發式算法2類。隨著VRP越來越復雜，精確解法呈指數級增長，難以滿足實際應用需要。而啟發式算法因具有收斂快、效率高等特點逐漸取代精確解法，成為當前研究熱點。目前，研究人員的主要研究方向是構造更適用于具體場景、高質量的啟發式算法，如遺傳算法、模擬退火算法、蟻群算法、粒子群算法、蝙蝠算法和免疫算法等。但是隨著研究的深入，VRP規模越來越大，約束條件也越來越多，啟發式算法雖然具有運算簡單的特點，但局部搜索能力較弱，易陷入局部最優。研究人員發現：啟發式算法融合其他算法或技術特性組成的混合算法，可有效緩解局部最優問題。如混合粒子群算法就是粒子群算法融合其他算法或因子的比較有代表性的算法。混合粒子群算法最終優化目標主要為：

1）提高種群的收斂性和多樣性，防止早熟收斂；

2）快速得出最優解，降低時間成本；

3）提高PSO的局部搜索性能和精度。

目前，為達到以上目標，通常有2個改進方向：1）混合進化算子；2）混合其他搜索算法，如圖1所示。

圖1 混合粒子群算法混合思路

2.1 混合進化算子的改進

EBERHART等[38]將慣性系數引入標準粒子群算法，并將使用慣性權重與收縮因子的粒子群優化性能進行比較，得出適當選擇慣性權重可有效提高粒子群優化性能，從此開始混合進化算子的研究。周馳等[39]在進行窄巷道倉儲三維揀選時，將動態慣性權重的思想引入粒子群算法，并在優化過程中使用交叉算子和變異算子，實驗證明，該混合粒子群算法在解決三維揀選問題上效果比遺傳算法好。KENNEDY等[40]在尋找使粒子群起作用特性時，去除粒子群的一些傳統特征，通過消除速度公式來修改粒子群算法。梁旭[41]等將混沌優化的思想引入粒子群，在解決在線檢測與路徑規劃方面比蟻群算法的效果好。ANGELINE[42]將優勝劣汰的思想轉化為選擇算子，并將其引入粒子群算法，根據適應度值的好壞，將最差的一般粒子淘汰，保留最差粒子的個體極值，提高算法的全局搜索能力與精度。MENG[43]等以交叉搜索作為進化催化劑，提出新型交叉搜索的粒子群算法，該方法通過在相反方向執行不同的交叉操作，在每一代中復制大量的中度解，水平交叉搜索提高粒子群算法的全局搜索能力，與水平交叉搜索不同，垂直交叉搜索用于保持群體多樣性，并且也是避免局部最優問題的有效手段，大量實驗結果表明，與大多數其他最新的粒子群變體相比，交叉粒子群算法具有更好的搜索性能。

2.2 混合其他搜索算法的改進

葛宏義等[44]結合粒子群算法與模擬退火算法，根據糧食運輸分布分散、數量多等特點建立VRPTW模型，取得較好效果。馬艷芳等[14]利用模糊隨機理論的特點解決環境不確定性，結合粒子群算法求解VRPSPD。楚學偉[45]為提高車間效率將粒子群與模擬退火和遺傳算法結合，對DVRP進行建模求解，實驗效果比離散粒子群算法好。陸琳[46]將導引式局部搜索理論引入種群搜索中，提出新的混合粒子群算法解決VRPSC，證明了混合粒子群算法的有效性。The Jin Ai等[47]提出粒子群不同的編碼方式，結合模擬退火算法對CVRP進行建模編碼，并比較2種不同編碼方式對優化結果的影響。MIRHASSANI[48]在解碼方法中以降序構造顧客位置向量，實現一種真值版本的混合粒子群算法解決OVRP，該算法在可行性條件下，給每個客戶分配一條路線。Yannis Marinakis[49]將局部搜索策略應用于粒子群算法，針對VRPSD進行求解，并與差分進化算法和遺傳算法進行對比，驗證其優越性。Du Jiaoman[50]綜合考慮危險材料的需求和潛在威脅，提出4種基于模糊仿真的混合粒子群算法，解決了存有危險材料的多倉庫物流車輛路徑問題。李和洋[51]根據庫存路徑和車輛路徑的關系，同時考慮不同型號車輛的運輸能力，設計雙層遺傳算法，結合粒子群算法對PVRP和VRPLC提出全新算法，為相關企業的庫存路徑優化決策提供參考。

3 VRP及混合粒子群問題和趨勢

VRP由于不同約束條件而呈現出不同的變形。本文上述所列舉的VRP變形僅是冰山一角。實際應用中，單一的變形可根據現實情況調整，從而衍生出更符合實際應用的模型，而不是把研究目標過于理想化，僅僅注重成本最小或路徑最短。此外，上述車輛路徑變形不是獨立存在的，存在著各種變形問題的組合，最終還是歸結于實際情況，不能拘泥于某一個特定的模型。隨著物流業的發展，VRP更加復雜，規模也越來越大，必然會出現更多路徑問題的組合，甚至全新的車輛路徑模型。

混合粒子群算法以其優越的性能而被廣泛應用于VRP的研究。值得一提的是，不是所有的VRP及其變形都適合使用混合粒子群算法進行求解，遺傳算法、共生生物搜索算法或混合遺傳算法等更適合于某些模型的求解，對于其他啟發式算法的組合性能問題將是下一個優化VRP需要考慮的問題。此外，粒子群算法在混合過程中，慣性權重、混合算法的選取也是一個值得研究的方向?；旌纤惴ú僮鬟^程中，以哪個算法為主導，何時應用所需算法也是亟需解決的問題，如粒子群混合遺傳算法中，并行式混合與串行式混合對模型的求解有很大不同。推而廣之，在與其他算法混合時，需要考慮到混合的時機選取，混合方法選取等問題。隨著VRP復雜程度增加，多種啟發式算法的混合使用已成為趨勢，多種混合算法所衍生出來的問題也會越來越多，需要更多的實驗來佐證算法的可行性。

4 結語

本文通過對近年來研究車輛路徑問題的文章進行分析，總結出多種目前正在研究的模型。同時對求解車輛路徑問題的2種解法進行對比，得出啟發式算法是目前較為合理解法，并引出一系列常見的啟發式算法。在此基礎上以混合粒子群算法為代表，詳細分析總結了混合粒子群在車輛路徑問題上的應用。最后指出車輛路徑問題以及混合粒子群算法的研究問題及發展趨勢，表明車輛路徑問題及混合粒子群算法研究的必要性以及具有良好的應用前景。

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem [J]. Management Science, 1959,6(1):80-91.

[2] Yan Liying, Grifoll Manel, Zheng Pengjun. Model and algorithm of two-stage distribution location routing with hard time window for city cold-chain logistics[J]. Applied Sciences, 2020, 10(7):2564.

[3] 李博威,戶佐安,賈葉子,等.帶軟時間窗的同時取送貨車輛路徑問題研究[J].工業工程,2020,23(5):75-81.

[4] 丁建立,孫彩蘋,李永華,等.基于混合時間窗的航空貨運車輛動態調度模型[J].計算機與數字工程,2016,44(5):838-842.

[5] Mauricio Granada-Echeverri, Luis Carlos Cubides, Jésus Orlando Bustamante. The electric vehicle routing problem with backuals[J]. International Journal of Industrial Enginee- ring Computations, 2020, 11(1):131-152.

[6] 劉濤. 基于改進遺傳算法的H公司VRPB優化研究[D].邯鄲:河北工程大學,2013.

[7] Javier Belloso, Angel A Juan, Enoc Martinez, et al. A biased‐randomized metaheuristic for the vehicle routing problem with clustered and mixed backhauls[J]. Networks, 2017, 69(3):241- 255.

[8] Andreas Bortfeldt, Thomas Hahn, Dirk M?nnel, et al. Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints[J]. Eur J Oper Res,2015, 243(1):82-96.

[9] Henriette Koch, Maximilian Schl?gell, Andreas Bortfeldt. A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls[J]. Journal of Scheduling, 2020, 23(9):71-93.

[10] 李琳,孟嬌,陳瑩.電子商務環境下基于預售模式的混合帶回程取貨車輛路徑問題[J].沈陽航空航天大學學報, 2020,37(4):90-96.

[11] Olcay Polat. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups[J]. Computers and Operations Research, 2017,85: 71-86.

[12] Julian Hof, Michael Schneider. An adaptive large neighborhood search with path relinking for a class of vehicle‐routing problems with simultaneous pickup and delivery[J]. Networks, 2019,74(3): 207-250.

[13] Richard P Hornstra, Allyson Silva, Kees Jan Roodbergen, et al. The vehicle routing problem with simultaneous pickup and delivery and handling costs[J]. Computers and Operations Research, 2020,115.

[14] 馬艷芳,閆芳,康凱,等.不確定同時取送貨車輛路徑問題及粒子群算法研究[J].運籌與管理,2018,27(12):73-83.

[15] Anirudh Subramanyam, Panagiotis P Repoussis, Chrysanthos E Gounaris. Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty[J]. INFORMS J Computing, 2020,32(3):72-80.

[16] Majid Salavati-Khoshghalb, Michel Gendreau, Ola Jabali, et al. A rule-based recourse for the vehicle routing problem with stochastic demands[J]. Transportation Science, 2019,53(5):26-31.

[17] 張永鵬. 帶隨機需求的綠色物流多目標優化問題研究[D]. 北京:中國地質大學,2020.

[18] Magdalene Marinaki, Yannis Marinakis. A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands[J]. Expert Systems With Applications, 2016,46: 145-163.

[19] 陸琳,蔡紹洪.一類隨機顧客車輛路徑問題及其算法[J].南京航空航天大學學報,2010,42(4):521-525.

[20] Rajeev Goel, Raman Maini, Sandhya Rani Bansal. Corrigendum to “vehicle routing problem with time windows having stochastic customers demands and stochastic service times: modelling and solution” [J]. Journal of Computational Science,2019,35: 111.

[21] 周振紅,黃深澤.隨機需求下考慮顧客策略行為的預售和退貨策略[J].系統管理學報,2019,28(2):277-284.

[22] Hossein Hashemi Doulabi, Gilles Pesant, Louis-Martin Rousseau. Vehicle routing problems with synchronized visits and stochastic travel and service times: applications in healthcare[J]. Transportation Science, 2020,54(4):30-40.

[23] Li Xiangyong, Tian Peng, Leung Stephen C H. Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm[J]. International Journal of Production Economics, 2010,125(1): 137-145.

[24] Raafat Elshaer, Hadeer Awad. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants[J]. Computers & Industrial Engineering, 2020,140.

[25] FITRIANA R, MOENGIN P, KUSUMANINGRUM U. Improvement route for distribution solutions MDVRP (multi depot vehicle routing problem) using genetic algorithm[J]. IOP Conference Series: Materials Science and Engineering, 2019, 528(1) 70-81.

[26] Chen Binhui, Qu Rong, Bai Ruibin, et al. A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes[J]. RAIRO - Operations Research, 2020,54(5): 1467-1494.

[27] LATIFFIANTI E, SISWANTO N, FIRMANDANI R A. Split delivery vehicle routing problem with time windows: a case study[J]. IOP Conference Series: Materials Science and Engineering, 2018,337(1):012042.

[28] Valeria Soto-Mendoza, Irma García-Calvillo, Efraín Ruiz-y-Ruiz, et al. A hybrid grasshopper optimization algorithm applied to the open vehicle routing problem[J]. Algorithms, 2020,13(4) :55-62.

[29] Maha Gmira, Michel Gendreau, Andrea Lodi, et al. Tabu search for the time-dependent vehicle routing problem with time windows on a road network[J]. European Journal of Operational Research, 2021,288(1): 129-140.

[30] 胡蓉,李洋,錢斌,等.結合聚類分解的增強蟻群算法求解復雜綠色車輛路徑問題[J].自動化學報,DOI:10.16383/j.aas. c190872,2020:1-16.

[31] 周鮮成,王莉,周開軍,等.動態車輛路徑問題的研究進展及發展趨勢[J].控制與決策,2019,34(3):449-458.

[32] 李俊. 帶有裝載約束的車輛路徑優化問題研究與應用[D].西安:西安建筑科技大學,2016.

[33] Feng Liang, Zhou Lei, Gupta Abhishek, et al. Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking[J]. IEEE transactions on cybernetics, 2019.

[34] Diego Cattaruzza, Nabil Absi, Dominique Feillet, et al. A memetic algorithm for the multi trip vehicle routing problem[J]. European Journal of Operational Research, 2014, 236(3): 833-848.

[35] Sophie N Parragh, Jean-Fran?ois Cordeau. Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows[J]. Computers and Operations Research, 2017,83: 28-44.

[36] Lu Chen, Yang Liu, André Langevin. A multi-compartment vehicle routing problem in cold-chain distribution[J]. Computers and Operations Research, 2019,111: 58-66.

[37] Morteza Kiani, Hany Seidgar, Iraj Mahdavi. Scheduling multi-skilled manpower with considering teams replacement and site-dependent vehicles routing[J]. Int. J. of Mathematics in Operational Research, 2017,10(1): 49-68.

[38] EBERHART R C. Comparing inertia weights and constriction factors in particle swarm optimization[C]// Proceedings of the 2000 IEEE Congress on Evolutionary Computation, La Jolla, CA. IEEE, 2002.

[39] 周馳,董寶力.基于改進混合粒子群算法的窄巷道倉儲三維揀選路徑規劃[J].浙江理工大學學報(自然科學版),2020,43(6):823-830.

[40] KENNEDY J. Bare bones particle swarms[C]// Swarm Intelligence Symposium. IEEE, 2003.

[41] 梁旭,劉才慧.基于混合粒子群算法的在線檢測路徑規劃[J].國外電子測量技術,2015,34(12):30-34.

[42] ANGELINE P J. Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences[J]. Springer, Berlin, Heidelberg, 1998,27:50-54.

[43] MENG A B, LI Z, YIN H, et al. Accelerating particle swarm optimization using crisscross search[J]. Information Sciences, 2016,329: 52-72.

[44] 葛宏義,甄彤,車毅,等.糧食物流車輛路徑問題的混合粒子群算法[J].計算機應用與軟件,2011,28(7):69-71,151.

[45] 楚學偉.混合粒子群算法在動態車間調度中的應用[J].無線互聯科技,2020,17(7):155-157,165.

[46] 陸琳,譚清美.一類隨機需求VRP的混合粒子群算法研究[J].系統工程與電子技術,2006(2):244-247.

[47] The Jin Ai, Voratas Kachitvichyanukul. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem[J]. Computers & Industrial Engineering, 2009, 56(1):380-387.

[48] MIRHASSANI S A, ABOLGHASEMI N. A particle swarm optimization algorithm for open vehicle routing problem[J]. Expert Systems with Applications, 2011,38(9):11547-11551.

[49] Yannis Marinakis, Georgia-Roumbini Iordanidou, Magdalene Marinaki. Particle swarm optimization for the vehicle routing problem with stochastic demands[J]. Applied Soft Computing Journal, 2013,13(4):1693-1704.

[50] Du Jiaoman, Li Xiang, Yu Lean, et al. Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming[J]. Information Sciences, 2017, 399:201-218.

[51] 李和洋.考慮多車型的多周期庫存路徑優化研究[D].大連:大連海事大學,2020.

A Survey of Hybrid Particle Swarm Optimization Algorithm for Solving Vehicle Routing Problem and Its Variants

Yang Guanfu Cai Yanguang

(School of Automation, Guangdong University of Technology, Guangzhou 510006, China)

Through the analysis and summary of vehicle path problems, the paper concludes that heuristic algorithm has advantages in solving vehicle path problems. And it also describes the application of hybrid particle swarm optimization in different VRP deformation problems in detail. Finally, the shortcomings and trends of vehicle routing and hybrid particle swarm optimization are pointed out. It is emphasized that the problem and algorithm have good expansibility and have a broad application prospect in logistics field.

vehicle routing; heuristic algorithm; hybrid particle swarm optimization

TP18; TP311.13

A

1674-2605(2021)02-0002-07

10.3969/j.issn.1674-2605.2021.02.002

楊觀富，男，1996年生，碩士研究生，主要研究方向：控制與優化。E-mail:13710255965@163.com

蔡延光，男，1963年生，博士，教授，主要研究方向：網絡控制與優化、組合優化、智能交通系統。E-mail: caiyg99@163.com