劉恒孜， 賀玉龍， 宋太龍， 許 鵬

(北京工業(yè)大學, 北京市交通工程重點實驗室， 北京 100124)

在共享經(jīng)濟的發(fā)展下，共享單車出現(xiàn)在了城市的大街小巷，綠色、低碳和健康的自行車出行方式正在被居民普遍接受。共享單車系統(tǒng)能夠有效解決用戶短途出行問題，是城市交通系統(tǒng)中的重要組成部分。準確的共享單車需求預(yù)測以及合理的調(diào)度研究可以為共享單車運營部門和交通管理部門提供有效的參考，從而提高共享單車系統(tǒng)的運行效率。

由于競爭激烈，全球大多數(shù)共享單車公司似乎都在虧損經(jīng)營。不斷增加的收入加上持續(xù)的虧損表明，共享單車公司迫切需要改進運營。大多數(shù)調(diào)度優(yōu)化和供需平衡都依賴于對未來需求的準確預(yù)測[1]。關(guān)于共享單車的需求預(yù)測，曹旦旦等[2]和高巍等[3]采用長短期記憶神經(jīng)網(wǎng)絡(luò)模型對紐約市共享單車每小時需求量進行預(yù)測。Fournier等[4]建立了一個估計自行車季節(jié)性需求的正弦模型。Gao等[5]提出了一種基于模糊c均值的遺傳算法和反向傳播網(wǎng)絡(luò)相結(jié)合的混合方法，來預(yù)測共享單車需求。共享單車需求受時空狀態(tài)、騎行人心理生理狀態(tài)、氣候環(huán)境條件等因素影響，是隨機的、不確定的。共享單車系統(tǒng)存在不確定性，獲得的信息通常也是不完整的，因此可以被建模為一個灰色系統(tǒng)，進而用灰色預(yù)測理論來研究共享單車需求。Xiao等[6]在傳統(tǒng)GM(1,1)模型的基礎(chǔ)上，通過季節(jié)性累加得到新的序列，提出了一種季節(jié)性GM(1,1)模型。從預(yù)測結(jié)果上來看，傳統(tǒng)GM(1,1)模型的殘差序列具有較強的波動性，而Markov鏈適用于具有隨機波動性的數(shù)據(jù)序列[7]。馬爾可夫模型是一種無后效性的時間序列模型，采用馬爾可夫模型修正殘差可以提高殘差序列的隨機靈活性，進而使預(yù)測結(jié)果更加科學合理[8]。

共享單車調(diào)度優(yōu)化研究是共享單車系統(tǒng)優(yōu)化的重要組成部分，中外學者在靜態(tài)調(diào)度[9]、動態(tài)調(diào)度[10]、調(diào)度路徑[11-13]、調(diào)度時間[14]和調(diào)度成本[15]等方面做了大量的研究。Kadri等[16]用分支定界算法研究了再平衡車輛路徑問題，找出用戶等待總時間最小的最優(yōu)調(diào)度方案。胡郁蔥等[17]用雙層規(guī)劃模型來解決投放區(qū)域虛擬站點的選址及規(guī)模問題。Du等[18]針對車輛路徑問題建立一個模糊二層規(guī)劃模型，并設(shè)計了4種基于模糊仿真的啟發(fā)式算法。Hemmati等[19]研究了一個混合整數(shù)二層規(guī)劃公式，尋求博弈雙方利潤最大化。Yue等[20]提出了一個混合整數(shù)二層規(guī)劃建?？蚣芤约白顑?yōu)供應(yīng)鏈設(shè)計和運營的求解算法。共享單車調(diào)度涉及到各個部門的組織規(guī)劃，是一個NP(nondeterminism polynomial)難問題，雙層規(guī)劃模型考慮了決策過程中不同決策者的作用與表現(xiàn)，可以在不同層次上為決策者提供決策，是解決多層結(jié)構(gòu)決策問題的最佳數(shù)學規(guī)劃方法之一[21]。

現(xiàn)提出一種基于Markov模型修正殘差的季節(jié)性灰色Markov模型來預(yù)測共享單車的需求，選取紐約市17個站點來驗證模型的預(yù)測精度。然后基于預(yù)測得到的需求值，建立雙層規(guī)劃模型，上層目標為運營商的調(diào)度成本，下層目標為調(diào)度中心的調(diào)度時間，用GUROBI求解器求解。最后根據(jù)雙層規(guī)劃模型結(jié)果來制定調(diào)度優(yōu)化方案，在最大化滿足用戶需求的同時，使調(diào)度成本和調(diào)度時間最少。

