徐悅甡，周奕杉，黃健斌，李 瑩，黑 蕾

(1.西安電子科技大學 計算機科學與技術學院，陜西 西安 710071；2.浙江大學 計算機科學與技術學院，浙江 杭州 310058；3.西安電子科技大學 期刊中心，陜西 西安 710071)

0 引言

隨著經(jīng)濟社會各行業(yè)與前沿高新技術間聯(lián)系的日漸緊密，共享經(jīng)濟悄然興起。在共享經(jīng)濟模式下，共享單車服務與城市交通逐漸融合，在一定程度上彌補了城市傳統(tǒng)公共交通存在的“首尾一公里”問題，有效緩解了交通道路擁堵，構(gòu)建了低碳出行體系。共享單車服務遍布世界各地，截止2020年7月，全世界已有超過2 000個正在運行的共享單車服務[1]，其中擁有悠久歷史的有樁共享單車服務占主導地位。

雖然共享單車服務充分利用了社會資源，但是由于人們用車的復雜隨機性，以及多種外界因素的影響，共享單車站點經(jīng)常出現(xiàn)單車資源分布不均衡的情況，如果經(jīng)常找不到可以滿足用車需求的站點，則在極大降低用戶用車體驗和滿意度的同時損害運營商的品牌形象和收入。解決站點單車資源分布不均衡問題的關鍵在于合理規(guī)劃共享單車服務調(diào)度的流程，具體為：①確定每個站點的用車需求量，這取決于對站點借車和還車需求的準確預測，然而由于時間、環(huán)境等多種因素和人們行動的復雜性，難以得到某個站點需求變化的規(guī)律；②共享單車服務調(diào)度的流程規(guī)劃是一個多目標優(yōu)化問題，需要考慮各個供需失衡站點在未來一段時間內(nèi)的用車需求，以及形式路徑、調(diào)度成本和調(diào)度車容量等約束，再規(guī)劃出合理的調(diào)度流程。運營商通常用一個調(diào)度車隊為站點重新分配單車，或者運走單車，來滿足站點未來一段時間的用車需求，而為每個站點確定未來時間的借車、還車需求，以及為每輛卡車按約束條件規(guī)劃調(diào)度路線，即為共享單車服務調(diào)度的流程規(guī)劃問題。

實際上，每個站點與鄰近站點密切相關，因為車站的車樁和單車數(shù)量有限，如果站點單車資源短缺，則在運營商重新調(diào)整站點的單車資源前，車站將長時間處于不可服務狀態(tài)，這段時間內(nèi)站點無法滿足用車需求。當人們到達的站點沒有足夠單車時，通常會前往附近車站借用單車，因此站點及其周圍站點組成的合理的站點集群更能反映人們的真實用車需求。在發(fā)生單車短缺后，對該站點用車需求進行的預測將不再準確，然而以往研究僅集中于預測站點的用車需求，站點集群對共享單車服務真實用車需求的體現(xiàn)及其在調(diào)度流程規(guī)劃中的價值常被忽略。

本文提出一種面向共享單車服務調(diào)度的流程規(guī)劃算法，具體貢獻如下：①結(jié)合歷史騎行數(shù)據(jù)中站點的用車需求相關性和位置關系動態(tài)挖掘站點集群，從時空和氣象數(shù)據(jù)中提取特征，利用極端梯度提升(eXtreme Gradient Boosting, XGBoost)模型對不同時段站點集群的用車需求進行預測；②提出一種歷史時間窗口K近鄰與再分配算法估計每個站點的用車需求；③基于蟻群算法(Ant Colony Algorithm, ACA)建立數(shù)學約束模型，提出一種解決共享單車服務靜態(tài)調(diào)度的流程規(guī)劃算法；④通過實驗驗證了所提算法的準確性和有效性。

1 相關工作

