摘" 要： 針對(duì)帶容量約束的電動(dòng)車輛路徑問(wèn)題（CEVRP），以最小化總行駛里程為優(yōu)化目標(biāo)，提出一種混合文化基因求解算法。將原問(wèn)題分解為兩個(gè)子問(wèn)題，即帶容量約束的車輛路徑問(wèn)題和固定路徑下的車輛充電問(wèn)題。針對(duì)該問(wèn)題設(shè)計(jì)雙層解碼，上層解碼采用分割算法獲得滿足容量約束的路徑，下層采用移除啟發(fā)式算法獲得可行的充電路徑。首先，利用k最近鄰算法獲得多樣性的編碼個(gè)體，再采用雙層解碼獲得優(yōu)良初始種群；然后，對(duì)種群執(zhí)行變鄰域搜索改進(jìn)個(gè)體的解質(zhì)量；接著，使用精英保留策略對(duì)精英個(gè)體繼續(xù)采用三種局部強(qiáng)化策略，對(duì)帶容量約束的車輛路徑進(jìn)行局部搜索，對(duì)車輛路徑中的充電站和客戶點(diǎn)進(jìn)行優(yōu)化調(diào)整；最后，采用兩種選擇操作并使用順序交叉在不同解之間共享信息。實(shí)驗(yàn)部分采用國(guó)際競(jìng)賽中的CEVRP測(cè)試數(shù)據(jù)集，將所提算法與對(duì)比算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，所提算法在中小規(guī)模實(shí)例上優(yōu)于對(duì)比算法，在大規(guī)模實(shí)例上也能得到滿意解，并且具有良好的穩(wěn)定性。

關(guān)鍵詞： 電動(dòng)車輛路徑問(wèn)題； 混合文化基因算法； k最近鄰； 變鄰域搜索； 局部搜索； 精英保留策略

中圖分類號(hào)： TN919?34； TP301.6" " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " "文章編號(hào)： 1004?373X（2025）07?0177?10

Hybrid memetic algorithm for solving capacitated electric vehicle routing problem

LUO Wei1， 2， CHEN Shijun3， WU Huawei1， 2

（1. Hubei Longzhong Laboratory， Hubei University of Arts and Science， Xiangyang 441053， China;

2. Hubei Key Laboratory of Power System Design and Test for Pure Electric Vehicles， Hubei University of Arts and Science， Xiangyang 441053， China;

3. School of Mathematics and Statistics， Hubei University of Arts and Science， Xiangyang 441053， China）

Abstract： For the capacitated electric vehicle routing problem （CEVRP）， a hybrid memetic algorithm （HMA） is proposed to solve the problem with the optimization objective of minimizing the total distance. The original problem is decomposed into two subproblems， i.e.， capacitated vehicle routing problem and charging problem of vehicles with fixed routes. A two?layer decoding is designed for the problems， with the upper decoding using the split algorithm to obtain routes that satisfy the capacity constraints， and the lower decoding using the removal heuristic algorithm to obtain feasible charging routes. Firstly， diverse coding individuals are obtained by k?nearest neighbors （kNN）， and then the two?layer decoding is used to obtain a good initial population. Then， a variable neighborhood search （VNS） is performed on the population to further improve the solution quality of individuals. Next， an elite retention strategy is used， and three local reinforcement strategies are used for the elite individuals： a local search strategy is performed for the capacitated vehicle routing， the charging stations and the customer convergence points in the routing are optimized and adjusted. Finally， two selection operations are adopted， and the information is shared among different solutions by sequential crossover. The proposed algorithm is compared with the contrast algorithms by the CEVRP test dataset in the international competition. The experimental results show that the proposed algorithm is superior to the contrast algorithms on small and medium?scale instances， and can also get satisfactory solutions on large?scale instances， and has good stability.

Keywords： electric vehicle routing problem; HMA; kNN; VNS; local search; elite retention strategy

0" 引" 言

隨著生態(tài)環(huán)境問(wèn)題日益加劇和人工智能技術(shù)快速發(fā)展，物流運(yùn)輸業(yè)正經(jīng)歷著巨大變革。特別是國(guó)家提出“碳達(dá)峰、碳中和”的戰(zhàn)略目標(biāo)后，管理部門(mén)和物流企業(yè)對(duì)CO2的排放指標(biāo)提出了更高要求，部分地區(qū)通過(guò)設(shè)置限行時(shí)間或限行區(qū)域來(lái)逐步淘汰傳統(tǒng)燃油車輛[1]。與傳統(tǒng)燃油車相比，電動(dòng)車輛（Electric Vehicle， EV）有著環(huán)保節(jié)能的優(yōu)點(diǎn)，很多物流企業(yè)如FedEx、DHL、XPO及JD等已經(jīng)逐步采用電動(dòng)車輛進(jìn)行配送作業(yè)[2]。如何優(yōu)化電動(dòng)車輛的配送路徑，對(duì)物流企業(yè)降低運(yùn)營(yíng)成本、提高配送效率具有重要現(xiàn)實(shí)意義。關(guān)于傳統(tǒng)燃油車輛的配送路徑優(yōu)化問(wèn)題已有大量研究成果[3]。然而，電動(dòng)車輛存在續(xù)航能力弱、充電時(shí)間較長(zhǎng)以及部分地區(qū)充電站數(shù)量少等難題，使得針對(duì)傳統(tǒng)燃油車的車輛路徑優(yōu)化方法無(wú)法直接應(yīng)用于求解電動(dòng)車輛路徑問(wèn)題（Electric Vehicle Routing Problem， EVRP）。為此，部分學(xué)者對(duì)EVRP及其擴(kuò)展問(wèn)題做了研究，如帶時(shí)間窗口EVRP[4]、部分充電EVRP[5]、多車型EVRP[6?7]、動(dòng)態(tài)EVRP[8]、非線性充電EVRP[9]等。

