動(dòng)態(tài)負(fù)載下電動(dòng)汽車充電策略及路徑優(yōu)化問(wèn)題

黃建華,劉方翔

(福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院,福建 福州 350116)

0 引言

使用新能源汽車替代傳統(tǒng)燃油汽車,是降低我國(guó)運(yùn)輸行業(yè)碳排放水平和減少環(huán)境污染的重要措施,也是我國(guó)實(shí)現(xiàn)“碳中和”和“碳達(dá)峰”目標(biāo)的重要手段。但是,現(xiàn)階段電動(dòng)汽車配送存在續(xù)航里程有限、充電時(shí)間較長(zhǎng)、充電裝置建設(shè)不足等問(wèn)題,使得物流企業(yè)在配送方案設(shè)計(jì)時(shí)需要面臨更多的約束條件,同時(shí),也極大地增加了電動(dòng)汽車配送路徑優(yōu)化問(wèn)題的求解難度。因此,在考慮電動(dòng)汽車負(fù)載影響其耗電速率的前提下,探討電動(dòng)汽車的不完全充電策略以及如何求解復(fù)雜的配送路徑優(yōu)化問(wèn)題,具有重要的現(xiàn)實(shí)意義。

電動(dòng)汽車的充電策略問(wèn)題是近年來(lái)研究的熱點(diǎn)。李明等[1]在出行路徑選擇、充電和放電狀態(tài)互斥以及有限續(xù)航等約束條件下,分別以出行時(shí)間和充電成本為目標(biāo),對(duì)電動(dòng)汽車的行駛路徑和充電策略進(jìn)行優(yōu)化。DESAULNIERS等[2]從每條路徑上的允許充電次數(shù)和充電量的角度出發(fā),提出4種不同的電動(dòng)汽車充電策略,并經(jīng)案例研究表明每條路徑上允許多次充電且允許部分充電的策略有助于降低物流成本。在此基礎(chǔ)上,葛顯龍等[3]將部分充電策略引入電動(dòng)汽車配送路徑優(yōu)化問(wèn)題,建立以物流成本和充電成本最小為目標(biāo)的電動(dòng)汽車配送路徑優(yōu)化模型,證明了部分充電策略的優(yōu)越性,其研究結(jié)果表明,在充電設(shè)施不足的情況下,充電等待時(shí)間越長(zhǎng),部分充電策略的優(yōu)勢(shì)越明顯。

電動(dòng)汽車配送路徑優(yōu)化問(wèn)題的相關(guān)文獻(xiàn),則更多聚焦電動(dòng)汽車的特點(diǎn)對(duì)路徑優(yōu)化結(jié)果的影響[4]。例如:郭放等[5]在研究電動(dòng)汽車的配送問(wèn)題時(shí),重點(diǎn)關(guān)注了電動(dòng)物流車的電池?fù)p耗問(wèn)題,并將車輛繞行充電的時(shí)間及電池?fù)p耗成本納入規(guī)劃模型的目標(biāo)函數(shù)中;LIN等[6]將車輛負(fù)載對(duì)電量消耗的影響作為約束條件,并以行駛成本和能源成本最小為目標(biāo),對(duì)電動(dòng)車輛路徑問(wèn)題(Electric Vehicle-Routing Problem,EVRP)進(jìn)行了研究,揭示了車輛負(fù)載變化對(duì)車輛路徑規(guī)劃結(jié)果的影響較為顯著;KANCHARLA等[7]在考慮負(fù)載變化對(duì)車輛續(xù)航里程影響的基礎(chǔ)上,構(gòu)建了以行駛距離最小為目標(biāo)的EVRP模型,并針對(duì)模型的復(fù)雜特征,探討了具有自適應(yīng)鄰域搜索特征的求解算法;劉玉良等[8]認(rèn)為車輛負(fù)載會(huì)影響電動(dòng)汽車的實(shí)時(shí)能耗,并以此為前提,進(jìn)一步分析了電動(dòng)汽車的配送路徑優(yōu)化和充電策略。此外,CONRAD等[9]發(fā)現(xiàn),電動(dòng)汽車的配送路徑還受到客戶時(shí)間窗約束的影響。