對共享單車服務中資源分配不平衡站點的調(diào)度流程進行規(guī)劃，調(diào)整單車數(shù)量，已經(jīng)成為解決單車資源不平衡問題最常用的方式。然而，發(fā)生短缺后再向站點重新調(diào)度單車資源為時已晚，需要提前規(guī)劃調(diào)度流程，目前對調(diào)度流程規(guī)劃的研究分為動態(tài)調(diào)度流程規(guī)劃和靜態(tài)調(diào)度流程規(guī)劃兩類。

動態(tài)調(diào)度流程規(guī)劃主要在白天進行，對站點的調(diào)度操作依賴于用車需求。ZHANG等[2]考慮車站的實時容量，并建立預測用戶到達站點的時空網(wǎng)絡流模型，結(jié)合混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming, MILP)模型和數(shù)學啟發(fā)式方法提出動態(tài)單車調(diào)度流程規(guī)劃方法；SHUI等[3]利用混動視野法將時間分成一組時間段，每個時間段看作一個靜態(tài)調(diào)度流程規(guī)劃問題，然后采用人工蜂群算法求解；CHIARIOTTI等[4]對站點的歷史騎行數(shù)據(jù)進行統(tǒng)計，并對借車和還車情況建立統(tǒng)計學模型以確定動態(tài)調(diào)度的時間，利用圖論給出單車資源調(diào)度流程的規(guī)劃策略。

2 基于預測的需求調(diào)度

2.1 站點集群動態(tài)挖掘

準確預測站點集群需求量可為后續(xù)單車分配和調(diào)度流程規(guī)劃提供指導，這對共享單車服務調(diào)度至關重要。為更準確地得到集群中站點的用車需求量，應該盡可能將具有相似使用需求的站點劃分到同一個且大小合適的站點集群中。適宜的站點集群能夠讓集群中的用車需求量更加集中并凸顯用車規(guī)律，以使預測的用車需求量更加可靠。由站點劃分得到的站點集群應該包含相同時間跨度內(nèi)用車需求趨勢相似和地理距離相互鄰近的站點，構(gòu)造鄰接圖G=(S,E)，其中節(jié)點集S=(S1,S2,…,Sn)表示數(shù)據(jù)集中所有的n個站點，E是相應兩個站點間的連接邊集。構(gòu)建圖時僅需考慮相互鄰近的站點，本文用K近鄰(K-Nearest Neighbor, KNN)方法為每個站點選取k個具有前k個邊權重值的站點來構(gòu)造一個稀疏的鄰接圖G。sim(Si,Sj)表示站點間在一組時間段內(nèi)用車需求向量的皮爾森相關系數(shù)，邊權重值用站點、使用需求相似度sim(Si,Sj)和站點間的地理距離計算，即

W(Si,Sj)=

(1)

式中：dist(Si,Sj)為站點Si和站點Sj之間的地理距離；τ為站點間的相鄰距離閾值。站點集群中的站點應該相互鄰近，故式(2)中站點間的地理距離小于閾值τ會被獎勵，大于閾值τ會被懲罰。將構(gòu)建出的鄰接圖G切分為一組子簇，每次迭代時動態(tài)選擇兩個子簇進行合并，被選擇合并成新簇的子簇應該具有較高的相對連通度RI(Ci,Cj)和相對緊密度RC(Ci,Cj)(見式(3))。相對連通度RI考慮了簇和簇之間的距離以及簇內(nèi)部各數(shù)據(jù)點之間的距離，相對緊密度RC用于避免將較小的稀疏簇合并到較大的密集簇。

RC(Ci,Cj)=

(2)

2.2 站點用車需求預測與估計

相對而言，人們更傾向于在晴天和春天騎車出行。本文在天氣報告和紐約花旗單車歷史出行數(shù)據(jù)[8-10]中提取特征，將天氣類別、星期、工作日、小時、月份和季節(jié)映射為One-Hot編碼，溫度、風速、濕度和降水強度的特征用數(shù)值編碼表征。然后將提取出的特征組合為矩陣，特征矩陣中的列表示特征，行表示所有類型特征的組合向量。將特征矩陣和歷史每小時用車需求量輸入XGBoost回歸模型預測未來不同時段站點集群的用車需求。

