“第三方代管”參與下的共享單車回收路線優(yōu)化問題

徐國勛, 王書偉, 郭 強(qiáng), 趙 達(dá)

(1.海南大學(xué) 旅游學(xué)院,海南 ?？?570228; 2.山東科技大學(xué) 經(jīng)濟(jì)管理學(xué)院,山東 青島 266590; 3.海南大學(xué) 管理學(xué)院,海南 海口 570228)

0 引言

在中國，共享單車已成為第三大公共交通系統(tǒng)，僅2017年便為人們節(jié)約出行時間0.76億小時，減少霧霾成本13億元，提高平均出行效率15%[1]。然而根據(jù)調(diào)查研究發(fā)現(xiàn)，由于故意損壞、機(jī)械故障和零配件老化等原因，過去三年全國各城市損壞共享單車數(shù)量快速增加[2]。這些損壞的共享單車帶來了嚴(yán)重的資源浪費(fèi)問題[3]，用戶滿意度下降問題[4]，用戶騎行安全問題等[1]。因此，及時召回?fù)p壞單車成為共享單車系統(tǒng)可持續(xù)發(fā)展的關(guān)鍵因素之一。

除法律法規(guī)建設(shè)之外[5]，利用卡車進(jìn)行高效回收是目前共享單車回收問題研究的重點(diǎn)。一些研究者[6～8]考慮再平衡整個共享單車網(wǎng)絡(luò)時加入損壞單車回收的操作，即卡車在各個站點(diǎn)既轉(zhuǎn)運(yùn)可用單車又同時回收損壞單車。徐國勛等[9]認(rèn)為很難同時實(shí)現(xiàn)這兩個目標(biāo)，需要均衡考慮損壞單車的回收數(shù)量和可用單車的轉(zhuǎn)運(yùn)數(shù)量，并通過增大回收懲罰系數(shù)來提高回收需求的優(yōu)先級。一些研究者提出在回收過程中應(yīng)考慮時間因素的制約。例如王涵霄等[10]認(rèn)為部分損壞單車可以當(dāng)場維修，將維修時間加入到某些站點(diǎn)的服務(wù)時間內(nèi)，并規(guī)定維修成功的單車可即刻轉(zhuǎn)運(yùn)到別的站點(diǎn)。Lu等[11]以最小化總時間為目標(biāo)建立了一種基于真實(shí)數(shù)據(jù)的回收模型，并在模型中同時考慮了調(diào)度人員的開車時間、行走時間和損壞單車查找時間。還有一些研究者考慮了損壞單車的分布情況。例如張巍[12]等提出站點(diǎn)損壞單車近似服從正態(tài)分布，并選擇合適的成本閾值來作為站點(diǎn)選取的標(biāo)準(zhǔn)。

當(dāng)共享單車系統(tǒng)規(guī)模不是很大時，或可滿足完全基于卡車進(jìn)行回收。而我國大中城市的共享單車系統(tǒng)規(guī)模普遍很大，回收任務(wù)非常繁重，派遣卡車回收的成本又很高，運(yùn)營商沒有足夠的資源及時回收損壞單車，從而導(dǎo)致城市公共空間被損壞單車擠占的問題很突出。因此政府與社會在呼吁共享單車用戶參與損壞單車的回收利用，但由于并沒有找到有效的激勵機(jī)制，效果不盡人意[13]。鑒于此，近年來多地開始推出“第三方代管”這一新措施，由城管部門牽頭，聯(lián)合運(yùn)營商聘請第三方代管員在路面巡查。代管員除了規(guī)范車輛停放外，還使用電動三輪車將零散分布的損壞單車運(yùn)送至指定地點(diǎn)，以協(xié)助運(yùn)營商完成回收操作。第三方代管具有成本低和靈活度高的優(yōu)點(diǎn)，很快成為共享單車回收的重要補(bǔ)充力量。但同時也存在著效率和可靠性相對較低等問題，因此僅適合短距離小批量操作，而中長距離大批量操作仍需要派遣調(diào)度卡車來完成。然而在實(shí)際中卻經(jīng)常出現(xiàn)：代管員被委派將損壞單車運(yùn)送至較遠(yuǎn)距離的維修地，導(dǎo)致其單個操作周期大大變長，進(jìn)而喪失性價比；卡車被委派去回收操作困難的地點(diǎn)(例如零散分布的居民小區(qū)、擁堵的街道等)，回收成本與回收數(shù)量不成比例，喪失性價比。

