韋鵬飛 張建軍

文章編號(hào)：1005-9679（2022）03-0091-08

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

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

中圖分類號(hào)：F272

文獻(xiàn)標(biāo)志碼：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

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

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

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

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

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

1文獻(xiàn)綜述

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

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

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

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

目前多目標(biāo)電動(dòng)車(chē)路徑規(guī)劃問(wèn)題的研究較少，在電動(dòng)車(chē)背景下同時(shí)考慮成本與路徑平衡的研究更為稀少。在此背景下，本文對(duì)以成本和路徑平衡為目標(biāo)的帶時(shí)間窗的電動(dòng)車(chē)路徑規(guī)劃問(wèn)題展開(kāi)了研究。

2模型

2.1問(wèn)題描述

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

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

3.2數(shù)學(xué)模型

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

3算法設(shè)計(jì)

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

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

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

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

3.2多目標(biāo)迭代局部搜索算法（MOILS）

3.2.1解的編碼

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

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

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

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

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

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

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

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

3.2.3算法迭代機(jī)制

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

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

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

（3）擾動(dòng)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），否則進(jìn)行下一步。

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

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

具體流程如圖1所示：

3.2.4鄰域算子

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

（1）交換算子

隨機(jī)選擇任意兩個(gè)節(jié)點(diǎn)，交換其位置。

（2）逆序算子

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

（3）插入算子

隨機(jī)選擇解中的一個(gè)節(jié)點(diǎn)，將其移動(dòng)到原路徑或其他路徑的另一個(gè)隨機(jī)位置。

（4）移除算子

隨機(jī)選擇解中的一個(gè)充電站節(jié)點(diǎn)將其移除。

（5）合并算子

隨機(jī)選擇兩條路徑，將其合并。

3.2.5擾動(dòng)與接受準(zhǔn)則

（1）擾動(dòng)方式

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

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

（2）接收準(zhǔn)則

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

4實(shí)驗(yàn)

4.1實(shí)驗(yàn)設(shè)置

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

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

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

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

4.2實(shí)驗(yàn)結(jié)果

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

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

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

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

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

實(shí)驗(yàn)數(shù)據(jù)表明，本文提出的算法能夠在求解多目標(biāo)電動(dòng)車(chē)路徑規(guī)劃問(wèn)題時(shí)取得較好的結(jié)果。

5結(jié)論

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

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

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

參考文獻(xiàn)：

[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]揭婉晨，楊珺，楊超.多車(chē)型電動(dòng)汽車(chē)車(chē)輛路徑問(wèn)題的分支定價(jià)算法研究[J].系統(tǒng)工程理論與實(shí)踐，2016，36（7）：1795-805.

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

[7]葛顯龍，竹自強(qiáng).帶軟時(shí)間窗的電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題[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].上海管理科學(xué)，2018，40（5）：90-96.

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

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

[12]李嘉，楊東，賈永基，等.裝卸一體化電動(dòng)汽車(chē)路徑問(wèn)題建模與優(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

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