時變交通下生鮮配送電動車輛路徑優(yōu)化方法

趙志學(xué)，李夏苗

(1.中南大學(xué)交通運輸工程學(xué)院，長沙410205；2.湖南工商大學(xué)移動商務(wù)智能湖南省重點實驗室，長沙410205)

0 引 言

電動車憑借其節(jié)能、綠色、環(huán)保的優(yōu)勢，在物流終端配送過程中得到廣泛利用，并逐漸替代了傳統(tǒng)燃油車.但電動車存在充電時間較長，電池容量較小和續(xù)航里程相對較短的短板.如何在技術(shù)條件的限制下合理地進行電動車調(diào)度，配送路徑規(guī)劃，廣受國內(nèi)外研究學(xué)者的關(guān)注.

電動車輛路徑問題是傳統(tǒng)車輛路徑問題的延伸與拓展.Borja Beltran[1]提出將電動車應(yīng)用于城市交通運輸中，建立了運輸距離最短的優(yōu)化模型.Desaulniers G.[2]在研究帶時間窗電動車輛路徑問題(Electric Vehicle Routing Planning, EVRP)優(yōu)化中，考慮了4 種不同充電策略，并在客戶點時間窗約束下對4種充電策略進行優(yōu)化，從而得到最佳充電方式.揭婉晨等[3]區(qū)分不同車型電池容量，單位耗電率和車載等因素，設(shè)計分級定價法求解該問題最優(yōu)解.Hiermann等[4]根據(jù)不同車型電動車能耗和載重的差異性，研究合理配置車隊結(jié)構(gòu)進行配送.Afroditi等[5]考慮車載、充電方式和電量等約束，構(gòu)建電動車路徑規(guī)劃模型.近幾年，國內(nèi)外學(xué)者開始將冷鏈物流與電動車輛路徑問題結(jié)合起來研究.Poks A.等[6]研究帶有電冷卻裝置的電動卡車冷鏈配送車輛路徑的數(shù)學(xué)模型.馮杰等[7]研究生鮮供應(yīng)商通過同質(zhì)電動車向零售商進行生鮮配送的冷鏈物流路徑優(yōu)化問題.

綜上，以下問題還待深入研究：多數(shù)文獻是獨立研究EVRP和生鮮冷鏈配送路徑問題，兩者結(jié)合文獻較少；關(guān)于電動車配送的外界環(huán)境，大多忽視路網(wǎng)動態(tài)交通時變特征對電動車實際配送過程的影響；多數(shù)生鮮冷鏈配送文獻，只考慮生鮮配送過程中的服務(wù)時間窗，忽略了客戶對生鮮產(chǎn)品新鮮度最低限制要求.因此，本文考慮客戶最低新鮮度需求，以總成本為目標(biāo)建立時變交通下生鮮配送電動車輛路徑優(yōu)化模型，并設(shè)計自適應(yīng)改進蟻群算法求解.

1 符號說明與模型構(gòu)建

1.1 模型假設(shè)

某生鮮配送企業(yè)具有充足同質(zhì)電動車，所有車輛滿電狀態(tài)從配送中心出發(fā)為客戶進行配送.每個客戶點的位置、服務(wù)時間窗、生鮮產(chǎn)品需求量和最低新鮮度限制均已知，時變交通路網(wǎng)數(shù)據(jù)可從交通部門獲得，車輛在配送過程中根據(jù)實際情況利用社會充電站進行快速充電，制定總成本最小的配送計劃.對研究問題做如下約定：

(1)配送網(wǎng)絡(luò)中只有一個配送中心，所有配送電動車起止點均為配送中心；

(2)配送過程中滿足電量約束，當(dāng)所剩電量不能滿足配送要求時，車輛到耗電量最低的充電站進行快充，充滿電后繼續(xù)完成配送任務(wù)；

(3)每隔10 min更新路網(wǎng)交通狀態(tài)；

(4)客戶點需求量均小于車輛載重量，有服務(wù)時間窗和最低新鮮度限制的要求.

1.2 符號及參數(shù)

(1)集 合.

N,C,F——分別為路網(wǎng)所有節(jié)點、客戶點和充電站的集合，N={0}∪C∪F，其中，0 表示配送中心；

T——工作所有時間段集合 ，T={T1,T2,…,TB}，其中，B為時間段總數(shù)；

K——電動車集合.

(2)參數(shù).

Emax,E0——分別為電動車最大電池容量(kWh)，正常行駛的最低電量(kWh)；