由于電動(dòng)物流車路徑優(yōu)化模型具有更高的復(fù)雜性,因此,現(xiàn)有文獻(xiàn)更多地采用智能算法或者啟發(fā)式算法進(jìn)行求解。例如:葛顯龍等[3]在求解電動(dòng)車汽車配送路徑問(wèn)題時(shí),將遺傳算法和模擬退火算法相結(jié)合,設(shè)計(jì)了一種兼顧GA全局搜索能力和SA局部搜索能力的混合啟發(fā)式求解算法;郭放等[5]針對(duì)充電策略與電池?fù)p耗影響下的電動(dòng)汽車路徑優(yōu)化模型,設(shè)計(jì)了MCWIGALNS求解算法,該算法融合了改進(jìn)節(jié)約算法、迭代貪婪算法和自適應(yīng)大領(lǐng)域搜素算法的優(yōu)點(diǎn);針對(duì)求解帶時(shí)間窗約束的EVRP問(wèn)題,SCHNEIDER等[10]設(shè)計(jì)了變鄰域搜索算法(Variable Neighborhood Search,VNS)和禁忌搜索算法(Tabu Search,TS)相結(jié)合的混合啟發(fā)式求解算法;劉玉良等[8]等針對(duì)EVRP具有車輛負(fù)載和客戶時(shí)間窗要求的特點(diǎn),引入了時(shí)間緊迫因子,并對(duì)轉(zhuǎn)移概率和信息素更新進(jìn)行了重新定義,并以此為基礎(chǔ),設(shè)計(jì)了求解的改進(jìn)蟻群算法;顧青等[11]設(shè)計(jì)了新的啟發(fā)式能耗預(yù)估代價(jià)對(duì) A*算法進(jìn)行改進(jìn),并應(yīng)用其尋找可達(dá)的能耗最小路徑。此外,針對(duì)充電自動(dòng)引導(dǎo)車的調(diào)度問(wèn)題,李崢?lè)宓萚12]根據(jù)實(shí)際工件分配及任務(wù)分配特點(diǎn),從染色體編碼及解碼兩個(gè)角度對(duì)遺傳算法進(jìn)行改進(jìn),使算法的尋優(yōu)能力及收斂速度得到明顯提升。

綜上可知,當(dāng)前文獻(xiàn)更多是從充電策略或負(fù)載變化的視角對(duì)電動(dòng)汽車配送路徑優(yōu)化問(wèn)題進(jìn)行研究。實(shí)際上,電動(dòng)汽車配送過(guò)程中需要綜合考慮車輛負(fù)載對(duì)充電速率的影響、充電策略對(duì)優(yōu)化結(jié)果的影響、客戶需求的時(shí)間窗約束等一系列問(wèn)題,但現(xiàn)有文獻(xiàn)鮮有對(duì)該問(wèn)題進(jìn)行集成化研究。此外,從研究方法來(lái)看,現(xiàn)有成果在構(gòu)造求解帶時(shí)間窗的電動(dòng)車輛路徑問(wèn)題(Electric Vehicle-Routing Problem with Time Windows,EVRPTW)問(wèn)題的啟發(fā)式算法時(shí),忽略了充電站編碼對(duì)解的搜索空間和搜索效率的影響。鑒于此,本文將在構(gòu)建電動(dòng)車路徑優(yōu)化模型的過(guò)程中,綜合考慮充電策略、車輛負(fù)載變化以及時(shí)間窗約束等因素的影響,并探討設(shè)計(jì)求解該復(fù)雜模型的改進(jìn)混合遺傳退火算法。

1 問(wèn)題及模型

1.1 模型假設(shè)

在利用電動(dòng)汽車進(jìn)行物資配送時(shí),車輛負(fù)載會(huì)直接影響耗電速率,間接影響配送路徑。因此,本文主要研究的問(wèn)題是在車輛負(fù)載動(dòng)態(tài)變化、電池容量有限及服務(wù)需求時(shí)間窗限制的情況下,如何選擇合理的充電策略及配送路徑,使得貨物配送在滿足客戶時(shí)間窗約束的同時(shí)配送成本最低。考慮充電策略的電動(dòng)汽車貨物配送網(wǎng)絡(luò)如圖1所示。

1.2 模型假設(shè)與變量說(shuō)明

1.2.1 模型假設(shè)

(1)配送車輛駛出配送中心時(shí),電池處于滿電狀態(tài);

(2)配送車輛僅配送單種貨物;

(3)配送過(guò)程中客戶的需求一次滿足;

(4)配送車輛的規(guī)格統(tǒng)一;

(5)配送車輛的充電時(shí)間與充電量成線性關(guān)系;