EVRP及其擴(kuò)展問(wèn)題的求解方法主要分為精確算法和啟發(fā)式算法。精確算法通常將EVRP建模成混合整數(shù)線性規(guī)劃模型來(lái)求解[10]，可以在小規(guī)模問(wèn)題上求得最優(yōu)解，但由于其計(jì)算時(shí)間復(fù)雜度高，從而在求解超過(guò)50個(gè)客戶點(diǎn)的中大型問(wèn)題上效率低下[11]。啟發(fā)式算法尋求在短時(shí)間內(nèi)求得問(wèn)題的滿意解，大體可分為單解算法和種群算法兩大類。前者包括模擬退火（Simulated Annealing， SA）[12]算法、可變鄰域搜索（Variable Neighborhood Search， VNS）[13]算法、自適應(yīng)大鄰域搜索（Adaptive Large Neighborhood Search， ALNS）[14]算法等；后者包括粒子群優(yōu)化（Particle Swarm Optimization， PSO）[15]算法、遺傳算法（Genetic Algorithm， GA）[16]、蟻群算法（Ant Colony Algorithm， ACO）[17]等。

帶容量約束的電動(dòng)車輛路徑問(wèn)題（Capacitated Electric Vehicle Routing Problem， CEVRP）作為一種重要的EVRP擴(kuò)展問(wèn)題，其研究成果能為更復(fù)雜的問(wèn)題提供借鑒或參考，因此也引起了部分學(xué)者的重視。文獻(xiàn)[18]提出一種雙層蟻群優(yōu)化算法（Bilevel Ant Colony Optimization Algorithm， BACO），將CEVRP分解為帶容量約束的車輛路徑問(wèn)題（Capacitated Vehicle Routing Problem， CVRP）和固定路徑的車輛充電問(wèn)題（Fixed Route Vehicle Charging Problem， FRVCP）兩個(gè)子問(wèn)題，并使用ACO進(jìn)行求解，證實(shí)了CEVRP分層求解的有效性。但是BACO對(duì)兩個(gè)子問(wèn)題之間的耦合關(guān)系挖掘不夠，導(dǎo)致部分實(shí)例的求解效果并不理想。文獻(xiàn)[19]提出了一種基于雙種群的協(xié)同進(jìn)化算法，該算法使用兩個(gè)進(jìn)化種群對(duì)這兩個(gè)子問(wèn)題進(jìn)行協(xié)同優(yōu)化。在文獻(xiàn)[20]的基礎(chǔ)上，文獻(xiàn)[21]對(duì)混合遺傳算法進(jìn)行改進(jìn)，用于求解CEVRP，并使用一種復(fù)雜的種群管理框架來(lái)處理子問(wèn)題間的耦合關(guān)系。文獻(xiàn)[22]提出了一種基于閾值接受度的多層搜索算法，該算法由三層組成，第一層產(chǎn)生多樣化的CVRP解，第二層篩選出優(yōu)質(zhì)的CVRP解，第三層采用啟發(fā)式結(jié)合枚舉法求解FRVCP，最終得到滿足電量約束的CEVRP可行解。

盡管已有部分研究成果，但由于CEVRP是相對(duì)于CVRP的NP?hard問(wèn)題，其大規(guī)模問(wèn)題的高效求解方法仍然存在巨大的優(yōu)化空間，也是目前國(guó)際上研究的熱點(diǎn)和難點(diǎn)。為此，2020年IEEE世界計(jì)算智能大會(huì)舉辦了求解大規(guī)模CEVRP的國(guó)際競(jìng)賽[18]，并提供一系列CEVRP測(cè)試數(shù)據(jù)集（以下簡(jiǎn)稱WCCI2020 CEVRP）。為進(jìn)一步探究CEVRP的高效求解方法，本文提出一種混合文化基因算法（Hybrid Memetic Algorithm， HMA）。首先，將CEVRP分解為兩個(gè)子問(wèn)題：帶容量約束的車輛路徑問(wèn)題（CVRP）和固定路徑的車輛充電問(wèn)題（FRVCP），并根據(jù)子問(wèn)題設(shè)計(jì)雙層解碼，即先構(gòu)造只考慮客戶點(diǎn)的旅行商問(wèn)題的解編碼（以下簡(jiǎn)稱TSP編碼），再利用分割（Split）算法獲得滿足車輛容量約束的路徑，最后使用移除啟發(fā)式（Remove Heuristic， RH）算法獲得可行的充電路徑。在初始化種群時(shí)，利用k最近鄰（k?Nearest Neighbor， kNN）算法獲得良好的解個(gè)體，并維持初始種群的多樣性。為加快種群進(jìn)化速度，采用VNS策略對(duì)種群個(gè)體進(jìn)行優(yōu)化，VNS框架中包括3種鄰域算子和SA中的Metropolis準(zhǔn)則。為提高算法的尋優(yōu)能力，采用精英保留策略，并對(duì)精英個(gè)體采用針對(duì)子問(wèn)題特征而設(shè)計(jì)的三種強(qiáng)化策略。此外，使用兩種選擇策略和順序交叉加快種群個(gè)體之間的優(yōu)良信息共享。最后，利用測(cè)試數(shù)據(jù)集WCCI2020 CEVRP驗(yàn)證所提算法的有效性。

