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

王星又

（海南大學(xué)管理學(xué)院，海南 ?？?570100）

1 概述

為緩解溫室效應(yīng)，控制CO2等溫室氣體的排放，打造低碳社會(huì)，我國(guó)于2020 年9 月22 日提出雙碳戰(zhàn)略目標(biāo)。在全球范圍的交通領(lǐng)域內(nèi)，由道路運(yùn)輸導(dǎo)致的二氧化碳排放超過了總排放量的70%，各國(guó)政府和企業(yè)開始考慮用電動(dòng)物流車代替?zhèn)鹘y(tǒng)燃油車完成城市配送業(yè)務(wù)[1]。

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

本文構(gòu)建了需求不確定時(shí)帶軟時(shí)間窗的電動(dòng)物流車充電站選址與路徑規(guī)劃模型，其目標(biāo)是成本最小化，通過使用box 和budget 方法構(gòu)建需求不確定集，并使用SA-VND 算法進(jìn)行求解。

2 模型描述與建立

2.1 問題描述

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

2.2 符號(hào)說明

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

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

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

2.3 兩階段模型建立

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

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

3 SA-VND 算法設(shè)計(jì)

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

3.1 初始解的構(gòu)造

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

3.2 混合變鄰域搜索算子

在模擬退火算法的基礎(chǔ)上加入變鄰域搜索的2Opt、Insert、Swap 三個(gè)算子，通過擾動(dòng)來產(chǎn)生新鄰域結(jié)構(gòu)，提高搜索的效率和質(zhì)量。

3.3 流程圖

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

圖1 SA-VND 算法流程圖

4 實(shí)驗(yàn)案例

本案例考慮配送中心0 和20 個(gè)需求點(diǎn)，使用歐氏幾何坐標(biāo)表示各點(diǎn)位置，并生成了平均需求以及時(shí)間窗的上下界，具體數(shù)據(jù)如表1 所示。

表1 算例數(shù)據(jù)

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

通過使用SA-VND 算法進(jìn)行求解，得出本案例的最優(yōu)路線以及充電樁選址與充電模式的選擇，分別為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，快充充電站選址為點(diǎn)2、4 和13，慢充充電站選址為點(diǎn)10、12、18 和19。如圖2 所示。

圖2 車輛配送路線圖

通過圖3 可知，總行駛成本為938.384 元，在第1092 次迭代處達(dá)到收斂，為了進(jìn)一步驗(yàn)證本文算法的求解效率，對(duì)比了遺傳算法，傳統(tǒng)的模擬退火算法，粒子群算法，其CPU時(shí)間分別為7.46s、9.78s、10.23s、8.76s，成本分別為是938.38、956.22、1002.34、980.67，因此求得解的各項(xiàng)指標(biāo)均為最優(yōu)?？梢缘贸?，本文算法在求解此類問題時(shí)可行高效。

圖3 SA-VND 迭代曲線

5 結(jié)論

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