(6)各個(gè)充電站的訪問(wèn)次數(shù)不受限制;

(7)配送車輛完成配送任務(wù)后需返回配送中心;

(8)整個(gè)配送過(guò)程全程不考慮其他特殊因素(如交通擁堵、車輛故障等)影響且行駛速度恒定;

(9)配送車輛駛出配送中心的時(shí)間從0時(shí)開(kāi)始計(jì)算;

(10)配送網(wǎng)絡(luò)中每條行駛路線的路面的坡度均為0;

(11)配送車輛在每個(gè)需求點(diǎn)的服務(wù)時(shí)間相等;

(12)配送車輛的耗電速率受負(fù)載量影響,且可以用負(fù)載—耗電速率模型表示。

1.2.2 符號(hào)與變量說(shuō)明

(1)參數(shù)符號(hào)說(shuō)明

0為配送中心;

N為客戶點(diǎn)的集合,N={1,2,3,...,n};

K為使用車輛的集合,K={1,2,3,...,k};

F為充電站點(diǎn)的集合,F={1,2,3,...,f};

V為全部節(jié)點(diǎn)的集合,V=0∪N∪F;

Vk為車輛k行駛路徑節(jié)點(diǎn)集合;

dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離;

pi為客戶點(diǎn)i的需求量;

C為車輛的最大裝載容量;

Cijk為車輛k從節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j時(shí)的負(fù)載量;

Q為車輛的總電池容量;

ei為客戶節(jié)點(diǎn)i的最早服務(wù)時(shí)間,i∈N;

li為客戶節(jié)點(diǎn)i的最晚服務(wù)時(shí)間,i∈N;

tωi為車輛在客戶節(jié)點(diǎn)i的等待時(shí)間,i∈N;

tfi為車輛在節(jié)點(diǎn)i的服務(wù)時(shí)間,i∈N;

tci為車輛在充電站i的充電時(shí)間,i∈F;

tij為車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間,i,j∈V;

v為車輛的行駛速度;

g為電池充電系數(shù);

epu為車輛到達(dá)時(shí)間早于左時(shí)間窗的單位懲罰成本;

lpu為車輛到達(dá)時(shí)間晚于右時(shí)間窗的單位懲罰成本;

c0為單位車輛的固定成本;

c1為單位距離成本;

c2為單位電量充電成本;

S為車輛行駛速度;

(2)決策變量說(shuō)明

1.3 電動(dòng)汽車負(fù)載與耗電速率關(guān)系模型構(gòu)建

實(shí)際配送中,電動(dòng)汽車的耗電速率受負(fù)載量、行駛環(huán)境等因素影響,參考文獻(xiàn)[8]構(gòu)建動(dòng)態(tài)負(fù)載下電動(dòng)汽車耗電速率模型如下:

(1)

式(1)表示動(dòng)態(tài)負(fù)載下車輛耗電速率計(jì)算,式中:Pijk表示車輛k從節(jié)點(diǎn)i前往節(jié)點(diǎn)j過(guò)程中的電量消耗系數(shù);m為車重;gr為重力常量;ρ為空氣密度;A為迎風(fēng)面積;Cd為空氣動(dòng)力阻力系數(shù);Cr為滾動(dòng)阻力系數(shù);ε為車輛傳動(dòng)系效率。

1.4 不完全充電策略模型構(gòu)建

區(qū)別于完全充電策略,不完全充電策略下電動(dòng)汽車在配送過(guò)程中每次充電時(shí)的充電量并非電池剩余容量,而是根據(jù)其后續(xù)服務(wù)所需耗電量進(jìn)行決策,因此根據(jù)實(shí)際配送情況構(gòu)建不完全充電策略模型如下:

?k∈K,?j∈F∪Vk,?i,l,m,n∈N∪Vk;

(2)

(3)

s.t

(4)

(5)

(6)

其中:式(2)表示車輛k在充電站j后服務(wù)該路線余下節(jié)點(diǎn)所需總電量;式(3)表示車輛k從節(jié)點(diǎn)i前往充電站j進(jìn)行充電時(shí)的充電量;式(4)表示車輛在充電站j進(jìn)行充電的充電時(shí)間;式(5)和式(6)表示對(duì)服務(wù)節(jié)點(diǎn)順序進(jìn)行約束,即i,l,m表示車輛k配送路徑上服務(wù)客戶節(jié)點(diǎn)的先后順序。

