張 巍，李鵬翔，仝自強(qiáng)，岳毅蒙

(西安交通大學(xué) 管理學(xué)院，陜西 西安 710049)

損壞車輛是指在共享單車系統(tǒng)運(yùn)營過程中，出現(xiàn)的因故障、磨損或到達(dá)換修期限等原因而不能正常使用，需要回收處理的共享單車。對損壞車輛的回收是使共享單車系統(tǒng)良性運(yùn)營和降低損失的關(guān)鍵環(huán)節(jié)。如何降低損壞車輛的回收成本和提高車輛使用效率是困擾共享單車系統(tǒng)運(yùn)營的難題，合理優(yōu)化回收路線和回收網(wǎng)絡(luò)等研究已成為學(xué)者和企業(yè)關(guān)注的焦點(diǎn)問題[1]。

國內(nèi)外對共享單車系統(tǒng)的研究日漸流行，Laporte和Meunier等對共享單車問題提供了一個(gè)綜合性的調(diào)研，將共享單車問題劃分為四大研究分支：策略設(shè)計(jì)、需求分析、服務(wù)水平分析和再平衡運(yùn)作。文獻(xiàn)[2-9]對上述問題作出了廣泛的研究，認(rèn)為共享單車系統(tǒng)的服務(wù)水平通常有兩個(gè)方面。可使用的單車和車位數(shù)量，因而損壞車輛占用有限的車位所造成的顧客不滿意度，將會引起運(yùn)營收益的損失；將系統(tǒng)的損失與收益分解到每個(gè)站點(diǎn)，提出了有限容量的排隊(duì)系統(tǒng)，用于模擬每個(gè)共享單車站點(diǎn)用戶不滿意度的期望值。同時(shí)指出，雖然與傳統(tǒng)有樁的共享單車系統(tǒng)相比較，無樁共享單車系統(tǒng)的使用規(guī)則有很多不同，但是其停放規(guī)則愈發(fā)近似于有樁的共享單車系統(tǒng)。因此，無樁共享單車系統(tǒng)的損壞車輛回收問題可以歸類為有樁共享單車的同類問題。

在已有的關(guān)于共享單車損壞車輛回收問題研究中，較為經(jīng)典的工作如Chang等[2]在文章中將損壞車輛的分布假設(shè)為在各站點(diǎn)出現(xiàn)的概率相同，這與現(xiàn)實(shí)情況有所差異?，F(xiàn)有的研究在規(guī)劃回收車輛指派方案時(shí)，對所有站點(diǎn)都安排訪問，并不考慮站點(diǎn)遍歷的損益與成本。本文立足于不同單車站點(diǎn)損壞車輛出現(xiàn)頻率不盡相同的現(xiàn)實(shí)背景，提出網(wǎng)絡(luò)中各節(jié)點(diǎn)問題車輛近似服從正態(tài)分布的預(yù)測模型，同時(shí)考慮以成本最低和效率最大化為原則，在指派方案制定前對回收成本作出分析，選擇合適的成本閾值作為回收網(wǎng)絡(luò)節(jié)點(diǎn)選取的標(biāo)準(zhǔn)，以確定最優(yōu)回收網(wǎng)絡(luò)應(yīng)該包含的節(jié)點(diǎn)?；谒⒌淖顑?yōu)回收網(wǎng)絡(luò)方案建立共享單車回收車輛的最短路徑指派模型，結(jié)合遺傳算法(genetic algorithm，GA)和禁忌搜索法(tabu search，TS)，設(shè)計(jì)TSGA的混合啟發(fā)式算法用于求解回收車輛路徑指派問題。用實(shí)例進(jìn)行測試和驗(yàn)證。由實(shí)例分析的結(jié)果可以得到結(jié)論：根據(jù)分布預(yù)測和損益分析制定回收網(wǎng)絡(luò)后，再進(jìn)行指派方案規(guī)劃，能大幅度降低運(yùn)營商的回收成本且提高回收效率。

1 問題描述與假設(shè)條件

1.1 問題描述

本文研究的損壞車輛回收問題是指從對共享單車各站點(diǎn)的壞車分布進(jìn)行預(yù)測和成本分析后確定回收網(wǎng)絡(luò)，進(jìn)而指派回收車輛從維修站出發(fā)至各個(gè)站點(diǎn)將損壞車輛進(jìn)行回收，最終送回維修站維修的兩階段決策過程。

1.2 問題假設(shè)

