基于Geohash編碼的共享單車分層調(diào)度方法研究

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

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

0 引 言

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

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

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

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

1 調(diào)度需求與調(diào)度方法分析

1.1 調(diào)度需求分析

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

對(duì)騎行的起終點(diǎn)位置采用Geohash地理編碼進(jìn)行網(wǎng)格劃分．其原理為通過二進(jìn)制將一定經(jīng)緯度范圍的區(qū)域進(jìn)行分割，把二維的空間經(jīng)緯度數(shù)據(jù)編碼成字符串，該區(qū)域內(nèi)的點(diǎn)共享一個(gè)編碼．Geohash編碼的位數(shù)越多，則區(qū)域分割的次數(shù)越多，區(qū)域面積越?。煌粩?shù)的Geohash編碼對(duì)應(yīng)的區(qū)域范圍見表1．

表1 不同編碼位數(shù)的區(qū)域范圍 單位：km

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

表2 不同編碼位數(shù)區(qū)域內(nèi)的調(diào)度需求分布 單位：輛

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

1.2 分層調(diào)度方法

傳統(tǒng)的調(diào)度方法為一個(gè)調(diào)度站服務(wù)一定的區(qū)域范圍，通過調(diào)度車將共享單車從一處供大于求的租賃點(diǎn)搬運(yùn)至另一處供小于求的租賃點(diǎn)．傳統(tǒng)的調(diào)度方法僅依賴區(qū)域內(nèi)的調(diào)度無法實(shí)現(xiàn)該區(qū)域的供需平衡，調(diào)度站需容納一定量的共享單車以供調(diào)度，蔣塬銳等[14]基于該問題提出了基于調(diào)度池的調(diào)度方案，但該方案未考慮調(diào)度站的容量限制，調(diào)度站存放的共享單車同樣需調(diào)入或調(diào)出．

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

圖1 分層調(diào)度方案示意圖

2 區(qū)間調(diào)度模型

2.1 VRP理論

在VRP理論基礎(chǔ)上考慮共享單車調(diào)度服務(wù)特性，某一區(qū)域內(nèi)的共享單車的調(diào)度過程見圖2．

圖2 共享單車區(qū)間調(diào)度示意圖

2.2 模型假設(shè)

考慮到實(shí)際調(diào)度場(chǎng)景的復(fù)雜性，為了使調(diào)度問題抽象為數(shù)學(xué)模型且較為真實(shí)的反映圖4中的區(qū)間調(diào)度場(chǎng)景，對(duì)模型做出如下假設(shè).

1) 任意兩個(gè)調(diào)度點(diǎn)間均有道路連通．

2) 所有調(diào)度車均從調(diào)度站出發(fā)且最終返回調(diào)度站，為簡化模型，一輛調(diào)度車只對(duì)每個(gè)調(diào)度點(diǎn)最多訪問一次．

3) 調(diào)度站與調(diào)度點(diǎn)有足夠多的空間可容納一個(gè)周期內(nèi)所需調(diào)入或調(diào)出的共享單車．

4) 以一定時(shí)間段為調(diào)度周期，所有調(diào)度任務(wù)均可在調(diào)度周期內(nèi)完成．

2.3 模型建立

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

以時(shí)間T為調(diào)度周期，調(diào)度點(diǎn)Vn在調(diào)度周期內(nèi)的調(diào)度需求為dVn，當(dāng)dVn<0時(shí)，表示調(diào)度點(diǎn)的共享單車為過飽和狀態(tài)，需調(diào)出|dVn|輛共享單車；當(dāng)dVn>0時(shí)，則需調(diào)入dVn輛共享單車．在分層調(diào)度方案中，調(diào)度總站與調(diào)度分站的調(diào)度需求取決于底層調(diào)度區(qū)的調(diào)度點(diǎn)的調(diào)度需求，對(duì)于調(diào)度點(diǎn)Vn，以時(shí)間T為調(diào)度周期時(shí)，其調(diào)度需求的計(jì)算方法為

(1)

式中：drent(t)、dreturn(t)分別為調(diào)度點(diǎn)Vn所在區(qū)域在時(shí)刻t的用戶借車量與還車量．

對(duì)于共享單車運(yùn)營企業(yè)，其在執(zhí)行調(diào)度方案時(shí)首要考慮的為調(diào)度成本，包括調(diào)度車的運(yùn)行成本和調(diào)度員的作業(yè)成本兩部分．計(jì)算方法為

(2)

(3)

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

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

(4)

(5)

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

在上述模型假設(shè)的基礎(chǔ)上，以廣義的調(diào)度成本最小為目標(biāo)，建立模型.

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)為調(diào)度車Kn離開調(diào)度站時(shí)的初始裝載量；x(ij,Kn)為二元變量．