1.5 EVRPTW模型構(gòu)建

在構(gòu)建電動(dòng)汽車負(fù)載變化與耗電速率關(guān)系模型的基礎(chǔ)上,構(gòu)建EVRPTW優(yōu)化模型:

(7)

s.t.

(8)

(9)

(10)

(11)

?i∈V,?j∈V,i≠j,k∈K;

(12)

0≤h0k≤C,k∈K;

(13)

qj≤q0-p0jd0jx0j+Q(1-x0j),?j∈V;

(14)

?i∈V,?j∈V,i≠j,k∈K;

(15)

(16)

?i∈N,?j∈F,k∈K;

(17)

(18)

(19)

(20)

(21)

(22)

2 混合遺傳退火算法設(shè)計(jì)

2.1 算法改進(jìn)與創(chuàng)新

(1)采用Striniras提出的自適應(yīng)公式對(duì)遺傳交叉及變異概率進(jìn)行改進(jìn),使求解質(zhì)量隨著迭代結(jié)果的更新而不斷提高。

(2)引入貪心3父代交配(Parents Mating,PM)交叉算子對(duì)傳統(tǒng)遺傳交叉操作進(jìn)行改進(jìn),進(jìn)一步提高搜索效率。

(3)利用退火選擇算法決定所產(chǎn)生的子代是否替代父代,使算法避免陷入局部最優(yōu)。

(4)設(shè)計(jì)充電站變異操作,將充電站的基因記錄位置并提取出來(lái),獨(dú)自進(jìn)行變異操作進(jìn)而避免劣解的產(chǎn)生。

(5)利用模擬退火算法對(duì)遺傳算法求得的全局解進(jìn)行局部尋優(yōu)。

改進(jìn)后的算法框架如圖2所示。

2.2 參數(shù)設(shè)置

初始化遺傳算法及模擬退火算法的各項(xiàng)參數(shù),如自適應(yīng)交叉概率涉及的pc1、pc2,自適應(yīng)變異概率涉及的pm1、pm2,終止迭代次數(shù)maxgen,種群數(shù)量N,初始溫度t,結(jié)束溫度tf,降溫系數(shù)hy,遺傳代溝gap等。

2.3 編碼設(shè)計(jì)

本文根據(jù)EVRPTW的問(wèn)題特性,采用自然數(shù)編碼的方式,即問(wèn)題中的配送中心、客戶點(diǎn)以及充電站點(diǎn)都有各自對(duì)應(yīng)的自然數(shù),染色體則由這些代表不同節(jié)點(diǎn)的自然數(shù)構(gòu)成,設(shè)定配送中心的編碼為0,客戶需求點(diǎn)的編碼為1,2,3,4,…,n;充電站的編碼為n+1,n+2,…,n+f。

2.4 種群初始化

在確定編碼形式的基礎(chǔ)上,本文采用掃描算子進(jìn)行初始種群的生成,從而提高初始種群的質(zhì)量,具體步驟如下:

步驟1獲取各節(jié)點(diǎn)位置信息,建立以配送中心為原點(diǎn)的極坐標(biāo)系,將其余節(jié)點(diǎn)置于該坐標(biāo)系中,利用下式求出各個(gè)節(jié)點(diǎn)與極坐標(biāo)X軸的夾角θi,集合為G={θ1,θ2,...,θn}。

(23)

其中(ox,oy)表示配送中心的坐標(biāo)數(shù)據(jù),(xi,yi)表示客戶需求節(jié)點(diǎn)的坐標(biāo)數(shù)據(jù),R為各個(gè)客戶節(jié)點(diǎn)到配送中心的距離。

步驟2按照升序?qū)進(jìn)行排列,從而生成一條涵蓋配送中心及客戶需求節(jié)點(diǎn)的初始染色體。