基于站點集群的每小時預測結(jié)果，通過歷史時間窗口K近鄰與再分配(Historical Time Window K-Nearest Neighbor and Redistribution, HTKR)算法估計站群中每個站點在預測時間組TGθ的用車需求量。選取3個高峰期時間組，即工作日早高峰TG1(6:00～9:00)、工作日晚高峰TG2(16:00～20:00)、休息日白天高峰TG3(11:00～20:00),分別計算站點不同時間組內(nèi)的用車需求。首先選取前K個與TGθ最近的時間組用車需求，采用式(3)計算得到單個站點Si平均用車需求量占站群Cj的比率，再與站群在時間組TGθ內(nèi)預測的需求量相乘求得站點的基本預測需求量

(3)

(4)

(5)

站點估計的用車需求量

(6)

當站點的估計用車需求量DSi,TGθ≠0時對該站點進行調(diào)度。

3 基于蟻群優(yōu)化的流程規(guī)劃算法

為了解決共享單車系統(tǒng)中站點單車資源失衡的問題，運營商通常用一組調(diào)度卡車將系統(tǒng)中的單車重新分配到站點或者增加站點空閑車樁容量。共享單車服務調(diào)度的流程規(guī)劃問題如圖1所示，在卡車容量限制下，站點的用車需求完全由這組卡車按照調(diào)度流程順序滿足，圖中括號內(nèi)的數(shù)字表示站點的用車需求，在每一次調(diào)度流程中，一輛卡車承載著初始數(shù)量的單車出發(fā)或者空車出發(fā)，經(jīng)過若干站點后返回倉庫。

針對小型靜態(tài)調(diào)度流程規(guī)劃問題，傳統(tǒng)方法[2,5-6]采用MILP模型求解，然而對于中大型規(guī)模，如200輛卡車和3輛卡車的場景，傳統(tǒng)方法不能在有效時間內(nèi)得到最優(yōu)解[11]，而元啟發(fā)式方法則可在有效時間內(nèi)得到足夠好的近似最優(yōu)解。蟻群算法為一種重要的元啟發(fā)算法，該算法為解決旅行商問題而提出,在此基礎上提出蟻群系統(tǒng)，本文對蟻群算法進行優(yōu)化來求解調(diào)度流程規(guī)劃問題。

3.1 調(diào)度流程規(guī)劃的約束模型

調(diào)度流程規(guī)劃的優(yōu)化目標是在給定約束模型下找到調(diào)度成本最小的流程可行解，本文將系統(tǒng)中需要調(diào)度的站點看作圖G=(S,E)，其中S={S0,S1,S2,…,Sn}，S0為配送倉庫，n為站點數(shù)量。2.2節(jié)對每個站點確認了用車需求量，當DSi,TGθ>0時表示站點在目標時間組內(nèi)的還車需求更多，站點內(nèi)的單車需要卡車拾?。划擠Si,TGθ<0時表示站點在目標時間組內(nèi)的借車需求更多，卡車需要將單車運送到站點。dij(i,j∈S)為站點和配送倉庫的地理距離，xij(i,j∈S)為二元變量，有卡車經(jīng)過站點Si和Sj時為1，否則為0。假設車隊中最多有V輛最大運載容量為C的卡車參與調(diào)度。為了滿足各站點用車需求的基本條件，對各站點的調(diào)度流程規(guī)劃進行優(yōu)化，建立如下數(shù)學模型：

(7)

s.t.

xij∈{0,1},i,j∈S;

(8)

(9)

(10)