約束條件(7)～(10)針對(duì)模型的假設(shè)2，式(7)～(8)為每個(gè)調(diào)度點(diǎn)最多被服務(wù)一次(允許不被服務(wù))；式(9)為當(dāng)調(diào)度車不經(jīng)過站點(diǎn)Vn時(shí)，其調(diào)入或調(diào)出的車輛數(shù)為0；式(10)為調(diào)度車的起終點(diǎn)為調(diào)度站；式(11)為調(diào)度車在任意調(diào)度點(diǎn)作業(yè)時(shí)，其裝載的共享單車數(shù)量滿足最大裝載量的約束；式(12)為調(diào)度車在任意調(diào)度點(diǎn)作業(yè)時(shí)，其可卸載的共享單車數(shù)量滿足其當(dāng)前裝載量的約束．

3 案例分析

以北京市內(nèi)Geohash編碼為wx4eh的區(qū)域?yàn)橹袑诱{(diào)度區(qū)，采用6位編碼將該區(qū)域劃分為32個(gè)底層調(diào)度區(qū)，見圖3a)．采用均值漂移算法對(duì)騎行起訖點(diǎn)進(jìn)行聚類處理，確定各底層調(diào)度區(qū)的用戶騎行聚集位置，即為調(diào)度點(diǎn)，見圖3b)．

圖3 調(diào)度圖

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

圖4 一周內(nèi)的共享單車借車與還車量變化

在此調(diào)度周期下，以5月10日為例，根據(jù)騎行的歷史訂單數(shù)據(jù)，各調(diào)度點(diǎn)的調(diào)度需求見表3．在實(shí)際進(jìn)行調(diào)度作業(yè)時(shí)，由于共享單車需求量的可預(yù)測(cè)性，可采用機(jī)器學(xué)習(xí)等方法對(duì)調(diào)度需求進(jìn)行預(yù)測(cè)，以此為依據(jù)制定調(diào)度方案．

表3 各調(diào)度點(diǎn)的調(diào)度需求 單位：輛

假定調(diào)度站V0位于區(qū)域wx4ehk內(nèi)，根據(jù)各調(diào)度點(diǎn)的具體位置和路網(wǎng)分布，距離矩陣見表4．

表4 距離矩陣 單位：km

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

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

考慮到在規(guī)劃調(diào)度方案時(shí)，若以整個(gè)北京市為調(diào)度服務(wù)區(qū)，區(qū)域內(nèi)站點(diǎn)數(shù)量龐大，對(duì)算法的求解速度具有較高的要求．因此，采用爬山性較強(qiáng)、搜索速度快的禁忌搜索算法(tabu search, TS)對(duì)算例進(jìn)行求解，算法的基本流程見圖5．

圖5 TS算法流程

以最短路為初始解，當(dāng)調(diào)度車的數(shù)量分別為1、2、3、4輛時(shí)，最優(yōu)解見表5.

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

表5 最優(yōu)調(diào)度路徑

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

圖6 不同調(diào)度模型的收斂速度對(duì)比結(jié)果

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

4 結(jié) 束 語

基于VRP理論，針對(duì)傳統(tǒng)調(diào)度方法忽略了調(diào)度區(qū)的整體供需失衡的不足，提出了一種分層調(diào)度策略．通過Geohash地理編碼和用戶騎行訂單數(shù)據(jù)分析，以編碼位數(shù)為4、5、6將共享單車調(diào)度服務(wù)區(qū)劃分為上、中、底三層，每層調(diào)度區(qū)內(nèi)設(shè)有調(diào)度站和對(duì)應(yīng)的調(diào)度點(diǎn)，并建立區(qū)間調(diào)度模型規(guī)劃每層調(diào)度區(qū)內(nèi)的調(diào)度路徑．

以Geohash編碼為wx4eh的區(qū)域?yàn)閰^(qū)間調(diào)度案例，以24h為調(diào)度周期，通過騎行歷史訂單數(shù)據(jù)確定調(diào)度需求，采用禁忌搜索算法求解出不同初始調(diào)度車數(shù)量下的最優(yōu)調(diào)度路徑．案例分析表明：所提出的分層調(diào)度方法和區(qū)間調(diào)度模型可有效的對(duì)共享單車的調(diào)度方案進(jìn)行規(guī)劃，對(duì)比已有的分層調(diào)度方案，求解過程的收斂速度更快，模型時(shí)間復(fù)雜度較低．

由于存在高峰期的調(diào)度點(diǎn)的容量小于用戶需求的情形，需針對(duì)不同調(diào)度點(diǎn)設(shè)置不同的調(diào)度周期，待下階段的研究進(jìn)一步展開．