需求不確定的故障共享單車回收PVRP研究

徐陽(yáng),周亞南,蘇兵,黎建強(qiáng),張欣

摘要：為了及時(shí)有效地回收城市道路網(wǎng)絡(luò)中的故障共享單車，本文考慮單車停放站點(diǎn)上回收需求呈現(xiàn)的不確定特征，建立以行駛總距離最小為目標(biāo)的回收周期性車輛路徑選擇模型。采用基約束魯棒優(yōu)化方法，利用有界區(qū)間對(duì)不確定的回收量進(jìn)行描述，并引入擾動(dòng)系數(shù)和控制系數(shù)調(diào)節(jié)模型的魯棒性和適應(yīng)性。針對(duì)模型設(shè)計(jì)近似算法進(jìn)行求解，分析算法近似比的上下界，通過(guò)實(shí)例分析驗(yàn)證了算法和模型的有效性。

關(guān)鍵詞：需求不確定；周期性車輛路徑；魯棒優(yōu)化；近似算法

中圖分類號(hào)：C934文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2097-0145（2022）05-0073-08doi：10.11847/fj.41.5.73

Period Vehicle Routing Problem for Fault-sharing Bicycle

Recycling with Demand Uncertain

XU Yang1，2，3， ZHOU Ya-nan1，2，3， SU Bing1，2，3， LI Jian-qiang4， ZHANG Xin1，2，3

（1.School of Economics and Management， Xian Technological University， Xian 710021， China; 2.Soft Science Base for Ordnance Industry Innovation & Dvelopment in Shaanxi Province， Xian 710021， China; 3.Civil-Military Integration Science and Technology Innovation Research Center of Shaanxis Colleges and Universities， Xian 710021， China; 4.International Business School， Shaanxi Normal University， Xian 710119， China）

Abstract：In order to recover the fault-sharing bicycle in the urban road network timely and effectively， considering the uncertain characteristics of the recovery demand on the single vehicle parking spot， a recovery periodic vehicle route selection model aiming at minimizing the total distance is established. The basis constrained robust optimization method is adopted， the uncertain recovery is described by bounded interval， and the disturbance coefficient and control coefficient are introduced to adjust the robustness and adaptability of the model. The approximation algorithm is designed to solve the model， and the upper and lower bounds of the approximation ratio of the approximation algorithm are analyzed. An example analysis is given to verify the effectiveness of the algorithm and the model.

Key words：demand uncertain; period vehicle routing problem; robust optimization; approximate algorithm

1引言

共享單車作為城市交通的重要組成部分，是實(shí)現(xiàn)城市綠色、低碳出行的重要工具，其輕便快捷的優(yōu)勢(shì)，是解決城市出行“最后一公里”問(wèn)題的重要手段。但是共享單車在快速發(fā)展的同時(shí)，遇到了諸多問(wèn)題：共享單車因自然損耗、人為損壞等原因會(huì)出現(xiàn)故障，需要進(jìn)行回收處理。而實(shí)際中，故障共享單車存在的停放點(diǎn)和產(chǎn)生量往往是不確定的，對(duì)所有站點(diǎn)進(jìn)行單次回收，常常難以滿足實(shí)際的回收需求。因此，如何根據(jù)共享單車這一特殊貨物的特性，考慮回收量不確定的情形下，設(shè)計(jì)科學(xué)、有效的周期性回收調(diào)度策略是一個(gè)亟待解決的問(wèn)題。