1" CEVRP問(wèn)題及數(shù)學(xué)模型

在CEVRP問(wèn)題中，給定具有特定負(fù)載容量和電池容量的電動(dòng)車隊(duì)，目標(biāo)是在負(fù)載容量、電池容量等約束條件下，找到一組滿足客戶點(diǎn)需求的最佳車輛配送路徑，最小化所有車輛的總行駛里程。CEVRP可以采用一個(gè)完全連通的加權(quán)圖[G=（V，E）]進(jìn)行描述。記頂點(diǎn)[V={0}?Vc?Vf]，包括：配送中心[0]，客戶點(diǎn)集[Vc]和充電站集[Vf]。其中：配送中心是車輛出發(fā)和返回的位置，假定只有一個(gè)配送中心；客戶點(diǎn)代表需要執(zhí)行配送任務(wù)的位置，每個(gè)客戶點(diǎn)[i∈Vc]都有固定數(shù)量的貨物需求[ci]；充電站集[Vf]為電動(dòng)車提供充電服務(wù)，配送中心也能提供充電服務(wù)。每條邊[（i，j）∈E]有一個(gè)固定權(quán)值[dij]，表示[i]與[j]之間的距離。電動(dòng)車除了像傳統(tǒng)車一樣有最大負(fù)載容量[Qc]外，還有最大電池容量[Qb]。定義電池消耗率為[rb]，即經(jīng)過(guò)邊[（i， j）]將會(huì)消耗[dij?rb]的電量。考慮到每個(gè)充電站可多次被訪問(wèn)，引入充電站擴(kuò)展集[V′f]，其中每個(gè)充電站[i∈Vf]復(fù)制[2Vc]次。這樣，在最壞情況下，每輛電動(dòng)車在服務(wù)一個(gè)客戶點(diǎn)的往返途中最多進(jìn)出一次充電站。另外，引入兩個(gè)變量[ui]和[yi]，分別表示當(dāng)EV到達(dá)[i]時(shí)的剩余負(fù)載容量和剩余電池容量。因此，CEVRP的數(shù)學(xué)模型如下：

[minF（X）=i∈V， j∈V，i≠jdijxij] （1）

[s.t. j∈V，i≠jxij=1，" "?i∈Vc] （2）

[j∈V，i≠jxij≤1，" " ?i∈V′f] （3）

[j∈V，i≠jxij-j∈V，i≠jxji=0，" " ?i∈V] （4）

[uj≤ui-cixij+Qc（1-xij），" " ?i∈V，?j∈V，i≠j] （5）

[0≤ui≤Qc，" " ?i∈V] （6）

[yj≤yi-rbdijxij+Qb（1-xij），" " ?i∈Vc，?j∈V，i≠j] （7）

[yj≤Qb-rbdijxij，" " ?i∈V′f?{0}，" "?j∈V，i≠j] （8）

