基于自適應變鄰域搜索的大規模電動車輛路徑優化

趙燦華， 侍洪波

（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

隨著國家對電動汽車的大力推廣，越來越多的物流車輛開始采用電動車。與常規的燃油車相比，電動車具有較低的污染排放和噪聲，但同時也面臨著續航里程短、充電時間長、充電樁少等問題[1-3]，這使得電動車輛路徑問題(Electric Vehicle Routing Problem, EVRP)的求解更加復雜。

車輛路徑問題(Vehicle Routing Problem, VRP)[4]是典型的NP-hard 問題[5]。在精確式算法研究方面，文獻[6]使用分支定界法對VRP 進行了建模求解，可求解260 點的VRP。文獻[7]使用k 度中心樹算法將原問題轉化為3 個易求解的子問題，然后進行求解。文獻[8]提出了一種節約值計算方法，能夠較好地生成車輛路徑。對于組合優化問題，精確式算法常常無法在合理的時間內給出滿意解，因此多采用啟發式算法求解。文獻[9]提出了一種反饋精英教學優化算法，通過引入反饋機制提高了算法的全局搜索能力，并將算法成功應用于背包問題。文獻[10]使用禁忌搜索算法對帶有隨機需求的動態VRP 進行了建模求解。文獻[11]針對粒子群算法容易陷入局部極值的缺陷，提出了一種多相粒子群優化算法(Multi-phases Particle Swarm Optimization,MPSO)，對帶軟時間窗的VRP 進行了建模求解。文獻[12]構造了一種求解VRP 的自適應蟻群算法，能夠有效地解決小規模的VRP。文獻[13]在充分分析了啟發式算法的基礎上，構造了新型的染色體結構及操作算子，使用遺傳算法對VRP 進行了有效求解。文獻[14]面向倉庫VRP，對禁忌搜索算法進行了改進及應用。對于大規模的VRP，由于可行解空間極大，通常使用多種搜索算法混合的策略對問題進行求解，其中變鄰域搜索(Variable Neighborhood Search，VNS)[15]是解決大規模VRP 的有效方法。文獻[16]將變鄰域搜索和禁忌搜索算法結合起來，采用動態懲罰機制，求解了帶時間窗的電動車輛路徑問題(EVRP-TW)。文獻[17]將自適應大規模鄰域搜索與變鄰域搜索算法相結合，提出了一種自適應變鄰域搜索算法求解帶中間站的EVRP，根據在不同抖動過程中的搜索表現來自適應調整抖動的鄰域算子選擇。文獻[18]使用變鄰域搜索對三維裝箱問題下的VRP 進行了求解。文獻[19]研究了部分充電的EVRP-TW，提出了一種變鄰域搜索分支的元啟發式算法。文獻[20]使用了一種改進的變鄰域搜索算法對客戶規模達到兩萬的超大規模VRP 進行求解，其中利用引導局部搜索算法來跳出局部最優。文獻[21]提出了兩種并行協作方案，使用了一種協作自適應變鄰域搜索算法求解了多車場帶時間窗的VRP。文獻[22]對混合車型的帶時間窗的VRP 進行了建模，并使用反應式變鄰域搜索算法進行了求解。

本文以京東物流為案例背景，對大規模帶時間窗可回程取貨的電動車輛路徑問題（Electric Vehicle Routing Problem with Backhauls and Time Window,EVRP-BTW）進行了建模分析。利用客戶時間窗、地理位置等信息構造了高效的初始解生成算法；針對傳統變鄰域搜索算法在后期出現優化效率降低的情況，提出了一種高效的自適應變鄰域搜索算法(Adaptive Variable Neighborhood Search，AVNS)，設計了新的鄰域搜索算子，并結合經典的2-opt、Relocation、Cross-change 等算子進行了變鄰域搜索。最后，使用不同規模的實際脫敏數據驗證了本文算法的有效性。

1 問題描述及數學模型

上述模型中，式(1)為目標函數；式(2)表明所有的客戶需要被訪問；式(3)保證了每名客戶只能被一輛車服務一次；式(4)、式(5)分別為車輛上午送貨行駛路徑的質量和體積約束；式(6)、式(7)分別為車輛下午取貨行駛路徑的質量和體積約束；式(8)為電動車輛的里程約束，保證了車輛能夠在電量耗盡之前到達下一個充電站；式(9)為每個客戶的服務時間窗約束。

2 基礎算法

3 AVNS 算法

在變鄰域搜索的后期，往往會出現在某些鄰域內長時間無法找到更優可行解的情況，此時對這些鄰域過多地重復搜索會降低算法的優化效率。針對上述問題，本文提出的AVNS 算法能夠根據每個鄰域的優化情況，自適應調整選擇在某個鄰域進行搜索的概率，從而減少算法在一些長時間無改進鄰域的搜索時間，提高算法的優化效率。AVNS 算法包括一步更新和階段更新兩種概率更新方式。

3.1 一步更新AVNS 算法

