低碳車輛路徑問題及求解算法研究綜述

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

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

中圖分類號：U116.2 文獻(xiàn)標(biāo)志碼：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)保理念的不斷普及以及對經(jīng)濟(jì)高質(zhì)量發(fā)展的轉(zhuǎn)型需求，低能耗、低排放、低污染的低碳經(jīng)濟(jì)發(fā)展理念被提出，得到了學(xué)術(shù)界和政府部門的廣泛關(guān)注。物流業(yè)是推動國民經(jīng)濟(jì)發(fā)展的基礎(chǔ)性、支柱性產(chǎn)業(yè)，是低碳經(jīng)濟(jì)的重要組成部分，而在物流業(yè)減排行動中，由于交通運(yùn)輸業(yè)以公路貨車運(yùn)輸為主的特性，能耗和碳排放量更大，物流運(yùn)輸成本更高，從而成為了國家環(huán)保攻堅、節(jié)能減排的重點改進(jìn)領(lǐng)域。因此，研究低碳化物流運(yùn)作具有一定現(xiàn)實意義和理論價值。

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

1 LCVRP研究進(jìn)展

1.1 油耗和碳排放影響因素

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

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

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

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

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

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

1.2 油耗和碳排放測度模型

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

2 LCVRP求解算法

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

2.1 精確算法

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

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

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

2.3 元啟發(fā)式算法

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

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

3 總結(jié)與展望

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

參考文獻(xiàn)：

[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)境科學(xué)學(xué)報，2018，38（5）：1783-1790.

[7] 李進(jìn)，張江華. 基于碳排放與速度優(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ù)驅(qū)動下的山地城市道路條件對車輛碳排放影響研究[J]. 交通運(yùn)輸系統(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ī)制下生鮮農(nóng)產(chǎn)品配送車輛路徑優(yōu)化問題[J]. 南京財經(jīng)大學(xué)學(xué)報，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)工程學(xué)報，2013，28（6）：804-811.

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

[19] 丁澍，邱玉琢. 考慮低碳的多目標(biāo)冷鏈混合車隊路徑規(guī)劃研究[J/OL]. 計算機(jī)工程與應(yīng)用：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]. 鐵道科學(xué)與工程學(xué)報，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). 基于減排驅(qū)動的選址-路徑-庫存集成問題模型與求解研究[D]. 沈陽：東北大學(xué)，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]. 中國管理科學(xué)，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]. 計算機(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ìn)蟻群算法的低碳車輛路徑問題研究[J]. 中國管理科學(xué)，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.