基于多目標迭代局部優(yōu)化算法的成本

韋鵬飛 張建軍

文章編號：1005-9679（2022）03-0091-08

摘要：電動車憑借低碳、環(huán)保的優(yōu)勢越來越多地被企業(yè)接受用于物流場景，但續(xù)航里程和充電限制仍制約著電動車的應(yīng)用。以往文獻極少在電動車背景下同時考慮運行成本和路徑平衡。因此，將總運營成本和路徑平衡兩個目標納入問題，構(gòu)建了數(shù)學模型，結(jié)合迭代局部搜索算法和變領(lǐng)域搜索算法的特性，采用五種領(lǐng)域算子，設(shè)計了多目標優(yōu)化算法求解問題。研究構(gòu)造了九組算例，對比了提出的算法與VNS算法、ILS算法的表現(xiàn)。數(shù)據(jù)實驗驗證了算法的可行性、有效性和穩(wěn)定性。

關(guān)鍵詞：電動車;路徑規(guī)劃;多目標優(yōu)化;迭代局部搜索

中圖分類號：F272

文獻標志碼：A

TheElectricVehicleRoutingProblemConsideringCostandRouteBalanceUsingaMulti-ObjectiveLteratedLocalSearchAlgorithm

WEIPengfeiZHANGJianjun

（SchoolofEconomicsandManagement，TongjiUniversity，Shanghai200092，China）

Abstract：Electricvehicles（EVs）areincreasinglyadoptedbycorporationsforlogisticsscenariosduetobeinglow-carbonandenvironmentallyfriendly，butrangeandcharginglimitationsstillconstraintheapplicationofelectricvehicles.PreviousliteraturerarelyconsidersbothoperatingcostandroutebalanceinthecontextofEVs.Therefore，thestudyconsiderstotaloperatingcostandroutebalanceintotheelectricvehiclesroutingproblemsimultaneously，anddesignsamulti-objectiveoptimizationalgorithmbycombiningiteratedlocalsearchalgorithmsandvariableneighborhoodsearchalgorithmsandusingfiveoperators.Thestudyprovidesninesetsofarithmeticcasestocomparetheperformanceoftheproposedalgorithmwiththevariableneighborhoodsearchalgorithmandtheiteratedlocalsearchalgorithm.Computationalexperimentsverifythefeasibility，effectivenessandstabilityoftheproposedalgorithm.

Keywords：electricvehicle;routingproblem;multi-objectiveoptimization;iteratedlocalsearch

目前世界氣候和能源問題嚴峻，國際社會一致尋求變革。我國于2020年9月明確提出2030年碳達峰與2060年碳中和的“雙碳”目標，帶動了新能源相關(guān)行業(yè)的發(fā)展。國際汽車市場上，奔馳、大眾、通用等國際知名車企紛紛提出了全面電氣化的新戰(zhàn)略，新能源汽車逐漸取代傳統(tǒng)燃油車已是未來趨勢。

電商的進一步發(fā)展也帶動物流業(yè)規(guī)模迅速擴大?！?021年12月中國快遞發(fā)展指數(shù)報告》顯示，我國年快遞業(yè)務(wù)量突破1000億件。在此背景下，企業(yè)向綠色物流轉(zhuǎn)變對于成本效益和環(huán)境保護都有積極意義。

與燃油車相比，電動車有著不可忽視的特性，因此在對電動車進行路徑規(guī)劃時，必須充分考慮其特點。電動車在節(jié)能、環(huán)保等方面都較燃油車有顯著優(yōu)勢，但在續(xù)航、充電速率方面有明顯的短板。另外，電動車的配套公共設(shè)施還遠不如燃油車完善，這也制約了電動車的推廣。在這樣的限制下，采用電動車的企業(yè)需要開發(fā)高效的車隊管理方案，在充分考慮電動車自身限制的情況下擴大經(jīng)濟效益。

