丁飛陽，張 思

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

0 引言

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

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

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

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

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

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

1 模型建立

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

圖1 共享單車調(diào)度和回收故障車輛示意圖

本模型提出如下假設：

（1）站點調(diào)度與回收故障車工作發(fā)生于深夜，此時不考慮站點單車數(shù)量的變動，為靜態(tài)重平衡；

（2）只存在一個調(diào)度中心，調(diào)度車輛從該處出發(fā)，最后需返回該處；

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

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

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

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

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

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

表1 變量符號及含義

模型建立如下：

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

2 算法設計

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

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

2.1 初始解的生成

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

如其中一條染色體為：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 適應度函數(shù)

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

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

2.3 選擇與爬山操作

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

圖2 選擇操作流程圖

2.4 遺傳自適應操作

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

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

設置變異概率為：

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

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

圖3 算法流程圖

3 算例分析

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

3.1 參數(shù)設計

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

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

圖4 遺傳算子參數(shù)設計

3.2 算例分析

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

表2 遺傳算法參數(shù)設置

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

表3 小規(guī)模算例求解結(jié)果分析（算例R1001-算例R1010）

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

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

從表4 可知，在中規(guī)模算例中，改進遺傳算法所得的目標函數(shù)值總成本比gurobi 求解結(jié)果高0.80%，但是算法計算速度在大多算例中遠遠快于gurobi 求解。從表5 可知，在大規(guī)模算例中，改進的遺傳算法依舊能保持較好的魯棒性，且依舊能快速得出近似最優(yōu)值，但gurobi求解在規(guī)定的2小時內(nèi)已經(jīng)無法求出解?？梢婋S著算例規(guī)模的進一步增大，遺傳算法在速度方面的優(yōu)勢愈發(fā)體現(xiàn)出來，可用來求解大規(guī)模問題。

表4 中規(guī)模算例求解結(jié)果分析（算例R2001-R2020）

表5 大規(guī)模算例求解結(jié)果分析算例（R4001-R4010）

3.3 敏感度分析

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

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

表6 調(diào)度車次限制（NV）敏感度分析

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

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

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

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

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

3.3.3 分析G_max敏感度。從表8可知，隨著車輛容量G_max的增加，目標函數(shù)先下降后趨于平穩(wěn)，其下降幅度從大到?。ㄈ鐖D7（a）所示）。

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

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

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

4 結(jié)語

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

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