摘 要：隨著綠色物流的興起，低碳車輛路徑問題（Low-carbon Vehicle Routing Problem， LCVRP）成為了物流領域研究的焦點，對LCVRP最新研究文獻及進展進行綜述。首先，對影響車輛油耗和碳排放的主要因素進行分析歸納，總結常用的油耗和碳排放測度模型；其次，對求解LCVRP及其變體問題的精確算法、經典啟發(fā)式算法、元啟發(fā)式算法進行較為詳細的綜述；最后，針對LCVRP現(xiàn)有的研究不足指出未來待發(fā)展方向。

關鍵詞：低碳車輛路徑問題；油耗；啟發(fā)式算法

中圖分類號：U116.2 文獻標志碼：A

DOI：10.13714/j.cnki.1002-3100.2024.19.020

Abstract： With the rise of green logistics， Low-carbon Vehicle Routing Problem（LCVRP）has become the focus of research in the field of logistics. This paper is intended to review the latest research literature and progress of LCVRP. Firstly， the main factors affecting vehicle fuel consumption and carbon emissions are analyzed， and the commonly used measurement models of fuel consumption and carbon emissions are summarized. Secondly， the precise algorithms， classical heuristic algorithms and meta-heuristic algorithms for solving LCVRP and its variants are reviewed in detail. Finally， the future development direction of LCVRP is pointed out in view of the lack of existing research.

Key words： low-carbon vehicle routing problem; fuel consumption; heuristic algorithm

0 引 言

隨著環(huán)保理念的不斷普及以及對經濟高質量發(fā)展的轉型需求，低能耗、低排放、低污染的低碳經濟發(fā)展理念被提出，得到了學術界和政府部門的廣泛關注。物流業(yè)是推動國民經濟發(fā)展的基礎性、支柱性產業(yè)，是低碳經濟的重要組成部分，而在物流業(yè)減排行動中，由于交通運輸業(yè)以公路貨車運輸為主的特性，能耗和碳排放量更大，物流運輸成本更高，從而成為了國家環(huán)保攻堅、節(jié)能減排的重點改進領域。因此，研究低碳化物流運作具有一定現(xiàn)實意義和理論價值。

車輛路徑問題（Vehicle Routing Problem， VRP）是交通運輸優(yōu)化和運籌學領域中的重點研究方向之一，是物流配送領域中的熱點問題。最早由Dantzing et al.[1]提出，其主要研究內容為：存在一個配送中心與若干個客戶點，已知其地理位置和客戶需求量，在不違反約束的條件下規(guī)劃恰當?shù)姆枕樞蛞赃_到配送成本最小的目的。隨著應用場景的不斷拓寬，經典的VRP已不能應對復雜多變情形的要求，出現(xiàn)了諸多VRP變體類型，如帶時間窗的VRP（VRP with Time Windows， VRPTW）、低碳VRP（Low-carbon VRP， LCVRP）、同時取送貨的VRP（VRP with Simultaneous Pickup and Delivery， VRPPD）等，不同的約束條件和影響要素組合成了不同的變體問題。LCVRP在經典的VRP上加入了碳排放約束，在考慮經濟效益的前提下，旨在科學的規(guī)劃行車路線以降低配送過程中的燃油消耗和碳排放，由于影響車輛碳排放的因素眾多且因素之間參差交錯，LCVRP的模型更為復雜，求解難度更大。為順應物流綠色低碳發(fā)展要求，學者們對LCVRP展開了一系列研究，具體集中在兩個方面：一是對影響車輛碳排放的因素進行研究；二是碳排放計量方法。本文通過對國內外相關文獻進行梳理和總結，先對LCVRP的研究進展進行綜述，再對求解此類問題最具代表性的算法進行分析和討論，最后結合現(xiàn)有文獻，展望LCVRP未來的研究趨勢。

1 LCVRP研究進展

1.1 油耗和碳排放影響因素