故障共享單車的回收是共享單車運(yùn)營(yíng)過(guò)程中不可避免的問(wèn)題。現(xiàn)有對(duì)共享單車系統(tǒng)的研究主要集中在共享車輛調(diào)度優(yōu)化與站點(diǎn)需求預(yù)測(cè)方面。針對(duì)考慮庫(kù)存的車輛調(diào)度問(wèn)題，以公共自行車調(diào)運(yùn)庫(kù)存量最小為目標(biāo)，Ines和Anabela［1］首次考慮了共享單車站點(diǎn)的服務(wù)水平來(lái)平衡庫(kù)存的共享單車車輛調(diào)度問(wèn)題。Brinkmann等［2］研究了自行車共享系統(tǒng)的隨機(jī)庫(kù)存路徑問(wèn)題。Schuijbroek等［3］根據(jù)每個(gè)公共自行車站點(diǎn)的服務(wù)水平，選擇車輛路徑進(jìn)行調(diào)配。針對(duì)解決公共自行車需求不平衡問(wèn)題，Ghosh等［4］提出基于車輛路徑選擇的公共自行車動(dòng)態(tài)復(fù)位優(yōu)化方法。Leonardo等［5］提出了根據(jù)空間和社會(huì)公平的原則對(duì)區(qū)域中的自由式共享單車系統(tǒng)進(jìn)行調(diào)度的分配策略。針對(duì)公共自行車需求預(yù)測(cè)問(wèn)題，Xu等［6］提出了一種基于隨機(jī)森林（RF）的改進(jìn)預(yù)測(cè)方法，并利用遺傳算法對(duì)共享單車調(diào)度路線進(jìn)行優(yōu)化。Wang等［7］基于深度學(xué)習(xí)（DL）模型對(duì)自行車共享網(wǎng)絡(luò)短期需求預(yù)測(cè)進(jìn)行研究。針對(duì)共享單車系統(tǒng)的站點(diǎn)需求預(yù)測(cè)同時(shí)對(duì)站點(diǎn)的數(shù)量及容量規(guī)劃安排問(wèn)題，Chen等［8］基于自行車出行模式的稀疏性和局部性，提出了一個(gè)稀疏加權(quán)正則化模型分析站點(diǎn)的潛在需求。Dell等［9］運(yùn)用啟發(fā)式算法研究了自行車共享再平衡問(wèn)題。多數(shù)車輛調(diào)度研究仍使用傳統(tǒng)的數(shù)學(xué)優(yōu)化方式，也有另辟蹊徑的研究者，試圖使用激勵(lì)機(jī)制來(lái)提高共享單車的使用率。如Tsai等［10］研究通過(guò)調(diào)節(jié)返回焦慮信息值提高共享單車調(diào)度的效果。

相對(duì)于共享單車的調(diào)度研究，故障共享單車的回收研究相對(duì)較少?，F(xiàn)有對(duì)故障共享單車的研究大多假設(shè)回收需求量確定。Wang等［11］研究了可用自行車再平衡過(guò)程中損壞車輛的回收問(wèn)題。以系統(tǒng)調(diào)度時(shí)間最短為目標(biāo)，肖建華等［12］將故障單車信息的不確定性引入車輛調(diào)度中，研究了新車投放、舊車調(diào)撥、壞車回收的共享單車聯(lián)合調(diào)度問(wèn)題。Kaspi等［13］提出了一種EUDF函數(shù)用來(lái)表示給定時(shí)間段內(nèi)不同租用或還車的用戶數(shù)量的期望加權(quán)之和。

現(xiàn)有研究，大多是假設(shè)回收量確定情形下的單周期回收；而實(shí)際中，回收工作是一個(gè)長(zhǎng)期且回收量動(dòng)態(tài)變化的系統(tǒng)工程，但單周期的最優(yōu)方案不能滿足全局最優(yōu)。因此，引入“全周期管理”（product lifecycle management， PLM）理念，即把回收對(duì)象視為一個(gè)動(dòng)態(tài)變化的個(gè)體，從其分布特點(diǎn)、系統(tǒng)要素等層面進(jìn)行全周期統(tǒng)籌和全過(guò)程整合，以確保整個(gè)回收體系形成一個(gè)有機(jī)的閉環(huán)，真正做到運(yùn)轉(zhuǎn)高效。

鑒于此，本文提出了回收需求不確定的故障共享單車回收周期車輛路徑（PVRP）問(wèn)題。即考慮回收需求不確定下，根據(jù)站點(diǎn)上的故障共享單車回收量進(jìn)行不同周期的回收服務(wù)。并以行駛總距離最小為目標(biāo)，決策每個(gè)站點(diǎn)回收量和回收車輛路徑，給出可操作性強(qiáng)的故障共享單車回收方案，最終將研究成果應(yīng)用于實(shí)際，為城市共享單車企業(yè)高效率回收故障共享單車提供理論依據(jù)。

2問(wèn)題描述與建模

2.1問(wèn)題描述與分析

已知無(wú)向網(wǎng)絡(luò)G=（V，E），V={v1，…，vi，…，vn}∪{v0}為點(diǎn)集，其中v0表示回收中心，{v1，…，vi，…，vn}表示網(wǎng)絡(luò)中有n個(gè)共享單車停放點(diǎn)，停放點(diǎn)vi上的故障共享單車回收量qi∈［i-i，i+i］，i為理想值或均值，i為絕對(duì)偏差。一輛容載量為Q的回收車輛空載從回收中心出發(fā)進(jìn)行回收服務(wù)，對(duì)停放點(diǎn)vi進(jìn)行hi=「qi/Q次回收，車輛滿載后回到回收中心。滿載的回收車輛在回收中心卸載后繼續(xù)進(jìn)行回收任務(wù)，直到服務(wù)完所有站點(diǎn)的回收需求。因此，如何選擇回收車輛路徑，使得車輛滿載后返回回收中心的行駛總距離最小。

