考慮故障車回收的共享單車靜態重平衡問題

丁飛陽，張 思

（上海大學 管理學院，上海 200444）

0 引言

共享單車給人民帶來便利的同時，其快速發展也帶來了一系列問題。在一些城市，共享單車被隨處停放，導致有些區域形成交通擁堵，有些區域又一車難求，造成了供需不平衡的局面。此外，由于共享單車長時間接受風吹日曬，其故障率也遠遠高于普通自行車，影響用戶體驗。

共享單車系統的平穩運行通常需要滿足用戶波動出行需求的能力。為了保證系統可靠性和提高用戶的滿意度，運營商需要對共享單車系統進行重平衡。重平衡問題旨在研究如何調度各個站點間不平衡的共享單車數量，以更好地滿足客戶需求。其調度通常有兩種策略，一是客戶激勵：運營商根據系統的當前和預測狀態，計算出停放共享單車在各個站點的獎勵，并提供給顧客，具體可參考文獻[1]、[2]。二是運營商利用卡車將自行車從過剩（供應）站運到不足（需求）站，以實現理想的平衡。基于運營商的重新平衡有兩種類型：靜態重平衡和動態重平衡。

靜態重平衡側重于在夜間進行平衡過程，此時用戶使用和道路擁堵情況可以忽略不計，主要包含靜態完全重平衡問題（SCRP）和靜態部分重平衡問題（SPRP）。對于SCRP，Dell'Amico，等[3]首次完整定義了共享單車靜態重平衡問題；為了求解該問題，Forma，等[4]提出了一種三步啟發式算法。Erdogan，等[5]提出了帶需求區間的共享單車重平衡，將其視為1-PDTSP的變種。劉喜梅，等[6]和呂暢，等[7]分別用改進啟發式算法進行求解。Pal和Zhang[8]提出了一種混合嵌套的大鄰域搜索與可變鄰域下降算法，在大規模問題上表現高效。秦冰芳[9]以最小化總成本和車輛工作時間為目標建立了分批配送車輛路徑模型。陳植元，等[10]根據共享單車的時空分布將具有相似時空屬性的站點進行聚類，將問題轉化為帶時間窗和容量約束的VRP問題。對于SPRP，Ravia，等[11]首次提出了多調度車輛問題。Ho和Szeto[12]提出一種迭代的禁忌搜索算法來求解。Li，等[13]考慮了多種單車類型的重平衡問題。Mohammadi，等[14]設計了一個基于旅行商的多目標、多商品、多時期的數學模型，對其小規模問題進行精確求解。Szeto和Shui[15]引入了總需求不滿意（TDD）的概念，目標函數首先最小化系統總需求不滿度的正偏差，然后使車輛的總服務時間最小。于德新，等[16]以最小化總成本和最大化投放率（投放與需求的比值）為目標,其創新點在于采用TOPSIS法在遺傳算法求解出的有效路線中選擇最優路線。汪慎文，等[17]設計了一種離散差分進化算法來求解該問題。許媛媛[18]構建了多目標混合整數規劃模型，采用混合遺傳算法和變鄰域搜索算法的粒子群算法進行求解。

動態重平衡則與白天操作的平衡有關，此時系統處于高使用率，車站的需求會在重平衡期間發生變化。Kloimullner，等[19]將每個累積的需求函數分割成弱單調片段，用四種啟發式方法對實例進行了測試。馮麟博[20]提出了一種BP神經網絡算法對共享單車需求進行預測，引入虛擬調度中心的概念，從而將動態問題轉化為靜態問題。張徐[21]提出了改進的隨機森林預測方法對需求進行預測，之后利用K-means對區域進行劃分，將問題從全局最優轉化為局部最優，采用改進蟻群算法求解。但是人們出行充滿不確定性，因此多數動態問題轉化為靜態問題時對需求的預測也會存在一定偏差。此外在需求高位波動的白天，運營商調度成本更高的同時還易受到交通擁堵等外界影響。因此本文選擇靜態重平衡為研究對象。

以上研究只考慮到了對好車的重平衡，未考慮到對故障車的回收。近年來，逐步有學者開始考慮到故障車的回收。徐國勛，等[22]在調度中考慮了損壞自行車的回收，設計了混合禁忌搜索算法求解。Wang 和Szeto[23-24]首次提出了考慮CO2排放的帶故障車回收的重平衡問題，采用增強型人工蜂群算法求解該綠色BRP問題。Du，等[25]研究了多中心、多車型、允許多次訪問的帶故障車回收的重平衡問題，其結果量化了帶故障車回收的綜合重平衡相比于單獨重平衡的好處。王涵霄，等[26]首次提出了小故障單車當場維修、大故障單車回收、好單車調度的概念，其采用蟻群算法來求解。

