混合文化基因算法求解帶容量約束的電動車輛路徑問題

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

關鍵詞： 電動車輛路徑問題； 混合文化基因算法； k最近鄰； 變鄰域搜索； 局部搜索； 精英保留策略

中圖分類號： TN919?34； TP301.6" " " " " " " " " 文獻標識碼： A" " " " " " " " " " "文章編號： 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" 引" 言

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

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

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

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

1" CEVRP問題及數學模型

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

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

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

1） 同一個車輛可以多次訪問同一充電站，如EV1訪問13號充電站2次；

2） 電動車可以不訪問充電站，如EV2沒有訪問任何充電站；

3） 電動車可以只訪問1次充電站，如EV3只訪問15號充電站1次；

4） 電動車可以多次訪問不同充電站，如EV4先后訪問了16號與17號充電站；

5） 不是所有充電站都需要訪問，圖1中電動車沒有訪問14號和18號充電站。

2" 混合文化基因算法

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

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

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

Step2：針對種群的每個個體TSP編碼，設計VNS框架對種群進行強化。在VNS框架中使用交換、插入和逆轉三種鄰域算子，并添加SA中的Metropolis準則避免過早陷入局部最優。

Step3：采取精英保留策略，并對精英個體采取三種策略強化：對精英個體的CVRP路徑添加Relocate、Swap和2?Opt局部搜索算子；設計一種插入充電站的簡單枚舉算法，對充電路徑有1個和2個充電站的子路徑的充電站重新調整；針對CEVRP路徑的客戶點進行優化調整。

Step4：執行選擇和交叉操作，共享個體之間的優良信息。最后，設置停止準則，可以是最大的迭代次數、評價次數、運行時間等。本文選擇最大評價次數作為算法的終止條件，即滿足最大評價次數就輸出最優解，否則，返回Step2。

2.1" 初始種群與編碼解碼

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

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

2.2" 基于VNS的種群強化

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

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

2.3" 精英個體強化

根據HMA中種群個體的目標值進行排序后，采用精英保留策略選出最優數量為[E]的個體，本文[E]等于總客戶點數的10%；然后對精英個體采取下面三種改進策略。

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

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

2.3.2" 基于FRVCP的充電站調整策略

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

算法：簡單枚舉法（SEM）

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

輸出：精細化的CEVRP子路徑[Γ]

1.計算路徑需要充電站數[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個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]表示子路徑[Γ]中的客戶點，CS代表充電站。SHM中優化一個充電站路徑的操作簡稱AdjustOneCS，優化兩個充電站路徑的操作為AdjustTwoCS。

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

AdjustTwoCS：偽代碼7～20行。將該充電站從子路徑中移除，然后確定每個CS范圍。對于具有2個CS的可行子路線，完成該路線的總電量需求應滿足2[Qb]～3[Qb]，其中[Qb]為電池容量。[CS1_a]、[CS1_b]是第1個CS范圍的上限和下限，[CS1_a]到該路徑結尾應小于[2Qb]。路徑開始到[CS1_b]的路程應小于[Qb]；[CS2_a]、[CS2_b]是第2個CS范圍的上限和下限。[CS2_a]到該路徑結尾應小于[Qb]，路徑開始到[CS2_b]小于[2Qb]。當第一個充電站確定為CS1′后，CS2應在CS1′后的[Qb]路程內，于是CS2的上限可以進一步縮小為[CS2_c]。

2.3.3" 基于CEVRP路徑的客戶點調整策略

由于CEVRP的最優解與其相應CVRP的最優解之間沒有直接的關聯性[22]，本文最后添加針對CEVRP路徑的客戶點調整策略。該策略首先生成包含所有客戶點的隨機序列，然后從序列開始依次刪除原路徑的客戶點進行枚舉插入，直到考慮到所有客戶點。該策略類似Relocate算子，與Relocate算子相比有兩點好處：每個客戶點隨機選擇，增加了算子的隨機性；可以忽略充電站只進行客戶點的調整。

2.4" 選擇與交叉

2.4.1" 選擇操作

本文選擇操作區別于傳統遺傳算法，為了提高交叉的多樣性，選擇所有個體進行交叉。定義精英群體作為精英組，而其余的個體組成普通組，設計兩種選擇操作：對于普通組中的每一個體，從精英組中隨機選擇一個體進行交叉操作生成兩個新解，并用更好的新個體替換普通組中的舊個體；對于精英組中的每一個解，當前最優個體進行交叉生成兩個新解，用更好的新個體替換精英組中的舊個體。