面對這個困難，眾多學者對電動車路徑規(guī)劃問題（ElectricVehicleRoutingProblem，EVRP）進行了探索。EVRP的核心是在考慮電動車的里程、充電和載貨量限制的情況下，合理配置路徑，以最低成本滿足客戶需求。在此基礎(chǔ)上，實際問題還需要考慮時間窗、可變能耗、充電站容量限制等因素。Conrad和Figliozzi首先介紹了途中充電的路徑規(guī)劃問題。Erdogan和Miller-Hooks第一次提出了充電站的路徑規(guī)劃問題。Schneider等介紹了一種帶時間窗的電動車路徑規(guī)劃。

然而，目前極少有文獻考慮里程限制和客戶時間窗，并將成本和路徑平衡作為目標。在電動車加速進入物流場景，物流企業(yè)比拼服務(wù)質(zhì)量，勞動者權(quán)益越來越受重視的當下，同時將電動車特性、客戶時間窗、路徑平衡納入考慮是非常必要的。因此，本文結(jié)合這些因素，提出了帶時間窗的多目標電動車路徑規(guī)劃問題，設(shè)計了一種基于ILS算法、結(jié)合VNS算法領(lǐng)域搜索框架的多目標優(yōu)化算法。

1文獻綜述

為了減少傳統(tǒng)燃油車的負面影響，采用電動車作為城市物流的主要載具是一個有效的措施。由于電動車存在續(xù)航里程短和充電時間長等不可忽視的短板，許多學者將其特點納入考慮，針對電動車路徑規(guī)劃問題展開了研究和探索。

電動車路徑規(guī)劃問題脫胎于路徑規(guī)劃問題（VehicleRoutingProblem，VRP）。Conrad和Figliozzi介紹了一種考慮途中充電的路徑規(guī)劃問題（RechargingVehicleRoutingProblem，RVRP），問題假設(shè)客戶處可提供充電服務(wù)，車輛可在客戶處服務(wù)的過程中充電。Erdogˇan和Miller-Hooks提出了綠色路徑規(guī)劃問題（GreenVehicleRoutingProblem，GVRP）的概念，并且第一次提出了考慮充電站的路徑規(guī)劃問題，但沒有考慮時間窗和載貨量限制。Schneider等介紹了一種帶時間窗和充電站的電動車路徑規(guī)劃問題（ElectricVehicleRoutingProblemwithTimeWindowsandRechargingStations，EVRPTW），問題的主要目標是用最少的車輛和最短的總行駛里程滿足需求。Hiermann等將EVRPTW進一步拓展，考慮了由在載貨量、電池容量和采購價格方面有區(qū)別的不同車型組成的混合車隊。揭婉晨等也研究了多車型的電動車路徑規(guī)劃問題，并提出了一種改進的分支定價算法。

為了使模型更貼近現(xiàn)實，一些研究人員考慮了更多細致的現(xiàn)實情況。為了更快地完成服務(wù)，電動車在有些情況下并不需要進行完全充電，只要將電量補充至所需值即可。Keskin和Catay構(gòu)建了允許部分充電的EVRPTW模型并用實驗證明部分充電可以減少交通成本、優(yōu)化路徑?jīng)Q策。葛顯龍和竹自強研究了帶軟時間窗的電動車輛路徑優(yōu)化問題。Montoya等考慮了電動車充電速率的現(xiàn)實情況，構(gòu)建了帶非線性充電函數(shù)的EVRP模型并提出了一種混合元啟發(fā)算法來求解。唐佩佩等考慮生鮮產(chǎn)品的特點，研究了生鮮同城配送的路徑問題。Schiffer和Walther將充電站的位置也設(shè)為變量，同時研究了充電站的選址問題和車輛的路徑規(guī)劃問題。為了克服電動車充電時間長的缺點，以更換電池代替充電的方案吸引了一些學者的注意。王琪瑛等研究了帶軟時間窗的電動車換電站選址路徑問題。李嘉等考慮到客戶同時存在收貨和寄件需求的情況，研究了裝卸一體化的電動車路徑問題。