其中：目標函數(shù)式(7)為多目標優(yōu)化的加權度量，第1部分表示調(diào)度路徑的成本，為路徑長度乘以每公里調(diào)度單價λ，第2部分表示調(diào)度用車成本，為調(diào)度卡車數(shù)量p乘以每輛調(diào)度卡車的成本φ。式(8)表示每個站點只能被調(diào)度卡車服務一次；式(9)表示從配送倉庫出發(fā)調(diào)度的卡車最多有V輛，而且所有從配送中心出發(fā)的卡車都會回到調(diào)度中心；式(10)表示一條調(diào)度路徑上所有站點的需求量不會超過調(diào)度卡車的最大車載容量C。

3.2 蟻群系統(tǒng)優(yōu)化

在共享單車服務場景下，普通蟻群算法首先將a只螞蟻放在調(diào)度倉庫S0上，并將每條路徑上的信息素量初始化為相同的常數(shù)值。在每只螞蟻的尋路過程中，根據(jù)各路徑上的殘余信息素濃度τij(t)和路徑啟發(fā)式信息ηij選擇下一個沒有訪問且需要調(diào)度的站點。螞蟻k在第t次迭代時從站點Si到Sj的概率

(11)

式中：α為路徑(i,j)上殘余信息素的重要性，β為路徑上啟發(fā)式信息的重要性；allowedk={C-tabuk}表示對于螞蟻可以訪問的下一個站點集合，tabuk記錄螞蟻k已經(jīng)訪問過的站點。當所有站點都被訪問后，螞蟻k即完成對一次站點的遍歷，記錄螞蟻k這次遍歷的站點便得到一個調(diào)度可行解。

啟發(fā)式信息ηij用站點之間路徑距離的倒數(shù)計算，即ηij=1/dij。路徑上的信息素隨時間消散，ρ(ρ∈(0,1))為信息素的揮發(fā)比率，1-ρ為信息素的保持比率，螞蟻對所有站點每完成一次遍歷，站點之間路徑上的信息素即按式(12)進行更新。

τij(t+1)=

(12)

(13)

通過輪盤賭方法選擇下一個站點(式(11))，然而隨著問題規(guī)模的擴大，受路徑上所累積信息素的影響，輪盤賭法后期選擇的站點容易被局限于固定的站點范圍，普通蟻群算法易陷于局部解空間，導致收斂速度變慢，本文結(jié)合蟻群系統(tǒng)[12]的站點轉(zhuǎn)換規(guī)則對普通蟻群算法進行優(yōu)化，賦予路徑上的啟發(fā)式信息更多重要性，并使選擇站點的過程具有一定隨機性，從而使螞蟻有機會跳出局部解空間。與普通蟻群算法和蟻群系統(tǒng)不同，當q>q0時螞蟻k用式(12)選擇下一個待處理站點，當q≤q0時用式(13)選擇下一個待處理站點，即

j=argmax{[τij(t)][ηij(t)]β}。

(14)

(15)

3.3 混沌擾動優(yōu)化

在確定性系統(tǒng)中發(fā)生的具有隨機性的狀態(tài)稱為混沌狀態(tài)，混沌系統(tǒng)擁有不同的系統(tǒng)特性，可以在指定范圍內(nèi)遍歷所有狀態(tài)而不發(fā)生重復[13]，經(jīng)典的混沌系統(tǒng)Logistic映射根據(jù)混沌變量z第t次迭代的值，通過公式z(t+1)=μ×z(t)×(1-z(t)),0

4 實驗驗證與分析

本文算法在后文稱為HTKR-ACO，用HTKR-ACO對紐約市花旗單車2018年11月1日～2019年11月30日的歷史騎行數(shù)據(jù)集[8]、花旗單車系統(tǒng)站點狀態(tài)數(shù)據(jù)集[14]和氣象數(shù)據(jù)集[9]進行處理，歷史騎行數(shù)據(jù)集中共有706個站點和2 375萬條騎行記錄，站點狀態(tài)數(shù)據(jù)集包括共享單車服務中站點的運行狀態(tài)、可用車樁、可用單車、站點用量記錄，氣象數(shù)據(jù)集包括紐約市每小時的氣象報告數(shù)據(jù)。