P1,P2,P3——分別為車輛啟用成本(元/輛)，車輛單位時間行駛成本(元/min)，耗電量單位價格(元/kWh)；

P4,P5,P6——分別為生鮮單價(元/kg)，快速充電單位電價(元/kWh)，違反客戶點時間窗的單位懲罰成本(元/min)；

Q,Me——分別為電動車k的最大車載(kg)、裸車重(kg)；

——分別為道路(i,j)的直線距離(km)，路徑劃分策略中足夠短的距離(km)，道路(i,j)中第R子路段距離(km)；

tijk,Eijk——分別為車輛k在道路(i,j)上行駛時間(min)，耗電量(kWh)；

Nchargemax,Cbattery——分別為車輛k電池最大充電次數(shù)、成本(元)；

EC,EO——分別為運輸、裝卸過程中單位時間能耗(kW/h).

(3)決策變量.

xijk——車輛k在道路(i,j)行駛時為1，否則為0；

yik——車輛k服務(wù)客戶點i時為1，否則為0；

zik——車輛k在充電站i充電時為1，否則為0.

1.3 相關(guān)因素分析

1.3.1 時變路網(wǎng)交通相關(guān)分析

在時變交通下，不同時間段內(nèi)車輛行駛速度不同，行駛時間難以獲得，全天各時段行駛速度函數(shù)為

式中：vij(t)——t時刻車輛在道路(i,j)行駛速度(km/h)；

vijB——時間段B內(nèi)車輛在道路(i,j)行駛速度(km/h).

車輛在足夠短的距離內(nèi)行駛時，采用平均速度刻畫，即把路段開始行駛即時速度作為路段的平均速度[8]，因此，設(shè)計一種路徑劃分方法求解路段行駛時間.

Step 1根據(jù)?(?=0.2 km)[8]和dij把道路(i,j)分為U個子路段，其中，為向上取整.則每個子路段長度為

Step 2開始路段計算.出發(fā)時間為離開節(jié)點i時間：和式(1)確定，轉(zhuǎn)Step 3.

Step 3其余路段計算.

Step 3.1令ω=1.

Step 3.2如果1+ω ＜U，則ω=ω+1 ，轉(zhuǎn) Step 3.2；否 則1+ω=U，.

Step 4計算終止，返回路段行駛時間tijk.

1.3.2 耗電性能和充電需求分析

電動車耗電不僅與車輛自身屬性有關(guān)，還與其實際車載和速度有關(guān)，故實際車載Qk的電動車k以速度v行駛在平坦道路時，運行功率[9]為

式中：g——重力加速度(m/s2)；

η——傳動系統(tǒng)機械效率；

f、Cd、A——分別表示汽車滾動阻力系數(shù)，空氣阻力系數(shù)，汽車迎風(fēng)面積(m2).

可得時變路網(wǎng)下，車輛k在道路(i,j) 上行駛的功耗Eijk為

根據(jù)城市配送實際，電動車剩余電量不能滿足服務(wù)下一客戶點時，需采用在途快速充電模式進行充電.快速充電過程中，電動車k在充電站i快速充電時間為.

1.3.3 生鮮產(chǎn)品新鮮度分析

生鮮新鮮度與冷藏溫度和運輸時間相關(guān)[10].假設(shè)生鮮在配送過程中維持恒定溫度，則生鮮產(chǎn)品新鮮度的損耗系數(shù)?可認為是常數(shù)；生鮮新鮮度與配送時間相關(guān)，引入生鮮產(chǎn)品新鮮度衰減函數(shù)為

式中：Fi——車輛服務(wù)客戶點i時的生鮮新鮮度.

1.4 模型構(gòu)建

以配送總成本為目標(biāo)函數(shù)，構(gòu)建時變交通下考慮客戶最低新鮮度需求的電動車配送車輛路徑模型.

(1)目標(biāo)函數(shù).

式(7)為目標(biāo)函數(shù)總成本；式(8)為固定成本，行駛時間成本和時間懲罰成本；式(9)為行駛能耗成本和制冷成本，其中，制冷成本包含運輸過程和裝卸過程的耗電成本；式(10)為貨損成本；式(11)為快速充電成本和電池消耗成本，其中，電池消耗成本與快速充電次數(shù)正相關(guān).

(2)約束條件.

式(12)表示客戶點最低新鮮度需求；式(13)表示每個客戶點只接受由同一輛電動車服務(wù)；式(14)表示配送貨物重量不能超過車輛最大載重量；式(15)表示電動車離開節(jié)點i到達節(jié)點j之間電量關(guān)系；式(16)表示電動車到充電站充滿電后離開；式(17)表示車輛在每個節(jié)點電量約束；式(18)表示車輛到達和離開節(jié)點i時間關(guān)系；式(19)表示車輛離開節(jié)點i到達節(jié)點j時間關(guān)系；式(20)～式(22)為決策變量.

