潘立軍， 符 卓， 劉喜梅

(湖南工程學(xué)院 管理學(xué)院,湖南 湘潭 411104; 2.中南大學(xué) 交通運輸工程學(xué)院,湖南 長沙 410075)

0 引言

共享單車系統(tǒng)作為共享經(jīng)濟(jì)的典型應(yīng)用，在方便居民短距離出行、解決公交、地鐵等公共交通“最后1公里問題”、緩解城市交通擁堵等方面發(fā)揮著重要作用。共享單車系統(tǒng)可分為有樁共享單車系統(tǒng)與無樁共享單車系統(tǒng)，有樁共享單車系統(tǒng)通過在規(guī)劃的停放點設(shè)置固定單車停放鎖具裝置，用戶可在停放點經(jīng)授權(quán)取用單車。無樁共享單車系統(tǒng)則通過設(shè)置停放點電子地圖圍欄，同時加裝單車電子鎖具，配合專用手機(jī)APP來實現(xiàn)授權(quán)用戶取用。近二年來，共享單車系統(tǒng)在我國快速普及，如永安行租車系統(tǒng)作為全國最大規(guī)模的有樁共享自行車系統(tǒng)已實現(xiàn)對100余個地級市的服務(wù)覆蓋，而無樁共享自行車系統(tǒng)的代表——摩拜單車已在全國200多個城市投放共享單車。

無論是有樁還是無樁共享單車系統(tǒng)，停放點的單車容量均是有限的，通常共享單車系統(tǒng)初期會按周邊用戶分布情況規(guī)劃該容量，但由于用戶使用單車具有隨機(jī)性、單向性等特點，必然導(dǎo)致一段時間后各停放點單車數(shù)量不均，有的停放點車多，無空余停放設(shè)施，有的停放點無車，對后續(xù)用戶使用造成不便。因此，需定期組織載貨車輛回收單車，再次投放到單車數(shù)不足的停放點，實現(xiàn)對各停放點單車數(shù)量的再平衡。隨著共享單車在我國城市的快速普及，單車再平衡工作量與日俱增，如何科學(xué)組織城市內(nèi)共享單車系統(tǒng)再平衡，已成為各大共享單車運營企業(yè)降本增效、提升服務(wù)質(zhì)量的關(guān)鍵。

共享單車再平衡問題(Bike Sharing Rebalancing Problem, BRP)最早由Dell’Amico[1]提出，即利用有相同載重的車輛從自行車維護(hù)與補給中心出發(fā)完成一定區(qū)域內(nèi)各單車停放點自行車的再分配，使各停放點達(dá)到預(yù)先設(shè)置的容量后回到中心，如何使所有的車輛行駛的距離或花費的時間、成本最少。BRP被認(rèn)為是單一商品取送貨車輛路徑問題(One-commodity Pickup-and-delivery Capacitated Vehicle Routing Problem, 1-PDVRP)[2]的一個特例，即車輛出發(fā)時載重可不為零，但實踐中，單車既可以回收到中心，也可從中心取車投放到各停放點，因此BRP與PDVRP有本質(zhì)不同。針對BRP的求解，目前主要有二類算法，一是以分枝定界法為代表的精確算法[1,3～5]；二是啟發(fā)式算法，如線路破壞與修復(fù)啟發(fā)式算法[6]，該算法先假設(shè)車輛出發(fā)時載重為0，生成部分超出額定載重線路，最后調(diào)整車輛載重修復(fù)線路，使線路可行；線路再組合啟發(fā)式算法[7]，局部迭代搜索啟發(fā)式算法[8～10]等。從已有的研究報道分析來看，一是精確算法只適應(yīng)小規(guī)模問題的求解，一旦問題規(guī)模擴(kuò)大，精確算法將無能為力，二是由于車輛出發(fā)時載重可不為零，原來適用求解1-PDVRP的啟發(fā)規(guī)則不適用BRP，已有啟發(fā)式算法求解速度慢。因此深入研究BRP問題屬性，設(shè)計快速高效的啟發(fā)式算法對設(shè)計高效BRP調(diào)度軟件至關(guān)重要。

1 BRP數(shù)學(xué)模型