4.1 評價指標

為了評估不同方法對集群站點用車需求量預測結(jié)果的表現(xiàn)及其有效性，采用均方根對數(shù)誤差RMLSE和誤差率ER作為評價指標，RMLSE和ER被廣泛用于評價共享單車服務問題[2,15]：

RMLSE=

(16)

4.2 聚類參數(shù)敏感度分析

4.2.1 參數(shù)k的敏感度分析

在構(gòu)建稀疏的鄰接圖時，KNN方法中的k值表示為站點篩選出的相鄰站點的數(shù)量。若k值太小，則選取連接的站點少，在周圍尋找相似站點不充分；若k值太大，則構(gòu)建的鄰接圖過大，后續(xù)需將鄰接圖切分為小簇，但會增加計算量。本文分析k值在6～14區(qū)間時的聚類效果，聚類評估指標選用輪廓系數(shù)分數(shù)和戴維森堡丁指數(shù)DBI。

輪廓系數(shù)用于評估集群的內(nèi)聚度和分離度，取值范圍為[-1,1]，一個較大的輪廓系數(shù)分數(shù)表示聚類能夠更好地與其他集群分離，且在集群內(nèi)部有更高的內(nèi)聚性[16]。定義DBI為集群內(nèi)部離散度與集群之間分離度的比率，DBI分數(shù)越低，集群的邊界越清晰[16]。圖2所示為不同k值下兩個評價指標的得分情況。

圖2中，k=6時輪廓系數(shù)分數(shù)較低，原因是鄰接圖構(gòu)造中的相鄰站點規(guī)模太小，而且這些較小的相鄰站點無法成功挖掘站點之間自行車需求的相關性；k=12，14時輪廓系數(shù)分數(shù)也較低，可以推斷，較大的k會增加鄰接圖中的相鄰站點，進一步增大鄰接圖的復雜性，從而影響子簇劃分的有效性;當k=8，10時，可以獲得較高的輪廓系數(shù)得分，即集群結(jié)果較好。同時，因為單個站點中的單車使用需求經(jīng)常變化，而且同一個集群中的其他站點可以為目標站點用車需求預測的準確性提供有價值的信息，所以本文設k=10。

4.2.2 距離閾值τ的敏感度分析

在邊權重計算式(1)中，右邊第2部分表示站點間距離的權重，站點間距離超過距離閾值τ時會被懲罰。聚類指標DBI評估了τ在0.5 km～2 km取不同值時的聚類表現(xiàn)，圖3所示分別為不同τ值下的DBI和輪廓系數(shù)，當τ=1.5 km時，DBI取得最小值且輪廓系數(shù)達到最大，因此本文設鄰域距離閾值τ=1.5 km。

4.3 需求量預測驗證

(1)對比方法 本文預測了站點集群的用車需求量，并設計實驗與多個常用或經(jīng)典的基準預測方法進行比較來驗證預測準確度：①HA，為歷史均值方法，其通過每個歷史時間段租賃和歸還的單車需求量的平均數(shù)來預測當前的租車和還車需求[16-17]；②自回歸滑動平均模型(Auto-Regressive and Moving Average model, ARMA)，該模型將租賃和歸還單車需求量看作為時間序列，預測該時間段內(nèi)未來的需求；③自回歸積分滑動平均模型(Auto-Regressive Integrated Moving Average model, ARIMA),該模型適用于處理不穩(wěn)定數(shù)據(jù)[18]；④梯度提升回歸樹(Gradient Boosted Regression Tree, GBRT),該模型采用輸入樣本值中代價函數(shù)的負梯度作為殘差的近似值來擬合回歸樹，以預測未來時期的租賃和歸還單車需求量；⑤隨機森林(Random Forest, RF)，該模型由多個隨機樹組成，隨機樹輸出的平均值用作單車需求的預測值。