現(xiàn)實的物流場景往往還涉及多種不同的目標，例如經(jīng)濟成本、服務(wù)時長、路徑平衡等。一些學者將單目標EVRP問題拓展至包含多種目標的路徑規(guī)劃問題（Multi-objectiveVehicleRoutingProblem，MOVRP）。Lee和Ueng認為路徑之間的不平衡會導致員工的不滿意程度上升，提出了一種考慮路徑平衡的VRP。Sessomboon等研究了帶模糊時間窗的MOVRP，考慮了四種目標函數(shù)，并提出了一種混合遺傳算法來求解問題。Ombuki等研究了以車輛數(shù)和總行程為目標的MOVRP并提出了一種改進的遺傳算法求解問題。Jozefowiez等對MOVRP進行了歸納和回顧，他注意到多目標進化算法（Multi-objectiveEvolutionaryAlgorithms，MOEA）比較受研究者關(guān)注。Zhang等研究了一種帶彈性時間窗的MOVRP，并提出了一種基于蟻群算法的求解策略和三種變異算子。

目前多目標電動車路徑規(guī)劃問題的研究較少，在電動車背景下同時考慮成本與路徑平衡的研究更為稀少。在此背景下，本文對以成本和路徑平衡為目標的帶時間窗的電動車路徑規(guī)劃問題展開了研究。

2模型

2.1問題描述

本文研究的帶時間窗的多目標電動車路徑規(guī)劃問題（Multi-objectiveElectricVehicleRoutingProblemwithTimeWindows，MOEVRPTW）可以具體描述為某物流配送中心采用一電動車車隊向N位客戶提供物流配送服務(wù)，車隊中各車為相同車型。車輛從配送中心出發(fā)，服務(wù)若干名客戶，但須在每個客戶指定的時間窗內(nèi)向其提供配送服務(wù)，且每個客戶僅由一輛車服務(wù)一次。在服務(wù)過程中，車輛載貨量不能超過最大限值，由于電動汽車的行駛里程有限，車輛在配送途中可前往充電站進行充電。

本文研究的多目標問題包含兩個目標，分別為成本目標和路徑平衡目標。車輛的成本分為兩部分：固定的采購成本和與行駛里程線性相關(guān)的運輸成本。另外，在現(xiàn)實企業(yè)運營中，若車輛之間的任務(wù)量差距較大，會引起司機的不滿，影響企業(yè)的運營。因此，本文研究的MOEVRPTW決策問題為在滿足電動車續(xù)航和運力約束、時間窗約束的情況下，確定車輛數(shù)和路徑安排，并取得總成本與路徑平衡的均衡最優(yōu)。

3.2數(shù)學模型

其中，式（1）、（2）分別為總成本目標函數(shù)和路徑平衡目標函數(shù);式（3）、（4）對路徑平衡目標函數(shù)進行補充定義;式（5）為決策變量;式（6）確保每個客戶僅被一輛車服務(wù)且只服務(wù)一次;式（7）表示一個虛擬充電站最多只能接待一輛車;式（8）確保流量平衡，除了場站點，車輛到達某點后必須從該點離開;式（9）表示車輛最多只能執(zhí)行一條路線的任務(wù);式（10）、（11）分別保證了從場站點和客戶處、充電站處離開的路線的時間可行性;式（12）表示時間窗約束;式（10）～（12）防止子路徑的產(chǎn)生;式（13）確保路徑上的客戶的貨物需求得到滿足;式（14）為車輛載貨量約束;式（15）、（16）分別保證了從客戶處、從場站點和充電站處離開的路線的電量可行性。

3算法設(shè)計

3.1迭代局部搜索（ILS）算法

迭代局部搜索算法是一種簡潔而高效的啟發(fā)式算法，它結(jié)合了迭代方法和局部搜索，并將方法作為一種多樣性機制來搜索更廣范圍。

在迭代局部搜索算法中，先對初始解S0進行局部搜索，找到局部最優(yōu)并作為當前最優(yōu)解S*，然后開始迭代。在每一輪迭代中，對S*進行擾動得到中間解S′，再對S′實施局部搜索得到S′*，若S′*滿足設(shè)定的接受準則，則接受它作為新的S*，若不滿足，則保留原來的S*。

迭代局部搜索算法的核心在于專注于對局部最優(yōu)解而非全部可行域的搜索，算法的擾動機制使得新的搜索起點可以繼承原有局部最優(yōu)的部分片段，提高全局搜索效率。已有相當多的研究應(yīng)用了該算法并證明了其有效性。另外，迭代局部搜索算法擁有很好的適應(yīng)性，算法的擾動、接受準則部分可以靈活地根據(jù)具體情況進行調(diào)整，以滿足不同問題的優(yōu)化需求。