相關(guān)假設(shè)：

（1）故障共享單車停放站點(diǎn)已知。

（2）停放點(diǎn)的回收量的均值可通過(guò)歷史數(shù)據(jù)獲得。

（3）不考慮路段行駛時(shí)間對(duì)目標(biāo)的影響。

相關(guān)參數(shù)定義如下：qdi表示節(jié)點(diǎn)vi處在第d回收階段的回收量；hi表示節(jié)點(diǎn)vi需要回收的次數(shù)；Q表示回收車輛的最大裝載量；cij表示回收車輛從vi到vj的行駛距離；W表示回收中心的容量限制。決策變量定義如下：

xdij：當(dāng)回收車輛在第d回收階段從vi行駛到vj為1，否則為0。

ydi：當(dāng)回收車輛在第d回收階段對(duì)vi進(jìn)行服務(wù)為1，否則為0。

2.2故障共享單車回收PVRP模型建立

綜合考慮問(wèn)題目標(biāo)和所有的限制條件，建立如下模型

min Z=∑md=1∑ni=0∑nj=0cijxdij（1）

s.t.∑ni=1ydiqdiQ，d=1，2，…，m;i=1，2，…，n（2）

∑md=1ydi=hi，d=1，2，…，m;i=1，2，…，n（3）

∑ni=0xdij=ydi，i=0，1，…，n;i≠j;d=1，2，…，m（4）

∑nj=0xdij=ydi，j=0，1，…，n;i≠j;d=1，2，…，m（5）

∑nj=1xdj0=0，j=1，2，…，n（6）

∑ni=1qi-W0，i=1，2，…，n（7）

∑md=1∑ni=1∑nj=1xdij｜S｜-1，2｜S｜n-1（8）

（1）式為目標(biāo)函數(shù)，表示行駛總距離最短；（2）式表示容量約束，保證任一回收階段內(nèi)每條路徑上的回收量不超過(guò)車載容量；（3）式表示停放點(diǎn)被服務(wù)的次數(shù)等于其回收需求次數(shù)；（4）、（5）式表示任一回收階段內(nèi)每個(gè)站點(diǎn)只服務(wù)一次；（6）式表示回收車輛從回收中心出發(fā)并返回回收中心；（7）式表示所有停放點(diǎn)的故障單車回收總數(shù)量不超過(guò)回收中心的容量限制；（8）式表示避免子回路。

3模型分析與求解

車輛路徑問(wèn)題（VRP）是一個(gè)NP難問(wèn)題［14］，精確求解較為困難。而PVRP是車輛路徑問(wèn)題的拓展，相當(dāng)于多個(gè)VRP問(wèn)題的組合，因此求解更為困難。本文針對(duì)不確定的回收量的故障共享單車回收PVRP問(wèn)題，首先引入魯棒優(yōu)化的思想處理不確定的回收量，然后對(duì)構(gòu)建的回收模型設(shè)計(jì)近似算法進(jìn)行求解。

3.1求解思路

針對(duì)上述提出回收模型中，約束（2）和（7）含有不確定的回收需求參數(shù)qi，本節(jié)將qi用基約束魯棒方法進(jìn)行處理。

3.1.1基約束魯棒方法的求解思路

基約束魯棒方法的基本思想是為了避免絕對(duì)的魯棒優(yōu)化問(wèn)題，即在所有的不確定參數(shù)中只有一部分參數(shù)的變化值達(dá)到上限，其余一部分不變或變化較小，在此情況下，求得滿足所有約束的解，其具體模型如下

max c′x

s.t.∑aijxj+max{Si′∪{ti}｜SiJi，｜Si｜=Γi」，ti∈Ji＼Si}{∑j∈Siijyj+

（Γi-Γi」）itiyt}bi，-0yjxjyj，

lxu，y0

3.1.2不確定需求的表示