以往研究全部基于有足夠數(shù)量的調(diào)度卡車完成回收任務(wù)這一前提，僅考慮部署調(diào)度卡車進(jìn)行回收，并沒有針對實(shí)際中存在的第三方代管參與回收的情況來制定回收策略。鑒于此，本文提出第三方代管參與下的共享單車回收路線優(yōu)化問題，并聚焦于將問題建模成混合整數(shù)規(guī)劃，以及設(shè)計(jì)高效智能優(yōu)化算法，為共享單車的回收管理提供重要的科學(xué)理論依據(jù)。

1 問題描述和模型建立

在本問題中，網(wǎng)絡(luò)中的站點(diǎn)被劃分為回收需求點(diǎn)和中轉(zhuǎn)點(diǎn)?；厥招枨簏c(diǎn)是存在若干損壞單車的站點(diǎn)，而中轉(zhuǎn)點(diǎn)是普通的租還車站點(diǎn)，用來臨時停放從別處運(yùn)送過來的損壞單車。運(yùn)營商調(diào)派第三方代管員進(jìn)行短距離小批量回收操作，同時派遣調(diào)度卡車進(jìn)行中長距離大批量操作?；厥杖蝿?wù)則分成兩部分：首先激勵代管員將損壞單車從回收需求點(diǎn)運(yùn)送至附近的中轉(zhuǎn)點(diǎn)，然后派遣卡車將這些集中起來的損壞單車從中轉(zhuǎn)點(diǎn)運(yùn)送至維修中心。實(shí)際中運(yùn)營商采用購買服務(wù)的方式來雇傭代管員，為衡量其完成一次任務(wù)應(yīng)獲得的獎勵，需考慮以下因素：

(1)運(yùn)送距離。由于工作成本(例如時間花費(fèi))與回收需求點(diǎn)至中轉(zhuǎn)點(diǎn)的距離成正比，因此獎勵大小與運(yùn)送距離正相關(guān)，以體現(xiàn)代管員的工作成本。

(2)回收需求點(diǎn)損壞單車數(shù)量?；厥招枨簏c(diǎn)內(nèi)共享單車損壞數(shù)量越多，公共空間被擠占情況越嚴(yán)重，因此獎勵大小與回收需求點(diǎn)損壞單車數(shù)量正相關(guān)，以激勵代管員及時將損壞單車運(yùn)走，解決這些站點(diǎn)公共空間被損壞單車擠占的問題。

(3)對中轉(zhuǎn)點(diǎn)租還車服務(wù)的影響。運(yùn)送到中轉(zhuǎn)點(diǎn)的損壞單車過多，會影響其正常租還車服務(wù)[4]，因此獎勵大小與對中轉(zhuǎn)點(diǎn)正常業(yè)務(wù)的影響程度負(fù)相關(guān)，以限制代管員出于各種原因(例如圖方便省事)將損壞單車堆積在某些站點(diǎn)。而中轉(zhuǎn)點(diǎn)容量越大，運(yùn)送過來一輛損壞單車的占比則越小，則對正常業(yè)務(wù)的影響就相對越小，故可用中轉(zhuǎn)點(diǎn)容量的倒數(shù)來表示對租還車服務(wù)的影響程度。

根據(jù)以上分析，代管員從回收需求點(diǎn)s運(yùn)送一輛損壞單車至中轉(zhuǎn)點(diǎn)i獲得的獎勵rsi可由公式(1)計(jì)算得到。其中ω表示單位獎勵系數(shù)，csi表示回收需求點(diǎn)至中轉(zhuǎn)點(diǎn)的距離，Is表示回收需求點(diǎn)s內(nèi)損壞單車數(shù)量，rmin表示獎勵下限，Li表示中轉(zhuǎn)點(diǎn)的可用容量(由于Li≥0且為整數(shù)，為防止分母為0，采用Li+1來表示)。

(1)

為表示數(shù)學(xué)模型，用到了以下符號：

集合

K:運(yùn)營商派遣的調(diào)度卡車集合；U:代管員集合；M:回收需求點(diǎn)集合；N:中轉(zhuǎn)點(diǎn)集合；N0=N∪{0}，其中0點(diǎn)表示車場(即維修中心)；V=M∪N∪{0}。

參數(shù)

Is:回收需求點(diǎn)s的初始庫存，即待回收單車數(shù)量；Li:中轉(zhuǎn)點(diǎn)i的容量；cij:點(diǎn)i和j之間的距離；μ:卡車的單位距離成本；C:卡車的容量上限；H:代管員運(yùn)送能力上限；T:用于激勵代管員的總預(yù)算；M0:一個很大的正數(shù)。