3.2多目標迭代局部搜索算法（MOILS）

3.2.1解的編碼

本研究運用整數(shù)編碼方式，以一個含有10位客戶、2個充電站的案例為例。0表示場站點，1～10表示客戶，11、12表示終點站，解的編碼如下：

以上編碼表示在一條路徑中，車輛從場站點出發(fā)，依順序服務(wù)了1、3、4號客戶，前往12號充電站充電后又服務(wù)了9、2號客戶，然后經(jīng)過11號充電站充電并回到場站點。

3.2.2初始解的構(gòu)造

本文運用一種貪心構(gòu)造法構(gòu)造初始解，在描述初始解的構(gòu)造方法之前，先定義“可到達客戶”，即以當前電量，從當前位置可以直接到達或途經(jīng)充電站充電后可以到達的客戶。

構(gòu)造初始解的步驟如下：

（1）當存在未服務(wù)的客戶時，開啟一條新路徑。車輛從場站點出發(fā)，尋找所有未服務(wù)的可到達客戶，從中選擇最近的客戶前往提供服務(wù)。

（2）在客戶處，尋找當前狀態(tài)的所有未服務(wù)的可到達客戶，若存在未服務(wù)的可到達客戶，則從中選擇最近的客戶前往提供服務(wù);若不存在未服務(wù)的可到達客戶，則返回場站點并回到步驟（1）。

（3）重復步驟（1）、（2）直至所有客戶均接受到服務(wù)，即完成了初始解的構(gòu)造。

3.2.3算法迭代機制

本文設(shè)計的多目標迭代局部搜索（MOILS）算法以迭代局部搜索（ILS）為基礎(chǔ)，步驟如下：

（1）構(gòu)造初始解S0并初始化目標函數(shù)權(quán)重參數(shù)α、β，接受初始解作為當前最優(yōu)解S*。

（2）用原目標函數(shù)和權(quán)重參數(shù)構(gòu)造新的目標函數(shù)，初始化迭代參數(shù)i。

（3）擾動S*得到中間解S′，并初始化領(lǐng)域搜索參數(shù)k。

（4）在S′的k領(lǐng)域內(nèi)搜索得到S″，若S″優(yōu)于S′，接受S″作為新的中間解并重置領(lǐng)域搜索參數(shù)k，否則保留S′并使k增加1。

（5）若k≤5，回到步驟（4），否則進行下一步。

（6）若S′通過接受準則，則接受S′作為新的當前最優(yōu)解，否則保留原當前最優(yōu)解，無論是否接受，都使迭代參數(shù)i增加1;若i不超過終止迭代次數(shù)It，退回步驟（3），否則進行下一步。

（7）縮小α并增大β，調(diào)整步長為δ。若調(diào)整后α>0，回到步驟（2），否則停止算法。

具體流程如圖1所示：

3.2.4鄰域算子

在局部搜索階段，本文應(yīng)用五種算子構(gòu)造鄰域。

（1）交換算子

隨機選擇任意兩個節(jié)點，交換其位置。

（2）逆序算子

隨機選擇一條路徑中的兩個節(jié)點并反轉(zhuǎn)兩個節(jié)點及其之間的順序。

（3）插入算子

隨機選擇解中的一個節(jié)點，將其移動到原路徑或其他路徑的另一個隨機位置。

（4）移除算子

隨機選擇解中的一個充電站節(jié)點將其移除。

（5）合并算子

隨機選擇兩條路徑，將其合并。

3.2.5擾動與接受準則

（1）擾動方式

在對當前最優(yōu)解進行擾動時，本文選用經(jīng)典的double-bridgemove擾動策略，其擾動方式如圖2所示。

在double-bridgemove擾動策略中，依序隨機選擇四個節(jié)點i、j、k、l，并如圖2中點虛線所示切斷（i，i+1），（j，j+1），（k，k+1），（l，l+1）四個路段，然后將路徑按圖中短劃虛線所示方式連接（i，k+1），（k，i+1），（j，l+1），（l，j+1）四個路段，構(gòu)成新路徑。