停放點(diǎn)上的故障共享單車回收需求量qi的變化范圍滿足以i為中心，i為步長(zhǎng)，即qi∈［i-i，i+i］，但停放點(diǎn)實(shí)際的回收需求量qi的值是未知的。其中i表示停放點(diǎn)回收需求量qi的名義值（即qi的平均值）；i表示停放點(diǎn)回收需求量的最大絕對(duì)偏離值，即最大擾動(dòng)值，i=σi，i0（σ為需求擾動(dòng)系數(shù)）。每個(gè)停放點(diǎn)的回收求量qi在上述區(qū)間內(nèi)隨機(jī)取值。從取值的區(qū)間可以看出，停放點(diǎn)的回收需求量qi，都取值均值（或理想值）i或最小值i-i的可能性很小，實(shí)際情況中qi的取值在區(qū)間的任一位置都是有可能的。為了更好刻畫停放點(diǎn)回收需求取值情況，運(yùn)用魯棒優(yōu)化的思想引入需求控制系數(shù)Γi和需求偏離系數(shù)λi。

定義1停放點(diǎn)回收需求量qi偏離均值的偏離系數(shù)λi為

λi=qi-iσi，λi∈［-1，1］

定義2引入回收需求控制系數(shù)Γi，使得所有停放點(diǎn)的回收需求偏差系數(shù)之和不大于Γi。即

∑｜λi｜Γi，Γi0

Γi用來(lái)描述回收需求變化的情況，即需求發(fā)生變化的停放點(diǎn)的個(gè)數(shù)。當(dāng)Γi=0時(shí)，所有停放點(diǎn)的回收需求量為名義需求值（均值），此時(shí)該問(wèn)題轉(zhuǎn)為需求確定的回收問(wèn)題；當(dāng)Γi=n時(shí)表示所有停放點(diǎn)的回收需求量達(dá)到最大偏離值，此時(shí)該問(wèn)題轉(zhuǎn)為絕對(duì)魯棒問(wèn)題，魯棒性最強(qiáng)，但求解所得的解過(guò)于保守，解的最優(yōu)性比較差。因此，當(dāng)控制系數(shù)Γi越大時(shí)，停放點(diǎn)的回收需求的不確定性也越大。

第1步需求量的確定。

在停放點(diǎn)回收需求變化擾動(dòng)系數(shù)σ下，為了使停放點(diǎn)回收需求波動(dòng)后總的回收需求量最大（即魯棒性達(dá)到最大），將停放點(diǎn)平均需求量i從大到小排列1′，2′，…，n′，選擇前Γi個(gè)停放點(diǎn)需求進(jìn)行擾動(dòng)，計(jì)算擾動(dòng)后所有停放點(diǎn)的回收需求之和達(dá)到的最大值q′sum，q′sum=∑i′+max{S∪{t}｜Sn，｜S｜=?！?，t∈n＼S}{∑i+（Γi-Γi」）t}。若q′sumW，則確定前Γi個(gè)停放點(diǎn)的回收需求進(jìn)行擾動(dòng)，qi=i+iλi。

第2步需求波動(dòng)后停放點(diǎn)回收次數(shù)的計(jì)算。

根據(jù)擾動(dòng)后的停放點(diǎn)需求量與車輛最大容量的比值，求得各停放點(diǎn)的所需的回收次數(shù)hi=「（i+iλi）/Q。

第3步回收車輛路徑的求解。

（1）分多個(gè)階段對(duì)停放點(diǎn)上的故障共享單車進(jìn)行回收。首先，以所有的停放點(diǎn)為回收對(duì)象V′={v1，…，vi，…，vn}，以回收中心v0為回收路徑的起點(diǎn)，車輛初始剩余裝載量s0=Q，選擇距離v0最短的一條邊e（v0，vi）加入到路徑當(dāng)中。

（2）判斷vi的回收需求量是否大于車輛剩余裝載量，若大于則回收車輛滿載后找最短路e（vi，v0）回到回收中心，輸出回收路徑并更新vi的需求量qi=qi-s0；若小于，則回收vi的全部需求量，更新車輛剩余裝載量si=s0-qi，搜索距離vi最近的停放點(diǎn)加入到路徑當(dāng)中，直到滿載后找最短路回到回收中心，輸出回收路徑重復(fù)上述操作，直到所有停放點(diǎn)都服務(wù)了一次y1i=1。

（3）在V′的基礎(chǔ)上更新停放點(diǎn)回收服務(wù)集合。判斷停放點(diǎn)vi被服務(wù)的次數(shù)是否與其回收次數(shù)（周期個(gè)數(shù)）相等，若相等∑ni=1ydi=hi，則將vi從V′刪除，更新停放點(diǎn)服務(wù)集合V′。