(2)預測結(jié)果對比 基于上述站點集群聚類結(jié)果，對比不同預測方法的用車需求預測誤差，包括HA、ARMA、ARIMA、基于位置敏感的層次聚類的梯度提升回歸樹(Location-aware Hierarchical Clustering-Gradient Boosted Regression Tree, LHC-GBRT)、基于位置敏感的層次聚類的隨機森林(Location-aware Hierarchical Clustering-Random Forest, LHC-RF)、基于位置敏感的層次聚類的極端梯度提升方法 (Location-aware Hierarchical Clustering-eXtreme Gradient Boosting, LHC-XGBoost)。實驗對基于機器學習的方法使用相同的樣本特征，包括XGBoost，GBRT，RF，并利用網(wǎng)格搜索選擇最優(yōu)的參數(shù)組合。表1所示為數(shù)據(jù)集需求量預測的所有時刻的平均RMSLE和ER，其中LHC-XGBoost產(chǎn)生的預測精度最佳，因此本文采用LHC-XGBoost預測得到的站點用車需求來預測結(jié)果。

表1 不同預測方法的用車需求預測誤差對比

4.4 調(diào)度流程規(guī)劃驗證

為評估HTKR-ACO尋找最小調(diào)度成本的流程規(guī)劃的有效性，與以下方法進行對比：①普通蟻群算法ACA；②適應參數(shù)的蟻群算法(Adapt-AS)[19]，修改AS的信息素更新公式，每次迭代參與更新的信息素揮發(fā)率ρ正比于信息素濃度τij(t)；③基于蟻群系統(tǒng)站點轉(zhuǎn)換規(guī)則的蟻群算法(Station Transfer Regulation-Ant System, STR-AS)，利用蟻群系統(tǒng)(Ant Colony System, ACS)算法的站點轉(zhuǎn)換規(guī)則對ACA進行修改；④ACS算法[12]。

4.4.1 調(diào)度流程規(guī)劃結(jié)果對比

根據(jù)LHC-XGBoost得到的站點集群預測結(jié)果，觀察早晚高峰期站點集群的用車需求量，如圖4所示。圖中(0～800)表示還車數(shù)量大于借車數(shù)量，(-800～0)表示借車數(shù)量大于還車數(shù)量。圖4a和圖4b中同一個站點的紅藍兩色對比顯示早晚高峰期用車需求的差異性和對稱性，例如早高峰借車需求高的站群在晚高峰還車需求高。為驗證本文所提流程規(guī)劃算法的性能，取圖中實線圓圈圈住的早晚高峰用車需求差異大、用車需求旺盛的6個站點集群共143個站點進行調(diào)度流程規(guī)劃，其他站點的流程規(guī)劃與其類似。

實驗為所有方法設置相同的參數(shù)，由4.2節(jié)可知參數(shù)取值會直接影響蟻群算法的收斂效果和速度，參照文獻[12-13]，本文在數(shù)據(jù)集上對不同參數(shù)取值進行了預實驗，最終選取參數(shù)α=2，β=5，Q=10，q0=0.9，a=100，ρ=0.4;同時,為了對比最小成本調(diào)度的流程規(guī)劃結(jié)果，本文將式(7)的目標參數(shù)設為λ=1和φ=0,卡車調(diào)度容量C=100,通過規(guī)劃得到調(diào)度流程的路徑長度來直觀地比較算法性能。為提高實驗結(jié)果的可靠性，將每個方法運行30遍，每一遍運行迭代150次，對所得結(jié)果求平均值。