（2）接收準則

對局部搜索得到的中間解S^'，本文采用模擬退火算法中的解接受準則。每次進行判斷時，取隨機數(shù)ε∈[0，1]，若ε<e-OF（S′）-OF（S*）T·ρi，則接受S′，否則保留S*。

4實驗

4.1實驗設(shè)置

本文采用Java編寫算法，并在處理器為Intel（R）Core（TM）i5-5257UCPU@2.70GHz、內(nèi)存為8G的計算機平臺上進行實驗。

在參數(shù)設(shè)置方面，本文做如下假設(shè)：

由于本文研究的多目標電動車路徑規(guī)劃問題目前缺少可橫向比較的研究算例，本文構(gòu)造了九組算例來驗證算法的有效性。九組算例的顧客數(shù)和充電站數(shù)如表5所示。

為了對比算法的表現(xiàn)，除了用本文提出的算法，研究還應(yīng)用VNS算法和ILS算法求解了九組算例，其求解結(jié)果也在實驗結(jié)果中展示。

4.2實驗結(jié)果

用本文提出的MOILS算法求解九組算例，每組運行5次。由于多目標問題的解為帕累托解，以下以α-0.7，β-0.3為參數(shù)設(shè)置展示多目標算法的求解結(jié)果，結(jié)果如表4所示。

在上述求解結(jié)果表中，單目標MOILS表示將算法中的成本函數(shù)權(quán)重參數(shù)固定為1，并將路徑平衡函數(shù)權(quán)重參數(shù)設(shè)為0，以達到求解單目標的效果。

表4為對成本函數(shù)求解的結(jié)果，每種算法分別展示了算法運行5次的最優(yōu)結(jié)果和平均結(jié)果。由表4可知，本文提出的MOILS在求解EVRP問題時可以得到較好的結(jié)果。與經(jīng)典VNS算法和ILS算法相比，MOILS在僅求解成本目標時明顯優(yōu)于VNS和ILS，在九組算例中求得的最優(yōu)解成本比VNS平均低9.41%，比ILS平均低17.72%。

表5展示了每種算法所求的最優(yōu)成本及最優(yōu)成本對應(yīng)的路徑平衡結(jié)果。表6展示了各種算法求得的最優(yōu)成本對應(yīng)的路徑平衡結(jié)果以及多目標MOILS求得的路徑平衡結(jié)果相較于VNS和ILS的改善程度。由表5和表6可以看出，在考慮雙目標的情況下，本文提出的MOILS同樣有較好的表現(xiàn)。與VNS和ILS相比，在不顯著提升成本的情況下，MOILS也可以使路徑之間的平衡得到大幅度改善，例如在算例R03中，MOILS的成本只比VNS和ILS的成本分別增加了0.58%和3.37%，但路徑平衡卻分別改善了68.63%和64.49%。

表7展示了VNS、單目標MOILS和多目標MOILS求解各算例5次所得解的路徑平衡的均值和標準差。表7中數(shù)據(jù)表明MOILS在求解單目標問題和多目標問題時，都體現(xiàn)出比VNS更好的穩(wěn)定性。在九個算例中，VNS、單目標MOILS和多目標MOILS求得的路徑平衡的平均方差分別為7.7%、6.3%和2.8%。

實驗數(shù)據(jù)表明，本文提出的算法能夠在求解多目標電動車路徑規(guī)劃問題時取得較好的結(jié)果。

5結(jié)論

本文以成本和路徑平衡為目標，研究了多目標電動車路徑規(guī)劃問題，考慮了電動車行駛里程、載貨容量、充電速率以及顧客時間窗等限制因素，提出了相應(yīng)的數(shù)學模型，并設(shè)計了一種多目標優(yōu)化算法。

本文的算法以迭代局部搜索算法為基礎(chǔ)，采用了五種算子，結(jié)合VNS的領(lǐng)域搜索策略，通過調(diào)整目標函數(shù)權(quán)重參數(shù)迭代求解多目標問題的帕累托前沿。本文對九組算例進行了多次實驗，并對比了經(jīng)典的VNS和ILS算法，證明了本文中算法的可行性和有效性。