步驟3利用randi函數(shù)生成[0,n]內(nèi)的自然數(shù),對(duì)染色體相應(yīng)位置的基因?qū)φ{(diào),產(chǎn)生新的染色體。

步驟4進(jìn)行配送車輛分配、充電站的插入操作,生成符合條件的種群個(gè)體。

步驟5重復(fù)步驟3和步驟4生成初始種群。

步驟6刪除種群中重復(fù)個(gè)體并補(bǔ)齊。

2.5 適應(yīng)度函數(shù)設(shè)計(jì)

2.6 遺傳操作

(1)選擇操作 本文根據(jù)生成的初始種群的個(gè)體的適應(yīng)度值大小,采用經(jīng)典的輪盤(pán)賭算法進(jìn)行父代染色體的選擇,這種算法會(huì)使得適應(yīng)度值越高的個(gè)體被選作父代的概率越大。

(2)貪心3PM交叉 為了避免產(chǎn)生劣解影響算法搜索效率,在交叉前剔除配送中心及充電站基因,每次選擇3個(gè)父代,運(yùn)用貪心思想對(duì)3個(gè)父代進(jìn)行雙向輪轉(zhuǎn)交叉操作,最終產(chǎn)生兩個(gè)子代,具體流程如下:

1)第一個(gè)子代的產(chǎn)生:

步驟1利用輪盤(pán)賭的方法選擇3個(gè)父代個(gè)體

父代1:12345678;

父代2:87645321;

父代3:43127865。

步驟2利用randi函數(shù)隨機(jī)產(chǎn)生成一個(gè)自然數(shù)作為子代的第一個(gè)基因,假設(shè)為3,3號(hào)節(jié)點(diǎn)為標(biāo)準(zhǔn)節(jié)點(diǎn)。

步驟3向左輪轉(zhuǎn)節(jié)點(diǎn),將3個(gè)父代的當(dāng)前節(jié)點(diǎn)統(tǒng)一為步驟2生產(chǎn)的標(biāo)準(zhǔn)節(jié)點(diǎn)。

本例一次輪轉(zhuǎn)后如下:

父代1:34567812;

父代2:32187645;

父代3:31278654。

步驟4判斷節(jié)點(diǎn)3與節(jié)點(diǎn)4、2、1之間的距離,假設(shè)節(jié)點(diǎn)3到節(jié)點(diǎn)4的距離最短,則取標(biāo)準(zhǔn)城市為4,當(dāng)前位置加1,回到步驟2繼續(xù)輪轉(zhuǎn),累積執(zhí)行n-1次,最終生成新的個(gè)體。

2)第二個(gè)子代的產(chǎn)生:同樣將3號(hào)作為第一個(gè)城市并進(jìn)行向右輪轉(zhuǎn)。

(3)退火選擇算法 從3個(gè)父代中隨機(jī)挑選兩個(gè)父代,分別計(jì)算適應(yīng)度值fit(p1)和fit(p2),然后再計(jì)算兩個(gè)子代的適應(yīng)度值fit(s1)和fit(s2)及當(dāng)前退火溫度t,具體選擇流程如圖3所示。

(4)變異操作 分別對(duì)客戶點(diǎn)、充電站點(diǎn)進(jìn)行獨(dú)立變異,均通過(guò)randperm函數(shù)產(chǎn)生2個(gè)[1,N]之間不同的自然數(shù)z1和z2,最后將父代中兩個(gè)自然數(shù)對(duì)應(yīng)的基因信息進(jìn)行交換,具體操作如圖4所示。

(5)自適應(yīng)的交叉概率和變異概率 為了讓算法適應(yīng)尋優(yōu)的不同時(shí)期,提高魯棒性,本文引入的自適應(yīng)交叉概率和變異概率公式如下:

(24)

其中:fmax為種群中最優(yōu)個(gè)體的fit;favg為平均適應(yīng)度值,即種群適應(yīng)度總和/個(gè)體數(shù),f′為最優(yōu)父代的適應(yīng)度值;f為進(jìn)行變異的父代的適應(yīng)度值,一般pc1=0.9,pc2=0.6,pm1=0.1,pm2=0.001,針對(duì)不同問(wèn)題可相應(yīng)調(diào)整。

(6)逆轉(zhuǎn)操作 為了進(jìn)一步提高算法的局部尋優(yōu)能力,引入逆轉(zhuǎn)操作,具體操作如圖5所示。

(7)終止條件 當(dāng)條件滿足循環(huán)代數(shù)等于maxgen或滿足連續(xù)30代種群中最優(yōu)個(gè)體不變則終止遺傳循環(huán),否則每次循環(huán)結(jié)束后當(dāng)前循環(huán)代數(shù)加1,當(dāng)前溫度t=t×hy。

2.7 模擬退火操作

模擬退火操作是在遺傳算法操作尋得全局近似最優(yōu)解的基礎(chǔ)上,將其結(jié)果作為初始解,并且初始溫度使用的是遺傳算法執(zhí)行結(jié)束后的溫度tend,其余參數(shù)不變。