從圖論的角度，BRP可表示為一個完備圖G=(V,E)，V={V1,V2,…,Vn}表示頂點集，其中V1表示自行車維護(hù)與補給中心，V′={V2,…,Vn}表示單車停放點集，E={(i,j)|i,j∈V,i≠j}表示弧集或邊集。其符號定義為：M表示實施再平衡運輸?shù)膶Ｓ密囕v數(shù)；Q表示專用運輸車輛的最大載重量，di表示車輛在第i個單車停放點取送量，di的可能的取值范圍為[-Q,Q]，di小于零，表示該停放點需補充單車，di大于零，表示該停放點要回收單車；cij表示專用車輛訪問弧(i,j)產(chǎn)生的運輸成本或時間；θj表示專用車輛訪問第j個停放點后的載重量，即車輛當(dāng)前載重量。定義0-1決策變量xij，1表示車輛訪問了弧(i,j)，否則為0。BRP的數(shù)學(xué)模型如下:

(1)

(9)

(1)式為目標(biāo)函數(shù)，最小化運輸總成本或時間，(2)式、(3)式確保除維護(hù)補給中心外其余單車停放點均被訪問且只訪問一次，(4)式、(5)式確保所有專用運輸車輛在完成任務(wù)后均回到維護(hù)與補給中心，(6)式為消除子回路約束，(7)式、(8)式、(9)式為BRP車輛載重約束，確保各專用運輸車輛在實施單車回收與投放過程中，車輛當(dāng)前載重量不超過額定載重量。模型假設(shè)在某一停靠點回收的單車可被投放到任意其它需要的點，且車輛出發(fā)或者回到補給中心時，載重可不為零，因為可以事先裝入部分單車，或者帶回部分單車。BRP問題的新特點增加了問題求解難度，必須深入研究BRP模型性質(zhì)，才能設(shè)計高效的啟發(fā)規(guī)則。

2 BRP模型性質(zhì)

設(shè)Route(V1,V2,…,Vi-1,Vi,Vi+1,…Vn)為一條可行線路，V1為自行車維護(hù)補給中心，Vi(i=2,3,…,n)為自行車?？奎c，模型有以下性質(zhì):

性質(zhì)1若Route可行，則必有max{θj}≤Q,min{θj}≥0(j=1,2,…,n)成立，反之也成立。

證明依據(jù)BRP的定義，性質(zhì)1顯成立。

性質(zhì)2若Route可行，則在線路上任取兩點Vi,Vj(i,j=1,2,…,n,且i≤j)，截取Vi至Vj兩點之間的線路構(gòu)成子線路Routec(Vi,Vi+1,…,Vj-1,Vj)仍為一條可行線路。

證明可依據(jù)反證法證明。

性質(zhì)3若Route可行，則在線路上任取兩點Vi,Vj(i,j=1,2,…,n,且i≤j)，對點Vi,Vj的取送量di,dj實施以下變換得到的新線路Route′仍可行。

變換(1)：

變換(2):

對于變換，因為:θ′i～j=(θi-min{θi,θi+1,…,θj-1,θj},…,θj-min{θi,θi+1,…,θj-1,θj}),而max(θ′i～j)≤Q,min{θ′i～j}=0,對于變換(2)，因為:θ′i～j=(θi+Q-max{θi,θi+1,…,θj-1,θj},…,θj+Q-max{θi,θi+1,…,θj-1,θj}),而min(θ′i～j)≥0,max{θ′i～j}=Q,故性質(zhì)3成立。

定理1設(shè)Route為一條可行線路，Position(P1,P2,…,Pi-1,Pi,Pi+1,…Pn)為插入構(gòu)造線路時可插入待訪問取送點的位置(如圖1所示)，設(shè)Pi位置可插單車數(shù)量范圍為[Di,Ui]，若要保持插入后Route仍可行，則有:

Ui=Q+min{θ1,θ2,…,θi}-max{θi,θi+1, …,θn}

Di=-Q-min{θi,θi+1,…,θn}+max{θ1,θ2,…,θi}

圖1 線路可插入位置示意圖

充分性：

設(shè)dnew=Ui，依據(jù)性質(zhì)3對Route的點V1,Vi,實施變換(1)后，線路仍可行；

再插入dnew點，則:

θ2-min{θ1,θ2,…,θi},…,

θi-min{θ1,θ2,…,θi},

θi+Q-max{θi,θi+1,…,θn},

θi+1+Q-max{θi,θi+1,…,θn},…,