車輛作為分布最廣的移動碳排放源，產生的碳排放量達交通運輸排放總量的80%以上，重型卡車更是污染重災區(qū)。如何確定車輛油耗和碳排放的關鍵影響因素以便有效規(guī)劃配送路徑成為了LCVRP關注的焦點。學者們對影響燃油消耗的因素進行了一系列研究，大致可以分為與外部環(huán)境有關的天氣、交通狀況，涉及人為主觀因素的駕駛員經驗以及車輛自身參數(shù)等幾類[2-3]。通過總結整理相關文獻，本文以油耗影響相關度高的行駛速度為依據，將其分為以下五類：

（1）車輛參數(shù)。主要包括與車輛外觀有關的車輛大小、重量、類型與形狀，與車輛性能有關的發(fā)動機尺寸、燃油類型等。尤其是車型與負載在實際配送活動中容易測度與統(tǒng)一，因而有較多學者研究不同車輛類型[4]，如輕型、中型、重型車輛，以及車輛在不同節(jié)點完成配送后貨物卸載情況對油耗和碳排放的影響[5]。

（2）交通狀況。道路交通流量、行駛速度和加速度對燃油消耗和碳排放有直接影響。盧笙等[6]研究車輛平均速度與實際道路油耗的關系，發(fā)現(xiàn)油耗在30km/h以下時，會隨速度降低而顯著上升。但隨著當代城市交通擁堵愈加嚴重，車輛行駛速度普遍降低，偏離最佳行駛速度又會導致油耗和碳排放增加[7]，因而考慮交通擁堵的時變VRP研究[8]更能滿足實際需要，設計高效的擁堵規(guī)避方案有助于物流碳減排。

（3）環(huán)境因素。環(huán)境對碳排放的影響主要表現(xiàn)在道路坡度、路面類型以及溫度、風阻和海拔等自然條件方面。隨著道路坡度的升高，車輛為克服阻力需要做額外功，油耗和碳排放也隨之升高。尤其是碳排放因子對坡度更為敏感，影響排序為道路坡度>車輛類型>道路類型[9]。而在城市物流配送中，隨著道路等級越高，道路承載的交通量變大，相應的碳排放量也越高。同時，海拔和溫度的升高也在一定程度上增加了高油耗的概率[10]。

（4）駕駛員行駛習慣。駕駛員技術水平、行車習慣等顯著影響油耗和碳排放，經驗豐富且行車激進的駕駛員所消耗的燃油量通常更高。男性駕駛員碳排放量也往往高于女性駕駛員[11]。Loman et al.[12]對三種不同的駕駛風格進行測試，速度最高的動態(tài)駕駛風格往往伴隨著高油耗。

（5）運營管理。運營管理主要體現(xiàn)在車輛組合、調度等管理層面。現(xiàn)代居民需求多樣，配送商品種類更為繁雜，單車型配送難以滿足實際需要，因此考慮多車型組合的異構VRP十分必要。Cheng et al.[13]測試了同質車隊和異構車隊對碳排放的影響，表明使用異構車隊時的碳排放成本更少。邱玉琢等[14]進一步討論了租賃車隊和自有車隊的經濟性，證實考慮外部車隊對降低碳排放成本有效。

1.2 油耗和碳排放測度模型