2 算法設(shè)計

2.1 三約束決策因子

判斷車輛k離開客戶點i后對下一客戶點j的配送，主要取決于3種約束：車載約束，電量約束和客戶點最低新鮮度需求約束(簡稱新鮮度約束).

式(23)中第1 個不等式為車載約束，第2 個不等式為電量約束，第3個不等式為客戶點最低新鮮度需求約束.因此本文引入三約束因子σ對上述問題進行求解，其中，分別為當(dāng)前螞蟻m已訪問客戶點集合和未訪問客戶點集合；Cmin[i]k為從客戶點i出發(fā)耗電量最低的充電站.

(1)當(dāng)滿足三約束時，σ=3，客戶點j為下一個服務(wù)點.

(2)當(dāng)滿足載重和電量約束，不滿足新鮮度約束時，σ=2，車輛返回配送中心，并增派一輛新車繼續(xù)配送，客戶點j仍為未訪問節(jié)點.

(3)當(dāng)滿足載重約束，不滿足電量約束，則螞蟻m需要到Cmin[i]k進行充電后繼續(xù)配送客戶點j，更新j點信息.判斷是否滿足新鮮度約束，如果滿足則σ=1，則Cmin[i]k和j依次作為螞蟻m訪問的節(jié)點，；否則σ=0，螞蟻m返回配送中心，并增派一輛新車繼續(xù)配送，j仍為未訪問節(jié)點.

(4)返回σ值.

2.2 狀態(tài)轉(zhuǎn)移策略

螞蟻m從客戶點i到客戶點j轉(zhuǎn)移概率為

式中：τij,ηij——分別為信息度濃度和能見度，ηij=1/dij；

α,β——分別為信息濃度和能見度重要性因子，引入自適應(yīng)信息素啟發(fā)式因子和期望啟發(fā)式因子對蟻群算法進行改進[11]：，其中，Nmax，N分別為蟻群算法最大迭代次數(shù)和當(dāng)前迭代次數(shù).

為防止算法陷入局部最優(yōu)，結(jié)合輪盤賭法對狀態(tài)轉(zhuǎn)移策略進行改進，公式為

式中：R0——[0,1]固定算法參數(shù)；

R1——[0,1] 隨機數(shù)；

S——輪盤賭操作.

2.3 信息素更新策略

為使搜索過程更具指導(dǎo)性，所有螞蟻完成周游后，對建立路徑組成的路段信息素進行更新.更新規(guī)則[11]為

式中：ρ——揮發(fā)因子；

W——常數(shù)；

M——螞蟻總數(shù)量；

Zm——螞蟻m產(chǎn)生總配送成本；

——此次迭代前路段(i,j)的信息素；

——經(jīng)過此次迭代后更新的信息素；

Lm——螞蟻m在此次迭代中經(jīng)過路線.

2.4 改進蟻群算法設(shè)計

Step 1算法初始化.

所有螞蟻均從配送中心出發(fā).初始化算法參數(shù)：最大迭代次數(shù)Nmax，當(dāng)前迭代次數(shù)N，螞蟻總數(shù)M，當(dāng)前螞蟻數(shù)m，車輛數(shù)量標(biāo)識vn，三約束因子σ等.

Step 2構(gòu)建可行解.

Step 2.1判斷螞蟻m未訪問節(jié)點集合是否為空：如為空，轉(zhuǎn)Step 2.5；否則，轉(zhuǎn)Step 2.2.

Step 2.2根據(jù)狀態(tài)轉(zhuǎn)移策略選擇下一要服務(wù)的客戶點j.

Step 2.3計算客戶點j三約束因子σ：如果σ=3 ，j即為螞蟻下一訪問客戶點，，轉(zhuǎn)Step 2.1；如果σ=1，則把Cmin[i]k，j依次作為螞蟻訪問節(jié)點，轉(zhuǎn)Step 2.1；如果σ=2 或σ=0 時，螞蟻返回配送中心，同時新增一輛車繼續(xù)配送，vn=vn+1，轉(zhuǎn)Step 2.1.更新，根據(jù)車輛第一個服務(wù)客戶點時間窗計算出發(fā)時間.

Step 2.4m=m+1，如果m ＜M，vn=0 ，轉(zhuǎn)Step 2.1.

