基于Geohash編碼的共享單車分層調度方法研究

李 福 徐良杰 羅劍萍* 朱然博 劉 靜

(武漢理工大學交通與物流工程學院1) 武漢 430063) (湖北文理學院汽車與交通工程學院2) 襄陽 441053)

0 引 言

共享單車解決了公共交通難以實現“最后一公里”末端需求的弊端，近年來受到公眾的青睞得以快速發展．相比有樁停放的公共自行車，共享單車的借還車不受場地限制，完全由用戶的出行行為驅動．另一方面，由于不同區域的用地性質的不同而產生的出行吸引量與發生量的差異，造成了共享單車的空間分布不均．制定科學合理的調度策略有助于解決共享單車的供需失衡問題，提高共享單車的資源利用效率．

共享單車與公共自行車的調度問題均可轉化成車輛路徑問題(vehicle routing problem, VRP)．在調度方法上，主要為傳統的庫存-路徑模型，即一個調度站服務若干租賃點，在各個租賃點間尋找最優調度路線．Bell等[1-2]均以運營商的總調度成本為目標對調度路徑進行尋優；Liu等[3-4]以出行者的廣義出行成本為目標；Liang等[5]以提高用戶的滿意度為目標；Gao等[6-7]以總調度距離最小為目標；于德新等[8]以成本最小和投放率最高為目標進行多目標優化；Yang等[9]以成本最小和運轉量最大為目標；李興華等[10]以用戶需求的損失最小、用戶出行時間最短為目標，建立雙層規劃模型．

在實際的調度作業中，由于單個調度站的服務范圍的限制，經常會劃分不同的調度區分別進行調度作業，從而提出分層調度策略．徐建閩等[11]根據公共自行車的時空分布特性，將距離較近且調度需求的時空分布類型相似的站點設為同一層；關宏志等[12]將調度車分為兩類，采用大型調度車收集調度需求密集站點，采用小型車收集小區內分散站點，進行上下兩層調度．由于分層調度方法過于主觀化，分區依據不明確，實際應用時難以實施．

傳統的調度方法將調度站所服務的區域內的整體供需視為平衡狀態，只考慮區域內的調度路徑，忽略了各區域間的車輛流通．當前共享單車調度問題的研究大多集中于數學建模的過程，忽略了基于實際數據進行調度需求分析．本文基于北京市摩拜單車的用戶騎行訂單數據，分析不同區域范圍下的共享單車的調度需求，采用Geohash地理編碼劃分不同層級的調度站的服務范圍，進行分層調度．

1 調度需求與調度方法分析

1.1 調度需求分析

共享單車的運營時空數據可較好地反映用戶的騎行時空特征[13]，從而挖掘出共享單車的借還車需求量與調度需求量的空間分布．選用北京市的摩拜單車的用戶騎行歷史訂單數據，分析共享單車的調度需求．原始數據集包含共享單車用戶的訂單號、共享單車ID、用戶ID、單車類型、騎行的起始時間、騎行的起點和終點位置．數據樣本集涵蓋了兩周的3 214 096份摩拜單車用戶出行訂單，包含485 465輛共享單車和349 693個用戶．

對騎行的起終點位置采用Geohash地理編碼進行網格劃分．其原理為通過二進制將一定經緯度范圍的區域進行分割，把二維的空間經緯度數據編碼成字符串，該區域內的點共享一個編碼．Geohash編碼的位數越多，則區域分割的次數越多，區域面積越小．不同位數的Geohash編碼對應的區域范圍見表1．

表1 不同編碼位數的區域范圍 單位：km

利用Python中的pandas工具包對原始數據集進行處理，刪除異常數據后，以1 h為時間間隔，累計各個編碼區域內的用戶的借車量與還車量．當某區域一段時間的用戶借車量與還車量之間存在差值時，則該區域存在著調度需求．分別以編碼位數為4、5、6、7對北京市進行區域劃分，統計不同編碼位數區域內的累計借還車差值(絕對值)分布，見表2．

表2 不同編碼位數區域內的調度需求分布 單位：輛

由表2可知:以編碼位數為4、5、6、7對北京市進行區域劃分時，每塊區域內的平均調度需求分別為235、57、21、3．隨著劃分區域的增大，區域內的調度需求增加，但單位面積內的調度需求大大減少，即區域內的共享單車的借車與還車需求相對更加平衡．

1.2 分層調度方法

傳統的調度方法為一個調度站服務一定的區域范圍，通過調度車將共享單車從一處供大于求的租賃點搬運至另一處供小于求的租賃點．傳統的調度方法僅依賴區域內的調度無法實現該區域的供需平衡，調度站需容納一定量的共享單車以供調度，蔣塬銳等[14]基于該問題提出了基于調度池的調度方案，但該方案未考慮調度站的容量限制，調度站存放的共享單車同樣需調入或調出．