[0≤yi≤Qb，" " "?i∈V] （9）

[xij∈{0，1}，" " ?i∈V，?j∈V，i≠j] （10）

式（1）表示CEVRP的目標(biāo)，即最小化所有車輛的總行駛里程；式（2）表示每個(gè)客戶點(diǎn)當(dāng)且僅當(dāng)被服務(wù)一次；式（3）表示每個(gè)充電站（復(fù)制的副本）只能被訪問(wèn)一次；式（4）表示流量平衡約束，即進(jìn)入客戶點(diǎn)的流量應(yīng)等于離開(kāi)客戶點(diǎn)的流量；式（5）和式（6）表示負(fù)載容量約束，即電動(dòng)汽車在行駛過(guò)程中不能超載；式（7）～式（9）代表電池容量約束，即電動(dòng)汽車在行駛過(guò)程中要保證有充足的電量，除此之外，式（7）～式（9）還表明了另一個(gè)假設(shè)，即在可行的路徑上電動(dòng)車總是會(huì)在充電站為電池充電，以到達(dá)下一個(gè)充電站或配送中心；式（10）定義了0?1決策變量，即車輛經(jīng)過(guò)邊[（i， j）]，[xij]就取1，否則就取0。

圖1展示了一個(gè) CEVRP的示例。該示例列舉了車輛到訪充電站的五種情況：

1） 同一個(gè)車輛可以多次訪問(wèn)同一充電站，如EV1訪問(wèn)13號(hào)充電站2次；

2） 電動(dòng)車可以不訪問(wèn)充電站，如EV2沒(méi)有訪問(wèn)任何充電站；

3） 電動(dòng)車可以只訪問(wèn)1次充電站，如EV3只訪問(wèn)15號(hào)充電站1次；

4） 電動(dòng)車可以多次訪問(wèn)不同充電站，如EV4先后訪問(wèn)了16號(hào)與17號(hào)充電站；

5） 不是所有充電站都需要訪問(wèn)，圖1中電動(dòng)車沒(méi)有訪問(wèn)14號(hào)和18號(hào)充電站。

2" 混合文化基因算法

為求得CEVRP的最優(yōu)或準(zhǔn)最優(yōu)解，本文提出一種混合文化基因算法（HMA），具體的算法流程圖如圖2所示。

混合文化基因算法具體步驟如下。

Step1：利用kNN和雙層解碼方法生成高質(zhì)量TSP編碼序列，以保證初始種群的多樣性。

Step2：針對(duì)種群的每個(gè)個(gè)體TSP編碼，設(shè)計(jì)VNS框架對(duì)種群進(jìn)行強(qiáng)化。在VNS框架中使用交換、插入和逆轉(zhuǎn)三種鄰域算子，并添加SA中的Metropolis準(zhǔn)則避免過(guò)早陷入局部最優(yōu)。

Step3：采取精英保留策略，并對(duì)精英個(gè)體采取三種策略強(qiáng)化：對(duì)精英個(gè)體的CVRP路徑添加Relocate、Swap和2?Opt局部搜索算子；設(shè)計(jì)一種插入充電站的簡(jiǎn)單枚舉算法，對(duì)充電路徑有1個(gè)和2個(gè)充電站的子路徑的充電站重新調(diào)整；針對(duì)CEVRP路徑的客戶點(diǎn)進(jìn)行優(yōu)化調(diào)整。

Step4：執(zhí)行選擇和交叉操作，共享個(gè)體之間的優(yōu)良信息。最后，設(shè)置停止準(zhǔn)則，可以是最大的迭代次數(shù)、評(píng)價(jià)次數(shù)、運(yùn)行時(shí)間等。本文選擇最大評(píng)價(jià)次數(shù)作為算法的終止條件，即滿足最大評(píng)價(jià)次數(shù)就輸出最優(yōu)解，否則，返回Step2。

2.1" 初始種群與編碼解碼

初始種群的質(zhì)量會(huì)直接影響混合文化基因算法的性能，好的初始種群有助于算法快速收斂到最優(yōu)解。本文采用自然數(shù)編碼表示客戶點(diǎn)（或充電站）的訪問(wèn)順序，如圖3所示。其中，0代表配送中心，1～8代表客戶點(diǎn)，9和10代表充電站。為了保證種群個(gè)體的多樣性和解質(zhì)量，利用kNN和雙層解碼方法構(gòu)造初始種群。

利用kNN生成個(gè)體的步驟為：首先將配送中心0加入編碼路徑[I_route]；然后從距離配送中心0最近的[k]個(gè)客戶點(diǎn)中隨機(jī)選取某客戶點(diǎn)[i]；再?gòu)木嚯x客戶點(diǎn)[i]最近的[k]個(gè)客戶點(diǎn)中隨機(jī)選取某客戶點(diǎn)[j]；以此類推，直到所有客戶點(diǎn)都包含在[I_route]中。這樣，每個(gè)編碼序列被編碼為只包含配送中心0和所有客戶點(diǎn)的TSP路徑。再針對(duì)kNN得到的TSP編碼，設(shè)計(jì)雙層解碼，將CEVRP分成CVRP和FRVCP兩個(gè)子問(wèn)題。上層解碼利用Split算法生成容量可行的CVRP解，該方法最早由文獻(xiàn)[23]提出。本文使用文獻(xiàn)[24]優(yōu)化后的Split算法，該方法可以找到[I_route]滿足容量約束的最佳分割點(diǎn)，并得到CVRP的可行路徑[C_route]。下層編碼利用啟發(fā)式算法（RH）插入充電站，使其滿足電池容量約束。RH采用文獻(xiàn)[18]所提出的方法，通過(guò)在[C_route]中相鄰客戶點(diǎn)之間插入成本最優(yōu)的充電站，然后逐個(gè)移除多余充電站來(lái)優(yōu)化充電順序，最后得到解碼路徑[D_route]。

2.2" 基于VNS的種群強(qiáng)化

為提高種群的解質(zhì)量，采用VNS對(duì)種群個(gè)體進(jìn)行強(qiáng)化。在VNS中采用了三種鄰域算子作用于種群個(gè)體。三種鄰域算子包括交換、插入和逆轉(zhuǎn)，相關(guān)示例如圖4所示。圖4a）將客戶點(diǎn)4、7進(jìn)行交換；圖4b）將客戶點(diǎn)4插入到客戶點(diǎn)7后面；圖4c）選擇客戶點(diǎn)1與客戶點(diǎn)6，并將中間的客戶點(diǎn)（4，3，8，7）逆轉(zhuǎn)為（7，8，3，4）。

為了增強(qiáng)優(yōu)化效果，每個(gè)鄰域算子至少執(zhí)行LS次。為防止算法過(guò)早陷入局部最優(yōu)，解的接受準(zhǔn)則采用SA中的Metropolis準(zhǔn)則。SA的兩個(gè)參數(shù)初始溫度[T]和退火系數(shù)[λ]分別設(shè)置為初始最優(yōu)個(gè)體目標(biāo)值平方根[F（x0）]和0.95。VNS框架流程圖如圖5所示。圖5中，最優(yōu)鄰域解[x_neigh]初始化為無(wú)窮大，對(duì)個(gè)體解[x]進(jìn)行VNS，依次執(zhí)行鄰域算子交換、插入和逆轉(zhuǎn)。最后對(duì)[x]和[x_neigh]使用Metropolis準(zhǔn)則，如果接受概率[P（x，x_neigh）]gt;[rand（0，1）]，則[x←x_neigh]，并更新溫度[T]。

2.3" 精英個(gè)體強(qiáng)化

根據(jù)HMA中種群個(gè)體的目標(biāo)值進(jìn)行排序后，采用精英保留策略選出最優(yōu)數(shù)量為[E]的個(gè)體，本文[E]等于總客戶點(diǎn)數(shù)的10%；然后對(duì)精英個(gè)體采取下面三種改進(jìn)策略。