θn+Q-max{θi,θi+1,…,θn})

因為max{θ1,θ2,…,θi}≤Q(性質(zhì)2，原線路的子路線可行)，故有：

又設(shè)dnew=Di，依據(jù)性質(zhì)3對Route的點V1,V2,…,Vi-1,Vi,實施變換(2)后，線路仍可行；

再插入dnew點，則:

θ2+Q-max{θ1,θ2,…,θi},…,

θi+Q-max{θ1,θ2,…,θi},

θi-min{θi,θi+1,…,θn}),

θi+1-min{θi,θi+1,…,θn},…,

θn-min{θi,θi+1,…,θn})

證明必要性：

繼續(xù)對Route′取(Vnew,Vi+1,…Vn)實施變換2，則變換后：θj″=(θ1-min{θ1,θ2,…,θi},θ2-min{θ1,θ2,…,θi},…,θi-min{θ1,θ2,…,θi},θi+Q-max{θi,θi+1,…,θn},θi+1+Q-max{θi,θi+1,…,θn},…,θn+Q-max{θi,θi+1,…,θn})，則:

dnew=(θi+Q-max{θi,θi+1,…,θn})-

(θi-min{θ1,θ2,…,θi})

=Q-max{θi,θi+1, …,θn}+

min{θ1,θ2,…,θi}=Ui

同理可證dnew=Di

必要性得證。

定理1闡明了BRP插入構(gòu)造可行線路的量化判定條件，利用該條件可設(shè)計求解BRP的高效啟發(fā)規(guī)則。

3 求解BRP的容差插入啟發(fā)式算法

求解BRP的容差插入啟法式算法的具體步驟如下：

第1步初始化待插入位置集合P，初始化待插入點集V，初始化待插入位置集合P，初始化解X={ }，初始化參數(shù)a1,a2；

第2步選取種子點，插入R1，更新X、V、P；

第3步找最優(yōu)插入位置P*與最優(yōu)待插入點V*。具體步驟如下：

WhilePi屬于P

取位置Pi的前點Vi-1與后點Vi+1；

WhileVj屬于V

計算位置Pi可插入單車數(shù)量的上界UPi，可插入單車數(shù)量的下界DPi(定理1)；

IfdVj∈[UPi,DPi]

計算容差(Capacity Range Length, CRL)；

CRLPi,Vj=UPi-DPi-|dVj|

(10)

計算線路增加；

SVj,Vi-1,Vi+1=cVj,Vi-1+cVj,Vi+1-cVi-1,Vi+1

(11)

Endif

Endif

Endif

CRL、S進(jìn)行規(guī)一化處理，方法如式(12)、式(13)所示；

CRL′Pi,Vj=(CRLmax-CRL′Pi,Vj)/CRLmax

(12)

S′Vj,Vi-1,Vi+1=(Smax-S′Vj,Vi-1,Vi+1)/Smax

(13)

找到優(yōu)插入位置P*與最優(yōu)待插入點V*；

(14)

第4步插入點到當(dāng)前解中，具體如下:IfV*,P*≠?。

將當(dāng)前最優(yōu)待插入點V*插入到最優(yōu)位置P*，更新X、V；

Else

在V中重新選擇種子點生成一條新的線路Rk，更新X、V集；

Endif

返回第三步；

算法終止條件：待插入點集V為空。

該算法為經(jīng)典啟發(fā)式搜索算法，啟發(fā)規(guī)則主要考慮兩方面因素：一是待插入點插入后的增加量，其越小越好；二是容差，類似于文獻(xiàn)[12]中時差概念，容差反映了將待插入點插入到相應(yīng)位置后，在保持線路可行的情況下，還可插入單車數(shù)量的大小，該數(shù)量越大，越有利于插入更多的點。為了能綜合考慮兩個因素，算法中采用歸一化的方法將兩類因素量綱統(tǒng)一，同時引入兩個權(quán)重參數(shù)a1,a2(a1+a2=1) 將兩個因素綜合起來考慮，如式(14)所示。由于經(jīng)典啟發(fā)式搜索算法種子點的選取對算法的求解質(zhì)量影響較大，本文采用文獻(xiàn)[11]的方法，每次選待插入點中離補給中心距離最遠(yuǎn)的點作為當(dāng)前種子點，這有助于提高求解質(zhì)量。

