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

康雯軒

（燕山大學經濟管理學院，河北 秦皇島 066000）

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

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

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

1 建立模型

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

1.1 符號設定

1.1.1 參數符號

設有n個共享單車存放節點，每個共享單車存放的需求量為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：在運輸過程中單位時間內的損耗比例；

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

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

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

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

p：單位重量貨損價格；

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

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

fD：單次配送任務中，所有配送線路上產生的貨損量總和。

1.1.2 決策變量

1.2 模型建立

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

2 算法設計

2.1 模擬退火算法

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

2.2 算法流程設計

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

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

步驟3：根據當前解xi進行擾動，產生一新解xj，計算相應的目標函數值E（xj），計算兩者之差。

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

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

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

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

圖1 算法流程圖

3 實驗計算

3.1 問題數據

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

實驗數據如表1 所示。

表1 實驗數據表

表1（續）

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

3.2 實驗結果

本文實驗環境為2 GHz，8 GB RAM，采用MATLAB 編程。本文的數據實驗結果如圖2 所示。

圖2 VRP 配送路線圖

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

圖3 算法迭代次數圖

表2 實驗結果

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