現階段的研究多為考慮故障車回收的靜態完全重平衡問題，由多車輛進行工作，這勢必會增加車輛運行的固定成本。本文的研究考慮故障車回收的共享單車靜態部分重平衡問題，由單車輛進行多車次工作，將全部故障單車進行回收，下一次作業車輛上的初始單車數受到上一次作業最終狀態的影響。為此，提出了一種改進遺傳算法，引入了精英個體爬山、自適應交叉、變異等操作來求解該問題。

1 模型建立

在共享單車系統中一個調度中心通常服務多個站點，多車次具有相同容量的調度車從調度中心出發，在供應站提取正常的單車，并將它們送到需求站。同時每個站點的故障單車會被裝載到調度車上。當調度車的容量已滿或調度車的容量不足以服務下個站點時，返回調度中心進行卸貨。直到所有站點均被服務一次后任務結束。一個典型示例如圖1所示，包含一個調度中心和七個站點，車輛的容量為10。調度車返回調度中心，所有故障單車均被卸下，再次出發時允許調度車上存在不超過確定數量的好單車。

圖1 共享單車調度和回收故障車輛示意圖

本模型提出如下假設：

（1）站點調度與回收故障車工作發生于深夜，此時不考慮站點單車數量的變動，為靜態重平衡；

（2）只存在一個調度中心，調度車輛從該處出發，最后需返回該處；

（3）每個站點好車和壞車的數量已知；

（4）調度車輛的行駛成本只與距離成線性相關，不考慮其他因素；

（5）調度車第一次從調度中心出發時為空車，第二次及之后從調度中心出發時允許調度車上存在不多于一定數量的好單車；

（6）站點所存在的多余好車、壞車需全部被回收，但允許站點的好車需求數不被滿足。

在有向圖G=(V,A)上，其中V= {0,1,2,...,n} 表示所有節點的集合，0表示調度中心，0,1,2,...,n表示調度點，A表示弧的集合，A={(i,j):i,j ∈V,i ≠j} 。表示調度點的集合。

變量符號及其含義見表1。

表1 變量符號及含義

模型建立如下：

目標函數（1）表示最小化總成本，包括調度車輛的行駛成本，偏離好車需求期望的懲罰成本。約束條件（2）表示各個調度點的好車轉移方程，好車有裝有卸。約束條件（3）表示各個調度點的好車需先滿足自身期望后，多余的好車才可裝到調度車上。約束條件（4）表示各個調度點裝到調度車上的壞車數需等于該站點初始壞車數。約束條件（5）（6）表示服務點i 前后，調度車上所擁有的好車數和壞車數較剛到達站點i時的數量變化情況，其數值等于在站點i的裝卸量。約束條件（7）表示調度車到達與離開的是同一個站點，確保流守恒。約束條件（8）（9）表示調度車從調度中心出發時，第一次為空車，第二次車上允許存在一定數量好車。約束條件（10）表示車輛的容量約束。約束條件（11）表示每個站點只能被一輛調度車輛服務一次。約束條件（12）（13）表示每輛調度車均從調度中心出發，工作完后都返回調度中心。約束條件（14）（15）表示調度車在站點i所卸載的好車數要滿足該站點的需求和調度車容量的較小值。約束條件（16）表示消除子回路，避免不經過調度中心的回路出現。約束條件（17）-（21）分別定義了變量的定義域。

2 算法設計

遺傳算法最早由美國John Holland 教授于1975年提出,其靈感來自于自然進化的規律。在遺傳算法中，每個染色體需要定義一個適應度函數來進行評價，使適應度值好的染色體有更多的繁殖機會，從而形成下一代新種群。對這個新種群進行下一輪進化，如此往復直到找到滿意解。

在求解一些較為復雜的優化問題時，遺傳算法的計算效率高，全局搜索性強，能在較短時間內求出問題的滿意解，因此本問題采用遺傳算法進行求解。但經典遺傳算法局部搜索性能較差，容易過早收斂而陷入局部最優，因此本文在遺傳算法中引入了精英個體爬山操作、自適應交叉和變異操作，從而提高了其魯棒性。

2.1 初始解的生成

本文采用自然數編碼方式，每一條染色體由自然數0至N（待服務站點數目）所組成，代表調度車輛的行駛路徑。其中0代表調度中心，其余自然數代表每個待服務的站點。

如其中一條染色體為：0—3—7—5—0—2—4—6—0—1—8—0 表示共出動了三個車次，包含三條路徑。路徑1：0—3—7—5—0 路徑2：0—2—4—6—0 路徑3：0—1—8—0。