決策變量

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

(2)

(19)

目標(biāo)函數(shù)(2)包含兩部分，第一部分是卡車將中轉(zhuǎn)點(diǎn)損壞單車回收至維修中心的總成本，第二部分是代管員將損壞單車集中至中轉(zhuǎn)點(diǎn)后給予的總獎勵。約束條件(3)限定了獎勵支出預(yù)算。這是由于在實(shí)際中，一般是采用購買服務(wù)的方式來雇傭代管員，因此受到預(yù)算約束。約束條件(4)確保代管員將每個回收需求點(diǎn)內(nèi)的損壞單車全部運(yùn)出。約束條件(5)表明在中轉(zhuǎn)點(diǎn)，代管員運(yùn)送來的損壞單車總量不超過該中轉(zhuǎn)點(diǎn)容量。約束條件(6)是代管員運(yùn)送能力上限。約束條件(7)確保由代管員運(yùn)送至中轉(zhuǎn)點(diǎn)的這些損壞單車最終全部被回收至維修中心。約束條件(8)確保若卡車未服務(wù)某中轉(zhuǎn)點(diǎn)，則相應(yīng)的裝載數(shù)量為0。約束條件(9)～(11)確保每輛卡車在整個回收行程中的裝載量不超過容量限制。約束條件(9)確保每輛卡車空載狀態(tài)從維修中心出發(fā)。約束條件(10)表示卡車在該中轉(zhuǎn)點(diǎn)回收數(shù)量等于訪問該點(diǎn)前后對應(yīng)的裝載數(shù)量之差。約束(11)限定了卡車裝載量取值范圍。約束條件(12)～(13)確?？ㄜ噺木S修中心出發(fā)，并最后返回維修中心。約束條件(14)確?？ㄜ嚪?wù)過某中轉(zhuǎn)點(diǎn)后必須從該點(diǎn)離開。約束條件(15)是子環(huán)消除條件，防止卡車路線中出現(xiàn)不包括維修中心的回路。約束條件(16)～(19)限定變量取值范圍。

2 求解算法

由于本問題中包含的卡車路線問題是車輛路徑問題這一經(jīng)典的NP-Hard，這意味著本問題是更難求解的NP-Hard，當(dāng)規(guī)模較小的時候采用求解器(如CPLEX, Gurobi, Ipsolver, MOSEK等)可有效對問題進(jìn)行求解。但是Ho和Szeto[14]指出這些求解器的性能與問題規(guī)模呈負(fù)相關(guān)關(guān)系，不適合處理大規(guī)模問題，而智能優(yōu)化算法更適合處理這類問題。鑒于共享單車網(wǎng)絡(luò)規(guī)模很大，本文選擇設(shè)計(jì)智能優(yōu)化算法求解所提問題。

2.1 解的評估

2.2 教育與修復(fù)

為提高子代個體的質(zhì)量，引入了教育算子。在教育算子中，包含隨機(jī)刪除，半徑破壞，最小貢獻(xiàn)移除，隨機(jī)插入，最優(yōu)插入，多點(diǎn)插入，隨機(jī)交換和隨機(jī)逆序八種局部搜索方法：

(4)隨機(jī)插入。從未被訪問過的站點(diǎn)中隨機(jī)選擇一個點(diǎn)，然后插入到解中。

(5)最優(yōu)插入。隨機(jī)選擇未訪問過的點(diǎn)t，并將t插入解中最小成本位置。例如若t被插入至點(diǎn)i和j之間，若i,j=arc min(μcit+μctj-μcij)(i,j)∈A，則該插入位置為最小成本位置。

(6)多點(diǎn)插入。從未訪問站點(diǎn)中隨機(jī)挑選兩個點(diǎn)，然后將二者隨機(jī)插入到解中。

(7)隨機(jī)交換。從解隨機(jī)選擇兩個點(diǎn)并交換它們在解中的位置。

(8)隨機(jī)逆序。隨機(jī)選擇一條子序列并將該子序列逆序。

教育算子的具體流程如下：

經(jīng)過教育操作后的解如果變得可行則將其置于可行子種群中，如果仍然不可行則將其置于不可行子種群中，然后進(jìn)行概率為Prepair的修復(fù)操作。每個不可行解最多可以修復(fù)兩次，第一次將F(p)中的系數(shù)α乘 (1+γ)倍，第二次將系數(shù)α乘10(1+γ)，其中γ于區(qū)間(0,1]隨機(jī)取值。如果修復(fù)之后，原來的不可行解成為可行解，則將修復(fù)后的新可行解置于可行子種群中，與此同時在非可行子種群中保留原不可行解。

