基于模擬退火算法的共享單車城市配送路徑規(guī)劃

康雯軒

（燕山大學(xué)經(jīng)濟管理學(xué)院，河北 秦皇島 066000）

自行車共享企業(yè)在校園、地鐵站、公交站、住宅區(qū)等提供服務(wù)，其可以有效地解決市民在其出行過程中最后一公里的問題，與其他公共交通組合，共同完成市民出行的整個鏈條。自行車共享也是一種新型的綠色環(huán)保共享經(jīng)濟。

車輛路徑優(yōu)化是DANTZIG 等[1]提出的，其后出現(xiàn)了集合分割的方法，可以將整個路徑集合進行分割，創(chuàng)建了最初的VRP 模型[2]，此后李軍[3]通過啟發(fā)式的方法求解了VRP 問題，張海剛等[4]使用PSO 算法求解帶軟時間窗的VRP 問題。雷洪濤等[5]構(gòu)建了智慧物流路徑優(yōu)化的模型。王超[6]根據(jù)城市配送同時取送貨的車輛路徑問題、帶時間窗的同時取送貨的車輛路徑問題和配送網(wǎng)點優(yōu)化的車輛路徑問題，給出了智能啟發(fā)式求解算法。

由于城市內(nèi)大量共享單車的存在，導(dǎo)致了城市擁堵、道路上共享單車擺放無序等問題，許多學(xué)者開始研究如何在共享經(jīng)濟的環(huán)境下研究城市合理治理。王婷等[7]提出通過使用獎懲機制和押金的合理規(guī)劃管理來合理規(guī)劃共享單車。周建高[8]針對上述城市治理問題提出對于公共場所的共享單車存放點實行縮小規(guī)模增加存放地點的觀點。本文針對建立城市集中配送管理中心來進行城市共享單車的集中管理與配送。

1 建立模型

在本文運輸網(wǎng)絡(luò)中，包括了共享單車存放點和線路，其中每次共享單車配送量不能超過配送車輛的最大載重量。并且每輛共享單車配送車輛由共享單車配送中心出發(fā)，完成配送任務(wù)后，返回共享單車配送中心。

1.1 符號設(shè)定

1.1.1 參數(shù)符號

設(shè)有n個共享單車存放節(jié)點，每個共享單車存放的需求量為q（ii=1，2，…，n）；有m輛配送車輛（型號種類完全一致），每輛車的最大載重量為Q?？蛻鬷到客戶j的距離為dij，o表示配送中心，則共享單車配送中心到共享單車存放的距離為doi（i=1，2，…，n）。由于一條線路上所有共享單車存放由一輛車進行配送，所以要求考慮貨損量的前提下，每條線路共享單車存放需求量之和不超過每輛車的最大載重量。

K：配送中心車輛集合，K=1，…，m；

co：車輛單位里程的行駛費用；

cv：單輛車的一次出車固定成本；

vo：車輛勻速行駛時的速度；

tij：車輛從客戶i到客戶j的行駛時間；

Q：配送車輛的最大載重量；

T：在各共享單車存放點的裝卸貨時間；

β1：在運輸過程中單位時間內(nèi)的損耗比例；

β2：在運輸過程中因路況因素造成的共享單車損耗比例；

β3：在共享單車存放點裝卸過程中單位時間內(nèi)的損耗比例；

β4：在共享單車存放點裝卸過程中因裝卸操作導(dǎo)致的損耗比例；

uijk：配送車輛k在路徑i到j(luò)上行駛時的載重量；

p：單位重量貨損價格；

fv：單次配送任務(wù)中，配送中心派出的送貨車輛總數(shù)；

fT：單次配送任務(wù)中，所有配送車輛行駛里程數(shù)總和；

fD：單次配送任務(wù)中，所有配送線路上產(chǎn)生的貨損量總和。

1.1.2 決策變量

1.2 模型建立

本文中的模型考慮了車輛使用數(shù)量、總行駛里程和運輸共享單車不當而導(dǎo)致的耗損，并且通過3 個成本權(quán)重因子加權(quán)得到總成本。其中約束保證每個共享單車存放點的需求量需全部滿足，同時每個共享單車存放點只能有一輛車進行配送，配送不能超出共享單車派送車輛的最大載重量，配送完后返回共享單車配送中心。

2 算法設(shè)計

2.1 模擬退火算法

模擬退火模仿了金屬退火的過程，其內(nèi)循環(huán)使用Metropolis 法則，通過一定概率接受相對劣解，此方法可以有效跳出局部最優(yōu)，從而得到全局最優(yōu)，外層則是降溫的過程，具體步驟見算法流程設(shè)計。

2.2 算法流程設(shè)計

步驟1：令T=T0，即開始退火的初試溫度，隨機生成一個初始解S1，并計算相應(yīng)的目標函數(shù)值E（x0）。

步驟2：令T等于冷卻進度表中的下一個值Ti。

步驟3：根據(jù)當前解xi進行擾動，產(chǎn)生一新解xj，計算相應(yīng)的目標函數(shù)值E（xj），計算兩者之差。

步驟4：若df<0，則接受S2 作為新的當前解，即So1=So2；否則，計算So2 的接受概率exp（-df/T），隨機產(chǎn)生（0，1）區(qū)間上均勻分布的隨機數(shù)rand，若exp（-df/T）＞rand，也接受S2 作為新的當前解So1=So2，否則保留當前解So1。

步驟5：在溫度Ti下，重復(fù)L次的擾動和接受過程，即執(zhí)行步驟3 和4。

步驟6：判斷T是否已達到了Tend，如果是，則停止，否則繼續(xù)。

本文算法流程圖如圖1 所示。

圖1 算法流程圖

3 實驗計算

3.1 問題數(shù)據(jù)

通過調(diào)查得出北京48 個共享單車存放點的需求，并且以北京國際機場為中心，將共享單車存放點的坐標計算出來。

實驗數(shù)據(jù)如表1 所示。

表1 實驗數(shù)據(jù)表

表1（續(xù)）

對于調(diào)查的配送中心的車輛參數(shù)已知：配送中心坐標（97，297），車輛總數(shù)為14 輛，單位行駛費用為1 元/km，車輛一次出行固定成本為150 元/輛，平均行駛速度為40 km/h，最大載重量為1 000 kg。運輸過程損耗比例為0.8%，路況損耗比例為0.1%；裝卸過程中損耗比例為0.2%，裝卸操作損耗比例為0.2%。

3.2 實驗結(jié)果

本文實驗環(huán)境為2 GHz，8 GB RAM，采用MATLAB 編程。本文的數(shù)據(jù)實驗結(jié)果如圖2 所示。

圖2 VRP 配送路線圖

圖3 給出了模擬退火求解結(jié)果的目標函數(shù)優(yōu)化曲線。目標函數(shù)最優(yōu)值值在第1 000 代即從最初的5 300 元下降到最小值2 800 元，顯示了良好的收斂效果。目標中的車輛損耗降低了26.03%，由此可見本模型可以大幅降低損耗的浪費。通過實例可以看出，模擬退火算法在計算實例過程中表現(xiàn)良好。計算結(jié)果如表2 所示。

圖3 算法迭代次數(shù)圖

表2 實驗結(jié)果

本文設(shè)計的算法與搭建的模型可作為共享單車企業(yè)配送車輛路徑規(guī)劃工具，可靈活求解企業(yè)中不同情況問題，具有較高的實際應(yīng)用價值。