康雯軒

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

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

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

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

1 建立模型

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

1.1 符號設(shè)定

1.1.1 參數(shù)符號

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

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

co：車輛單位里程的行駛費(fèi)用；

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

vo：車輛勻速行駛時(shí)的速度；

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

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

T：在各共享單車存放點(diǎn)的裝卸貨時(shí)間；

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

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

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

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

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

p：單位重量貨損價(jià)格；

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

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

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

1.1.2 決策變量

1.2 模型建立

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

2 算法設(shè)計(jì)

2.1 模擬退火算法

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

2.2 算法流程設(shè)計(jì)

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

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

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

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

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

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

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

圖1 算法流程圖

3 實(shí)驗(yàn)計(jì)算

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

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

實(shí)驗(yàn)數(shù)據(jù)如表1 所示。

表1 實(shí)驗(yàn)數(shù)據(jù)表

表1（續(xù)）

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

3.2 實(shí)驗(yàn)結(jié)果

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

圖2 VRP 配送路線圖

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

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

表2 實(shí)驗(yàn)結(jié)果

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