基于改進模擬退火算法的考慮混合充電模式和需求不確定下的電動物流車魯棒配送問題研究

王星又

（海南大學管理學院，海南 海口 570100）

1 概述

為緩解溫室效應，控制CO2等溫室氣體的排放，打造低碳社會，我國于2020 年9 月22 日提出雙碳戰略目標。在全球范圍的交通領域內，由道路運輸導致的二氧化碳排放超過了總排放量的70%，各國政府和企業開始考慮用電動物流車代替傳統燃油車完成城市配送業務[1]。

充電設施可分為充電站和換電站兩類，王琪瑛等[2]研究了在軟時間窗下的電動車換電站選址問題，楊磊等[1]研究了電動物流車充電和換電設施選址模型。孫世澤[3]研究了電動物流車充電設施布局與配送路徑優化的問題，李得成等[4]研究了電動車與燃油車混合車輛路徑問題。侯登凱等[5]則研究了多中心混合車隊聯合配送的路徑優化問題。Hu 等[6]考慮需求不確定使用魯棒的方法對車輛路徑問題進行研究。

本文構建了需求不確定時帶軟時間窗的電動物流車充電站選址與路徑規劃模型，其目標是成本最小化，通過使用box 和budget 方法構建需求不確定集，并使用SA-VND 算法進行求解。

2 模型描述與建立

2.1 問題描述

某配送中心有K 輛相同車型的電動物流車，車輛電池的最大容量為Q，最大載重量為W，并且勻速行駛，需求點共N 個，需求點的需求量為變動的ω～i，要求到達時間為[Ei，Li]，車輛在該時間段外到達需要支付相應的機會成本費用或懲罰費用。每輛車均從配送中心滿電出發，最終返回配送中心。受電池容量的限制，車輛中途可能需要訪問充電站并選擇快充或慢充，其充電成本與行駛距離呈線性關系。要求選擇合理的充電站位置和配送路線，使得在滿足需求的同時最小化配送成本。

2.2 符號說明

Xijk：決策變量，若車輛k 從i 行駛至j，值為1，否則為0

Yijr：決策變量，若車輛在路徑r 中選擇在i 充電，值為1，否則為0

Zijr：決策變量，若車輛在路徑r 中選擇在i 慢充，值為1，否則為0

2.3 兩階段模型建立

第一階段首先考慮無充電行為時，受載重量、需求不確定和軟時間窗等因素影響的車輛調度及路徑規劃模型。

其中，式(1)分別表示在無充電行為下的車輛用電成本，時間機會成本，懲罰成本和車輛固定成本；式(2)表示每個需求點只能由一輛車輛服務，式(3)表示每輛車從配送中心出發，最終返回配送中心，式(4)表示流守恒，進入需求點的車輛數量始終等于離開該點的車輛數；式(5)表示離開點i 的實際時間，式(6)表示到達點j 的實際時間；式(7)表示回路中每輛車訪問的需求點的需求量之和不能超過車輛的最大載重量；式(8)表示配送車輛總數；式(9)，(10)表示需求的不確定集，式(11)分別表示車輛的用電成本，時間機會成本，懲罰成本和車輛固定成本；式(13)，(15)，(16)分別表示車輛離開配送中心0，充電站n 以及到達需求點i+1 時的電量水平，式(12)表示在需求點進行服務時不消耗電量；式(17)，(18)表示離開點i 的實際時間以及到達點i+1 的實際時間；式(19)表示當離開需求點i 后的剩余電量不足以訪問下一需求點以及任何充電站時，則在該點前往充電站，否則可以繼續前往下一需求點。

3 SA-VND 算法設計

模擬退火算法是模擬金屬退火的過程，從一較高初始溫度開始，隨著溫度下降，通過使用Metropolis 法則跳出局部最優解，尋找全局最優解。變鄰域算法是通過使用不同的鄰域搜索算子，提高計算的效率與精度。傳統的模擬退火算法效率不高，加入變鄰域搜索的方法對其進行改進可提高求解效率。

3.1 初始解的構造

初始解生成步驟如下：①將n 個需求點分配給k 輛車，表示配送中心，i 表示需求點，則路徑可表示為0-i-0，一共有n 條路徑；②如果路徑0-i-0 長度超過電動車物流車的最大行駛里程則需在該需求點選擇進行充電;③在滿足最大裝載量的前提下，對已有的路徑進行合并。

3.2 混合變鄰域搜索算子

在模擬退火算法的基礎上加入變鄰域搜索的2Opt、Insert、Swap 三個算子，通過擾動來產生新鄰域結構，提高搜索的效率和質量。

3.3 流程圖

本文SA-VND 算法的流程圖如圖1 所示。

圖1 SA-VND 算法流程圖

4 實驗案例

本案例考慮配送中心0 和20 個需求點，使用歐氏幾何坐標表示各點位置，并生成了平均需求以及時間窗的上下界，具體數據如表1 所示。

表1 算例數據

假設配送中心電動物流車型號相同，其中最大續航里程為200km，最大載重量為2.5t，平均車速為80km/h，單位里程成本為0.14 元，車輛早到的單位時間機會成本為25 元/h，遲到的單位懲罰成本為45 元/小時，車輛的固定出行成本為150 元/車，電量由0%至100%快充需0.75h，慢充需4h。

通過使用SA-VND 算法進行求解，得出本案例的最優路線以及充電樁選址與充電模式的選擇，分別為0-2(快充)-13 (快充)-7-8-12 (慢充)-0，0-20-6-9-10 (慢充)-0，0-11-14-19(慢充)-0，0-15-17-5-18(慢充)-0，0-1-16-4(快充)-3-0，快充充電站選址為點2、4 和13，慢充充電站選址為點10、12、18 和19。如圖2 所示。

圖2 車輛配送路線圖

通過圖3 可知，總行駛成本為938.384 元，在第1092 次迭代處達到收斂，為了進一步驗證本文算法的求解效率，對比了遺傳算法，傳統的模擬退火算法，粒子群算法，其CPU時間分別為7.46s、9.78s、10.23s、8.76s，成本分別為是938.38、956.22、1002.34、980.67，因此求得解的各項指標均為最優。可以得出，本文算法在求解此類問題時可行高效。

圖3 SA-VND 迭代曲線

5 結論

本文綜合考慮混合充電方式與需求不確定等因素，建立路徑規劃與電樁選址的兩階段魯棒模型。本文提出了SA-VND 算法，采取三種變鄰域算子提高搜索的效率。為驗證本文模型的有效和算法的高效構建了算例，并對比了不同和算法，得出本文算法在求解此類問題時可行高效，因此本文的模型與算法具有一定的實用價值，能為相關行業提供一定參考價值。