(1)鄰域操作 本文引入4種常見(jiàn)的鄰域搜索算子即逆序鄰域搜索算子、1-opt交換搜索算子、2-opt交換搜索算子以及3-opt交換搜索算子,并采用randi函數(shù)和switch函數(shù)在尋優(yōu)過(guò)程中隨機(jī)選擇4種算子中的一種,其中1-opt交換搜索算子與逆序鄰域搜索算子見(jiàn)前面圖3和圖4,1-opt交換搜索算子和3-opt交換搜索算子具體操作流程如下圖6和圖7所示。

(3)終止條件 當(dāng)T

3 實(shí)例驗(yàn)證

為檢驗(yàn)上述模型及算法的有效性,本文以福州市海峽農(nóng)副產(chǎn)品交易市場(chǎng)的A生鮮企業(yè)的電動(dòng)車配送業(yè)務(wù)為例,使用改進(jìn)的混合遺傳退火算法對(duì)其路徑優(yōu)化問(wèn)題進(jìn)行求解。

3.1 基礎(chǔ)數(shù)據(jù)

通過(guò)實(shí)地調(diào)研獲得算例相關(guān)數(shù)據(jù)如表1～表3所示,客戶需求點(diǎn)、配送中心以及充電站點(diǎn)的地理位置分布如圖8所示,實(shí)例涉及的節(jié)點(diǎn)之間距離均來(lái)自于谷歌地圖的實(shí)際地理數(shù)據(jù),圖中圓形圖示代表各個(gè)客戶需求點(diǎn)位置,五邊形圖代表配送中心的位置,正方形圖示為充電站點(diǎn)的位置,總計(jì)有27個(gè)客戶需求點(diǎn),1個(gè)配送中心,4個(gè)充電站點(diǎn)。

表1 電動(dòng)車車型參數(shù)表

表2 客戶及配送中心節(jié)點(diǎn)詳細(xì)信息

表3 充電站節(jié)點(diǎn)詳細(xì)信息

模型參數(shù)設(shè)置:電動(dòng)汽車行駛速度為v=60km/h,迎風(fēng)面積A=3.6m2,空氣動(dòng)力助力系數(shù)Cd=0.3,滾動(dòng)阻力系數(shù)Cr=0.01,車輛傳動(dòng)系效率ε=0.8,重力常量g=9.8,電池充電系數(shù)Cspeed=60kW/h,單位充電價(jià)格為Cprice=60元/h,單位里程行駛成本為0.4元,左時(shí)間窗懲罰系數(shù)β=0.05,右時(shí)間窗懲罰系數(shù)θ=0.1,違反容量約束的懲罰系數(shù)α=100。

算法參數(shù)設(shè)置:初始種群規(guī)模N=200,終止迭代次數(shù)maxgen=1 000,自適應(yīng)交叉概率參數(shù)pc1=0.9,pc2=0.7,自適應(yīng)變異概率參數(shù)pm1=0.1,pm2=0.001,充電站變異概率CPm=0.2,遺傳代溝gap=0.9,初始溫度t=1,降溫系數(shù)hy=0.999,遺傳循環(huán)結(jié)束溫度tf=0.3。

3.2 運(yùn)算結(jié)果分析

3.2.1 不同充電策略運(yùn)算結(jié)果對(duì)比

考慮動(dòng)態(tài)負(fù)載情形,采用改進(jìn)混合遺傳退火算法對(duì)兩種不同充電策略下的電動(dòng)汽車配送路徑優(yōu)化問(wèn)題進(jìn)行研究,運(yùn)算結(jié)果如圖9和圖10、表4和表5所示。

表4 兩種不同充電策略下配送路徑及充電位置對(duì)比

表5 兩種不同充電策略運(yùn)算結(jié)果對(duì)比

由表3、表4,以及圖9、圖10可以看出,由于受到車輛荷載和客戶時(shí)間窗的約束,采用兩種不同充電策略所需車輛數(shù)相同,配送路徑相似。與完全充電策略相比,在第三條配送路徑上采用不完全充電策略的行駛距離略短,充電率僅為14.61%,節(jié)省了75.6%的充電時(shí)間,進(jìn)而減少了該路徑上違反客戶時(shí)間窗約束的需求點(diǎn)數(shù)量,最終使總時(shí)間窗懲罰成本和總配送費(fèi)用分別降低了12%和9.3%。