教育算子1:將所有方法的編號放置在集合Ω中;2:隨機(jī)在Ω中挑出一種方法;3:如果該方法能夠改進(jìn)當(dāng)前解,則重復(fù)使用該方法對當(dāng)前解進(jìn)行改進(jìn)。如果連續(xù)進(jìn)行ITedu次迭代都無法改進(jìn)當(dāng)前解,則教育算子需被終止;4:從Ω中將該局部搜索方法剔除;5:如果Ω不為空集,則轉(zhuǎn)步驟2,否則結(jié)束教育算子。

2.3 嵌入算法

步驟1.1將剩余庫存不為零的回收需求點(diǎn)和剩余可用容量不為零中轉(zhuǎn)點(diǎn)對應(yīng)的OD對全部置于集合Ω；

步驟1.2根據(jù)rsi的數(shù)值，按照由小到大的順序?qū)夕钢腥縊D對排序；

步驟1.3確定Ω中第一個OD對可運(yùn)送的損壞單車最大數(shù)量Zsi=min{Is,Li}；

步驟1.4更新回收需求點(diǎn)的剩余庫存和中轉(zhuǎn)點(diǎn)的剩余可用容量。Is←Is-Zsi，Li←Li-Zsi。如果Is=0，則從Ω中將包含s點(diǎn)的OD對全部移除；如果Li=0，將包含i點(diǎn)的OD對全部移除；

步驟1.5重復(fù)執(zhí)行步驟1.3和步驟1.4，直到Ω中元素全部被清空，于是全部Zsi便可確定；

步驟1.6把運(yùn)送任務(wù)(Zsi輛損壞單車)分給v=[1+Zsi/H]個代管員，其中[.]表示取整。

步驟2.1令k=1；

步驟2.2將卡車k的剩余載重空間表示為Cleft；

步驟2.5若k≥|K|，轉(zhuǎn)步驟3。否則更新k←k+1，轉(zhuǎn)步驟2.2。

3 數(shù)值實(shí)驗(yàn)

3.1 回收需求點(diǎn)內(nèi)損壞單車數(shù)量與回收成本之間的關(guān)系

一般情況下，出于種種原因(調(diào)度車輛不足、預(yù)算限制等)原因，運(yùn)營商并不會及時回收損壞單車，常常導(dǎo)致?lián)p壞單車在站點(diǎn)內(nèi)逐漸積壓。本節(jié)論證在本文所提回收策略下及時回收損壞單車反而會減少運(yùn)營成本。為方便求出最優(yōu)解，令C=20,T=100,ω=0.5,μ=1,H=4,rmin=0,|K|=1,|U|=5。坐標(biāo)={(12,10);(8,20);(14,7);(10,15);(1,3);(5,6);(2,2);(0,0)}。其中前三個點(diǎn)為中轉(zhuǎn)點(diǎn)，其容量分別為{5,7,9}，最后一個點(diǎn)為沒有任何需求的車場，其余點(diǎn)為回收需求點(diǎn)，損壞單車數(shù)量分別為{4,4,2,2,1}。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 回收需求點(diǎn)內(nèi)損壞單車數(shù)量與回收成本的關(guān)系

以回收需求點(diǎn)1 為例論證損壞單車數(shù)量對運(yùn)營成本的影響。在橫坐標(biāo)(損壞單車數(shù)量)由0至10的變化過程中，卡車運(yùn)輸成本呈增加趨勢。這是由于中轉(zhuǎn)點(diǎn)存在容量上限，當(dāng)某個中轉(zhuǎn)點(diǎn)達(dá)到容量上限后，需要把損壞單車存放到其它中轉(zhuǎn)點(diǎn)。相應(yīng)地，卡車在回收過程中需要訪問的中轉(zhuǎn)點(diǎn)數(shù)量增加，進(jìn)而使得其運(yùn)輸成本增加。由圖1還可得，“第三方代管”的獎勵支出關(guān)于損壞單車數(shù)量的曲線斜率為正。這表明隨著站點(diǎn)內(nèi)積壓的損壞單車數(shù)量的增加，導(dǎo)致回收每輛損壞單車的單位獎勵增加也在增加，即需要支付給代管員更多的獎勵來激勵其將損壞單車運(yùn)走，以解決站點(diǎn)公共空間被損壞單車擠占的問題。由于總回收成本為卡車運(yùn)輸成本和“第三方代管”的獎勵支出之和，因此總回收成本亦隨著損壞單車數(shù)量的增加。其余回收需求點(diǎn)可以得到類似結(jié)論。