2.4.2" 交叉操作

對于TSP編碼序列，使用順序交叉。首先在父代1和父代2中隨機選擇一個片段，讓子代1和子代2分別繼承；然后父代1和父代2從分割點右側開始將其余的客戶點順序繼承給子代2和子代1。圖6是子代1的一個8個客戶點的順序交叉示例，父代1選擇（3，8，7）片段，由子代1繼承，父代2剔除相同客戶點，并從子代1片段右側7開始繼承給子代1，跳過重復客戶點，子代2同理。

3" 實驗仿真與分析

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

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

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

表1" CEVRP測試數據集信息

[名稱 路徑數 充電站數 客戶點數 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 ]

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

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

3.1" 中小規模實例的實驗比較與分析

表2是中小規模實例的實驗結果，對比數據中最好的最優值和平均值采用加粗顯示。

在算法尋優性上，排名依次是HMA、VNS、BACO、GA、SA。對于三個簡單的實例E22、E23、E30，五種算法都能達到最優解，且沒有誤差，其余的實例只有HMA同時取得了最優解。尤其對于實例E101，HMA取得了其他4種對比算法都沒有達到的最優解。

在算法穩定性上，排名依次是HMA、BACO、VNS、SA、GA。前3個實例，由于規模較小，五種算法對其求解穩定沒有偏差。當實例規模繼續擴大，只有HMA仍能保持穩定，HMA只有在求解實例E101時存在平均值和標準差上的極小偏差。總體上，HMA在求解中小規模實例上取得了最佳結果，并且具有良好的穩定性。

3.2" 大規模實例的實驗比較與分析

為繼續測試HMA求解大規模實例的性能，與SA、GA、VNS和BACO進行對比分析，實驗結果如表3所示。

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

針對客戶點呈聚類分布的X573和X916，且大多數客戶點離配送中心較遠，BACO的求解效果不佳，而HMA通過在解碼時將CEVRP分層處理，并且使用多種局部搜索策略來進一步優化路徑，HMA的尋優性優于BACO。

在算法穩定性上，算法最穩定的是HMA，其次是VNS，然后是BACO、SA和GA。HMA的穩定性更好，源于HMA運用了較多的局部搜索算子，并且所有個體都參與了交叉操作，使得算法快速收斂到局部最優解，保持較好的穩定性。總體來說，HMA在求解大規模實例上也有較好的尋優能力和算法穩定性。

3.3" 迭代圖與路徑圖分析

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

圖8展示了部分實例的最優解路徑圖，分別對應兩個小規模實例E33和E101，以及兩個大規模實例X819和X1001。

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

4" 結" 論

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

盡管如此，該算法仍然存在解碼時間消耗大、大規模求解上較早陷入局部最優等需要改進的問題。未來工作考慮將HMA擴展到求解諸如帶時間窗口等更加具有實際復雜約束場景的EVRP問題。

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

參考文獻

[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] 王偉權，丁鼎，顏林莎.線性充電策略下多車型電動車輛路徑模型研究[J].系統仿真學報，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] 李得成，陳彥如，張宗成.基于分支定價算法的電動車與燃油車混合車輛路徑問題研究[J].系統工程理論與實踐，2021，41（4）：995?1009.

[12] 黃建華，劉方翔.動態負載下電動汽車充電策略及路徑優化問題[J].計算機集成制造系統，2023，29（11）：3909?3921.

[13] 王偉權，丁鼎，曹淑艷.混合變鄰域搜索算法求解大規模電動車輛路徑優化問題[J].系統仿真學報，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] 金東遙，劉敏，朱燁娜，等.基于混合遺傳搜索求解載重約束的電動車輛路徑問題[J].系統仿真學報，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.

作者簡介：駱" 維（2000—），男，湖南岳陽人，碩士研究生，研究方向為車輛路徑問題建模與算法設計。

陳仕軍（1980—），男，湖北襄陽人，博士研究生，副教授，研究方向為組合最優化與調度算法。

吳華偉（1979—），男，湖北襄陽人，博士研究生，教授，研究方向為電機系統設計、故障診斷與健康管理工作。

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

基金項目：國家自然科學基金項目（71501064）；襄陽市科技計劃湖北隆中實驗室專項資助研究（2024KF?22）；湖北文理學院科研能力培育基金科技創新團隊項目（2020kypytd006）；湖北文理學院研究生創新計劃項目（YCX202421）