影響車輛碳排放的因素眾多，如何量化排放因子以建立適用不同場景的油耗和碳排放模型是LCVRP研究的基礎。目前應用最廣泛的油耗和碳排放模型可分為三類：（1）因素模型，早期研究對油耗的估算所考慮的影響因素較為簡單，通常將車輛油耗簡化成與載重、行駛距離等有關的線性函數(shù)。Xiao et al.[15]提出了基于載重的油耗模型（Load Based Fuel Consumption Model， LFCM）。Mohammadi et al.[16]在對碳排放和油耗的刻畫中，僅考慮了距離因素。吳麗榮等[17]構建了基于速度和負載的油耗測度模型。由于LFCM模型易于量化，因此學者們多用來簡單測算油耗[18-19]。（2）宏觀模型，主要使用參數(shù)平均值或構造回歸函數(shù)來估算整個區(qū)域的碳排放。在VRP領域應用較多的有Hickman et al.[20]提出的考慮車輛平均速度、載重和道路坡度的碳排放測度模型（Methodology for Calculating Transportation Emissions and Energy Consumption， MEET）和Kouridis et al.[21]提出的考慮速度和行駛距離的碳排放計量模型（Computer Programme to Calculate Emissions from Road Transportation，COPERT）。周果等[22]分別采用了LFCM模型、MEET模型估算油耗和碳排放。（3）微觀模型，以更全面的參數(shù)，如加速度、發(fā)動機效率、動態(tài)速度等來估算油耗。Bowyer et al.[23]提出了考慮車輛行駛牽引力、速度和加速度等多種微觀因素的瞬時油耗模型（Instantaneous Fuel Consumption Model， IFCM），用于近似計算車輛每秒的油耗量。Barth et al.[24]在IFCM模型基礎上，加入了發(fā)動機功率和轉速等相關參數(shù)，提出了綜合排放模型（Comprehensive Modal Emission Model， CMEM）。微觀模型考慮因素更多，對碳排放預測更為精確，因而在物流配送領域應用更多[25-28]。上述三類油耗模型在LCVRP領域均得到了一定的應用，相關研究成果歸納如表1所示。

2 LCVRP求解算法

LCVRP屬于NP-hard問題，求解難度會隨著模型約束增多而增大，難以在短時間內求得最優(yōu)解或近似最優(yōu)解。目前，國內外學者求解該類多復雜約束VRP[22]的算法主要有精確算法、經典啟發(fā)式算法和元啟發(fā)式算法。

2.1 精確算法

精確算法是指在組合優(yōu)化問題中能夠求得絕對最優(yōu)解的傳統(tǒng)算法，其計算復雜度會隨問題規(guī)模的增大呈指數(shù)增長，因而只適應于小規(guī)模算例的求解。用于求解LCVRP的精確算法主要有：分支界定法[8]、動態(tài)規(guī)劃法[29]、割平面法[30]和整數(shù)線性規(guī)劃法[31]。精確算法通常用來改進解的上界和下界，與啟發(fā)式算法結合進行優(yōu)化求解。

2.2 經典啟發(fā)式算法

啟發(fā)式算法是基于直觀或者經驗構造的算法，在滿足相應約束下給出問題的可行解，包括經典啟發(fā)式算法和元啟發(fā)式算法。經典啟發(fā)式算法通過逐步構造路徑來形成可行解，通常被用來求解大規(guī)模的VRP以及為元啟發(fā)式算法提供較高質量初始解[31-32]。穆東等[31]采用了前向插入算法構造初始解。Niu et al.[27]和Pu et al.[32]在求解LCVRP時，分別提出使用最近鄰法、貪心算法來求得高質量的初始解。

2.3 元啟發(fā)式算法

元啟發(fā)式算法通過對鄰域解進行不斷地擾動和變換操作，盡可能使得算法搜尋到整個搜索空間，從而無限接近最優(yōu)解。其求解性能優(yōu)于經典啟發(fā)式算法，常被用來求解帶復雜約束的LCVRP及其變體問題[24]。在實際的應用中，單一的元啟發(fā)式算法有其局限性，而混合多種局部搜索算子[23]、算法策略優(yōu)化[33]等的改進元啟發(fā)式算法適應性更強，求解表現(xiàn)更優(yōu)。

為進一步提高算法的搜索性能和收斂速度，學者們對多種啟發(fā)式算法進行組合優(yōu)化使用。常見的算法組合策略有：（1）兩種或多種呈并行關系的啟發(fā)式算法混合，如兩階段混合啟發(fā)式算法[34]，第一階段使用啟發(fā)式算法構造初始解或進行全局遍歷搜索，第二階段使用其他算法進行局部搜索，平衡算法的全局搜索和局部搜索能力。（2）兩種或多種啟發(fā)式算法完全混合，一般以某種啟發(fā)式算法為主算法，結合其他啟發(fā)式算法的個別搜索策略以提高算法的尋優(yōu)能力[28]?；旌蠁l(fā)式算法在求解復雜LCVRP上具有一定的優(yōu)越性如圖1所示。