1 季節(jié)性灰色Markov模型

共享單車的騎行數(shù)據(jù)通常具有復雜的非線性、隨機性和波動性等特征，并且呈現(xiàn)出季節(jié)性的特點。季節(jié)性GM(1,1)[SGM(1,1)]模型可以結(jié)合數(shù)據(jù)的周期性特征有效弱化數(shù)據(jù)的波動性，從而提高預(yù)測精度。

1.1 SGM(1,1)模型

對于原始非負序列

x(0)=(x(0)(1),x(0)(2),…,x(0)(n))

(1)

取q為一個循環(huán)，采用循環(huán)截斷累加生成算子(CTAGO)得到新的序列[6]為

y(0)=(y(0)(1),y(0)(2),…,y(0)(r)),

r=1,2,…,n-q+1

(2)

?k=1,2,…,n-q+1

(3)

y(0)的1-AGO序列為

y(1)=(y(1)(1),y(1)(2),…,y(1)(n))

(4)

計算式(4)可得

(5)

將通過季節(jié)性累加得到的式(2)代入傳統(tǒng)的GM(1,1)模型，則SGM(1,1)模型的基本形式可定義為

y(0)(k)+az(1)(k)=b

(6)

式(6)中：a表示發(fā)展系數(shù)；背景值z(1)(k)(k=2,3,…，n)可用均值生成序列表示，z(1)(k)=0.5y(1)(k)+0.5y(1)(k-1)；b表示灰作用量。

令

(7)

同樣，由最小二乘法求解p=(a,b)Τ=(BΤB)-1BΤY。

參照GM(1,1)模型[22]解白化微分方程得到SGM(1,1)模型的時間響應(yīng)序列為

k=1,2,…,r

(8)

將式(8)進行一次累減得

k=1,2,…,r

(9)

式(9)的還原值為

(10)

1.2 Markov模型修正預(yù)測殘差

馬爾可夫鏈是一種無后效性的時間序列模型，SGM(1,1)模型預(yù)測的殘差序列有正有負具有較強的隨機性，采用馬爾可夫鏈修正殘差可以提高殘差序列的隨機靈活性，進而使預(yù)測結(jié)果更加科學合理，具體步驟[23]如下。

(1)由初步預(yù)測結(jié)果得到殘差序列，即

ε(0)=(ε(0)(1),ε(0)(2),…,ε(0)(n))

(11)

將殘差序列劃分為s個狀態(tài)，記作E={E1,E2,…,Es}，確定序列中每個元素所在的狀態(tài)。

(2)計算狀態(tài)轉(zhuǎn)移概率矩陣，即

(12)

i,j=1,2，…,s

(13)

(3)修正殘差序列。根據(jù)新信息優(yōu)先原理，以殘差序列中待修正元素的前s個元素的狀態(tài)為原始狀態(tài)，依據(jù)其離待修正元素的遠近分別轉(zhuǎn)移1,2,…,s步，在轉(zhuǎn)移步數(shù)所對應(yīng)的轉(zhuǎn)移矩陣中，取原始狀態(tài)所對應(yīng)的行向量組成新的概率矩陣。對新的概率矩陣的列向量求和，得到待修正元素在每個狀態(tài)區(qū)間的概率矩陣p=[p1,p2,…,ps]，通過加權(quán)平均得到修正的殘差值

(14)

(4)優(yōu)化預(yù)測結(jié)果，得到最終預(yù)測值

(15)

1.3 模型步驟

Step 1確定原始序列x(0)，以q為周期，對原始序列進行季節(jié)性累加得到CTAGO序列y(0)(r),r=1,2,…,n-q+1。

Step 2對序列y(0)(r)進行一階累加，求解參數(shù)a、b。

Step 3將參數(shù)代入SGM(1,1)模型求解得到時間響應(yīng)序列，累減還原計算出初步預(yù)測值。

2 雙層規(guī)劃模型

中國對雙層規(guī)劃的研究始于20世紀80年代，最早開展雙層規(guī)劃研究的是東南大學的盛昭翰教授[21]。雙層規(guī)劃模型可以在不同層面上做出決策，為了滿足共享單車用戶的需求，同時使運營商的調(diào)度成本和調(diào)度中心的調(diào)度時間最低，引入雙層規(guī)劃模型來進行調(diào)度優(yōu)化。