4 算法測試

4.1 測試環(huán)境與測試方法

為了測試算法的求解效率，本文運用文獻(xiàn)[2]收集的BRP問題集作為標(biāo)準(zhǔn)測試算例，該算例均來自全球各地共享自行車系統(tǒng)的實際應(yīng)用數(shù)據(jù)，可在網(wǎng)站http://www.or.unimore.it-/resources/BRP/home.html下載。車輛載重量Q是該類問題的重要約束條件，Q越大則約束越松，反之則越緊。為了研究容差插入啟發(fā)式算法求解不同載重容量限制問題的效率差異，本文將問題分為大容量問題(Q=30)、中容量問題集(Q=20)及小容量問題(Q<20)三個子集。

運用matlab 2014編程實現(xiàn)算法，運行于CPU(core i3，3.1GHZ)、Rom(4G)的PC機(jī)上。參數(shù)a1,a2的取值區(qū)間為[0.1,0.9]，每次變對0.1，每個算例分別運行10次，取最好解與平均解。

4.2 測試結(jié)果

在已報道的BRP求解的經(jīng)典啟發(fā)式算法中，只有文獻(xiàn)[6]的線路破壞與修復(fù)啟發(fā)式算法(DR_BRP)，本文算法將主要與其比較。

表1 大容量問題測試結(jié)果(Q=30)

在求解質(zhì)量上，文獻(xiàn)6在構(gòu)建初始解后運用了鄰域搜索，求解質(zhì)量較高，本文算法在3類不同測試問題集上，整體求解質(zhì)量低于當(dāng)前最優(yōu)解，分別為9.1%(Q=30)、14.6%(Q=20)、13.9%(Q<20)，算法對大容量問題的求解質(zhì)量優(yōu)于中容量問題與小容量問題，中、小容量問題求解質(zhì)量差距不明顯。本文算法共找到11個問題的當(dāng)前最優(yōu)解，其中在問題Minneapolis(116/10)上找到了當(dāng)前新的最好解，優(yōu)于當(dāng)前最好解1.7%(見表3)。

表2 中容量問題測試結(jié)果(Q=20)

從求解的速度來看，兩算法均運行于CPU(core i3，3.1GHZ)、Rom(4G)的PC機(jī)上，本文算法在求解速度上顯示出較大優(yōu)勢，求解三類問題的平均速度均為0.02秒，優(yōu)于文獻(xiàn)6的89.20秒(Q=30)、116.56秒(Q=20)、136.43秒(Q<20)。

在參數(shù)設(shè)置上，本文算法為2個，DR_BRP為5個，本文算法的最優(yōu)參數(shù)設(shè)置a1為[0.1,0.4]，a2為[0.6,0.9]。表中平均解偏離計算方法為(平均解-最好解)/最好解，反映算法求解穩(wěn)定性。

表3 小容量問題測試結(jié)果(Q<20)

5 結(jié)論及研究展望

BRP雖為1-PDVRP的特例，但由于車輛出發(fā)或回來時載重可不為零，故BRP線路有其獨特的性質(zhì)，本文深入研究了該問題的線路可行變換性質(zhì)，證明了插入構(gòu)造可行解的充要條件，在此基礎(chǔ)上，引入容差概念，并提出了容差插入啟發(fā)式算法，應(yīng)用標(biāo)準(zhǔn)算例測試表明算法速度快，均可在1秒內(nèi)求出較好解，參數(shù)設(shè)置簡單；算法對11個問題可找到當(dāng)前最優(yōu)解，其中1個問題找到新的當(dāng)前最好解；算法對大容量問題的求解質(zhì)量優(yōu)于中、小容量問題。

BRP是共享經(jīng)濟(jì)背景下一類資源投放的再平衡問題，除了共享單車，其它共享設(shè)施如雨傘、微型汽車等設(shè)施同樣也有再平衡的需求，因此該類問題有較強(qiáng)的應(yīng)用背景。同時由于物聯(lián)網(wǎng)的使用，共享設(shè)施的再平衡問題規(guī)模變的越來越大，因此，依據(jù)問題特點設(shè)計良好的啟發(fā)規(guī)則，進(jìn)而設(shè)計針對大規(guī)模共享設(shè)施再平衡問題的高效智能啟發(fā)式算法值的后續(xù)深入研究。