由此可以看出,使用電動(dòng)汽車進(jìn)行配送時(shí),采用不完全充電策略不僅可以節(jié)約充電時(shí)間,避免車輛剩余電量浪費(fèi),還能在有效提高客戶時(shí)間滿意度的同時(shí)降低總配送成本。

3.2.2 算法尋優(yōu)能力對(duì)比

對(duì)改進(jìn)混合遺傳退火算法和經(jīng)典遺傳算法的求解結(jié)果進(jìn)行對(duì)比,如圖11～圖14所示。

運(yùn)算結(jié)果顯示,在兩種不同的充電策略下,采用改進(jìn)的混合遺傳退火算法的搜索效率及解的質(zhì)量均優(yōu)于經(jīng)典遺傳算法。這是因?yàn)橐?PM貪心算子和充電站變異算子,拓展了算法搜尋解的空間,進(jìn)而提高解的質(zhì)量;而利用退火選擇思想決定交叉/變異后的子代是否替代父代,改善了算法快速跳出局部最優(yōu)的能力,改進(jìn)后的算法在兩種策略下均能在200代左右達(dá)到最優(yōu)解附近,而傳統(tǒng)的算法則分別在400代和300代左右逼近最優(yōu)解;同時(shí)采用自適應(yīng)交叉/變異概率使得算法的各項(xiàng)操作可以針對(duì)不同階段的種群作出靈活的調(diào)整,從而提高了算法的尋優(yōu)效率。

3.2.3 敏感性分析

由于客戶服務(wù)具有時(shí)間窗限制,若違反時(shí)間窗限制,則會(huì)給企業(yè)帶來(lái)相應(yīng)的懲罰費(fèi)用以及對(duì)客戶服務(wù)產(chǎn)生負(fù)面影響,本文針對(duì)兩種充電策略下的時(shí)間窗懲罰系數(shù)進(jìn)行敏感性分析,求解結(jié)果如表6所示。

表6 不同時(shí)間窗懲罰系數(shù)下的結(jié)果對(duì)比

由表6可知,隨著時(shí)間窗懲罰系數(shù)不斷增大,采用兩種充電策略的時(shí)間窗懲罰費(fèi)用都不斷提高。但通過(guò)兩種策略的時(shí)間窗懲罰費(fèi)用差值這一列可以看出,隨著懲罰系數(shù)增大,采用不完全充電策略的配送方案的時(shí)間窗懲罰費(fèi)用增幅要小于完全充電策略,這表明客戶對(duì)服務(wù)時(shí)間窗的要求越高,采用不完全充電策略進(jìn)行配送的優(yōu)勢(shì)就越明顯。

4 結(jié)束語(yǔ)

本文以物流企業(yè)的電動(dòng)配送汽車為研究對(duì)象,綜合考慮車輛動(dòng)態(tài)負(fù)載對(duì)耗電速率的影響及服務(wù)時(shí)間窗約束,構(gòu)建以包含車輛固定成本、配送成本、充電成本以及時(shí)間窗懲罰成本在內(nèi)的總成本最小為目標(biāo)的EVRPTW優(yōu)化模型,并針對(duì)所研究問(wèn)題及模型設(shè)計(jì)改進(jìn)混合遺傳退火算法進(jìn)行求解,最后結(jié)合實(shí)例進(jìn)行分析,結(jié)果表明電動(dòng)車輛在進(jìn)行物流配送時(shí),采用不完全充電的策略在充電時(shí)間、服務(wù)滿意度、配送成本等方面均優(yōu)于完全充電策略,同時(shí)客戶對(duì)服務(wù)時(shí)間窗的要求越高,采取不完全充電策略的優(yōu)勢(shì)越明顯。此外,本文所設(shè)計(jì)改進(jìn)混合遺傳退火算法能有效求解EVRPTW問(wèn)題,尋優(yōu)能力及解的質(zhì)量有明顯提升。由于電動(dòng)汽車的特性,用戶在利用其進(jìn)行配送時(shí)還可能存在續(xù)航里程的焦慮,同時(shí)換電也逐漸成為電動(dòng)汽車進(jìn)行電量補(bǔ)充的主要手段,因此后續(xù)在研究EVRPTW問(wèn)題時(shí),在建模、算法設(shè)計(jì)中考慮用戶駕駛行為以及引入換電方式,將更加貼近現(xiàn)實(shí)優(yōu)化場(chǎng)景。