假設(shè)運營商下面設(shè)有多個調(diào)度部門，不同的調(diào)度部門負責不同區(qū)域的車輛調(diào)度；假設(shè)調(diào)度中心的車輛足夠；假設(shè)在開始調(diào)度前每個站點都處于空站狀態(tài)；假設(shè)在調(diào)度過程中沒有車輛駛?cè)敫髡军c。

根據(jù)以上假設(shè)，建立以運營商為上層，調(diào)度部門為下層的雙層規(guī)劃模型。其中上層運營商的決策變量是確定調(diào)度中心選址方案x=(x1,x2, …,xJ),使總的調(diào)度成本盡可能小。下層調(diào)度部門的決策變量為yij，將在上層調(diào)度中心選址方案x=(x1,x2, …,xJ)給定的前提下，確定各個調(diào)度中心的調(diào)度方案，使得調(diào)度時間盡可能小。

因此上層規(guī)劃為

(16)

(17)

(18)

(19)

約束條件式(17)表示不超過運營商給出的預(yù)算成本；式(18)表示調(diào)度中心的個數(shù)不超過給定的上限個數(shù)P；式(19)表示建立調(diào)度中心才能提供車輛。

下層調(diào)度部門的決策變量為yij，在上層調(diào)度中心選址方案x=(x1,x2, …,xJ)給定的前提下，確定如何從調(diào)度中心調(diào)度車輛到各個站點才能使整個區(qū)域的調(diào)度時間最小，從而提高調(diào)度中心的效率。因此下層調(diào)度部門的規(guī)劃為

(20)

(21)

(22)

yij-xj≤0,i=1,2,…,I,

j=1,2,…,J

(23)

yij,xj∈{0,1},i=1,2,…,I,

j=1, 2,…,J

(24)

式中：f()表示調(diào)度時間的目標函數(shù);tij表示第j個調(diào)度中心到達第i個站點所需的時間；Sj表示第j個調(diào)度中心的最大供應(yīng)能力；yij、xj都是0-1變量。

目標函數(shù)式(20)是使調(diào)度中心總的調(diào)度時間最小；約束條件式(21)表示只有一個調(diào)度中心為第i個站點調(diào)度車輛；約束條件式(22)表示調(diào)度中心j能配送的車輛數(shù)不超過它本身的供給能力；約束條件式(23)表示第j個調(diào)度中心為第i個站點調(diào)度車輛的前提是在第j個地點建立調(diào)度中心。

3 實例分析

3.1 數(shù)據(jù)來源

研究所采用的共享單車騎行數(shù)據(jù)來自美國紐約市Citi Bike共享單車的網(wǎng)站。選取紐約市17個共享單車站點作為研究對象，部分站點之間的距離如表1所示。

表1 部分站點之間的距離

3.2 誤差指標

平均絕對百分比誤差(mean absolute percentage error，MAPE)是一個非常有用的評價指標，它不僅能夠很直觀地看出模型對于整體數(shù)據(jù)樣本的相對誤差的數(shù)量，還可以對整體數(shù)據(jù)誤差做出估計。MAPE計算公式為

(25)

MAPE值越小表明模型的精度越高，即MAPE值低于10%則認為模型的精度高[24]，MAPE值的范圍11%～20%表示精度較高，為21%～50%表示精度一般，大于或等于51%表示精度差。

3.3 預(yù)測結(jié)果

研究選取美國紐約市Citi Bike共享單車2019年6月10—28日周一到周五的騎行數(shù)據(jù)作為原始數(shù)據(jù)，用季節(jié)性灰色Markov模型來預(yù)測，利用Matlab R2020b計算出各個站點的需求預(yù)測值，同時驗證模型的精度。17個站點在2019年6月24—28日的共享單車需求預(yù)測值如表2所示。

表2的結(jié)果表明：在17個站點里，有10個站點的MAPE平均值低于10%，預(yù)測精度高；有6個站點的MAPE平均值在11%～20%這個范圍，預(yù)測精度較高；有1個站點的MAPE平均值在21%～50%這個范圍，預(yù)測精度一般。站點14的預(yù)測精度一般可能是由于季節(jié)性灰色Markov模型中q取值的影響，由于研究預(yù)測的是周一至周五的需求量，所以原模型的q=5，而站點14的原始數(shù)據(jù)周期性和波動性更強，當q=4時，計算得到該站點的MAPE平均值為5.52%。17個站點的MAPE平均值為10.68%，所以該模型本身的預(yù)測效果是好的，可以用于共享單車需求預(yù)測。將季節(jié)性灰色Markov模型的預(yù)測結(jié)果與傳統(tǒng)GM(1,1)模型和SGM(1,1)模型做比較，由于站點較多，選取站點1～4的預(yù)測結(jié)果比較如圖1所示，預(yù)測誤差比較如圖2所示。