1) 壞車的分布接近服從正態(tài)分布；2) 單位損壞車輛造成的損失相同；3) 維修庫以及站點(diǎn)位置是已知的；4) 任意兩點(diǎn)往返路徑長度相同。

傳統(tǒng)問題假設(shè)所有站點(diǎn)出現(xiàn)損壞車輛的頻率相同?；趯?shí)際情況，將上述假設(shè)打破，認(rèn)為各站點(diǎn)出現(xiàn)損壞車輛的概率隨站點(diǎn)的使用強(qiáng)度不同而近似服從正態(tài)分布。

2 回收網(wǎng)絡(luò)及路由模型

2.1 模型描述

給定一個(gè)完整的有向圖G=(V,A)，其中頂點(diǎn)V={0,1,···,n}被劃分為維修庫(頂點(diǎn)0)和共享單車站點(diǎn)(頂 點(diǎn)1,2,···n)。路徑A=(i,j)表示從頂點(diǎn)i到頂點(diǎn)j的有向路徑，其中i∈V,j∈V,i≠j,j≠0。

所建立的回收網(wǎng)絡(luò)模型與傳統(tǒng)回收網(wǎng)絡(luò)不同，將回收過程分為2個(gè)周期。在第1個(gè)周期根據(jù)各站點(diǎn)使用強(qiáng)度的不同對回收需求進(jìn)行預(yù)測，并基于預(yù)測結(jié)果進(jìn)行成本分析，繼而選擇回收車輛應(yīng)該訪問的節(jié)點(diǎn)，在第2個(gè)周期安排車輛訪問所有節(jié)點(diǎn)。在實(shí)例分析部分可以看到，與遍歷所有節(jié)點(diǎn)相比較，基于成本分析下的2周期回收過程單個(gè)周期的平均成本大大降低。

2.2 回收網(wǎng)絡(luò)模型構(gòu)建

回收網(wǎng)絡(luò)模型相關(guān)參數(shù)含義詳見表1。

表1 回收網(wǎng)絡(luò)模型參數(shù)Table 1 Recycle network model parameters

其中，式(1)表示系統(tǒng)中借還服務(wù)的總次數(shù)等于各個(gè)站點(diǎn)借還次數(shù)之和；式(2)表示各站點(diǎn)的相對使用強(qiáng)度與該站點(diǎn)的使用次數(shù)的關(guān)系；式(3)表示各站點(diǎn)損壞車輛數(shù)的計(jì)算方式；式(4)表示各站點(diǎn)損壞車輛損失值的計(jì)算方式；式(5)表示經(jīng)歷所有共享單車站點(diǎn)的平均成本；式(6)表示回收站點(diǎn)選取閾值指標(biāo)的計(jì)算方法。

以下問題需注意：1)pi在P的基礎(chǔ)上受到qi的影響接近正態(tài)分布；2) 當(dāng)前周期的任意站點(diǎn)的壞車損失Li＜θn時(shí)，本次回收不訪問；3) 因?yàn)槟硞€(gè)站點(diǎn)未被訪問而產(chǎn)生的損失遺留在下次回收過程；4) 當(dāng)前周期未被訪問的站點(diǎn)下一周期必須訪問。

2.3 回收路由模型構(gòu)建

路由指派模型相關(guān)參數(shù)含義詳見表2。

表2 路徑指派模型參數(shù)描述Table 2 Path assignment model parameter description

決策變量：

xijh(i,j=1,2,···,V;h=1,2,···,h)：若回收車h經(jīng)過路徑(i,j)則取值為1，否則為0；

yih(i=1,2,···,V;h=1,2,···,h)：若共享單車站點(diǎn)i由車輛h來 回收，則取值為1，否則為0；

g：車的使用數(shù)量；

u：車站的訪問數(shù)量。

目標(biāo)函數(shù)：

約束條件：

目標(biāo)函數(shù)式(7)的目標(biāo)是求得最小的回收成本；約束式(8)、式(9)保證只有服務(wù)節(jié)點(diǎn)j的運(yùn)輸車輛經(jīng)歷路徑(i,j)；約束式(10)確保對于任意一個(gè)節(jié)點(diǎn)，有且僅有一輛回收車去服務(wù)它；約束式(11)保證了不會超過運(yùn)送車輛的容量極限；約束式(12)避免子圈。

3 模型求解

3.1 求解回收路由模型