為此，提出一種新的適用于共享單車的分層調度方案，上層調度區:39.1 km×19.5 km,中層調度區:4.89 km×4.89 km,底層調度區:1.22 km×0.61 km,見圖1．

圖1 分層調度方案示意圖

2 區間調度模型

2.1 VRP理論

在VRP理論基礎上考慮共享單車調度服務特性，某一區域內的共享單車的調度過程見圖2．

圖2 共享單車區間調度示意圖

2.2 模型假設

考慮到實際調度場景的復雜性，為了使調度問題抽象為數學模型且較為真實的反映圖4中的區間調度場景，對模型做出如下假設.

1) 任意兩個調度點間均有道路連通．

2) 所有調度車均從調度站出發且最終返回調度站，為簡化模型，一輛調度車只對每個調度點最多訪問一次．

3) 調度站與調度點有足夠多的空間可容納一個周期內所需調入或調出的共享單車．

4) 以一定時間段為調度周期，所有調度任務均可在調度周期內完成．

2.3 模型建立

對于某層級的調度區，存在一個調度站點集合V={V0,V1,…,Vn}，其中V0為調度站，Vn為其負責的n個調度點．調度站點與站點間的道路構成網絡G，G=(V,A)，其中A為調度點間的道路的集合，A={(i,j);i,j∈V,i≠j}，調度點Vi和Vj間的最短運輸距離為lij．調度站內的調度車用集合K表示，K={K1,K2,…,Kn}，每輛調度車的最大可裝載q輛共享單車．

以時間T為調度周期，調度點Vn在調度周期內的調度需求為dVn，當dVn<0時，表示調度點的共享單車為過飽和狀態，需調出|dVn|輛共享單車；當dVn>0時，則需調入dVn輛共享單車．在分層調度方案中，調度總站與調度分站的調度需求取決于底層調度區的調度點的調度需求，對于調度點Vn，以時間T為調度周期時，其調度需求的計算方法為

(1)

式中：drent(t)、dreturn(t)分別為調度點Vn所在區域在時刻t的用戶借車量與還車量．

對于共享單車運營企業，其在執行調度方案時首要考慮的為調度成本，包括調度車的運行成本和調度員的作業成本兩部分．計算方法為

(2)

(3)

式中：Cveh、Clab分別為調度車的運營成本和工人的作業成本；ck、cf分別為調度車的折舊成本和每公里的油耗成本；ct、cv分別為調度員的單位時間薪資和每輛共享單車的作業薪資；v為調度車的平均行駛車速；drVn為調度點Vn在調度作業時的實際調入或調出車輛數；x(ij,Kn)為二元變量，其值為1時表示調度車Kn經過調度點Vi和Vj，反之x(ij,Kn)=0．

由式(2)～(3)可知:調度車的運營成本和工人的作業成本均與調度量呈正相關，即調度量越小，調度成本越低．考慮到實際調度量的下限值無法進行有效約束，為保證調度方案的正常執行，設定當某個調度點的調度需求未被滿足時，存在著懲罰成本．懲罰成本定義為：對于共享單車系統，當借車需求未滿足或車輛閑置產生的收益下降與資源閑置浪費成本，具體量化方式為

(4)

(5)

式中：p1、p2分別為借車需求未被滿足和車輛閑置時，每輛共享單車的懲罰成本．

在上述模型假設的基礎上，以廣義的調度成本最小為目標，建立模型.

minC=Cveh+Clab+Cpun

(6)

s.t.

(7)

(8)

(9)

(10)

?Kn∈K,?Vn∈V

(11)

?Kn∈K,?Vn∈V

(12)

x(ij,Kn)∈{0,1},?Kn∈K,(i,j)∈V

(13)

式中：q(Kn,0)為調度車Kn離開調度站時的初始裝載量；x(ij,Kn)為二元變量．

約束條件(7)～(10)針對模型的假設2，式(7)～(8)為每個調度點最多被服務一次(允許不被服務)；式(9)為當調度車不經過站點Vn時，其調入或調出的車輛數為0；式(10)為調度車的起終點為調度站；式(11)為調度車在任意調度點作業時，其裝載的共享單車數量滿足最大裝載量的約束；式(12)為調度車在任意調度點作業時，其可卸載的共享單車數量滿足其當前裝載量的約束．

3 案例分析