綜上所述，在本文所提回收策略下，回收需求點(diǎn)內(nèi)損壞單車數(shù)量與總回收成本是正相關(guān)關(guān)系。這意味著本文所提回收策略下及時回收損壞單車，不僅能夠減輕站點(diǎn)公共空間被損壞單車擠占的問題，還能有效減少回收成本。

3.2 算法性能測試

數(shù)值實(shí)驗(yàn)環(huán)境是i7-2600CPU主頻3.40GHz內(nèi)存16GB的PC電腦，編程語言為C#。為了測試所設(shè)計(jì)HGA算法性能，采用Gurobi 8.0和遺傳算法(GA)作為比對算法。由于沒有針對本文所研究問題的算例，因此依據(jù)Ii均勻分布于[1,5]，Li均勻分布于[5,10]，T設(shè)為1000，站點(diǎn)坐標(biāo)均勻分布于[0,50]，C=20，H=10，rmin=0，ω=1和μ=1生成規(guī)模不同的數(shù)據(jù)組。HGA參數(shù)中，μ=25,Nindiv=25,Nelite=10,Prepair=0.5,ξ=0.2,λ=40,Itdiv=0.4ItNI。

表1最左側(cè)展示了Gurobi求解結(jié)果，包括了上界(UB)，下界(LB)以及反應(yīng)求解質(zhì)量的gap(數(shù)值越小則表明解的質(zhì)量越高)。表1中間和最右側(cè)分別展示了GA和HGA運(yùn)行20次求得的結(jié)果，包括平均目標(biāo)函數(shù)值(Avg)，最好的解(Min)，相應(yīng)的gap(數(shù)值越小則表明解的質(zhì)量越高)以及終止時間(CPU/s)。

表1 算法性能比較

首先，與Gurobi求解結(jié)果進(jìn)行比較。從算例3至算例6，發(fā)現(xiàn)在規(guī)定求解時間內(nèi)Gurobi只能得到一個上界和下界，已無法確定最優(yōu)解。從算例7至算例9，Gurobi在規(guī)定時間內(nèi)已無法確定一個上界和下界。對于算例1，HGA求解時間比Gurobi求解時間要長，這是由于只要沒有達(dá)到終止條件，HGA即使找到了最優(yōu)解也不會終止算法，這是智能優(yōu)化算法常見的問題。從算例3至算例6，HGA求解的gap與Gurobi求解的gap差距越來越大，這表明HGA求解質(zhì)量顯著超過了Gurobi。從算例7至算例9，相比Gurobi已無法確定一個可行解，HGA仍然能在短時間內(nèi)求得可行解。

其次，與GA求解結(jié)果進(jìn)行比較。從算例1至算例9，HGA全部指標(biāo)性能均超過GA。在相同的運(yùn)算時間內(nèi)，HGA平均目標(biāo)函數(shù)值比GA降低約4.3%，以HGA最好的解數(shù)值比GA平均減少約0.66%。

4 結(jié)束語

基于實(shí)際中第三方代管參與短距離小批量共享單車回收這一情況，本文提出激勵代管員將損壞單車從回收需求點(diǎn)運(yùn)送至附近的中轉(zhuǎn)點(diǎn)，然后派遣卡車將這些集中起來的損壞單車從中轉(zhuǎn)點(diǎn)運(yùn)送至維修中心。為衡量代管員完成一次任務(wù)應(yīng)獲得的獎勵，考慮運(yùn)送距離、回收需求點(diǎn)損壞單車數(shù)量和對中轉(zhuǎn)點(diǎn)正常業(yè)務(wù)的影響程度。并把問題建模為混合整數(shù)規(guī)劃模型，同時針對問題特征設(shè)計(jì)了一種改進(jìn)遺傳算法。其中遺傳算法用來確定卡車路線和中轉(zhuǎn)點(diǎn)，嵌入的啟發(fā)式算法用來確定代管員的路線和運(yùn)送數(shù)量以及卡車在每個中轉(zhuǎn)點(diǎn)的回收數(shù)量。

本文通過數(shù)值實(shí)驗(yàn)論證了所設(shè)計(jì)算法的高效性，并驗(yàn)證了第三方代管參與的回收策略不僅能夠減輕站點(diǎn)公共空間被損壞單車擠占的問題，還能有效減少回收成本，對改進(jìn)共享單車回收管理(包括提高回收效率和降低回收成本)具有重要的實(shí)際意義。未來研究可考慮將本問題擴(kuò)展到多重圖網(wǎng)絡(luò)中。