表2 季節(jié)性灰色Markov模型預(yù)測結(jié)果

圖1 原始數(shù)據(jù)和3種模型預(yù)測結(jié)果比較Fig.1 Comparison of the original data and the prediction results of the three models

圖2 3種模型預(yù)測結(jié)果的誤差比較Fig.2 Error comparison of prediction results of three models

從圖1和圖2可以看出：季節(jié)性灰色 Markov 模型的預(yù)測結(jié)果具有波動性且更加接近原始數(shù)據(jù)，其預(yù)測誤差在較低水平范圍內(nèi)波動，整體的預(yù)測效果要優(yōu)于傳統(tǒng)GM(1,1)模型和SGM(1,1)模型。

GUROBI是新一代大規(guī)模數(shù)學規(guī)劃優(yōu)化器，可以求解很多線性和非線性的問題。利用GUROBI求解器求解雙層規(guī)劃模型，得到各個站點和調(diào)度區(qū)域分布如圖3所示。

圖3 共享單車站點和調(diào)度區(qū)域分布圖Fig.3 Distribution map of shared bicycle stations and scheduling areas

從圖3可以看出，雙層規(guī)劃模型得出的最優(yōu)解將17個站點劃分為3個區(qū)域，分別設(shè)置調(diào)度中心，可以最大化滿足用戶需求的同時，使調(diào)度成本和調(diào)度時間最優(yōu)。2019年6月24日3個區(qū)域的最優(yōu)調(diào)度路徑和最差調(diào)度路徑的行駛時間和調(diào)度成本比較如表3所示。

從表3可以看出3個區(qū)域的最優(yōu)調(diào)度路徑相比最差調(diào)度路徑分別節(jié)省了23.05%、45.8%和35.19%的行駛時間，節(jié)省了23.15%、46.45%和34.93%的調(diào)度成本。表3所得行駛時間和調(diào)度成本具有比較意義，實際的行駛時間和調(diào)度成本會根據(jù)具體情況有所變化。如果站點增加，行駛時間和調(diào)度成本的優(yōu)化效果會更加明顯。

表3 各區(qū)域調(diào)度路徑的行駛時間和調(diào)度成本比較

3個區(qū)域的最優(yōu)調(diào)度路徑和最差調(diào)度路徑比較如圖4所示。

圖4 各區(qū)域調(diào)度路徑比較Fig.4 Comparison of scheduling routes in various regions

從圖4可以看出，最優(yōu)調(diào)度路徑的路線清晰順暢且沒有線路交叉，最差調(diào)度路徑的路線錯綜復雜且沒有規(guī)律性。在共享單車調(diào)度過程中，應(yīng)盡量避免過多的線路交叉，以節(jié)省調(diào)度時間和調(diào)度成本。

4 結(jié)論

通過對美國紐約市17個Citi Bike共享單車站點的算例分析，得出以下結(jié)論。

(1) 對于具有周期性波動特征的共享單車需求預(yù)測，SGM(1,1)模型比GM(1,1)模型有更好的適應(yīng)性。通過Markov模型修正之后的SGM(1,1)模型的精度有了一定的提高，季節(jié)性灰色Markov模型的預(yù)測效果要明顯優(yōu)于傳統(tǒng)GM(1,1)模型和SGM(1,1)模型，預(yù)測結(jié)果科學合理，可用于實際問題的計算。

(2) 雙層規(guī)劃模型考慮了決策過程中運營商和調(diào)度部門的作用與表現(xiàn)，在調(diào)度成本和調(diào)度時間上為決策者提供決策。利用雙層規(guī)劃模型制定的調(diào)度優(yōu)化方案能確定調(diào)度中心數(shù)量、位置，調(diào)度范圍和調(diào)度路徑，可以在滿足用戶需求的同時使調(diào)度成本和調(diào)度時間最優(yōu)。

基于Markov模型修正殘差的季節(jié)性灰色Markov模型的共享單車需求預(yù)測，以及在此基礎(chǔ)上根據(jù)雙層規(guī)劃模型結(jié)果提出的調(diào)度優(yōu)化方案，可以為共享單車運營部門和交通管理部門提供有效的參考，從而提高共享單車系統(tǒng)的運行效率。