Step 3目標(biāo)適應(yīng)度計算.

使用式(7)計算每只螞蟻搜索路徑的目標(biāo)適應(yīng)度值，此次迭代過程中記錄最優(yōu)適應(yīng)度值和相應(yīng)的最優(yōu)搜索路徑，N=N+1.

Step 4更新全局信息素.

按照信息素更新策略對本次迭代過程中所有螞蟻經(jīng)過的路徑信息素進行更新.

Step 5算法終止判斷.

如果N ＜Nmax，轉(zhuǎn)Step 2；否則，算法終止.通過每代適應(yīng)度最優(yōu)值和最優(yōu)路徑找出全局最優(yōu)值和最優(yōu)路徑.

3 實驗仿真

3.1 實驗設(shè)置

算例來源文獻[12]的電動車輛路徑數(shù)據(jù)庫，采用R類型(R208)算例作為仿真數(shù)據(jù).其中，0 為配送中心，1～100 為客戶點，101～120 為充電站.為模擬實際情況，做如下修改：

(1)實際配送中，需在直線距離的基礎(chǔ)上乘以迂回系數(shù)δ(δ=1.3)得到實際距離.

(2)設(shè)定配送工作開始時間為06:00(對應(yīng)0 min)，每10 min 為一個時間段.根據(jù)城市交通規(guī)律，將07:00-09:00(第7～18 時段)和17:00-19:00(第67～78 時段)設(shè)為交通擁堵時段(車速為30 km/h)，其余為正常時段.令?=0.1，設(shè)計3 種車速，即[50(1-?),50(1+2?),50(1-3?)] ，根據(jù)時間段B值，利用求余函數(shù)π=mod(B,3)，當(dāng)π取值為[0,1,2]時，對應(yīng)正常時段3種車速.

(3)算例中一個重量單位為10 kg.

相關(guān)參數(shù)值如表1所示.

3.2 大型數(shù)據(jù)算例路徑規(guī)劃

為驗證本文算法的穩(wěn)定性，運行程序10 次，平均運行時間為363.57 s，說明算法能夠在較短時間內(nèi)得到最優(yōu)電動車路徑規(guī)劃方案.程序運行10 次中取得最優(yōu)的物流配送規(guī)劃路徑如圖1 所示，配送成本分析如圖2 所示，具體路徑優(yōu)化方案如表2 所示.

表1 模型和算法的參數(shù)值Table 1 Model and algorithm parameter values

圖1 R208 最佳路徑圖Fig.1 R208 optimal routing planning

通過計算，配送總成本為4 913.98 元，使用8輛電動車，固定成本1 600 元，時間管理成本(包含時間成本和懲罰成本)2 041.77 元，運輸和制冷能耗成本301.03元，貨損成本515.04元，電池耗費成本225元，快速充電成本231.09元.

由圖2 可知，每輛車運行總成本中，時間成本和車輛固定成本占比最高，能耗成本、快速充電成本和電池損耗成本比例較低，說明物流配送成本主要影響因素就是行駛時間.由圖1 和表2 可知：①車輛1，4，6和8運輸過程中需要充電，說明車輛在途充電能在較短時間內(nèi)增加剩余里程，擴大配送范圍.②從開始時間可知，車輛1、2、3、5和7都是在0時刻開始從配送中心出發(fā)進行配送，其余車輛出發(fā)時間都各不相同.如果車輛4，6 和8 在0 時刻出發(fā)，將額外支付3 214.45 元時間懲罰費用，總配送成本也會超出65.0%，說明物流企業(yè)應(yīng)根據(jù)路網(wǎng)狀況，客戶點時間窗等實際情況合理安排出發(fā)時間，從而降低配送成本.③車輛1、2、3、5和7僅進入早高峰擁堵時段，車輛4和8都僅進入晚高峰擁堵時段，車輛6 幾乎避開交通擁堵時段.說明部分客戶時間窗在擁堵時段內(nèi)，車輛服務(wù)時間必須在該時段進行，同時也說明本文方法能有效的規(guī)避擁堵時段.

圖2 成本分析圖Fig.2 Cost analysis chart

表2 車輛路徑優(yōu)化結(jié)果Table 2 Vehicle routing optimization results

3.3 最低新鮮度需求靈敏度分析

為分析客戶不同最低新鮮度需求對車輛路徑規(guī)劃的影響，在其他條件不變的情況下采用不同最低新鮮度限制進行求解，實驗結(jié)果如表3 所示.其中，時間成本包含行駛時間成本和懲罰成本，能耗成本包含行駛能耗和制冷能耗成本.