3 總結與展望

LCVRP是在碳排放的約束下涉及行駛速度、環(huán)境、交通狀況等復雜路徑規(guī)劃問題，以整體運輸碳減排為目標，優(yōu)化配送路線從而實現(xiàn)總物流成本的降低，具有廣闊的應用前景與研究價值。近幾年針對LCVRP及其求解研究眾多，取得了豐富的研究成果，但仍存在急待解決問題：（1）現(xiàn)有的油耗和碳排放測度模型較少考慮會駕駛員主觀因素、實時交通狀態(tài)等對碳排放的影響，適用范圍有一定的局限。（2）碳排放量的轉換常用油耗乘以某個固定轉換系數(shù)，但實際中不同類型、大小的車輛油耗受多重因素影響表現(xiàn)出較大差異，進而碳排放量的計算也出現(xiàn)偏差。因此，在碳排放測度中考慮車輛參數(shù)、實時速度、突發(fā)狀況等動態(tài)影響因子十分必要。（3）新能源車因其能耗小、無污染在物流配送領域應用廣泛，但由于電池容量、充電限制，導致搭載貨物、配送范圍局限大，因此與燃油車輛共同組合配送研究成為了未來LCVRP的研究方向之一。

參考文獻：

[1] DANTZIG G B， RAMSER J H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] ARDEKANI S， HAUER E， JAMEI B. Traffic impact models[J]. Traffic Flow Theory， 1996，7（1）：1-26.

[3] BIGAZZI A Y， BERTINI R L. Adding green performance metrics to a transportation data archive[J]. Transportation Research Record， 2009，2121（1）：30-40.

[4] DEMIR E， BEKTAS T， LAPORTE G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research Part D： Transport and Environment， 2011，16（5）：347-357.

[5] DA COSTA P R O， MAUCERI S， CARROLL P， et al. A genetic algorithm for a green vehicle routing problem[J]. Electronic Notes in Discrete Mathematics， 2018，64：65-74.

[6] 盧笙，吳燁，張少君，等. 基于車載診斷系統(tǒng)的輕型乘用車實際道路油耗特征分析[J]. 環(huán)境科學學報，2018，38（5）：1783-1790.

[7] 李進，張江華. 基于碳排放與速度優(yōu)化的帶時間窗車輛路徑問題[J]. 系統(tǒng)工程理論與實踐，2014，34（12）：3063-3072.

[8] LUO H， DRIDI M， GRUNDER O. A branch-price-and-cut algorithm for a time-dependent green vehicle routing problem with the consideration of traffic congestion[J]. Computers & Industrial Engineering， 2023，177：109093.

[9] 周濤，李毅軍，孫琴梅，等. 大數(shù)據驅動下的山地城市道路條件對車輛碳排放影響研究[J]. 交通運輸系統(tǒng)工程與信息，2023（5）：172-183.

[10] GONG J， SHANG J， LI L， et al. A comparative study on fuel consumption prediction methods of heavy-duty diesel trucks considering 21 influencing factors[J]. Energies， 2021，14（23）：8106.

[11] KHADER A I， MARTIN R S. On-the-road testing of the effects of driver's experience， gender， speed， and road grade on car emissions[J]. Journal of the Air & Waste Management Association， 2019，69（10）：1182-1194.

[12] LOMAN M， ?ARKAN B， SKRUCANY T. Comparison of fuel consumption of a passenger car depending on the driving style of the driver[J]. Transportation Research Procedia， 2021，55：458-465.

[13] CHENG R， GEN M， TOZAWA T. Vehicle routing problem with fuzzy due-time using genetic algorithms[J]. Journal of Japan Society for Fuzzy Theory and Systems， 1995，7（5）：1050-1061.