（4）重復(fù)上述步驟直到所有停放點(diǎn)被服務(wù)的次數(shù)等于其回收次數(shù)，∑ni=1ydi=hi。

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

根據(jù)以上思路設(shè)計(jì)算法GA*，如圖1所示。

第1步V′={v1，…，vi，…，vn}為初始停放點(diǎn)服務(wù)集合，cij為網(wǎng)絡(luò)邊的行駛距離，σ為需求擾動(dòng)系數(shù)，Γi為需求發(fā)生波動(dòng)的站點(diǎn)個(gè)數(shù)，λi為停放點(diǎn)回收需求偏離均值的權(quán)重系數(shù)，si為回收車輛服務(wù)完vi后的剩余車載容量。

第2步將停放點(diǎn)vi按需求均值i從大到小排列，記為1′，2′，…，n′。

第3步對(duì)前Γi個(gè)停放點(diǎn)i需求量進(jìn)行擾動(dòng)1′，2′，…，n′，計(jì)算擾動(dòng)后的總需求最大值q′sum=max{S∪{t}｜Sn，｜S｜=?！?，t∈n＼S}{∑i+（Γi-Γi」）t}。

第4步若q′sum

第5步計(jì)算停放點(diǎn)回收頻次hi=「（i+iλi）/Q。

第6步令回收車輛初始剩余裝載量s0=Q，計(jì)算v0到V′中各個(gè)停放點(diǎn)的距離coi，選擇距離最短的一條邊e（v0，vi）加入到路徑p11={e（v0，vi）}，從V′中刪除vi，令x10i=1，y1i=1。

第7步判斷vi的回收量與車輛剩余裝載量的大小，若qis0，則裝滿后回到回收中心，將e（vi，v0）加入到p11={e（v0，vi），e（vi，v0）}，更新停放點(diǎn)vi的需求量qi′=qi-s0，轉(zhuǎn)第9步；否則，更新si=Q-∑ni=1qi，尋找距離vi最近的停放點(diǎn)vj，將邊e（vi，vj）加入到路徑p11={e（v0，vi），e（vi，vj）}，vj從V′中刪除，令x1ij=1，y1j=1。

第8步判斷vj的回收量與車輛剩余裝載量的大小，若qjsi，則裝滿后回到回收中心，將e（vj，v0）加入到p11={e（v0，vi），e（vi，vj），e（vj，v0）}，更新停放點(diǎn)vj的需求量qj′=qj-so，轉(zhuǎn)第9步；否則轉(zhuǎn)第7步。

第9步生成回路集合p11，x1ij，y1i，標(biāo)記回收路徑l11=1。

第10步重復(fù)步驟6～9，直到V′=，即V′中所有停放點(diǎn)都服務(wù)了一次，輸出第一回收階段的車輛路徑集合p11={p11，p12，…，p1u}。

第11步更新停放點(diǎn)服務(wù)集合。計(jì)算停放點(diǎn)被服務(wù)的次數(shù)∑d=1∑ni=1ydi，若∑md=1∑ni=1ydi=hi，則將停放點(diǎn)vi從V′={v1，…，vi，…，vn}中刪除，得到更新后的停放點(diǎn)服務(wù)集合V′。

第12步重復(fù)步驟6～11，直到所有停放點(diǎn)的服務(wù)次數(shù)∑md=1∑ni=1ydi=hi，輸出各回收階段的車輛路徑集合Pd，xdij，ydi，ldi。

3.3算法時(shí)間復(fù)雜度

第1～2步最大計(jì)算次數(shù)O（n2）；第3～4步計(jì)算次數(shù)不大于O（n）；第5步的計(jì)算次數(shù)為O（n）；第6～10步循環(huán)的計(jì)算次數(shù)不大于O（n）；第11～12步的循環(huán)計(jì)算次數(shù)小于O（n）；所以算法GA*可在O（n2）的時(shí)間內(nèi)求出回收方案。由此得到如下定理。

定理1在回收中心容量限制下，故障共享單車回收PVRP問(wèn)題算法GA*的時(shí)間復(fù)雜性為O（n2），其中n為共享單車停放點(diǎn)的數(shù)量。

3.4算法GA*的近似比

OPT（I）表示實(shí)例I的最優(yōu)解，A（I）表示應(yīng)用算法GA*對(duì)實(shí)例I的解。首先分析最優(yōu)解并給出以下引理。

引理1對(duì)于任一實(shí)例I，站點(diǎn)上的故障共享單車回收PVRP問(wèn)題的最優(yōu)解OPT（I）下界為（β+1）∑ni=1「qi/Qb*。