2.2 適應度函數

上述編碼方式不能保證解碼的染色體使用不超過規定的車次數，所以提出懲罰函數來解決這一問題。配送方案總成本的計算公式如下：

式中，X(i)為目標函數（1）的總成本，w(i)為使用超過規定數目車次的懲罰成本。γ為違反車次數量約束的懲罰因子，di為第i條染色體使用的車次數，ni為規定的最大車次數。

2.3 選擇與爬山操作

本文采用二元錦標賽與精英個體爬山操作相結合，具體如圖2所示。為了避免過早陷入局部最優，本文對選擇操作后的染色體進行去重操作，并與父代染色體相結合形成新種群。對該代染色體中適應度函數最高的精英個體進行爬山，采用2-opt領域搜索法，隨機交換染色體中兩個位置的基因，計算其適應度，若適應度提高，則互換基因后的個體替代原來的個體保存到下一代，跳出循環。若適應度未增加，則最優染色體不變。重復以上步驟，直到達到指定次數為止。

圖2 選擇操作流程圖

2.4 遺傳自適應操作

為保證算法的高效性，設置交叉概率為：

式中，fi表示待交叉的兩個染色體中適應度的較大值，fave表示該代種群適應度的平均值，fmax表示該代種群中適應度函數的最大值，Pc1表示較小的交叉概率，Pc2 表示較大的交叉概率。改進的交叉操作如下所示。

設置變異概率為：

式中，fi表示待變異的兩個染色體中適應度的較大值，fave表示該代種群適應度的平均值，Pm1 表示較小的變異概率，Pm2 表示較大的變異概率。其中變異操作采用兩互換方法。

改進遺傳算法運行流程如圖3所示。

圖3 算法流程圖

3 算例分析

現有一調度中心和若干個待服務的站點（小規模算例R1001-R1010 表示有10 個算例，每個算例有10 個待服務的站點，中規模算例R2001-R2010 表示有10 個算例，每個算例有20 個待服務的站點，大規模算例R4001-R4010 表示有10 個算例，每個算例有40 個待服務的站點），其中調度車輛的容量為40，好單車不足的懲罰成本為2，車輛行駛單位距離成本為1.5，使用過多調度車時的懲罰成本為10。每個案例的好單車需求期望均設置為15，未經服務前的好單車數設置為0到30的隨機數，壞單車數設置為0到10的隨機數。

3.1 參數設計

采用中規模R2001 算例來進行參數設置。首先設 定NIND=200，Pc1=0.4，Pc2=0.8，Pm1=0.1，Pm2=0.3，MAXGEN=2 000。

之后依次優化NIND、Pc1、Pc2、Pm1、Pm2。例如，當其他參數固定時，NIND需要設置80-440來比較優化效果，每個不同的NIND數都需進行五次運行來確定目標函數的平均值，如果優化效果最好時NIND 為200，固定此參數繼續優化其他參數。優化結果如圖4所示。最后優化后的參數為NIND=400，Pc1=0.3，Pc2=0.75，Pm1=0.125，Pm2=0.3，MAXGEN=2 000。

圖4 遺傳算子參數設計

3.2 算例分析

遺傳算法相關參數見表2，其中小規模中可使用的車次設置為2次。

表2 遺傳算法參數設置

采用改進遺傳算法對小規模算例進行求解，并用gurobi求解相同問題，從而進行比較分析。具體求解結果見表3。由于在小規模案例中，遺傳算法在同一實例中經過迭代所找出的近似最優解都相同，因此并不需計算其平均目標函數值。

表3 小規模算例求解結果分析（算例R1001-算例R1010）

從表3可以看出，在小規模問題中精確算法與改進遺傳算法相比，其目標函數值在大部分算例中都相同，在小部分算例中有微小的差異，可驗證所提出遺傳算法的有效性。

為進一步驗證本文提出遺傳算法的優勢，對中大規模算例進行實驗對比。其中遺傳算法對不同算例分別進行10 次求解。其中中規模算例可使用的車次設置為3 次，MAXGEN 設置為2 000 次；大規模算例可使用的車次設置為5 次，MAXGEN 設置為5 000次。

從表4 可知，在中規模算例中，改進遺傳算法所得的目標函數值總成本比gurobi 求解結果高0.80%，但是算法計算速度在大多算例中遠遠快于gurobi 求解。從表5 可知，在大規模算例中，改進的遺傳算法依舊能保持較好的魯棒性，且依舊能快速得出近似最優值，但gurobi求解在規定的2小時內已經無法求出解。可見隨著算例規模的進一步增大，遺傳算法在速度方面的優勢愈發體現出來，可用來求解大規模問題。