[14] 邱玉琢，張磊. 碳排放規(guī)制下生鮮農產品配送車輛路徑優(yōu)化問題[J]. 南京財經大學學報，2021（1）：68-78.

[15] XIAO Y， ZHAO Q， KAKU I， et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J]. Computers & Operations Research， 2012，39（7）：1419-1431.

[16] MOHAMMADI M， RAZMI J， TAVAKKOLI-MOGHADDAM R. Multi-objective invasive weed optimization for stochastic green hub location routing problem with simultaneous pick-ups and deliveries[J]. Economic Computation & Economic Cybernetics Studies & Research， 2013，47（3）：247-266.

[17] 吳麗榮，胡祥培，饒衛(wèi)振. 考慮燃料消耗率的車輛路徑問題模型與求解[J]. 系統(tǒng)工程學報，2013，28（6）：804-811.

[18] 張金良，李超. 碳排放影響下的動態(tài)配送車輛路徑優(yōu)化研究[J]. 中國管理科學，2022，30（9）：184-194.

[19] 丁澍，邱玉琢. 考慮低碳的多目標冷鏈混合車隊路徑規(guī)劃研究[J/OL]. 計算機工程與應用：1-13[2023-09-13]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20230517.1459.013.html.

[20] HICKMAN J， HASSEL D， JOUMARD R， et al. Methodology for calculating transport emissions and energy consumption[R]. Brussels， Belgium， 1999.

[21] KOURIDIS C， GKATZOFLIbq/mcfE7KQzKUXgcIJPBBA==AS D， KIOUTSIOUKIS I， et al. Uncertainty estimates and guidance for road transport emission calculations[R]. European Commission Joint Research Centre Institute for Environment and Sustainability， 2010.

[22] 周果，季彬，方曉平. 多對多越庫配送綠色車輛路徑問題及算法研究[J]. 鐵道科學與工程學報，2022，19（8）：2202-2210.

[23] BOWYER D P， BIGGS D C， AK?ELIK R. Guide to fuel consumption analyses for urban traffic management[R]. Australian Road Research Board Transport Research， 1985.

[24] BARTH M， BORIBOONSOMSIN K. Real-world carbon dioxide impacts of traffic congestion[J]. Transportation Research Record， 2008，2058（1）：163-171.

[25] BANDEIRA J， ALMEIDA T G， KHATTAK A J， et al. Generating emissions information for route selection： Experimental monitoring and routes characterization[J]. Journal of Intelligent Transportation Systems， 2013，17（1）：3-17.

[26] 唐金環(huán). 基于減排驅動的選址-路徑-庫存集成問題模型與求解研究[D]. 沈陽：東北大學，2017.

[27] NIU Y， YANG Z， CHEN P， et al. Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost[J]. Journal of Cleaner Production， 2018，171：962-971.

[28] 周鮮成，蔣濤營，賀彩虹，等. 冷鏈物流配送的綠色車輛路徑模型及其求解算法[J]. 中國管理科學，2023（12）：203-214.

[29] XIAO Y， KONAK A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. Journal of Cleaner Production， 2017，167（20）：1450-1463.

[30] KO? ?， KARAOGLAN I. The green vehicle routing problem： A heuristic based exact solution approach[J]. Applied Soft Computing， 2016，39：154-164.

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

[32] PU X， LU X， HAN G. An improved optimization algorithm for a multi-depot vehicle routing problem considering carbon emissions[J]. Environmental Science and Pollution Research， 2022，29（36）：54940-54955.

[33] 唐慧玲，唐恒書，朱興亮. 基于改進蟻群算法的低碳車輛路徑問題研究[J]. 中國管理科學，2021，29（7）：118-127.

[34] WANG X， LI X. Carbon reduction in the location routing problem with heterogeneous fleet， simultaneous pickup-delivery and time windows[J]. Procedia Computer Science， 2017，112：1131-1140.