每次迭代的平均路徑長度和每遍運行的最短調(diào)度路徑長度對比如圖5所示，Adapt-AS曲線表示動態(tài)調(diào)整ρ值和Q值雖然使算法沒有過早收斂到局部最優(yōu)解，但是相比AS曲線表示的AS平均最優(yōu)解，并未表現(xiàn)出優(yōu)越性；STR-AS曲線表示STR-AS結(jié)合了ACS的站點轉(zhuǎn)換規(guī)則;HTKR-ACO曲線表示HTKR-ACO基于STR-AS算法，但加入了混沌擾動；ACS曲線表示ACS算法收斂速度最慢，150次迭代仍不能收斂，其在前30次迭代優(yōu)化處于停滯狀態(tài)，可能由于更新信息素時以1為分子，而將實例中的路徑長度作為分母數(shù)值太大，導致迭代時路徑上的信息素累積緩慢，信息素正反饋效果不好。

由圖5b可見，HTKR-ACO每次運行找到的路徑較短且尋優(yōu)表現(xiàn)更穩(wěn)定。結(jié)合圖5a可知，HTKR-ACO在所有方法中求解得到的平均路徑最短，收斂速度較快，能為系統(tǒng)有效規(guī)劃出較短的調(diào)度路徑。不同對比方法規(guī)劃的調(diào)度流程路徑長度如表2所示。

表2 不同方法規(guī)劃的調(diào)度流程路徑長度

實驗預設站點中編號最小的站點為配送倉庫，運行HTKR-ACO取得兩個調(diào)度流程可行解的實例如圖6所示，圖中圓點和線段分別表示站點和流程路徑，圓點表示配送倉庫，實例中的共享單車服務調(diào)度共規(guī)劃出2個流程，需要2輛卡車完成調(diào)度流程。站點上方括號中的數(shù)字表示站點在調(diào)度流程階段的需求量，可見HTKR-ACO可以規(guī)劃出滿足站點需求且合理的調(diào)度流程。

4.4.2 調(diào)度流程的需求滿足驗證

在調(diào)度流程中要盡可能滿足各個站點的用車需求，因此將HTKR與歷史時間窗口K近鄰(Historical Time windowKnearest neighbor, HTK)方法進行對比，并通過需求滿足率DSR來評估調(diào)度時滿足站點集群用車需求的比例。在2019年8月5日～2019年8月12日連續(xù)一周的真實數(shù)據(jù)集上設計實驗，圖7所示分別為其中4天經(jīng)過HTKR和HTK分配后未滿足的需求量，以及預測站點集群總使用需求量的對比情況。

可見，每一天HTKR-ACO分配后未滿足的需求量均比HTK更少，說明利用站點集群內(nèi)空余的車樁和單車可以有效減少站群中未滿足的用車需求。本文分別計算單車需求及車樁需求的DSR并取兩者均值得到7天內(nèi)不同時間組的DSR，如表3所示，可見HTKR的平均DSR在7天中均高于88%，證明通過HTKR分配后可以極大地滿足預測站點集群的用車需求。

表3 HTKR和HTK分配后的DSR對比

5 結(jié)束語

為解決共享單車服務調(diào)度流程的優(yōu)化問題，本文分別從調(diào)度需求估計和流程規(guī)劃兩方面考慮，首先為共享單車服務站點劃分站點集群，預測站點集群用車需求并估計各站點的用車需求，然后建立調(diào)度流程優(yōu)化目標的問題模型，提出一個蟻群優(yōu)化的調(diào)度流程規(guī)劃算法，通過蟻群系統(tǒng)更強的信息素正向反饋機制、啟發(fā)式信息更快的局部搜索能力和混沌理論較強的全局搜索能力，改善了蟻群算法易陷入局部解空間和蟻群系統(tǒng)收斂速度過慢的問題，從而快速收斂到全局近似最優(yōu)解。實驗驗證，所提算法在用車需求分配和調(diào)度流程規(guī)劃上均能取得較好表現(xiàn)，可以有效指導共享單車服務調(diào)度流程規(guī)劃，提高共享單車服務的可行性。