趙燦華， 侍洪波

（華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

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

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

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

1 問題描述及數(shù)學(xué)模型

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

2 基礎(chǔ)算法

3 AVNS 算法

在變鄰域搜索的后期，往往會(huì)出現(xiàn)在某些鄰域內(nèi)長時(shí)間無法找到更優(yōu)可行解的情況，此時(shí)對(duì)這些鄰域過多地重復(fù)搜索會(huì)降低算法的優(yōu)化效率。針對(duì)上述問題，本文提出的AVNS 算法能夠根據(jù)每個(gè)鄰域的優(yōu)化情況，自適應(yīng)調(diào)整選擇在某個(gè)鄰域進(jìn)行搜索的概率，從而減少算法在一些長時(shí)間無改進(jìn)鄰域的搜索時(shí)間，提高算法的優(yōu)化效率。AVNS 算法包括一步更新和階段更新兩種概率更新方式。

3.1 一步更新AVNS 算法

3.2 階段更新AVNS 算法

3.3 算法收斂性分析

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

4 EVRP-BTW 的初始解生成與鄰域結(jié)構(gòu)

4.1 初始解構(gòu)造

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

4.2 鄰域結(jié)構(gòu)的設(shè)計(jì)和選擇

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

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

（2）基于空間鄰近性的路徑片段交換（Segchange）?；诳臻g鄰近性的路徑片段交換的基本思想是利用路徑片段的兩個(gè)端點(diǎn)客戶的空間鄰近性，有針對(duì)性地進(jìn)行路徑片段的交換，操作示例如圖2所示。

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

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

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

圖 3 交叉操作Fig. 3 Cross operation

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

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

5 實(shí)驗(yàn)研究

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

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

表 1 車型信息Table 1 Vehicle type information

表 2 客戶樣例Table 2 Customer sample

表 3 實(shí)驗(yàn)結(jié)果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 總結(jié)與展望

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