2.3.1" 基于CVRP路徑的局部搜索策略

CEVRP解的質(zhì)量通常與其對(duì)應(yīng)的CVRP解呈正相關(guān)[22]，所以本文對(duì)精英個(gè)體的CVRP路徑使用三種不同的局部搜索算子進(jìn)一步改進(jìn)解。三種算子分別是Relocate、Swap和2?Opt算子。Relocate算子將1個(gè)客戶點(diǎn)插入到另一位置；Swap算子隨機(jī)交換兩個(gè)客戶點(diǎn)位置；2?Opt算子針對(duì)單條子路徑隨機(jī)選擇兩點(diǎn)，將中間的客戶點(diǎn)逆轉(zhuǎn)。為縮小鄰域規(guī)模，并使得算法集中搜索在最可能帶來(lái)優(yōu)化效果的鄰域空間，執(zhí)行局部搜索算子時(shí)，每個(gè)客戶點(diǎn)選取離自己關(guān)聯(lián)度最高的[γ]個(gè)客戶點(diǎn)，關(guān)聯(lián)度只與距離有關(guān)，本文取[γ]為40%的總客戶點(diǎn)數(shù)量。為提高本文策略的多樣性，三種算子的使用順序隨機(jī)生成。

2.3.2" 基于FRVCP的充電站調(diào)整策略

由于車輛在配送過(guò)程中多次充電是低效的，車輛在行駛過(guò)程中最多充電4次，在大多數(shù)情況下，只會(huì)充電1次或2次[18]。RH方法可能會(huì)訪問(wèn)比最優(yōu)充電路徑上更多的充電站，而這種情況往往不是最優(yōu)的選擇[17]。本文采用一種簡(jiǎn)單枚舉法（Simple Enumeration Method， SEM）優(yōu)化那些只有1個(gè)或2個(gè)充電站的子路徑，算法偽代碼如下。

算法：簡(jiǎn)單枚舉法（SEM）

輸入：CEVRP子路徑[Γ]、距離矩陣[D]、客戶點(diǎn)集[Vc]、充電站集[Vf]、電池容量[Q]、電池消耗率[h]

輸出：精細(xì)化的CEVRP子路徑[Γ]

1.計(jì)算路徑需要充電站數(shù)[CS_num]

2.[if] [CS_num ==1]

3.從[Γ]移除充電站，選擇[Γi]與[Γi+1]之間距離最近的CS插入

4." "[if] [F（Γ） lt; F（Γ）]

5." " " "更新子路徑：[?！

6." "[end if]

7. [else if] [CS_num ==2]

8." " " 從[Γ]移除充電站，確定2個(gè)CS的范圍[[CS1_a， CS1_b ]]、[[CS2_a， CS2_b]]

9." "[for] [CS1_a→CS1_b]

10." " " 選擇[Γi]與[Γi+1]之間距離最近的CS插入，作為CS1

11." " " 更新CS2范圍：[[CS2_a， CS2_c]]

12." " [for] [CS2_a→CS2_c]

13." " " "選擇[Γj]與[Γj+1]之間距離最近的CS插入，作為CS2

14." " " "更新找到的最佳子路徑：[Γ*←Γ]

15." " "[end for]

16." "[end for]

17." " "[if] [F（Γ*）lt;F（Γ）]

18." " " "更新子路徑：[?！?]

19." " "[end if]

20. [end if]

其中，[Γi]表示子路徑[Γ]中的客戶點(diǎn)，CS代表充電站。SHM中優(yōu)化一個(gè)充電站路徑的操作簡(jiǎn)稱AdjustOneCS，優(yōu)化兩個(gè)充電站路徑的操作為AdjustTwoCS。

AdjustOneCS：偽代碼2～6行。首先，將該充電站從子路徑中移除；其次，對(duì)于子路徑中每個(gè)節(jié)點(diǎn)之間的位置插入一個(gè)新的具有相鄰兩個(gè)節(jié)點(diǎn)[Гi]與[Гi+1]之間最小距離的充電站CS，生成一個(gè)新的解。如果適應(yīng)度更優(yōu)，則用可行的新路徑替換子路徑，并更新CEVRP路徑。

AdjustTwoCS：偽代碼7～20行。將該充電站從子路徑中移除，然后確定每個(gè)CS范圍。對(duì)于具有2個(gè)CS的可行子路線，完成該路線的總電量需求應(yīng)滿足2[Qb]～3[Qb]，其中[Qb]為電池容量。[CS1_a]、[CS1_b]是第1個(gè)CS范圍的上限和下限，[CS1_a]到該路徑結(jié)尾應(yīng)小于[2Qb]。路徑開(kāi)始到[CS1_b]的路程應(yīng)小于[Qb]；[CS2_a]、[CS2_b]是第2個(gè)CS范圍的上限和下限。[CS2_a]到該路徑結(jié)尾應(yīng)小于[Qb]，路徑開(kāi)始到[CS2_b]小于[2Qb]。當(dāng)?shù)谝粋€(gè)充電站確定為CS1′后，CS2應(yīng)在CS1′后的[Qb]路程內(nèi)，于是CS2的上限可以進(jìn)一步縮小為[CS2_c]。

2.3.3" 基于CEVRP路徑的客戶點(diǎn)調(diào)整策略