以北京市內Geohash編碼為wx4eh的區域為中層調度區，采用6位編碼將該區域劃分為32個底層調度區，見圖3a)．采用均值漂移算法對騎行起訖點進行聚類處理，確定各底層調度區的用戶騎行聚集位置，即為調度點，見圖3b)．

圖3 調度圖

隨后確定調度方案的執行周期．圖4為Geohash編碼為wx4eh在5月10—16日一周內的每小時的借車與還車量的差值的變化過程．由圖4可知:當調度方案的執行周期小于24 h時，需在1 d內多次執行調度；調度周期過長則會造成每個周期的調度任務量多大，調度站難以容納過多的共享單車，因此選取24 h為調度周期較為合適．

圖4 一周內的共享單車借車與還車量變化

在此調度周期下，以5月10日為例，根據騎行的歷史訂單數據，各調度點的調度需求見表3．在實際進行調度作業時，由于共享單車需求量的可預測性，可采用機器學習等方法對調度需求進行預測，以此為依據制定調度方案．

表3 各調度點的調度需求 單位：輛

假定調度站V0位于區域wx4ehk內，根據各調度點的具體位置和路網分布，距離矩陣見表4．

表4 距離矩陣 單位：km

設置區間調度模型的相關參數：設調度車的最大可裝載量90輛，平均行駛速度為30 km/h，油耗成本為0.72元/km，每個周期內的折舊成本為13元．假定懲罰成本中，p1、p2分別為1.5、-1.0元/輛．根據調度員的行業薪資水平，確定調度員的單位時間薪資和每輛共享單車的作業薪資，對區間調度模型進行求解．

相比一般的最短路徑規劃問題，共享單車的調度路徑規劃涉及每個站點的調入與調出量的決策，由于調度車的容量的限制，每個站點的決策將對下一個站點的決策產生影響．Ho等[15]早已證明共享單車的調度路徑規劃屬于NP-hard問題，常采用啟發式算法對該類問題進行求解．

考慮到在規劃調度方案時，若以整個北京市為調度服務區，區域內站點數量龐大，對算法的求解速度具有較高的要求．因此，采用爬山性較強、搜索速度快的禁忌搜索算法(tabu search, TS)對算例進行求解，算法的基本流程見圖5．

圖5 TS算法流程

以最短路為初始解，當調度車的數量分別為1、2、3、4輛時，最優解見表5.

由表5可知:對于Geohash編碼為wx4eh的區域，當調度車的總量不超過3輛時，由于在調度成本中引入了懲罰成本，隨著調度車的增加，區域內的調度需求的滿足程度增加，調度成本隨著懲罰成本的降低而降低．由于3輛調度車的初始裝載量可滿足該區域的調度需求，因此，當調度車為4輛時，隨著調度車的折舊成本和作業成本的增加，調度成本開始變大．在本算例的假設情形下，wx4eh區域內設置3輛調度車，以上表的最優路徑執行調度的成本最低．同樣的，對于上層調度區wx4e，采用區間調度模型規劃出調度車在各中層調度區間的調度路徑，從而實現對整個北京市的摩拜單車的調度作業．

表5 最優調度路徑

為進一步驗證本文方法的可靠性，同樣的采用TS算法，針對上述案例，分別對文獻[8]中提出的分層調度模型與本文模型的求解迭代過程進行對比(調度車設為3輛)，結果見圖6．

圖6 不同調度模型的收斂速度對比結果

由于本文目標函數中調度成本與文獻[8]的衡量指標的不同，只比較兩者的收斂速度．由圖6可知:本文提出的共享單車分層調度方法在迭代50次時開始進化收斂，收斂速度顯著優于文獻[8]所提出的模型．由此表明，以同樣的算法進行求解時，本文所提出的調度模型的時間復雜度較低，適用于實際調度應用．

4 結 束 語

基于VRP理論，針對傳統調度方法忽略了調度區的整體供需失衡的不足，提出了一種分層調度策略．通過Geohash地理編碼和用戶騎行訂單數據分析，以編碼位數為4、5、6將共享單車調度服務區劃分為上、中、底三層，每層調度區內設有調度站和對應的調度點，并建立區間調度模型規劃每層調度區內的調度路徑．

以Geohash編碼為wx4eh的區域為區間調度案例，以24h為調度周期，通過騎行歷史訂單數據確定調度需求，采用禁忌搜索算法求解出不同初始調度車數量下的最優調度路徑．案例分析表明：所提出的分層調度方法和區間調度模型可有效的對共享單車的調度方案進行規劃，對比已有的分層調度方案，求解過程的收斂速度更快，模型時間復雜度較低．

由于存在高峰期的調度點的容量小于用戶需求的情形，需針對不同調度點設置不同的調度周期，待下階段的研究進一步展開．