損壞車輛的回收路由指派問題是經(jīng)典車輛路徑問題(vehicle routing problem，VRP)的延伸。當(dāng)問題規(guī)模較小時(shí)可使用已有的計(jì)算機(jī)求解器求解，而對于較大規(guī)模問題，本文結(jié)合TS和GA兩種啟發(fā)式算法的混合算法求解該問題[10-11]，見圖1。

1) 初始解。設(shè)計(jì)的TSGA混合算法使用多次掃描算法(sweep)獲得初始種群。

2) 適應(yīng)度計(jì)算。通過計(jì)算每個(gè)個(gè)體長度的倒數(shù)表示其適應(yīng)度值，即總路由長度越小的解越應(yīng)該被遺傳到下一代。

3) 選擇。使用輪盤賭博法進(jìn)行選擇，即先求出上代群體總個(gè)體適應(yīng)度的總和，再計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例作為其被選擇的概率。

4) 交叉。由交叉概率pc∈(0,1)，選擇進(jìn)行交叉的父代染色體，之后根據(jù)隨機(jī)概率產(chǎn)生的節(jié)點(diǎn)進(jìn)行逆轉(zhuǎn)得到新的個(gè)體。

5) 變異。變異概率取值pm∈(0,1)，采用隨機(jī)產(chǎn)生一個(gè)變異位置，將該位置和下一個(gè)位置的基因互換的變異技術(shù)。

6) 轉(zhuǎn)錄。將染色體基因的一部分進(jìn)行逆序排列，例如：S=100/1100/11，倒位以后為S′=100/0011/11。

7) 更新禁忌表。以父代的平均適應(yīng)度值作為渴望水平，以個(gè)體的適應(yīng)度值作為禁忌對象。

圖1 TSGA混合算法流程圖Figure 1 TSGA hybrid algorithm flow chart

8) 禁忌表特赦。如果子代個(gè)體的適應(yīng)度值大于渴望水平，則不論子代個(gè)體是否被禁忌，將子代個(gè)體加入到新代中。

9) 局部搜索。只要?dú)v史最優(yōu)解得到改進(jìn)，就記錄下來。如果在一定代數(shù)內(nèi)沒有更新，就回到已經(jīng)保存的解，從這個(gè)解的鄰域出發(fā)進(jìn)行搜索。

10) 判斷是否滿足終止條件。若滿足迭代次數(shù)或者滿足收斂條件則終止循環(huán)，否則重復(fù)執(zhí)行2)—9)。

11) 輸出最優(yōu)解。將滿足終止條件時(shí)的最優(yōu)解及其對應(yīng)的最優(yōu)值輸出。

3.2 制定回收網(wǎng)絡(luò)模型

使用TSGA混合算法求得實(shí)際問題進(jìn)行全部節(jié)點(diǎn)遍歷的最優(yōu)路由線路，然后進(jìn)行成本閾值分析，即計(jì)算θ 和 θn的值，最后確定出經(jīng)濟(jì)效益最高的回收網(wǎng)絡(luò)。并再次使用TSGA混合算法對2周期路由網(wǎng)絡(luò)的最優(yōu)回收路由進(jìn)行求解,以得出最優(yōu)方案。

4 實(shí)例分析

本文調(diào)研了北京市公共自行車系統(tǒng)，隨機(jī)選取朝陽區(qū)部分區(qū)域作為調(diào)研對象，共有64個(gè)共享單車站。對各個(gè)共享單車站點(diǎn)擬定編號。所涉及到的各站點(diǎn)損壞車輛預(yù)測數(shù)目對于非整數(shù)的部分向上取整。通過已公布的站點(diǎn)信息標(biāo)記該區(qū)域共享單車系統(tǒng)各個(gè)站點(diǎn)的分布坐標(biāo)，以維修庫為坐標(biāo)原點(diǎn)建立平面直角坐標(biāo)系，得到當(dāng)前案例的回收網(wǎng)絡(luò)數(shù)據(jù)，見表3。其中，C1=10,C2=200,C3=18，單位損壞車輛堆積成本為8；節(jié)點(diǎn)的位置數(shù)據(jù)利用GIS地圖應(yīng)用程序獲取。

4.1 全部遍歷的最優(yōu)回收方案

使用Matlab2016a軟件工具編程實(shí)現(xiàn)TSGA混合算法求解本案例。求解得到的最優(yōu)路徑結(jié)果和最優(yōu)路徑圖如表4及圖2所示。

