徐國勛, 王書偉, 郭 強, 趙 達
(1.海南大學 旅游學院,海南 海口 570228; 2.山東科技大學 經(jīng)濟管理學院,山東 青島 266590; 3.海南大學 管理學院,海南 海口 570228)
在中國，共享單車已成為第三大公共交通系統(tǒng)，僅2017年便為人們節(jié)約出行時間0.76億小時，減少霧霾成本13億元，提高平均出行效率15%[1]。然而根據(jù)調查研究發(fā)現(xiàn)，由于故意損壞、機械故障和零配件老化等原因，過去三年全國各城市損壞共享單車數(shù)量快速增加[2]。這些損壞的共享單車帶來了嚴重的資源浪費問題[3]，用戶滿意度下降問題[4]，用戶騎行安全問題等[1]。因此，及時召回損壞單車成為共享單車系統(tǒng)可持續(xù)發(fā)展的關鍵因素之一。
除法律法規(guī)建設之外[5]，利用卡車進行高效回收是目前共享單車回收問題研究的重點。一些研究者[6～8]考慮再平衡整個共享單車網(wǎng)絡時加入損壞單車回收的操作，即卡車在各個站點既轉運可用單車又同時回收損壞單車。徐國勛等[9]認為很難同時實現(xiàn)這兩個目標，需要均衡考慮損壞單車的回收數(shù)量和可用單車的轉運數(shù)量，并通過增大回收懲罰系數(shù)來提高回收需求的優(yōu)先級。一些研究者提出在回收過程中應考慮時間因素的制約。例如王涵霄等[10]認為部分損壞單車可以當場維修，將維修時間加入到某些站點的服務時間內(nèi)，并規(guī)定維修成功的單車可即刻轉運到別的站點。Lu等[11]以最小化總時間為目標建立了一種基于真實數(shù)據(jù)的回收模型，并在模型中同時考慮了調度人員的開車時間、行走時間和損壞單車查找時間。還有一些研究者考慮了損壞單車的分布情況。例如張巍[12]等提出站點損壞單車近似服從正態(tài)分布，并選擇合適的成本閾值來作為站點選取的標準。
當共享單車系統(tǒng)規(guī)模不是很大時，或可滿足完全基于卡車進行回收。而我國大中城市的共享單車系統(tǒng)規(guī)模普遍很大，回收任務非常繁重，派遣卡車回收的成本又很高，運營商沒有足夠的資源及時回收損壞單車，從而導致城市公共空間被損壞單車擠占的問題很突出。因此政府與社會在呼吁共享單車用戶參與損壞單車的回收利用，但由于并沒有找到有效的激勵機制，效果不盡人意[13]。鑒于此，近年來多地開始推出“第三方代管”這一新措施，由城管部門牽頭，聯(lián)合運營商聘請第三方代管員在路面巡查。代管員除了規(guī)范車輛停放外，還使用電動三輪車將零散分布的損壞單車運送至指定地點，以協(xié)助運營商完成回收操作。第三方代管具有成本低和靈活度高的優(yōu)點，很快成為共享單車回收的重要補充力量。但同時也存在著效率和可靠性相對較低等問題，因此僅適合短距離小批量操作，而中長距離大批量操作仍需要派遣調度卡車來完成。然而在實際中卻經(jīng)常出現(xiàn)：代管員被委派將損壞單車運送至較遠距離的維修地，導致其單個操作周期大大變長，進而喪失性價比；
卡車被委派去回收操作困難的地點(例如零散分布的居民小區(qū)、擁堵的街道等)，回收成本與回收數(shù)量不成比例，喪失性價比。
以往研究全部基于有足夠數(shù)量的調度卡車完成回收任務這一前提，僅考慮部署調度卡車進行回收，并沒有針對實際中存在的第三方代管參與回收的情況來制定回收策略。鑒于此，本文提出第三方代管參與下的共享單車回收路線優(yōu)化問題，并聚焦于將問題建模成混合整數(shù)規(guī)劃，以及設計高效智能優(yōu)化算法，為共享單車的回收管理提供重要的科學理論依據(jù)。
在本問題中，網(wǎng)絡中的站點被劃分為回收需求點和中轉點。回收需求點是存在若干損壞單車的站點，而中轉點是普通的租還車站點，用來臨時停放從別處運送過來的損壞單車。運營商調派第三方代管員進行短距離小批量回收操作，同時派遣調度卡車進行中長距離大批量操作。回收任務則分成兩部分：首先激勵代管員將損壞單車從回收需求點運送至附近的中轉點，然后派遣卡車將這些集中起來的損壞單車從中轉點運送至維修中心。實際中運營商采用購買服務的方式來雇傭代管員，為衡量其完成一次任務應獲得的獎勵，需考慮以下因素：
(1)運送距離。由于工作成本(例如時間花費)與回收需求點至中轉點的距離成正比，因此獎勵大小與運送距離正相關，以體現(xiàn)代管員的工作成本。
(2)回收需求點損壞單車數(shù)量。回收需求點內(nèi)共享單車損壞數(shù)量越多，公共空間被擠占情況越嚴重，因此獎勵大小與回收需求點損壞單車數(shù)量正相關，以激勵代管員及時將損壞單車運走，解決這些站點公共空間被損壞單車擠占的問題。
(3)對中轉點租還車服務的影響。運送到中轉點的損壞單車過多，會影響其正常租還車服務[4]，因此獎勵大小與對中轉點正常業(yè)務的影響程度負相關，以限制代管員出于各種原因(例如圖方便省事)將損壞單車堆積在某些站點。而中轉點容量越大，運送過來一輛損壞單車的占比則越小，則對正常業(yè)務的影響就相對越小，故可用中轉點容量的倒數(shù)來表示對租還車服務的影響程度。
根據(jù)以上分析，代管員從回收需求點s運送一輛損壞單車至中轉點i獲得的獎勵rsi可由公式(1)計算得到。其中ω表示單位獎勵系數(shù)，csi表示回收需求點至中轉點的距離，Is表示回收需求點s內(nèi)損壞單車數(shù)量，rmin表示獎勵下限，Li表示中轉點的可用容量(由于Li≥0且為整數(shù)，為防止分母為0，采用Li+1來表示)。
(1)
為表示數(shù)學模型，用到了以下符號：
集合
K:運營商派遣的調度卡車集合；
U:代管員集合；
M:回收需求點集合；
N:中轉點集合；
N0=N∪{0}，其中0點表示車場(即維修中心)；
V=M∪N∪{0}。
參數(shù)
Is:回收需求點s的初始庫存，即待回收單車數(shù)量；
Li:中轉點i的容量；
cij:點i和j之間的距離；
μ:卡車的單位距離成本；
C:卡車的容量上限；
H:代管員運送能力上限；
T:用于激勵代管員的總預算；
M0:一個很大的正數(shù)。
決策變量
數(shù)學模型
(2)
(19)
目標函數(shù)(2)包含兩部分，第一部分是卡車將中轉點損壞單車回收至維修中心的總成本，第二部分是代管員將損壞單車集中至中轉點后給予的總獎勵。約束條件(3)限定了獎勵支出預算。這是由于在實際中，一般是采用購買服務的方式來雇傭代管員，因此受到預算約束。約束條件(4)確保代管員將每個回收需求點內(nèi)的損壞單車全部運出。約束條件(5)表明在中轉點，代管員運送來的損壞單車總量不超過該中轉點容量。約束條件(6)是代管員運送能力上限。約束條件(7)確保由代管員運送至中轉點的這些損壞單車最終全部被回收至維修中心。約束條件(8)確保若卡車未服務某中轉點，則相應的裝載數(shù)量為0。約束條件(9)～(11)確保每輛卡車在整個回收行程中的裝載量不超過容量限制。約束條件(9)確保每輛卡車空載狀態(tài)從維修中心出發(fā)。約束條件(10)表示卡車在該中轉點回收數(shù)量等于訪問該點前后對應的裝載數(shù)量之差。約束(11)限定了卡車裝載量取值范圍。約束條件(12)～(13)確保卡車從維修中心出發(fā)，并最后返回維修中心。約束條件(14)確保卡車服務過某中轉點后必須從該點離開。約束條件(15)是子環(huán)消除條件，防止卡車路線中出現(xiàn)不包括維修中心的回路。約束條件(16)～(19)限定變量取值范圍。
由于本問題中包含的卡車路線問題是車輛路徑問題這一經(jīng)典的NP-Hard，這意味著本問題是更難求解的NP-Hard，當規(guī)模較小的時候采用求解器(如CPLEX, Gurobi, Ipsolver, MOSEK等)可有效對問題進行求解。但是Ho和Szeto[14]指出這些求解器的性能與問題規(guī)模呈負相關關系，不適合處理大規(guī)模問題，而智能優(yōu)化算法更適合處理這類問題。鑒于共享單車網(wǎng)絡規(guī)模很大，本文選擇設計智能優(yōu)化算法求解所提問題。
2.1 解的評估
2.2 教育與修復
為提高子代個體的質量，引入了教育算子。在教育算子中，包含隨機刪除，半徑破壞，最小貢獻移除，隨機插入，最優(yōu)插入，多點插入，隨機交換和隨機逆序八種局部搜索方法：
(4)隨機插入。從未被訪問過的站點中隨機選擇一個點，然后插入到解中。
(5)最優(yōu)插入。隨機選擇未訪問過的點t，并將t插入解中最小成本位置。例如若t被插入至點i和j之間，若i,j=arc min(μcit+μctj-μcij)(i,j)∈A，則該插入位置為最小成本位置。
(6)多點插入。從未訪問站點中隨機挑選兩個點，然后將二者隨機插入到解中。
(7)隨機交換。從解隨機選擇兩個點并交換它們在解中的位置。
(8)隨機逆序。隨機選擇一條子序列并將該子序列逆序。
教育算子的具體流程如下：
經(jīng)過教育操作后的解如果變得可行則將其置于可行子種群中，如果仍然不可行則將其置于不可行子種群中，然后進行概率為Prepair的修復操作。每個不可行解最多可以修復兩次，第一次將F(p)中的系數(shù)α乘 (1+γ)倍，第二次將系數(shù)α乘10(1+γ)，其中γ于區(qū)間(0,1]隨機取值。如果修復之后，原來的不可行解成為可行解，則將修復后的新可行解置于可行子種群中，與此同時在非可行子種群中保留原不可行解。
教育算子1:將所有方法的編號放置在集合Ω中;2:隨機在Ω中挑出一種方法;3:如果該方法能夠改進當前解,則重復使用該方法對當前解進行改進。如果連續(xù)進行ITedu次迭代都無法改進當前解,則教育算子需被終止;4:從Ω中將該局部搜索方法剔除;5:如果Ω不為空集,則轉步驟2,否則結束教育算子。
2.3 嵌入算法
步驟1.1將剩余庫存不為零的回收需求點和剩余可用容量不為零中轉點對應的OD對全部置于集合Ω；
步驟1.2根據(jù)rsi的數(shù)值，按照由小到大的順序對集合Ω中全部OD對排序；
步驟1.3確定Ω中第一個OD對可運送的損壞單車最大數(shù)量Zsi=min{Is,Li}；
步驟1.4更新回收需求點的剩余庫存和中轉點的剩余可用容量。Is←Is-Zsi，Li←Li-Zsi。如果Is=0，則從Ω中將包含s點的OD對全部移除；
如果Li=0，將包含i點的OD對全部移除；
步驟1.5重復執(zhí)行步驟1.3和步驟1.4，直到Ω中元素全部被清空，于是全部Zsi便可確定；
步驟1.6把運送任務(Zsi輛損壞單車)分給v=[1+Zsi/H]個代管員，其中[.]表示取整。
步驟2.1令k=1；
步驟2.2將卡車k的剩余載重空間表示為Cleft；
步驟2.5若k≥|K|，轉步驟3。否則更新k←k+1，轉步驟2.2。
3.1 回收需求點內(nèi)損壞單車數(shù)量與回收成本之間的關系
一般情況下，出于種種原因(調度車輛不足、預算限制等)原因，運營商并不會及時回收損壞單車，常常導致?lián)p壞單車在站點內(nèi)逐漸積壓。本節(jié)論證在本文所提回收策略下及時回收損壞單車反而會減少運營成本。為方便求出最優(yōu)解，令C=20,T=100,ω=0.5,μ=1,H=4,rmin=0,|K|=1,|U|=5。坐標={(12,10);(8,20);(14,7);(10,15);(1,3);(5,6);(2,2);(0,0)}。其中前三個點為中轉點，其容量分別為{5,7,9}，最后一個點為沒有任何需求的車場，其余點為回收需求點，損壞單車數(shù)量分別為{4,4,2,2,1}。實驗結果如圖1所示。
圖1 回收需求點內(nèi)損壞單車數(shù)量與回收成本的關系
以回收需求點1 為例論證損壞單車數(shù)量對運營成本的影響。在橫坐標(損壞單車數(shù)量)由0至10的變化過程中，卡車運輸成本呈增加趨勢。這是由于中轉點存在容量上限，當某個中轉點達到容量上限后，需要把損壞單車存放到其它中轉點。相應地，卡車在回收過程中需要訪問的中轉點數(shù)量增加，進而使得其運輸成本增加。由圖1還可得，“第三方代管”的獎勵支出關于損壞單車數(shù)量的曲線斜率為正。這表明隨著站點內(nèi)積壓的損壞單車數(shù)量的增加，導致回收每輛損壞單車的單位獎勵增加也在增加，即需要支付給代管員更多的獎勵來激勵其將損壞單車運走，以解決站點公共空間被損壞單車擠占的問題。由于總回收成本為卡車運輸成本和“第三方代管”的獎勵支出之和，因此總回收成本亦隨著損壞單車數(shù)量的增加。其余回收需求點可以得到類似結論。
綜上所述，在本文所提回收策略下，回收需求點內(nèi)損壞單車數(shù)量與總回收成本是正相關關系。這意味著本文所提回收策略下及時回收損壞單車，不僅能夠減輕站點公共空間被損壞單車擠占的問題，還能有效減少回收成本。
3.2 算法性能測試
數(shù)值實驗環(huán)境是i7-2600CPU主頻3.40GHz內(nèi)存16GB的PC電腦，編程語言為C#。為了測試所設計HGA算法性能，采用Gurobi 8.0和遺傳算法(GA)作為比對算法。由于沒有針對本文所研究問題的算例，因此依據(jù)Ii均勻分布于[1,5]，Li均勻分布于[5,10]，T設為1000，站點坐標均勻分布于[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最左側展示了Gurobi求解結果，包括了上界(UB)，下界(LB)以及反應求解質量的gap(數(shù)值越小則表明解的質量越高)。表1中間和最右側分別展示了GA和HGA運行20次求得的結果，包括平均目標函數(shù)值(Avg)，最好的解(Min)，相應的gap(數(shù)值越小則表明解的質量越高)以及終止時間(CPU/s)。
表1 算法性能比較
首先，與Gurobi求解結果進行比較。從算例3至算例6，發(fā)現(xiàn)在規(guī)定求解時間內(nèi)Gurobi只能得到一個上界和下界，已無法確定最優(yōu)解。從算例7至算例9，Gurobi在規(guī)定時間內(nèi)已無法確定一個上界和下界。對于算例1，HGA求解時間比Gurobi求解時間要長，這是由于只要沒有達到終止條件，HGA即使找到了最優(yōu)解也不會終止算法，這是智能優(yōu)化算法常見的問題。從算例3至算例6，HGA求解的gap與Gurobi求解的gap差距越來越大，這表明HGA求解質量顯著超過了Gurobi。從算例7至算例9，相比Gurobi已無法確定一個可行解，HGA仍然能在短時間內(nèi)求得可行解。
其次，與GA求解結果進行比較。從算例1至算例9，HGA全部指標性能均超過GA。在相同的運算時間內(nèi)，HGA平均目標函數(shù)值比GA降低約4.3%，以HGA最好的解數(shù)值比GA平均減少約0.66%。
基于實際中第三方代管參與短距離小批量共享單車回收這一情況，本文提出激勵代管員將損壞單車從回收需求點運送至附近的中轉點，然后派遣卡車將這些集中起來的損壞單車從中轉點運送至維修中心。為衡量代管員完成一次任務應獲得的獎勵，考慮運送距離、回收需求點損壞單車數(shù)量和對中轉點正常業(yè)務的影響程度。并把問題建模為混合整數(shù)規(guī)劃模型，同時針對問題特征設計了一種改進遺傳算法。其中遺傳算法用來確定卡車路線和中轉點，嵌入的啟發(fā)式算法用來確定代管員的路線和運送數(shù)量以及卡車在每個中轉點的回收數(shù)量。
本文通過數(shù)值實驗論證了所設計算法的高效性，并驗證了第三方代管參與的回收策略不僅能夠減輕站點公共空間被損壞單車擠占的問題，還能有效減少回收成本，對改進共享單車回收管理(包括提高回收效率和降低回收成本)具有重要的實際意義。未來研究可考慮將本問題擴展到多重圖網(wǎng)絡中。
猜你喜歡維修中心代管約束條件維修中心參與回收時閉環(huán)供應鏈的定價決策及回收模式選擇運籌與管理(2022年7期)2022-08-16基于一種改進AZSVPWM的滿調制度死區(qū)約束條件分析電機與控制應用(2022年4期)2022-06-27冬殘奧會上的“4S店”文萃報·周二版(2022年10期)2022-03-19道通科技成都售后維修中心正式成立汽車維修與保養(yǎng)(2019年8期)2019-11-26試論如何有效強化村級財務管理經(jīng)營者(2019年11期)2019-07-25“代管家長”到我家人大建設(2019年4期)2019-07-13A literature review of research exploring the experiences of overseas nurses in the United Kingdom (2002–2017)Frontiers of Nursing(2018年1期)2018-05-21——記能化集團公司“十大工匠”、中原大化閥門維修中心主任高建軍">技能大師的“ 閥門情”——記能化集團公司“十大工匠”、中原大化閥門維修中心主任高建軍河南化工(2017年6期)2017-07-07資金代管應堅持以村為本農(nóng)村財務會計(2016年7期)2016-04-02幸福來敲門觀察與思考(2011年4期)2011-09-20