由于CEVRP的最優(yōu)解與其相應(yīng)CVRP的最優(yōu)解之間沒(méi)有直接的關(guān)聯(lián)性[22]，本文最后添加針對(duì)CEVRP路徑的客戶點(diǎn)調(diào)整策略。該策略首先生成包含所有客戶點(diǎn)的隨機(jī)序列，然后從序列開(kāi)始依次刪除原路徑的客戶點(diǎn)進(jìn)行枚舉插入，直到考慮到所有客戶點(diǎn)。該策略類似Relocate算子，與Relocate算子相比有兩點(diǎn)好處：每個(gè)客戶點(diǎn)隨機(jī)選擇，增加了算子的隨機(jī)性；可以忽略充電站只進(jìn)行客戶點(diǎn)的調(diào)整。

2.4" 選擇與交叉

2.4.1" 選擇操作

本文選擇操作區(qū)別于傳統(tǒng)遺傳算法，為了提高交叉的多樣性，選擇所有個(gè)體進(jìn)行交叉。定義精英群體作為精英組，而其余的個(gè)體組成普通組，設(shè)計(jì)兩種選擇操作：對(duì)于普通組中的每一個(gè)體，從精英組中隨機(jī)選擇一個(gè)體進(jìn)行交叉操作生成兩個(gè)新解，并用更好的新個(gè)體替換普通組中的舊個(gè)體；對(duì)于精英組中的每一個(gè)解，當(dāng)前最優(yōu)個(gè)體進(jìn)行交叉生成兩個(gè)新解，用更好的新個(gè)體替換精英組中的舊個(gè)體。

2.4.2" 交叉操作

對(duì)于TSP編碼序列，使用順序交叉。首先在父代1和父代2中隨機(jī)選擇一個(gè)片段，讓子代1和子代2分別繼承；然后父代1和父代2從分割點(diǎn)右側(cè)開(kāi)始將其余的客戶點(diǎn)順序繼承給子代2和子代1。圖6是子代1的一個(gè)8個(gè)客戶點(diǎn)的順序交叉示例，父代1選擇（3，8，7）片段，由子代1繼承，父代2剔除相同客戶點(diǎn)，并從子代1片段右側(cè)7開(kāi)始繼承給子代1，跳過(guò)重復(fù)客戶點(diǎn)，子代2同理。

3" 實(shí)驗(yàn)仿真與分析

采用WCCI2020進(jìn)化計(jì)算競(jìng)賽中提出的CEVRP測(cè)試數(shù)據(jù)集[18]，其中，包括一組中小規(guī)模實(shí)例集，其中[Vc∈[21，100]]，[Vf∈[5，9]]，所需路徑數(shù)[Route∈[4，8]]；一組大規(guī)模實(shí)例集[Vc∈[142，1 000]]，[Vf∈[4，35]]，[Route∈[7，207]]。表1給出了這些實(shí)例集的基本信息。

lt;E：＼2025年第7期＼2025年第7期＼Image＼83t6.tifgt;

圖6" 子代1順序交叉示例

表1" CEVRP測(cè)試數(shù)據(jù)集信息

[名稱 路徑數(shù) 充電站數(shù) 客戶點(diǎn)數(shù) E22 4 8 21 E23 3 9 22 E30 4 6 29 E33 4 6 32 E51 5 5 50 E76 7 7 75 E101 8 9 100 X143 7 4 142 X214 11 9 213 X352 40 35 351 X459 26 20 458 X573 30 6 572 X685 75 25 684 X749 98 30 748 X819 171 25 818 X916 207 9 915 X1001 43 9 1 000 ]

本文通過(guò)初步實(shí)驗(yàn)為所有實(shí)例設(shè)置合理的參數(shù)，設(shè)置種群數(shù)量[m]=200，精英個(gè)體數(shù)量[E]=20，LS=5，能使得算法有較好的收斂性。參照文獻(xiàn)[20]，以最大評(píng)價(jià)次數(shù)（MaxEvals）作為算法的終止條件，[MaxEvals=25 000×Vc+1+Vf]。

對(duì)比算法采用WCCI2020 CEVRP的前三名算法，即遺傳算法（GA）、模擬退火算法（SA）、獲得第一名的變鄰域搜索（VNS）算法，以及文獻(xiàn)[18]提出的BACO算法。本文算法使用C++語(yǔ)言編程實(shí)現(xiàn)，在一臺(tái)配備8.0 GB RAM，2.2 GHz CPU的Windows 10電腦上求解實(shí)例，每個(gè)實(shí)例重復(fù)運(yùn)行20次。

3.1" 中小規(guī)模實(shí)例的實(shí)驗(yàn)比較與分析

表2是中小規(guī)模實(shí)例的實(shí)驗(yàn)結(jié)果，對(duì)比數(shù)據(jù)中最好的最優(yōu)值和平均值采用加粗顯示。

在算法尋優(yōu)性上，排名依次是HMA、VNS、BACO、GA、SA。對(duì)于三個(gè)簡(jiǎn)單的實(shí)例E22、E23、E30，五種算法都能達(dá)到最優(yōu)解，且沒(méi)有誤差，其余的實(shí)例只有HMA同時(shí)取得了最優(yōu)解。尤其對(duì)于實(shí)例E101，HMA取得了其他4種對(duì)比算法都沒(méi)有達(dá)到的最優(yōu)解。

在算法穩(wěn)定性上，排名依次是HMA、BACO、VNS、SA、GA。前3個(gè)實(shí)例，由于規(guī)模較小，五種算法對(duì)其求解穩(wěn)定沒(méi)有偏差。當(dāng)實(shí)例規(guī)模繼續(xù)擴(kuò)大，只有HMA仍能保持穩(wěn)定，HMA只有在求解實(shí)例E101時(shí)存在平均值和標(biāo)準(zhǔn)差上的極小偏差?？傮w上，HMA在求解中小規(guī)模實(shí)例上取得了最佳結(jié)果，并且具有良好的穩(wěn)定性。