3.2 階段更新AVNS 算法

3.3 算法收斂性分析

文獻[23]對VNS 算法的全局收斂性進行了論證說明，本文AVNS 算法的鄰域結構以及抖動的過程與VNS 算法完全一致。由于設置了最小鄰域選擇概率，AVNS 算法在收斂到全局最優解之前，每次迭代后的改進概率可以始終保證大于0，故AVNS 算法的全局收斂性依舊可由文獻[23]中關于VNS 算法的全局收斂性證明方法得出。圖1 為一步更新和階段更新方式下的AVNS 算法流程圖。

4 EVRP-BTW 的初始解生成與鄰域結構

4.1 初始解構造

圖 1 AVNS 算法流程圖Fig. 1 Flow chart of AVNS algorithm

4.2 鄰域結構的設計和選擇

在進行自適應變鄰域搜索時，按照送取貨路徑片段交換、基于空間鄰近性的路徑片段交換、2-opt 算子、Cross 算子以及Relocation 算子的鄰域順序進行搜索，同時這些鄰域也在抖動過程中使用。在使用鄰域算子對路徑進行變換之前，會先刪除路徑中的充電站；完成變換后，使用4.1 節的充電策略將充電站插入到變換后的路徑中，最后計算得出變換前后的成本變化。

（1）送取貨路徑片段交換（Part-change）。送取貨路徑片段交換是指利用車輛上午送貨、下午回程取貨的特點，隨機選取已生成的兩條路徑，將兩條路徑各自上、下午的行駛路徑進行交換，若交換后的兩條路徑均路徑合法且總成本下降，則進行路徑覆蓋；否則，取消交換。

（2）基于空間鄰近性的路徑片段交換（Segchange）。基于空間鄰近性的路徑片段交換的基本思想是利用路徑片段的兩個端點客戶的空間鄰近性，有針對性地進行路徑片段的交換，操作示例如圖2所示。

圖 2 路徑片段交換Fig. 2 Route segment exchange

（3）2-opt 算子。2-opt 算子是指隨機地選擇兩條路徑，從兩條路徑中各自選擇一個客戶進行互換，若交換后的路徑合法且總成本出現下降，則進行路徑覆蓋；否則，取消交換。

（4）Cross 算子。在Cross 算子中，先隨機選擇兩條路徑，然后從兩條路徑中各自選擇一個客戶作為路徑的斷點，每一條路徑被分成了兩段，最后進行交叉，操作示例如圖3 所示。

圖 3 交叉操作Fig. 3 Cross operation

（5）Relocation 算子。Relocation 是指從一條路徑中隨機選擇一個客戶，隨機地插入到其他路徑中的某個客戶之前，若執行上述操作后的路徑合法且總成本出現下降，則進行路徑覆蓋；否則，不進行插入操作。操作示例如圖4 所示。

圖 4 重定位操作Fig. 4 Relocation operation

5 實驗研究

以京東某城配物流中心已脫敏的實際數據作為實驗數據。城配物流中心每天要使用電動車輛為分布在本城區的1 000 余名客戶進行城市配送。本文分別對客戶規模為1 100、1 200、1 300、1 400、1 500的數據進行了實驗分析，充電站的數量為200 個，每小時充電成本為100 元，每小時等待成本為24 元，最早發車時間為早上8 點，回配送中心最晚時間為當日24 點，充電站里的充電樁沒有數量限制。具體的車型信息以及客戶樣例如表1、表2 所示。

由實驗結果可以看出，蟻群算法計算效率較低，較容易陷入局部最優，故效果較差；而使用模擬退火算法進行仿真時，由于充分利用了本文提出的鄰域結構，因此其優化結果VNS 較為接近；一步更新AVNS 算法和階段更新AVNS 算法的結果最好，從5 種客戶規模優化后的最終成本的角度分析，兩種概率更新方式下的AVNS 算法的性能表現沒有顯著差別。

表 1 車型信息Table 1 Vehicle type information

表 2 客戶樣例Table 2 Customer sample

表 3 實驗結果Table 3 Experimental result

圖 5 一步更新AVNS 下的選擇概率收斂曲線Fig. 5 Select probability vector convergence curves under one step update

圖 6 階段更新AVNS 下的選擇概率收斂曲線Fig. 6 Select probability vector convergence curves under phase update

6 總結與展望

本文提出了一種有效的自適應變鄰域搜索算法，在算法中為每個鄰域都設置了一個選擇概率，并使用一步更新和階段更新兩種方式對選擇概率向量進行了更新，提高了算法優化效率。該算法部署方便，具有較強的通用性。建立了大規模帶時間窗可回程取貨的電動車輛路徑問題的數學模型，利用時間窗寬度、客戶地理位置等信息生成了高質量的初始解；使用2-opt、Relocation、Cross-change 等算子進行了自適應變鄰域搜索。通過對5 組不同客戶規模的實際脫敏數據的仿真計算表明，AVNS 算法能夠更有效地降低物流成本，驗證了算法的有效性。