對該案例求得的最優(yōu)結(jié)果，回收車輛的指派方案總共包含9條路徑?？紤]到共享單車的實(shí)際運(yùn)營中，損壞車輛回收作業(yè)多在夜間或其他閑時(shí)進(jìn)行，因此該作業(yè)并無時(shí)間窗要求。同時(shí)該案例的路由總路程95.24 km對于回收車輛行駛而言，亦非很長的路線，一輛回收車擁有在一個(gè)周期內(nèi)遍歷所有路線的能力。所以在無時(shí)間窗約束的條件下，以上9條路徑是可以交由一輛車來完成，這樣安排也能提高車輛利用率且降低成本。

回收成本為

站點(diǎn)平均成本為

4.2 考慮成本閾值的二周期回收方案

以 θ2為 例分析，計(jì)算可知Li<θ2=18的節(jié)點(diǎn)有2，4，5，6，7，8，11，13，14，15，36，44，45，46，62。本方案分2部分進(jìn)行，第1個(gè)回收周期中回收網(wǎng)絡(luò)不包含上述節(jié)點(diǎn)。其造成的損失值232累加到成本中。第2個(gè)回收周期在對回收網(wǎng)絡(luò)作預(yù)測時(shí)，將上1周期未作回收的節(jié)點(diǎn)直接放入該周期的回收網(wǎng)絡(luò)中，其他過程與第1周期相同。第1周期未安排回收的節(jié)點(diǎn)所遺留下的損壞車輛與第2周期該節(jié)點(diǎn)的損壞車輛相累加。

第1周期總路徑長度為65.09 km，與全站點(diǎn)路由理由相同，采取一輛車連續(xù)回收的方案，路徑方案為如圖3所示。

表3 站點(diǎn)信息Table 3 Site information

第1周期成本為

第2周期總路徑長度為92.49 km，同理，采取一輛車連續(xù)回收的方案，如圖4所示。

第2周期成本為

表4 回收路由路線指派方案Table 4 Recycling routing assignment scheme

圖2 回收路由指派圖Figure 2 Recycling routing assignment diagram

圖3 第1周期回收路由指派圖Figure 3 First cycle recycle routing assignment diagram

2個(gè)周期的平均成本為

考慮損益成本的回收指派方案的平均周期成本2 120.9小于全站點(diǎn)的回收路由成本2 304.4。去除固定成本 200 后，二者變動成本相差2 104.4?1 920.9=183.5 (元)，即變動成本節(jié)約了

圖4 第2周期回收路由指派圖Figure 4 Second cycle recycle routing assignment diagram

在本案例中兩者的成本數(shù)值差距為183.5，而變動成本節(jié)約率為8.72%。從近10%的成本節(jié)約中可以看出，在較大規(guī)模的案例中兩者的成本差距將會相當(dāng)可觀。因而，與對所有站點(diǎn)均安排訪問相比較，本文設(shè)計(jì)的方法更為經(jīng)濟(jì)高效。

表5列舉了不同 θn下的變動成本節(jié)約數(shù)值和變動成本節(jié)約率。

表5 不同θn下的平均可變成本及節(jié)約率Table 5 Variable cost savings under different θn

由表5可知，在本案例中選取成本閾值為θ2時(shí)制定指派方案的成本節(jié)約比率最高，為8.72%。在該實(shí)際案例的決策過程中，應(yīng)該選擇 θ2為成本閾值。

5 結(jié)語

本文通過對損壞車輛的分布作出概率預(yù)測和對回收節(jié)點(diǎn)的損益進(jìn)行成本分析，設(shè)計(jì)了最優(yōu)回收節(jié)點(diǎn)網(wǎng)絡(luò)方案，并根據(jù)回收成本最低的目標(biāo)提出回收路由指派模型，使用TSGA混合算法求解。通過對北京朝陽區(qū)部分區(qū)域的公共自行車網(wǎng)絡(luò)進(jìn)行實(shí)際調(diào)研獲得了案例數(shù)據(jù)，對損壞車輛分布預(yù)測結(jié)果進(jìn)行損益分析，得到更為低成本和高效率的回收路由指派方案。實(shí)例分析的結(jié)果體現(xiàn)本文提出的損壞車輛回收規(guī)劃具有很高的應(yīng)用價(jià)值和實(shí)踐價(jià)值，不僅考慮了損壞車輛的非均勻分布，同時(shí)注重減少成本和提高車輛使用效率，突顯了實(shí)用性和真實(shí)性，從而保證運(yùn)營效益的最大化。