3.2" 大規(guī)模實(shí)例的實(shí)驗(yàn)比較與分析

為繼續(xù)測(cè)試HMA求解大規(guī)模實(shí)例的性能，與SA、GA、VNS和BACO進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果如表3所示。

在算法尋優(yōu)性上，BACO總體排名第一，取得了對(duì)比算法中10個(gè)大規(guī)模實(shí)例中的5個(gè)最優(yōu)解，其次是HMA，取得了4個(gè)最優(yōu)解，其中最大規(guī)模的實(shí)例X1001，HMA取得了對(duì)比算法中的最好解。然后是VNS，取得了X916的最優(yōu)解。排名最后的是SA和GA。在求解X214、X351和X459時(shí)，HMA的尋優(yōu)性不及BACO，其中X351和X459客戶點(diǎn)的分布呈條狀，HMA在求解具有條狀分布的實(shí)例時(shí)效果不佳。

針對(duì)客戶點(diǎn)呈聚類分布的X573和X916，且大多數(shù)客戶點(diǎn)離配送中心較遠(yuǎn)，BACO的求解效果不佳，而HMA通過(guò)在解碼時(shí)將CEVRP分層處理，并且使用多種局部搜索策略來(lái)進(jìn)一步優(yōu)化路徑，HMA的尋優(yōu)性優(yōu)于BACO。

在算法穩(wěn)定性上，算法最穩(wěn)定的是HMA，其次是VNS，然后是BACO、SA和GA。HMA的穩(wěn)定性更好，源于HMA運(yùn)用了較多的局部搜索算子，并且所有個(gè)體都參與了交叉操作，使得算法快速收斂到局部最優(yōu)解，保持較好的穩(wěn)定性。總體來(lái)說(shuō)，HMA在求解大規(guī)模實(shí)例上也有較好的尋優(yōu)能力和算法穩(wěn)定性。

3.3" 迭代圖與路徑圖分析

圖7中方形、三角、圓形、菱形線條分別代表VNS、GA、HMA和BACO，由于SA的算法代碼和運(yùn)行數(shù)據(jù)并沒(méi)有公開(kāi)，所以并未繪制SA的迭代曲線。從圖7可以看出：HMA能取得更優(yōu)的初始解，這歸功于基于kNN的雙層解碼方法可以形成優(yōu)質(zhì)的初始解。HMA在測(cè)試的10個(gè)大規(guī)模實(shí)例上有著更快的收斂速度和較好的收斂質(zhì)量。這得益于HMA運(yùn)用了較多的局部搜索策略，并且所有個(gè)體都參與了交叉操作，使得算法快速收斂到局部最優(yōu)解。從圖7可以看出，HMA在迭代的中后階段已趨于收斂。

圖8展示了部分實(shí)例的最優(yōu)解路徑圖，分別對(duì)應(yīng)兩個(gè)小規(guī)模實(shí)例E33和E101，以及兩個(gè)大規(guī)模實(shí)例X819和X1001。

圖8a）展示了E33的最優(yōu)路徑，可以看出配送中心分布在邊緣，HMA得到的配送方案達(dá)到了最優(yōu)解840.14 km；圖8b）的E101測(cè)試結(jié)果超越了已知最優(yōu)解，行駛距離只有834.22 km，共派出了8輛電動(dòng)車進(jìn)行配送；圖8c）和圖8d）的客戶點(diǎn)較多，但HMA也達(dá)到了最優(yōu)解，表明無(wú)論問(wèn)題規(guī)模多大，HMA都能給出高質(zhì)量的配送路徑。

4" 結(jié)" 論

針對(duì)CEVRP，本文以最小化總行駛里程為優(yōu)化目標(biāo)，設(shè)計(jì)了一種混合文化基因算法進(jìn)行求解。根據(jù)問(wèn)題特征，設(shè)計(jì)了基于子問(wèn)題分解的雙層解碼方法，利用kNN啟發(fā)式獲取較高質(zhì)量的初始種群，對(duì)種群執(zhí)行變鄰域搜索，增強(qiáng)解個(gè)體的質(zhì)量，并通過(guò)Metropolis準(zhǔn)則避免算法過(guò)早陷入局部最優(yōu)；然后，對(duì)精英個(gè)體提出了三種強(qiáng)化策略，此外，使用順序交叉在不同解之間共享信息；最后，利用國(guó)際競(jìng)賽的測(cè)試數(shù)據(jù)集WCCI2020 CEVRP進(jìn)行實(shí)驗(yàn)，證明了所提出算法在求解CEVRP的有效性。

盡管如此，該算法仍然存在解碼時(shí)間消耗大、大規(guī)模求解上較早陷入局部最優(yōu)等需要改進(jìn)的問(wèn)題。未來(lái)工作考慮將HMA擴(kuò)展到求解諸如帶時(shí)間窗口等更加具有實(shí)際復(fù)雜約束場(chǎng)景的EVRP問(wèn)題。

注：本文通訊作者為陳仕軍。

參考文獻(xiàn)

[1] LO P L， MARTINI G， PORTA F， et al. The determinants of CO2 emissions of air transport passenger traffic： An analysis of Lombardy （Italy） [J]. Transport policy， 2020， 91： 108?119.