表3 不同最低新鮮度需求仿真結(jié)果Table 3 Simulation results of different minimum freshness requirements

由表3可知：

(1)固定成本和時間成本占總配送成本比例最低為74.1%，最高為93.5%；能耗成本和貨損成本占比較低，其中，能耗成本最高占比僅為6.1%，貨損成本最高占比為10.5%.這說明總配送成本主要來自固定成本和時間成本，降低配送成本的關(guān)鍵就是控制好車輛數(shù)和配送時間.

(2)隨著最低新鮮度限制提高，總配送成本隨之增加，最低新鮮度限制為97%相比90%，總配送成本增加26.7%，固定成本和時間成本增加60.0%，車輛數(shù)翻了1倍.這說明隨著最低新鮮度限制的提高，客戶點對配送時間的要求更加嚴格，使每輛電動車配送行駛時間縮短，服務(wù)客戶點數(shù)量減少，需要更多的電動車完成配送任務(wù)，總行駛時間和行駛距離增加，從而提高固定成本和時間成本，總配送成本也會相應(yīng)增加.

(3)隨著最低新鮮度限制提高，每輛電動車配送時間和服務(wù)客戶點數(shù)目減少，相應(yīng)的行駛距離縮短，電動車在配送過程中充電次數(shù)和充電電量降低，當(dāng)電動車行駛距離減少到續(xù)航里程內(nèi)時，車輛不需在途充電，故電池損耗成本和快速充電成本降低.但配送車輛數(shù)增加，固定成本和時間成本仍會增加.

總之生鮮配送企業(yè)在制定配送路徑規(guī)劃時，一定要考慮客戶點最低新鮮度限制需求，科學(xué)調(diào)度車輛和規(guī)劃路徑.

3.4 不同算法對比分析

為驗證本文算法的有效性，將本文算法(Improved Ant Colony Algorithm, IACA)與經(jīng)典蟻群算法(Ant Colony Algorithm,ACA)[13]和禁忌搜索算法(Tabu Search Algorithm,TSA)[14]進行比較.ACA中狀態(tài)轉(zhuǎn)移規(guī)則里無自適應(yīng)算子，且ACA和TSA 中車輛出發(fā)時間均為0.采用算例R208 進行實驗，最低新鮮度取值為90%和95%，結(jié)果如表4所示.

由表4可知：①關(guān)于配送總成本，本文算法比ACA和TSA更優(yōu).當(dāng)最低新鮮度限制為90%時，本文算法比ACA 總成本降低10.1%，比TSA 降低13.6%；當(dāng)最低新鮮度限制為95%時，本文算法比ACA 總成本降低12.2%，比TSA 降低13.8%.說明本文算法能夠降低配送成本，提高企業(yè)經(jīng)濟效益.②在計算時間層面，雖然本文算法相較于ACA和TSA，多考慮了狀態(tài)轉(zhuǎn)移概率的改進和出發(fā)時間計算，但兩種算法耗時相差不多，均能在較短的時間里得到最優(yōu)結(jié)果.通過引入自適應(yīng)啟發(fā)算子，能夠有效提高蟻群算法的局部搜索能力和全局收斂的能力.

表4 不同算法對比仿真結(jié)果Table 4 Simulation results of different algorithms

4 結(jié) 論

本文在考慮客戶對生鮮最低新鮮度限制的情況下，建立時變交通下生鮮物流配送的電動車輛路徑優(yōu)化模型，運用路段劃分策略求解時變網(wǎng)絡(luò)下車輛行駛時間，根據(jù)模型特點提高求解效率，設(shè)計三約束因子和自適應(yīng)方法對蟻群算法進行改進，通過標(biāo)準案例進行驗證.實驗結(jié)果表明：企業(yè)在調(diào)度電動車配送過程中，應(yīng)充分考慮時變網(wǎng)絡(luò)、客戶時間窗等實際情況，合理安排出發(fā)時間和規(guī)劃路線，從而降低配送成本，合理規(guī)避擁堵時段；隨著客戶對生鮮最低新鮮度限制需求提高，配送車輛數(shù)增加，配送總成本隨之提高，故生鮮企業(yè)在制定配送路徑時，一定要充分考慮客戶最低新鮮度限制，科學(xué)合理的調(diào)度車輛和規(guī)劃路線，從而有效降低成本；改進蟻群算法相比經(jīng)典蟻群算法和禁忌搜索算法，配送總成本最高可分別減少12.2%和13.8%，說明本文算法能夠有效降低配送成本，提高經(jīng)濟效益.