面向共享單車服務(wù)調(diào)度的流程規(guī)劃算法

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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

2 基于預(yù)測(cè)的需求調(diào)度

2.1 站點(diǎn)集群動(dòng)態(tài)挖掘

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

W(Si,Sj)=

(1)

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

RC(Ci,Cj)=

(2)

2.2 站點(diǎn)用車需求預(yù)測(cè)與估計(jì)

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

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

(3)

(4)

(5)

站點(diǎn)估計(jì)的用車需求量

(6)

當(dāng)站點(diǎn)的估計(jì)用車需求量DSi,TGθ≠0時(shí)對(duì)該站點(diǎn)進(jìn)行調(diào)度。

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

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

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

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

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

(7)

s.t.

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

(8)

(9)

(10)

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

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

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

(11)

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

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

τij(t+1)=

(12)

(13)

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

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

(14)

(15)

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

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

4 實(shí)驗(yàn)驗(yàn)證與分析

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

4.1 評(píng)價(jià)指標(biāo)

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

RMLSE=

(16)

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

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

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

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

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

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

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

4.3 需求量預(yù)測(cè)驗(yàn)證

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

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

表1 不同預(yù)測(cè)方法的用車需求預(yù)測(cè)誤差對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

表3 HTKR和HTK分配后的DSR對(duì)比

5 結(jié)束語(yǔ)

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