[2] HUANG X， GE J. Electric vehicle development in Beijing： An analysis of consumer purchase intention [J]. Journal of cleaner production， 2019， 216： 361?372.

[3] ZHANG H F， GE H E， YANG J L， et al. Review of vehicle routing problems： Models， classification and solving algorithms [J]. Archives of computational methods in engineering， 2022， 29： 195?221.

[4] LIN B， GHADDAR B， NATHWANI J. Deep reinforcement learning for the electric vehicle routing problem with time windows [J]. IEEE transactions on intelligent transportation systems， 2022， 23（8）： 11528?11538.

[5] BEZZI D， CESELLI A， RIGHINI G. A route?based algorithm for the electric vehicle routing problem with multiple technologies [J]. Transportation research part C： Emerging technologies， 2023， 157： 104374.

[6] 王偉權(quán)，丁鼎，顏林莎.線性充電策略下多車型電動(dòng)車輛路徑模型研究[J].系統(tǒng)仿真學(xué)報(bào)，2022，34（3）：614?623.

[7] WANG W Q， ZHAO J Y. Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations [J]. European journal of operational research， 2023， 308（2）： 929?948.

[8] BASSO R， KULCSáR B， SANCHEZ?DIAZ I， et al. Dynamic stochastic electric vehicle routing with safe reinforcement learning [J]. Transportation research part E： logistics and transportation review， 2022， 157： 102496.

[9] MONTOYA A， GUéRET C， MENDOZA J E， et al. The electric vehicle routing problem with nonlinear charging function [J]. Transportation research part B： Methodological， 2017， 103： 87?110.

[10] LEE C. An exact algorithm for the electric?vehicle routing problem with nonlinear charging time [J]. Journal of the operational research society， 2021， 72（7）： 1461?1485.

[11] 李得成，陳彥如，張宗成.基于分支定價(jià)算法的電動(dòng)車與燃油車混合車輛路徑問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐，2021，41（4）：995?1009.

[12] 黃建華，劉方翔.動(dòng)態(tài)負(fù)載下電動(dòng)汽車充電策略及路徑優(yōu)化問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2023，29（11）：3909?3921.

[13] 王偉權(quán)，丁鼎，曹淑艷.混合變鄰域搜索算法求解大規(guī)模電動(dòng)車輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)仿真學(xué)報(bào)，2022，34（4）：910?919.

[14] RASTANI S， ?ATAY B. A large neighborhood search?based matheuristic for the load?dependent electric vehicle routing problem with time windows [J]. Annals of operations research， 2021， 324： 761?793.

[15] ZHEN L， XU Z， MA C， et al. Hybrid electric vehicle routing problem with mode selection [J]. International journal of production research， 2020， 58（2）： 562?576.

[16] HIEN V Q， DAO T C， BINH H T T. A greedy search based evolutionary algorithm for electric vehicle routing problem [J]. Applied intelligence， 2023， 53（3）： 2908?2922.

[17] JIA Y H， MEI Y， ZHANG M. Confidence?based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes [J]. IEEE transactions on evolutionary computation， 2022， 26（6）： 1394?1408.

[18] JIA Y H， MEI Y， ZHANG M. A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem [J]. IEEE transactions on cybernetics， 2022， 52（10）： 10855?10868.

[19] WANG C， QIN F， XIANG X S， et al. A dual?population based co?evolutionary algorithm for capacitated electric vehicle routing problems [J]. IEEE transactions on transportation electrification， 2024， 2（10）： 2663?2676.

[20] VIDAL T. Hybrid genetic search for the CVRP： Open?source implementation and SWAP* neighborhood [J]. Computers amp; operations research， 2022， 140： 105643.

[21] 金東遙，劉敏，朱燁娜，等.基于混合遺傳搜索求解載重約束的電動(dòng)車輛路徑問(wèn)題[J].系統(tǒng)仿真學(xué)報(bào)，2024，36（11）：2528?2541.

[22] CHEN Y N， XUE J H， ZHOU Y M， et al. An efficient threshold acceptance?based multi?layer search algorithm for capacitated electric vehicle routing problem [J]. IEEE transactions on intelligent transportation systems， 2024， 25（6）： 5867?5879.

[23] BEASLEY J E. Route first—cluster second methods for vehicle routing [J]. Omega， 1983， 11（4）： 403?408.

[24] PRINS C. A simple and effective evolutionary algorithm for the vehicle routing problem [J]. Computers amp; operations research， 2004， 31（12）： 1985?2002.

作者簡(jiǎn)介：駱" 維（2000—），男，湖南岳陽(yáng)人，碩士研究生，研究方向?yàn)檐囕v路徑問(wèn)題建模與算法設(shè)計(jì)。

陳仕軍（1980—），男，湖北襄陽(yáng)人，博士研究生，副教授，研究方向?yàn)榻M合最優(yōu)化與調(diào)度算法。

吳華偉（1979—），男，湖北襄陽(yáng)人，博士研究生，教授，研究方向?yàn)殡姍C(jī)系統(tǒng)設(shè)計(jì)、故障診斷與健康管理工作。

收稿日期：2024?06?15" " " " " "修回日期：2024?07?12

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（71501064）；襄陽(yáng)市科技計(jì)劃湖北隆中實(shí)驗(yàn)室專項(xiàng)資助研究（2024KF?22）；湖北文理學(xué)院科研能力培育基金科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目（2020kypytd006）；湖北文理學(xué)院研究生創(chuàng)新計(jì)劃項(xiàng)目（YCX202421）