未來的研究可以考慮其他現(xiàn)實目標，也可以將軟時間窗、隨機需求或隨機道路條件等不確定性因素納入考量，以增加模型、算法的現(xiàn)實應(yīng)用價值。

參考文獻：

[1]CONRADR，F(xiàn)IGLIOZZIM.Therechargingvehicleroutingproblem[J].Procofthe61stAnnualIIEConference，2011.

[2]ERDOGˇANS，MILLER-HOOKSE.Agreenvehicleroutingproblem[J].TransportationResearchPartE：LogisticsandTransportationReview，2012，48（1）：100-14.

[3]SCHNEIDERM，STENGERA，GOEKED.Theelectricvehicle-routingproblemwithtimewindowsandrechargingstations[J].TransportationScience，2014，48（4）：500-20.

[4]HIERMANNG，PUCHINGERJ，ROPKES，etal.Theelectricfleetsizeandmixvehicleroutingproblemwithtimewindowsandrechargingstations[J].EuropeanJournalofOperationalResearch，2016，252（3）：995-1018.

[5]揭婉晨，楊珺，楊超.多車型電動汽車車輛路徑問題的分支定價算法研究[J].系統(tǒng)工程理論與實踐，2016，36（7）：1795-805.

[6]KESKINM，CATAYB.Partialrechargestrategiesfortheelectricvehicleroutingproblemwithtimewindows[J].TransportationResearchPartC-EmergingTechnologies，2016，65：111-27.

[7]葛顯龍，竹自強.帶軟時間窗的電動車輛路徑優(yōu)化問題[J].工業(yè)工程與管理，2019，24（4）：96-104，12.

[8]MONTOYAA，GURETC，MENDOZAJE，etal.Theelectricvehicleroutingproblemwithnonlinearchargingfunction[J].TransportationResearchPartB：Methodological，2017，103（87-110.

[9]唐佩佩，馮曉威，宮英麗.基于遺傳算法的生鮮同城配送路徑優(yōu)化研究[J].上海管理科學，2018，40（5）：90-96.

[10]SCHIFFERM，WALTHERG.Theelectriclocationroutingproblemwithtimewindowsandpartialrecharging[J].EuropeanJournalofOperationalResearch，2017，260（3）：995-1013.

[11]王琪瑛，李英，李惠.帶軟時間窗的電動車換電站選址路徑問題研究[J].工業(yè)工程與管理，2019，24（3）：99-106.

[12]李嘉，楊東，賈永基，等.裝卸一體化電動汽車路徑問題建模與優(yōu)化[J].工業(yè)工程與管理，2020，25（1）：29-37.

[13]LEETR，UENGJH.Astudyofvehicleroutingproblemswithload‐balancing[J].InternationalJournalofPhysicalDistribution&LogisticsManagement，1999，29（10）：646-57.

[14]SESSOMBOONW，WATANABEK，IROHARAT，etal.Astudyonmulti-objectivevehiclerountingproblemconsideringcustomersatisfactionwithdue-time（thecreationofparetooptimalsolutionsbyhybridgeneticalgorithm）[J].TransactionsoftheJapanSocietyofMechanicalEngineersSeriesC，1998，64（1108-15.

[15]OMBUKIB，ROSSBJ，HANSHARF.Multi-objectivegeneticalgorithmsforvehicleroutingproblemwithtimewindows[J].AppliedIntelligence，2006，24（1）：17-30.

[16]JOZEFOWIEZN，SEMETF，TALBIE-G.Multi-objectivevehicleroutingproblems[J].EuropeanJournalofOperationalResearch，2008，189（2）：293-309.

[17]ZHANGH，ZHANGQ，MAL，etal.Ahybridantcolonyoptimizationalgorithmforamulti-objectivevehicleroutingproblemwithflexibletimewindows[J].InformationSciences，2019，490（166-90.

收稿日期：2022-03-16

作者簡介：韋鵬飛（1997—），男，江蘇無錫人，碩士研究生，研究方向：物流管理、路徑規(guī)劃，E-mail：pfwei973@163.com;張建軍（1978—），男，江西上饒人，博士，副教授，博士生導師，研究方向：物流與供應(yīng)鏈管理，E-mail：Zhangjianjun@#edu.cn。