表4 中規模算例求解結果分析（算例R2001-R2020）

表5 大規模算例求解結果分析算例（R4001-R4010）

3.3 敏感度分析

在對算例進行求解時，調度車的車次限制（NV）、調度車的最大容量（Cap）以及第二次及之后從調度中心出發時允許初始的最大好車數（G_max）都會對結果有影響。為了探究以上三種因素的變化對總目標函數的影響，本節在中規模算例（R2001-R2010）下對其進行靈敏度分析。在敏感度分析時，初始NV=3，Cap=40，G_max=10。對不同因素進行分析時，十個算例分別進行五次求解且取其中的最小值記錄，將每個算例中所記錄的最小值取平均值，作為當前的目標函數平均值。

3.3.1 分析NV敏感度。從表6可知，隨著NV從1到5逐漸變大，目標函數先降低后趨于平穩態勢（如圖5（b）所示）。

表6 調度車次限制（NV）敏感度分析

圖5 目標函數和求解時間隨著NV變化的敏感性分析

3.3.2 分析Cap敏感度。從表7可知，隨著車輛容量Cap的增加，目標函數值下降，其下降斜率從大到小逐漸變小（如圖6（b）所示）。

表7 車輛容量（Cap）敏感度分析

圖6 目標函數和求解時間隨著Cap變化的敏感性分析

分析原因為：當Cap小于40時，其完成任務所需要使用的調度車次大于初始的NV（值為3），因此其不僅需要更多的調度車次增加了懲罰成本，還需要多次來回調度中心增加了額外的路徑成本。因此在Cap為20-40期間，目標函數值下降幅度較大，其下降幅度先大后小。當Cap大于40時，目標函數幅度下降變緩，其減少的成本在于減少來回調度中心的額外路徑成本。隨著車輛容量Cap的增加，求解時間總體呈下降趨勢（如圖6（a）所示）。原因在于隨著Cap的增大，所需要使用的車次數減少，因此算法搜索時間變少。

3.3.3 分析G_max敏感度。從表8可知，隨著車輛容量G_max的增加，目標函數先下降后趨于平穩，其下降幅度從大到小（如圖7（a）所示）。

表8 允許所帶的好車數（G_max）敏感度分析

圖7 目標函數和求解時間隨著G_max變化的敏感性分析

分析原因為：當調度車因容量限制返回調度中心，再次出發時調度車上的好車數會被初始化為G_max，若G_max過小，則會損失一些好車，從而造成好車不足懲罰成本的產生。隨著G_max從0逐步增大到15左右時，目標函數都在下降，因為增大G_max可以減少對路線規劃的限制從而搜索到目標函數值更小的滿意解。隨著G_max的進一步增加，由于其路徑滿意解中不存在需要G_max更大的路徑，因此其目標函數值并沒有下降。隨著G_max的改變，求解時間總體呈上升趨勢（如圖7（b）所示），原因在于G_max的增大會在一定程度上增大搜索規模。

4 結語

本文考慮了共享單車的實際情況，包括好車的調度和壞車的回收，對于共享單車企業具有重要的現實意義。本文的主要工作如下：（1）在遺傳算法的基礎上，對其進行了改進，引入了爬山操作、自適應交叉、變異等。（2）本文通過gurobi對模型進行精確求解，并與啟發式算法求解結果進行分析比較。通過小、中、大三個規模實驗分析，證明本文所提出的改進遺傳算法具有可行性和優勢性。最后，本文對調度車的車次限制、最大容量以及第二次及之后從調度中心出發時允許初始的最大好車數進行了敏感性分析，其結果總體呈下降趨勢，并得出了以下結論：（1）增加調度車的車次并不一定會降低成本，因為車次過多時一些調度車并不一定會以最優路線運行；（2）增加調度車的最大容量，調度車的運行成本降低，但降低幅度逐漸變小，因此需要結合調度車的固定成本來權衡合適的車輛容量；（3）增加第二次及之后從調度中心出發時允許初始的最大好車數，其運行成本先降低后略微上升，因此需要選擇適當的初始最大好車數來減少成本。

本文提出的共享單車平衡和回收已經有了一定的成果，但還存在許多不足需要改善，在未來的研究中可以從以下幾個方面進行改進：（1）可引入客戶的滿意度以及調度車作業時的碳排放量為目標函數，使其成為更復雜的多目標函數問題。（2）后續對模型假設復雜化，將其設置為每個站點可多次訪問，共享單車所停位置為非固定式的散亂停放，以及好車壞車數量在調度工作途中會在較小幅度波動的情況。