證明在無(wú)向完全網(wǎng)絡(luò)中，車輛服務(wù)完所有站點(diǎn)的回收需求后所行駛的路徑數(shù)量不少于回收量之和與車輛最大裝載量的比值，即所有回收階段使用的車輛總數(shù)l′=∑ni=1qi/Q，服務(wù)所有停放站點(diǎn)的次數(shù)為∑ni=1hi，則回收車輛服務(wù)完所有站點(diǎn)的需求至少要行駛的邊的數(shù)量為l′+∑ni=1hi，每條邊的行駛距離不小于min{cij}，具體證明如下

OPT（I）（l′+∑ni=1hi）min{cij}

=（∑ni=1qi/Q+∑ni=1「qi/Q）b*

=（β+1）∑ni=1「qi/Qb*

其中β=（∑ni=1qi/Q）/∑ni=1「qi/Q，0<β1;b*=min{cij}表示回收車輛行駛的最短路段的距離。應(yīng)用算法GA*對(duì)任一實(shí)例I進(jìn)行求解，算法GA*得到的解為

A（I）=∑md=1∑ni=0∑nj=0cijxdij

=∑d=1∑e（vi，vj）∈Pdicijxdij

（∑md=1∑li=1ldi+∑ni=1hi）max{cij}

=（∑md=1∑li=1ldi+∑ni=1「qi/Q）a*

其中a*=max{cij}表示回收車輛行駛的最長(zhǎng)路段的距離。根據(jù)以上分析，給出如下定理。

定理2故障共享單車回收PVRP問(wèn)題算法GA*的近似比為λβ+1（1+∑md=1∑li=1ldi∑ni=1「qi/Q）。

α=A（I）OPT（I）

=（∑md=1∑li=1ldi+∑ni=1「qi/Q）a*（β+1）∑ni=1「qi/Qb*

=λβ+1（1+∑md=1∑li=1ldi∑ni=1「qi/Q）

其中λ是a*=max{cij}與b*=min{cij}的比值。分析可知，算法GA*的近似比α與回收車輛行駛路段的最長(zhǎng)邊與最短邊的比值λ呈正比，與回收量之和∑qi呈反比；當(dāng)站點(diǎn)間分布相對(duì)均勻，且站點(diǎn)的回收量與整車容量差異越小，即β越大時(shí)，算法近似比越小。

結(jié)合定理2進(jìn)一步討論近似比的變化范圍并給出以下幾個(gè)推論。

當(dāng)∑md=1∑li=1ldi=∑max{hi}時(shí)，即服務(wù)回收需求次數(shù)最大的站點(diǎn)時(shí)途經(jīng)的剩余站點(diǎn)也剛好一起服務(wù)完，并且每輛車剛好滿載；當(dāng)且僅當(dāng)最大需求次數(shù)的站點(diǎn)為1時(shí)，此時(shí)α的值最小。因此分析算法GA*的近似比，得到推論1如下。

推論1故障共享單車回收PVRP問(wèn)題算法GA*的近似比下界為λβ+1（1+1n）。

α=λβ+1（1+∑md=1∑li=1ldi∑ni=1「qi/Q）

λβ+1（1+∑max{hi}∑ni=1「qi/Q）

λβ+1（1+max{hi}nmax{hi}）

=λβ+1（1+1n）

當(dāng)∑md=1∑li=1ldi=∑ni=1「qi/Q時(shí)，即空載回收車輛每次服務(wù)任一站點(diǎn)后都會(huì)滿載，并返回回收中心。此時(shí)算法GA*的近似比值α最大。因此分析算法GA*的近似比，得到推論2如下。

推論2故障共享單車回收PVRP問(wèn)題算法GA*的近似比上界為2λβ+1。

α=λβ+1（1+∑md=1∑li=1ldi∑ni=1「qi/Q）2λβ+1

3.5算例分析

為了驗(yàn)證算法的運(yùn)行效果，對(duì)算法進(jìn)行仿真模擬。取λ∈［1，4］，β∈（0，1］，以及回收站點(diǎn)的個(gè)數(shù)取n=20。使用軟件Matlab R2016a，運(yùn)行環(huán)境Intel（R）Core（TM）i7-8550U CPU/ 2.00 GHz。

通過(guò)算法近似比上下界的運(yùn)行結(jié)果，進(jìn)一步分析影響算法運(yùn)行效果的關(guān)鍵因素，及其影響程度的大小。如圖2和圖3所示。

從圖2和圖3可以看出，算法近似比下界最大在3.8左右，上界最大值在8左右（理想最優(yōu)值α=1），說(shuō)明算法整體運(yùn)行的效果較好。隨著λ的增大，算法近似比的增幅呈擴(kuò)大趨勢(shì)，而β的影響較小。因此，可以得出站點(diǎn)間位置分布的均衡性，對(duì)算法運(yùn)行的效果有重要影響。

4實(shí)例分析

西安雁塔區(qū)分布著眾多高校以及歷史人文景點(diǎn)，客流量較大，共享單車使用頻繁。本實(shí)例選取西安市雁塔區(qū)的故障共享單車進(jìn)行分析。實(shí)際回收過(guò)程中，共享單車停放站點(diǎn)上的故障單車的回收需求量難以獲得準(zhǔn)確的數(shù)值，由于人為損壞或單車GPS定位失靈以及其他不可抗拒的自然損耗，往往回收數(shù)量與共享單車運(yùn)營(yíng)后臺(tái)收到的報(bào)修數(shù)量有差異。本實(shí)例中采用2018年8月某時(shí)段，站點(diǎn)的平均回收量作為名義需求量，取最大擾動(dòng)系數(shù)σ=0.3時(shí)站點(diǎn)需求變化區(qū)間如表1所示。

當(dāng)回收需求量擾動(dòng)系數(shù)（需求量變化程度）和控制系數(shù)（需求量發(fā)生變化的停放站點(diǎn)個(gè)數(shù)）為固定值時(shí)，此時(shí)該不確定問(wèn)題轉(zhuǎn)化為需求已知的問(wèn)題。為了驗(yàn)證模型的有效性，以Γi=0為例，即回收需求量取均值的情況下，應(yīng)用算法GA*對(duì)實(shí)例進(jìn)行求解。

首先根據(jù)各站點(diǎn)的需求量計(jì)算各站點(diǎn)的回收次數(shù)hi=「i/Q，如表2所示。

運(yùn)用算法GA*對(duì)該實(shí)例進(jìn)行求解。求解得到11條回收路徑，需要分兩個(gè)階段進(jìn)行回收，回收車輛的行駛總距離為29.6 km，算法的近似比為3.38，說(shuō)明了該算法實(shí)際使用效果較好，求解的回收車輛路徑、回收量以及行駛距離如表3所示。

為了更好地驗(yàn)證模型和算法的魯棒性（穩(wěn)健性），引入需求擾動(dòng)系數(shù)σ和控制系數(shù)Γi，分析當(dāng)需求發(fā)生變時(shí)對(duì)目標(biāo)函數(shù)值和競(jìng)爭(zhēng)比的影響。擾動(dòng)系數(shù)σ越大表示需求量取值越大，偏離需求均值的程度越大；控制系數(shù)Γi越大表示需求量發(fā)生變化的停放點(diǎn)數(shù)量越多。本節(jié)需求量擾動(dòng)系數(shù)取σ=0.1，0.2，0.3（即需求量變化程度），需求控制系數(shù)取Γi=5，10，15（即需求量發(fā)生變化的停放站點(diǎn)個(gè)數(shù)），運(yùn)用算法GA*求解結(jié)果如下。

從表4可以看出，當(dāng)共享單車停放站點(diǎn)上的故障共享單車回收量變化程度σ給定后，隨著控制系數(shù)Γi的增大，最短行駛總距離呈現(xiàn)整體上漲趨勢(shì)；在Γi一定時(shí)，即發(fā)生需求變化的停放站點(diǎn)數(shù)量一定，隨著擾動(dòng)系數(shù)σ的增大，最短行駛總距離也逐漸增大，當(dāng)Γi=10時(shí)，最短行駛總距離目標(biāo)函數(shù)值變化不明顯，說(shuō)明該實(shí)例中算法具有較強(qiáng)的魯棒性（穩(wěn)健性）；且相對(duì)于擾動(dòng)系數(shù)σ，控制系數(shù)Γi對(duì)目標(biāo)函數(shù)值的影響更大，即需求發(fā)生變化的站點(diǎn)數(shù)量比站點(diǎn)回收量變化程度對(duì)回收車輛行駛總距離的影響更大。

從表5可以看出，算法的近似比與控制系數(shù)Γi呈正比，但與需求擾動(dòng)系數(shù)σ無(wú)明顯比例關(guān)系；總體看算法近似比基本穩(wěn)定在3.5與4之間；而通過(guò)近似比的分析可以得到該實(shí)例的近似比上下界為6.84和1.8；實(shí)例分析過(guò)程中算法的近似比α靠近下界，說(shuō)明該算法實(shí)際使用效果較好。

5結(jié)論與啟示

本文考慮需求不確定的停放站點(diǎn)上故障共享單車回收PVRP問(wèn)題。以行駛總距離最小為目標(biāo)，構(gòu)建故障共享單車回收PVRP模型。并針對(duì)模型中不確定的回收需求量采用魯棒優(yōu)化的方法，來(lái)刻畫回收需求變化情形，并設(shè)計(jì)近似算法對(duì)模型進(jìn)行求解，進(jìn)一步分析該算法的近似比和近似比的上下界。最后進(jìn)行實(shí)例分析，結(jié)果表明：回收量的波動(dòng)程度和需求變化的站點(diǎn)數(shù)量，都對(duì)目標(biāo)函數(shù)值有重要影響，且需求變化的站點(diǎn)數(shù)量影響更大。

因此，在實(shí)際回收過(guò)程中，共享單車企業(yè)在設(shè)置回收站點(diǎn)時(shí)，應(yīng)當(dāng)注重站點(diǎn)的位置分布的均勻性，站點(diǎn)數(shù)量的上限控制，以及站點(diǎn)容量的整車化，能有效地應(yīng)對(duì)回收需求的不確定性。另外，共享單車回收卡車還會(huì)執(zhí)行共享單車投放任務(wù)，面對(duì)乘客出行需求呈現(xiàn)的早晚高峰的時(shí)間差異，如何錯(cuò)峰回收和需求轉(zhuǎn)移等問(wèn)題將有待深入研究。

參考文獻(xiàn)：

［1］Ines F， Anabela R. Bike-sharing stations： a maximal covering location approach［J］. Transportation Research Part A： Policy and Practice， 2015， 82（9）： 216-227.

［2］Brinkmann J， Ulmer M W， Mattfeld D C. Short-term strategies for stochastic inventory routing in bike sharing systems［J］. Transportation Research Procedia， 2015， 10： 364-373.

［3］Schuijbroek J， Hampshire R C， Van H W J. Inventory rebalancing and vehicle routing in bike sharing systems［J］. European Journal of Operational Research， 2017， 257（3）： 992-1004.

［4］Ghosh S， Varakantham P， Adulyasak Y. Dynamic repositioning to reduce lost demand in bike sharing systems［J］. Journal of Artificial Intelligence Research， 2017， 58（2）： 387-430.

［5］Leonardo C， Rosalia C， Michele O. Planning and design of equitable free-floating bike-sharing systems implementing a road pricing strategy［J］. Journal of Advanced Transportation， 2017， （12）： 1-18.

［6］Xu H T， Duan F， Pu P. Dynamic bicycle scheduling problem based on short-term demand prediction［J］. Applied Intelligence， 2019， 49（5）： 1968-1981.

［7］Wang B， Vu H L， Kim I， et al.. Short-term traffic flow prediction in bike-sharing networks［J］. Journal of Intelligent Transportation Systems， 2021， （3）： 1-18.

［8］Chen L B， Ma X J， Nguyen T M T， et al.. Understanding bike trip patterns leveraging bike sharing system open data［J］. Frontiers of Computer Science， 2017， 11（1）： 38-48.

［9］Dell A M， Iori M， Novellani S， et al.. A destroy and repair algorithm for the bike sharing rebalancing problem［J］. Computers & Operations Research， 2016， 71（7）： 149-162.

［10］Tsai M F， Chen P， Hong Y J. Enhancing the utilization of public bike sharing systems using return anxiety information［J］. Future Generation Computer Systems， 2019， 92（3）： 961-971.

［11］Wang Y， Szeto W Y. Static green repositioning in bike sharing systems with broken bikes［J］. Transportation Research Part D， 2018， 65（12）： 438-457.

［12］肖建華，賈楠，潘鈺雅，等.基于破損信息不確定的共享單車新車投放-舊車調(diào)撥-壞車回收聯(lián)合調(diào)度優(yōu)化研究［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2021，（12）：89-101.

［13］Kaspi M， Raviv T， Tzur M. Bike sharing systems： user dissatisfaction in the presence of unusable bicycles［J］. IIE Transactions， 2017， （2）： 144-158.

［14］Salhi S， Rand G K. Incorporating vehicle routing into the vehicle fleet composition problem［J］. European Journal of Operational Research， 1993， 66（3）： 313-330.