城市共享單車的動態(tài)調(diào)度策略

謝青成　毛嘉莉　劉婷

摘要：為滿足城市共享單車用戶的用車需求，提高共享單車的使用效率，結(jié)合路況信息提出了一個兩階段的共享單車實時投放與調(diào)度框架：在離線建模階段，基于歷史的短程出租車軌跡數(shù)據(jù)聚類，使用區(qū)域提取技術(shù)（Regional Extraction Technique，RET）獲取不同時段的城市熱門用車區(qū)域、用車頻次與行程結(jié)束后的熱門停車區(qū)域及其停車頻次;在線調(diào)度階段，建立共享單車的實時調(diào)度優(yōu)化模型（Real-time Optimization Model，ROM），根據(jù)下一時段的熱門用車區(qū)域，搜索當(dāng)前時段內(nèi)距離其較近的k近鄰單車停車區(qū)域，并結(jié)合實時路況為調(diào)度車推薦前k條路況良好的行車線路.出租車軌跡數(shù)據(jù)集上的實驗表明，所提的調(diào)度策略相較于傳統(tǒng)的自行車調(diào)度策略具有較好的有效性.

關(guān)鍵詞：動態(tài)調(diào)度;城市共享單車;用車區(qū)域;停車區(qū)域; 實時路況

中圖分類號：TP311

文獻標(biāo)志碼：A

DOI： 10.3969/j.issn.1000-5641.2019.06.009

0 引言

市民出行最后l km問題一直是困擾城市交通出行的難點，近幾年，隨著摩拜、OFO等共享單車企業(yè)的出現(xiàn)，這一問題一度得到了緩解.然而，伴隨著共享單車在中國各大城市的廣泛應(yīng)用，在緩解城市交通壓力與方便人們出行的同時，共享單車的亂停亂放在很大程度上也影響了城市的正常交通秩序.共享單車大多被投放于POI（Point of Interest）（比如地鐵站、公交站、電影院、大型購物場所、體育場、火車站、大型居民區(qū)等）附近，忽略了POI區(qū)域以外的其他熱門用車區(qū)域，如因交通意外、臨時道路封鎖導(dǎo)致機動車無法正常通行的道路區(qū)域等，此外，不同的日期（如工作日/節(jié)假日）、同一天中不同的時段，以及不同的天氣狀況都會影響用戶的用車需求.普遍采用的共享單車投放策略由于忽略了這些外部因素，直接導(dǎo)致了大量單車閑置在沒有用車需求的POI附近，而大部分用戶的單車使用需求卻無法滿足，這與共享單車最早的投放初衷相違背，

隨著移動設(shè)備的廣泛應(yīng)用和位置采集技術(shù)的蓬勃發(fā)展，出租車作為一種非常重要的城市出行工具，廣泛地長時間分布于城市路網(wǎng)中，出租車車上裝備的GPS設(shè)備，以一定的時間間隔不斷地向出租車信息管理中心發(fā)送其實時的位置信息，包括出租車ID、載客狀態(tài)、時間戳、經(jīng)緯度坐標(biāo)、速度等數(shù)據(jù)，通過對出租車歷史軌跡數(shù)據(jù)的挖掘分析，可以有效提取出租車的移動行為模式，進而洞察城市的交通出行規(guī)律.已有大量學(xué)者基于出租車歷史軌跡數(shù)據(jù)，對載客熱門區(qū)域提取[1-2]、線路規(guī)劃[3-4]等問題進行了較為深入的研究.鑒于共享單車企業(yè)普遍使用POI附近投放單車策略而忽略不同日期、不同時段單車使用需求的差異性，導(dǎo)致共享單車的低效使用，本文考慮使用短程的出租車軌跡數(shù)據(jù)（出行距離在3 km以下），分時段獲取城市不同區(qū)域的熱門短途出行需求.

目前國內(nèi)各大中城市的共享單車數(shù)量已趨于飽和，基于有限數(shù)量的共享單車資源，要確保滿足各時段熱門出行區(qū)域的用車需求，亟需設(shè)計一個共享單車的實時投放和調(diào)度策略f含調(diào)度車的行車線路），這實質(zhì)上涉及了兩個子問題：第一，分時段提取城市熱門短程出行區(qū)域;第二，結(jié)合實時路況信息的共享單車動態(tài)調(diào)度.這兩個問題所面臨的關(guān)鍵挑戰(zhàn)在于：①預(yù)估不同時段內(nèi)的用車需求變化情況，這需要考慮諸多其他外部因素影響，比如不同的日期f工作日/節(jié)假日）、同一天中不同的時段，以及不同的天氣狀況;②預(yù)估不同時段城市各路段的共享單車停車情況;③合理規(guī)劃單車調(diào)度車輛的行車線路，

近年來，國內(nèi)外不少學(xué)者對城市公共自行車的需求預(yù)測和調(diào)度策略進行了深入探討，其中預(yù)估用車需求的研究大多基于歷史用車需求均值或歷史用車記錄數(shù)據(jù).Eoin等研究了城市高峰時段單車使用情況[5]，通過分析城市公共自行車系統(tǒng)數(shù)據(jù)，預(yù)估各駐車站點單車的用車頻次;Dimitrios等通過識別影響單車使用的因素以及城市公共自行車的流動模式，進而預(yù)測單車的用車需求[6]; Cheng等通過對具有時間相關(guān)的PCTMC（Population ContinuousTime Markov Chain）模型進行分析[7]研究了駐車站點的用車頻次預(yù)估問題;Chen等提出了一種半監(jiān)督特征選擇法預(yù)測用戶的出行需求[8]，即基于歷史用車次數(shù)的特征選擇法精準(zhǔn)地預(yù)估用車頻次;Divya等基于出租車數(shù)據(jù)，提出了一種多因素回歸模型預(yù)測城市公共自行車的用車需求[9]，但里面混有大量長途出租車數(shù)據(jù)，導(dǎo)致短程用車需求預(yù)估不精確.

城市公共自行車的調(diào)度策略研究大多數(shù)采用聚類建?；驍?shù)學(xué)算法建模.比如Liu等提出的自適應(yīng)能力約束的K中心聚類AdaCCKC（Adaptive Capacity Constained K-centerClustering）算法[10]，將多車輛行車線路問題簡化為內(nèi)部集群只需1輛調(diào)度車的行車線路問題;Fabio等提出的基于迭代的局部搜索ILS（Iterated Local Search）的啟發(fā)式算法[11]，篩選滿足有用車需求的駐車站點的最低成本行車路線.但這些研究者們都未考慮實時路況對調(diào)度效率的影響.

不同于城市公共自行車，摩拜、OFO等共享單車雖然和城市公共自行車在預(yù)測用車需求和調(diào)度優(yōu)化上有相同之處，但共享單車沒有固定的駐車站點，它可以隨取隨放，這就衍生出了共享單車的投放問題、停車區(qū)域的提取問題和單車動態(tài)調(diào)度問題，迄今為止還未有研究試圖解決上述問題.基于此，本文構(gòu)建了一個兩階段共享單車的實時投放及動態(tài)調(diào)度框架，包括離線建模和在線調(diào)度：在離線建模階段，采用區(qū)域提取技術(shù)，基于短程的出租車軌跡數(shù)據(jù)，實時獲取不同日期（工作日/節(jié)假日）各時段內(nèi)的城市熱門用車區(qū)域和共享單車停車區(qū)域，所獲得的熱門區(qū)域不僅能準(zhǔn)確預(yù)估單車投放區(qū)域，還能預(yù)估各時段單車的停車情況，為后續(xù)單車調(diào)度提供可靠的數(shù)據(jù)支持;在線調(diào)度部分，旨在解決單車的動態(tài)調(diào)度問題，涉及調(diào)度區(qū)域與調(diào)度效率.如前所述，城市公共自行車由于有固定的駐車站點，駐車站點的車儲量能滿足ld的需求，所以城市公共自行車的調(diào)度效率要求不高.然而，共享單車由于用車需求的動態(tài)變化，要確保有限數(shù)量的單車資源得到合理使用，必須根據(jù)各時段的用車需求設(shè)計更為高效的調(diào)度策略.具體來說，先確定調(diào)度區(qū)域，再基于用車區(qū)域的用車比例從k近鄰?fù)＼噮^(qū)域中確定待調(diào)度的停車區(qū)域，在此基礎(chǔ)上，結(jié)合實時交通狀況為共享單車調(diào)度車推薦top-k條路況優(yōu)選的調(diào)度線路.本文的主要貢獻如下.

（1）構(gòu)建并實施了一個兩階段的共享單車的實時投放與調(diào)度框架：①離線建模部分，提出了區(qū)域提取模型，采用基于DBSCAN（Density-Based Spatial Clustering of Applicationswith Noise）分時段最小值支持技術(shù)的聚類算法（RET算法），對短程的出租車歷史軌跡進行聚類，提取各時段內(nèi)城市熱門用車區(qū)域及其用車頻次、共享單車停車區(qū)域及其停車頻次;②在線調(diào)度部分，提出了結(jié)合實時交通狀況的調(diào)度優(yōu)化模型（ROM方法），根據(jù)用車比例和k近鄰?fù)＼噮^(qū)域的停車比例，確定待調(diào)度的停車區(qū)域，并結(jié)合實時路況為共享單車調(diào)度車推薦前k條路況優(yōu)選的行車線路，最終以具有較短的調(diào)度車行車里程和行駛時間的路線完成實時調(diào)度，確保滿足各時段內(nèi)單車的用車需求.

（2）在出租車軌跡數(shù)據(jù)集上進行了大量對比實驗.在預(yù)估用車和停車頻次上與算法MSI（Multi-Similarity-based Inference）[131、MSEWk（Multi-Similarity-Equally-WeightedkNN）[10]、IPPI（Inhomogeneous Poisson Process Inference）[12]、HM（Historical Mean）等進行對比，同時與NNIA（Nearest Neighbor Insertion Algorithm）[161、GA（Genetic Algorithm）[17]等進行調(diào)度效率的對比.對比實驗結(jié)果表明，本文所提方案在預(yù)估用車、停車頻次的精確度以及調(diào)度效率上均優(yōu)于其他算法，

本文的第1節(jié)介紹用車需求預(yù)估、共享單車的停車情況預(yù)估及調(diào)度車的行車線路推薦的相關(guān)工作;第2節(jié)對本文相關(guān)概念進行形式化定義;第3節(jié)介紹兩階段框架;第4節(jié)介紹實驗分析;第5節(jié)總結(jié)全文，

1 相關(guān)工作

1.1 共享單車用車需求及停車情況預(yù)估

共享單車用車需求預(yù)估包括熱門用車區(qū)域的位置預(yù)估和各熱門用車區(qū)域的用車頻次預(yù)估.根據(jù)用車需求預(yù)估，確定共享單車的投放區(qū)域和每個投放區(qū)域的投放量.共享單車停車情況預(yù)估包括共享單車停車區(qū)域的位置預(yù)估和每個停車區(qū)域的單車數(shù)量預(yù)估.

關(guān)于共享單車用車區(qū)域和停車區(qū)域的位置研究，由于共享單車隨取隨放、沒有固定駐車站點等特點，本文使用與共享單車服務(wù)直接或間接相關(guān)的各類數(shù)據(jù)來達到預(yù)測城市熱門用車區(qū)域和停車區(qū)域位置的效果，使用出租車的軌跡數(shù)據(jù)獲取熱門載客區(qū)域[1-2]，這能為用車區(qū)域和停車區(qū)域位置預(yù)測提供依據(jù).關(guān)于現(xiàn)有預(yù)估用車頻次和停車頻次的研究，大部分是基于歷史記錄數(shù)據(jù)的.Alvarez-Valde等提出了IPPI算法[12]，通過非齊次Poisson過程預(yù)測用車和停車頻次，根據(jù)歷史記錄預(yù)測用車和停車比例;Chen等提出了HM算法[8]，將有用車需求的歷史記錄數(shù)據(jù)作為用車和停車頻次的預(yù)測值.除此之外，還有考慮多影響因素建模以提高用車和停車頻次的預(yù)估精度，如，Li等提出的MSI算法考慮了天氣、溫度、風(fēng)速與時間的相似性[13]，似性函數(shù)是這3個相似性的乘法，但這幾個因素的權(quán)重沒有被研究;Liu等提出的MSEWk算法是對影響需求預(yù)測的不同因素采取相同的權(quán)值，運用混合高斯算法來預(yù)測需求[10].

以上關(guān)于單車用車需求及停車情況預(yù)估的研究，雖能提高用車頻次及停車頻次預(yù)估精度，但都缺乏實時且精確度較高的用車需求和停車情況預(yù)估.

1.2 調(diào)度車的行車線路推薦

關(guān)于行車線路的研究大部分是通過對用車區(qū)域和停車區(qū)域進行數(shù)學(xué)建模.Fabio等提出的基于迭代的局部搜索的啟發(fā)式算法[11]，是通過一條最優(yōu)的線路來完成所有調(diào)度，但僅考慮了每天單車使用空閑完成調(diào)度，并未考慮各時段內(nèi)用車需求的差異性;Christian等提出的混合整數(shù)線性規(guī)劃方法[14]，但未考慮實時路況，因此調(diào)度效率較低;Liu等運用帶約束的K中心聚類（AdaCCKC）算法對用車區(qū)域和單車分布區(qū)域進行聚類，將大型多車輛線路問題簡化為各簇內(nèi)駐車站點間的線路選擇問題[10]，相較于傳統(tǒng)的調(diào)度策略有一定提升，但仍缺乏實時且快速的調(diào)度.

上述研究未考慮日期、時段與實時路況對單車用車需求的影響，進而導(dǎo)致用車需求的預(yù)估準(zhǔn)確率較低.鑒于此，本文主要研究了共享單車用車需求預(yù)估、停車情況預(yù)估和調(diào)度車的行車線路等問題.具體地說，本文首先提出RET算法，基于短程出租車的軌跡數(shù)據(jù)，預(yù)估各時段的熱門交通出行需求及城市各路段的共享單車停車情況;再運用調(diào)度優(yōu)化模型ROM方法，動態(tài)評測行車里程及所需時長，從而合理規(guī)劃調(diào)度車的行車線路.

2 概念定義

不同于目前的共享單車投放和調(diào)度策略，本文不僅考慮用車區(qū)域?qū)崟r變化情況，還對用車區(qū)域進行k近鄰?fù)＼噮^(qū)域推薦，再結(jié)合實時路況對調(diào)度車進行top-k行車線路推薦，以減少調(diào)度車行車里程及所需時長.

3 總體框架

本文構(gòu)建了一個兩階段的城市共享單車的動態(tài)調(diào)度框架，總體框架如圖1所示.整體框架分為離線建模階段和在線調(diào)度階段.在離線建模階段，首先對歷史軌跡使用地圖匹配技術(shù)結(jié)合路網(wǎng)數(shù)據(jù)將有序路段的結(jié)點序列映射到真實路段上;然后對軌跡數(shù)據(jù)進行預(yù)處理，包括去除有損數(shù)據(jù)，將用車點和停車點的數(shù)據(jù)分別提取出來，分別對用車點數(shù)據(jù)和停車點數(shù)據(jù)進行分時段基于最小閡值支持的聚類，實現(xiàn)各時段用車需求和行程結(jié)束停車區(qū)域的提取.基于最小閾值支持的聚類，是指用車需求頻次和停車頻次必須達到一定閾值MinPts才能被視為用車區(qū)域和停車區(qū)域（詳見定義7、定義9）.聚類技術(shù)采用基于密度聚類（DBSCAN）方法，該方法適于任意形狀的軌跡數(shù)據(jù)聚類并能進一步去噪.在區(qū)域提取的過程中，使用實時軌跡對其進行增量更新，確保用車區(qū)域和停車區(qū)域提取的精準(zhǔn)性.在線調(diào)度階段，首先獲取當(dāng)前用車區(qū)域的位置信息和所屬時段，搜索距離用車區(qū)域最近的前一時段的k近鄰?fù)＼噮^(qū)域，并根據(jù)用車比例和停車比例在初始提取的top-k鄰近停車區(qū)域中選取最終調(diào)度的停車區(qū)域，同時結(jié)合當(dāng)前時段出租車軌跡流完成對各路段的交通擁塞情況的評測;然后根據(jù)各線路擁堵比例對每個最終調(diào)度的停車區(qū)域到用車區(qū)域之間的線路進行評測排序，獲取道路暢通的線路，實現(xiàn)對調(diào)度車的top-k行車線路的推薦.

3.1 離線建模

離線建模主要考慮區(qū)域提取模型。

考慮工作日、節(jié)假日，以及l(fā) d中的不同時段對用車區(qū)域和停車區(qū)域的影響，本文將出租車歷史軌跡劃分為工作日以及節(jié)假日兩個部分，并將ld分為12個時段{00：00～02：00，02：00～04：00，04：00～06：00，…，20：00～22：00，22：00～24：00），采用RET算法進行聚類，完成對不同時段內(nèi)用車/停車區(qū)域的提取.

用車區(qū)域提取.用車區(qū)域為在某個時段內(nèi)發(fā)生用車需求較為密集的區(qū)域（定義7）.這些區(qū)域通常具有特定的人群移動規(guī)律和功能特征，如受交通意外影響的出行區(qū)域、一個大型商業(yè)區(qū)、學(xué)校、旅游景點等.鑒于該區(qū)域的用車需求與所在日期/時段的緊密聯(lián)系，因此本文考慮獲取不同時段內(nèi)用車密度較大的區(qū)域.在現(xiàn)有的用車區(qū)域預(yù)測研究中，無法及時洞察用車區(qū)域的動態(tài)變化，本文則通過RET算法準(zhǔn)確且實時地發(fā)現(xiàn)了用車區(qū)域.

行程結(jié)束停車區(qū)域提取.停車區(qū)域為在某個時段內(nèi)發(fā)生停車事件較為密集的區(qū)域（定義9），即在該區(qū)域停車頻次比較大，且停放的單車數(shù)量也比較大.這些區(qū)域具有時段屬性，可能在火車站、電影院、公交站等地方，也可能在一些臨時的突發(fā)區(qū)域.本文通過RET算法實時且準(zhǔn)確地發(fā)現(xiàn)了停車區(qū)域，并在后續(xù)工作中會將這些停車區(qū)域的單車調(diào)度至下一時段的用車區(qū)域，確保了人們的用車需求，并從一定程度上緩解了共享單車的亂停亂放現(xiàn)象，

本文根據(jù)出租車軌跡數(shù)據(jù)提取用車和停車區(qū)域數(shù)據(jù)，考慮如下：鑒于共享單車解決最后1 km的交通問題，本文從出租車行程不超過3 km的歷史軌跡數(shù)據(jù)中提取由空載狀態(tài)跳轉(zhuǎn)為載客狀態(tài)的GPS樣本點，并將其視為用車點;將載客狀態(tài)跳轉(zhuǎn)為空載狀態(tài)的GPS位置點視為停車點.在提取用車區(qū)域與停車區(qū)域時，本文基于廣泛采用的軌跡聚類算法DBSCAN提出了RET算法.關(guān)于DBSCAN算法的重要參數(shù)r spatio和MinPts（r spatio表示空間維度的度量半徑，MinPts表示形成簇所要求的最少點數(shù)量1，使用基于實際軌跡數(shù)據(jù)集多次調(diào)參獲得的較優(yōu)值.通過RET算法聚類獲取數(shù)據(jù)點密度較大的簇，確保位于同一簇中的用車/停車點在地理位置上距離鄰近，偽代碼如算法l所示.

算法l中D為GPS位置點集合，C為聚類結(jié)果的集合，TaxiID_i為同一出租車的GPS位置點集合，Dpick表示用車點數(shù)據(jù)集，Ddrop表示停車點集合，Nr spatinPe為點pe鄰近的點集合.算法1的具體功能如下：首先從原始數(shù)據(jù)中提取每輛出租車所有的GPS點并按時間先后順序存儲（行1-8），然后提取出租車行程不超過3 km的歷史軌跡數(shù)據(jù)并將行程開始的GPS點放入相應(yīng)時段的用車點集合中，行程結(jié)束的GPS點放入相應(yīng)時段的停車點集合中（行9-11）;接著分別對每個時段的用車點集合和停車點集合中的點Pi搜索離其在空間維度上相鄰的點，如果相鄰點的數(shù)量大于等于MinPts，就把p。標(biāo)記為核心點，并建立新簇pe.cluster_ID，并將Pe領(lǐng)域內(nèi)所有點加入pe.cluster_ID中（行12-15）;最后對所有未被訪問的pe鄰域內(nèi)的點pa，再次搜索p。的鄰近點，如果相鄰的點數(shù)量至少為MinPts個，就把這些相鄰點中未歸入任何一個簇的點加入Pe .cluster_ID簇中（行1623）.

對于工作日/節(jié)假日產(chǎn)生的出租車軌跡，使用RET算法分時段提取用車點和停車點位置并對其進行聚類，獲得的各時段中空間密度較高的用車點與停車點區(qū)域，代表不同時段內(nèi)用車、停車事件發(fā)生較為頻繁的區(qū)域，各簇的簇心表示用車區(qū)域與停車區(qū)域的位置.

3.2 在線調(diào)度

獲取工作日、節(jié)假日中各時段的用車和放車區(qū)域集，該部分工作以離線的方式進行處理.在線調(diào)度階段中，提出ROM方法，首先為用車區(qū)域推薦k個近鄰?fù)＼噮^(qū)域，然后結(jié)合實時路況實現(xiàn)調(diào)度車行車線路推薦.

3.2.1 k近鄰?fù)＼噮^(qū)域推薦

對當(dāng)前用車區(qū)域進行k近鄰?fù)＼噮^(qū)域推薦.對于一個給定位置Pcurrent時間戳Tcurrent的用車區(qū)域而言，搜索與其鄰近的前一時段的停車區(qū)域，將用車區(qū)域當(dāng)前位置Pcurrent的簇心Ciheart與附近停車區(qū)域之間的最短距離線路作為選取附近top-k停車區(qū)域的評測標(biāo)準(zhǔn)，完成用車區(qū)域的k鄰近停車區(qū)域推薦.

采用Dij kstra算法[15]作為尋路策略，完成對用車區(qū)域簇心到停車區(qū)域簇心的最短線路的計算.Dijkstra算法通過距離權(quán)值SP找到從一個結(jié)點到任何其他結(jié)點的最低權(quán)重線路.該方法將在下文的最短線路函數(shù)Scost中得到充分運用.本文采用Dijkstra算法找到了離用車區(qū)域距離最短的top-k停車區(qū)域.以一個帶有權(quán)值的無向圖為例，如圖2，令A(yù)為用車區(qū)域簇心，G為停車區(qū)域簇心，用Dijkstra算法分析從用車區(qū)域簇心A到停車區(qū)域簇心G的最短線路.

步驟1以帶有權(quán)值的一個矩陣z表示含有各結(jié)點的帶權(quán)無向圖，矩陣相應(yīng)位置的數(shù)值代表對應(yīng)線段的權(quán)值，如果從一個結(jié)點到另一個結(jié)點不連通，那么其矩陣中的值為∞.帶權(quán)值的鄰接矩陣圖如圖3所示.

步驟3修改起始結(jié)點A，再次到集合{B，C，D，E，F(xiàn)）中任一結(jié)點vn之間的最短線路的長度值，若S（j）+z（j，n）

步驟4重復(fù)步驟2、步驟3，最終得到從起始點A到其他結(jié)點的最短距離線路，并對線路的長度遞增進行排序.

3.2.2 調(diào)度車的行車線路推薦

對于（下一時段的）用車區(qū)域應(yīng)考慮距離其最近的k個（上一時段的）停車區(qū)域，在此基礎(chǔ)上，結(jié)合實時路況為單車調(diào)度車輛規(guī)劃（下一時段的）用車區(qū)域到（上一時段的）停車區(qū)域之間距離最近且交通較暢通的線路.本文根據(jù)擁堵比例來評測交通狀況.首先計算出各路段的速度，通過基于滑動窗口的軌跡流聚類算法OCluST（Online Clustering Streaming Trajectorys）[16]獲得各路段基于時間Tcurrent的實時速度.該方法通過對實時到達的出租車軌跡進行增量式聚類分析，實時提取各簇的移動行為模式，實現(xiàn)對各簇所在路段的實時交通狀況評測，為了更為直觀地在地圖上展示道路狀況，本文將道路交通狀況分為兩種：速度低于30 km/h的將其視為交通緩慢（以黃色標(biāo)記）;速度超過30 km/h的定義為交通暢通（以綠色標(biāo)記）.

獲取各路段的實時速度后，則可計算各行車線路的擁堵情況.將交通緩慢的路段長度和總線路長度進行比例分析，并對所有線路按擁堵比例排序.從而完成停車區(qū)域到用車區(qū)域的調(diào)度車的行車線路推薦.擁堵比例（Traffic Congestion Ratio，TCR）計算公式為

4 實驗

4.1 實驗環(huán)境及數(shù)據(jù)集

本文實驗采用上海2015年4月共30 d的出租車軌跡數(shù)據(jù)集，該數(shù)據(jù)集包含近13 600輛出租車的GPS軌跡數(shù)據(jù).離線建模階段，首先基于前25 d的歷史軌跡數(shù)據(jù)C1提取用車區(qū)域和停車區(qū)域;在線調(diào)度階段基于后5d的軌跡數(shù)據(jù)C2模擬實時到達軌跡，通過各時段內(nèi)實時到達的出租車軌跡分析路網(wǎng)交通情況，利用C1提取各時段內(nèi)的用車區(qū)域和停車區(qū)域，利用C2對實時交通路況進行評測，其中出租車的GPS數(shù)據(jù)格式如表2所示，實驗使用Java語言實現(xiàn)算法的編寫，在Windows 7操作系統(tǒng)，機器配置為2.50 GHz Intel Core i5處理器和12 GB物理內(nèi)存的PC機上運行.

4.2 評測標(biāo)準(zhǔn)

本文提出的RET算法，對用車點和停車點進行時空聚類，該算法不僅能預(yù)測用車和停車區(qū)域位置，還能預(yù)測相應(yīng)區(qū)域的用車和停車頻次. 本文將RET算法與MSI[13]、MSEWk[10]、IPPI[12]，HM[8]進行有效性對比實驗.采用的衡量性能的標(biāo)準(zhǔn)是對每個時段用車頻次和停車頻次預(yù)測的平均絕對誤差（Mean Absolute Error，MAE），MAEpick表示用車頻次預(yù)測誤差，MAEdrop停車頻次預(yù)測誤差.公式分別為

本文提出的實時調(diào)度優(yōu)化模型（ROM方法）能以較短調(diào)度車的行車線路總里程和較短行車總時長的方式快速完成單車調(diào)度，確保下一時段的用車需求，行車線路總里程越小代表單車公司運營成本越低，總行車時長越短越能快速的完成整個調(diào)度過程.本文將所提出的調(diào)度優(yōu)化模型與其他調(diào)度優(yōu)化算法NNIA[17]和GA[18]進行了有效性對比實驗.衡量ROM方法性能的標(biāo)準(zhǔn)是行車線路總里程（Total Mileage of Driving Routes，TMR）和行車總時長（Total Driving Time，TDT），相關(guān)公式分別為

4.3 實驗效果

為了展示單車調(diào)度效果，本文選取出行需求相對密集的上海外灘周圍區(qū)域作為實驗區(qū)域，該區(qū)域范圍滿足經(jīng)度lon∈[121.417041，121.516261]、緯度lat∈[31.197382，31.239589].

4.3.1 用車頻次及停車頻次預(yù)測

為了驗證RET算法的有效性，本文將其與當(dāng)前預(yù)測用車頻次/停車頻次精確度較高的算法進行了對比分析，包含基于歷史數(shù)據(jù)處理的IPPI[12]算法、HM[8]算法和考慮多影響因素的MSI[13]算法、MSEWk[10]算法，結(jié)果如圖4、圖5所示.從圖4、圖5中可以看出，考慮多因素的算法（MSI[13]和MSEWk[10]）在用車需求更強烈的工作日期間雖然優(yōu)于傳統(tǒng)的單因素統(tǒng)計預(yù)測算法（IPPI[12]、HM[8]），但本文對用車頻次和停車頻次的時空聚類的RET算法的預(yù)測誤差無論在工作日還是在節(jié)假日均低于其他算法.

RET算法是對用車點/停車點的時空聚類，聚類效果的優(yōu)劣由MinPts和r spatio值決定.比如，首先給定MinPts值，雖然r spatio值設(shè)置越小，它的聚類效果越好，但是r spatio值過小，則會導(dǎo)致大量用車點、停車點被錯誤地標(biāo)記為噪聲點;如果r spatio值設(shè)置過大，則會將很多噪聲點被錯誤地歸入簇中.然后再給定r spatio值，如果MinPts值設(shè)置過大，聚類效果會很差;MinPts值設(shè)置過小，將會使大量點被標(biāo)記為核心點，從而將噪聲點錯誤的歸入簇中，所以需要合理設(shè)置參數(shù)r spatio和MinPts.鑒于此，本文基于實際的出租車軌跡數(shù)據(jù)進行反復(fù)調(diào)參，最終將r spatio設(shè)置為30 m，MinPts設(shè)置為15.

4.3.2 調(diào)度優(yōu)化

為了驗證實時調(diào)度優(yōu)化模型ROM方法的有效性，本文對調(diào)度車的行車線路的效率進行了實驗，圖6呈現(xiàn)的是本文提出的調(diào)度優(yōu)化模型ROM方法的效率圖，如圖6所示，隨著用車區(qū)域數(shù)量的增加，行車總時長增長幅度明顯減弱，擁堵比例明顯減小，最后擁堵比例保持在一個很小的范圍內(nèi).即本文所提出的調(diào)度優(yōu)化模型ROM方法在面對大型調(diào)度的情況下，能明顯減少行車總時長，快速完成全部調(diào)度，減少調(diào)度開銷.

本文呈現(xiàn)了上海外灘區(qū)域的用車/停車區(qū)域示意圖，如圖7所示.圖7中，圓的大小代表用車頻次或停車頻次，圓越大，用車/停車頻次越高;紅色圓表示本時段的用車區(qū)域，藍色圓表示上一時段的停車區(qū)域.為驗證調(diào)度優(yōu)化模型ROM方法的有效性和高效性，以圖7中的用車區(qū)域n4為例，首先搜索距離n4最近的top-k停車區(qū)域.

接著根據(jù)表3所示的數(shù)據(jù)，獲取鄰近用車區(qū)域n4且滿足用車比例（經(jīng)計算為4%）的停車區(qū)域，包括95、g40、910、g20、g8·

最后結(jié)合OCluST算法[16]獲取的實時路況向調(diào)度車推薦，各停車區(qū)域到用車區(qū)域的交通狀況如圖8所示.在圖8中，通過ROM方法得到g10到n4的推薦行車線路為線路1和線路2;g40到n4推薦行車線路為線路1;g8到n4的推薦行車線路為線路l;g20同g8 一樣，推薦線路也是線路l;g5到n4只有1條線路，無需對比分析.

接下來將本文所提的ROM方法同其他調(diào)度優(yōu)化方法NNIA[16]和GA[17]作對比，圖9、圖10展示了對比結(jié)果，測試的范圍為上海外灘區(qū)域，對42個用車區(qū)域進行投放和對35個停車區(qū)域進行調(diào)度，優(yōu)化后各時段的行車線路總里程（TMR）、行車總時長（TDT）.從本文的案例研究中可以看出.本文提出的調(diào)度優(yōu)化模型ROM方法在各時段都比NNIA[16]和GA[17]的行車線路總里程更小，并且完成行車總時長更短，尤其是在用車高峰時段f6.00～16：00）最為明顯.本文所提的ROM方法首先是尋找距離相關(guān)用車區(qū)域最短的top-k停車區(qū)域，這使得本文在行車線路的距離上最短，所以TMR值會是最優(yōu)的;NNIA[16]和GA[17]的TDT值之所以大，是因為它們沒有結(jié)合實時路況對行車線路進行分析，而本文提出的ROM方法結(jié)合了實時路況，能獲取路況最好的調(diào)度車的行車線路，所以ROM方法的TDT值更低，尤其是用車高峰時段最為明顯.

本文提出的兩階段的框架在預(yù)估城市用車需求和共享單車停車情況上，同考慮多因素的算法（MSI[13]，MSEWK[10]）和歷史數(shù)據(jù)統(tǒng)計預(yù)測算法（IPPI[12]，HM[8]）作對比，通過RET算法，首次預(yù)測出城市熱門用車區(qū)域、共享單車停車區(qū)域的變化情況，并能找到各時段內(nèi)熱門用車區(qū)域和停車區(qū)域的范圍和位置，且本文所提的RET算法在預(yù)估各時段內(nèi)用車頻次、停車頻次的精確度上更高.本文所提的ROM方法同NNIA[16]和GA[17]，在調(diào)度優(yōu)化上進行了有效性對比實驗，實驗結(jié)果證明了本文所提的ROM方法在各時段的調(diào)度過程中，TMR和TDT值都更小，即ROM方法能以較短的線路總里程和較短行車總時長的方式完成所有調(diào)度.

5 結(jié)語

為滿足不同時段的城市共享單車用車需求，本文提出了一個兩階段的共享單車實時投放及調(diào)度的框架，該框架能準(zhǔn)確預(yù)測各時段的用車需求及單車分布情況，并可結(jié)合實時路況推薦調(diào)度車的較優(yōu)行車線路，基于出租車數(shù)據(jù)集上的實驗結(jié)果表明，本文的RET算法能精確地預(yù)測用車需求、發(fā)現(xiàn)停車區(qū)域;本文的ROM方法能有效提升調(diào)度效率.在未來的工作中，擬結(jié)合包括天氣、日期、POI數(shù)據(jù)等提取多源外部特征，采用深度學(xué)習(xí)模型對軌跡數(shù)據(jù)與外部特征進行統(tǒng)一建模，進一步提升城市共享單車的動態(tài)調(diào)度策略的高效性.

[參考文獻]

[1]

CHANG H W， TAI Y c，HSU Y J Context-aware taxi demand hotspots prediction[J].International Jounal ofBusiness Intelligence and Data Mining， 2010， 5（1）： 3-18

[2] L1 x L，PAN G，WU z H，et al. Prediction of urban human mobility using large-scale taxi traces and itsapplication[J].Frontiers of Computer Science， 2012， 6（1）： 111-121

[3]

LIU H P，JIN c Q，ZHOU A Y.Popular route planing with travel cost estimation [C]//International Conferenceon Database Systems for Advanced Applications（DASFAA）， 2016， 2016： 403-418.

[4]

CHEN c，CHEN x，WANG z，et al. Scenicplanner： Planning scenic travel routes leveraging heterogeneoususer-generated digital footprints [J]. Frontiers of Computer Science， 2017， 11（1）： 61-74

[5] EOIN o M，DAVID B s.Data analysis and optimization for （citi）bike sharing [C]//Proceedings of the 29thAAAI Conference on Artificial Intelligence. AAAI. 2015： 687-694

[6]

DIMITRIOS T，IOANNIS B，VANA K.Lessons learnt from the analysis of a bike sharing system [C]//PETRA '17Proceedings of the lOth International Conference on PErvasive Technologies Related to Assistive Environments.2017： 261-264

[7]

CHENG F，JANE H，DANIEL R Moment-based probabilistic prediction of bike availability for bike-sharingsystems [C]//lnternational Conference on Quantitative Evaluation of Systems， QEST 2016： Quantitative Eval-uation of Systems. 2016： 139-155.

[8]

CHEN L B，ZHANG D Q，PAN G，et al.Bike sharing station placement leveraging heterogeneous Urban opendata [C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.ACM. 2015： 571-575

[9] DIVYA s，SOMYA s，PETER I F，et al. Predicting bike usage for New York City's Bike sharing system[C]//Association for the Advancement of Artificial Intelligence. 2015： 110-114.

[10]

LIU J M，SUN L L，CHEN w W. et al_Rebalancing bike sharing systems：A multi-source data smart optimization[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2016： 1005-1014.

[11]

FABIO c，ANAND s， BRUNO P.B， et al.A heuristic algorithm for a single vehicle static bike sharing rebalancingproblem[J] Computers& Operations Research， 2017. 79： 19- 33.

[12]

ALVAREZ-VALDES R，BELENGUER J M，BENAVENT E，et al.Optimizing the level of service quality of abike-sharing system[J].Omega， 2015， 62： 163-175.

[13]

L1 Y x，ZHENG Y，ZHANG H c，et al.Traffic prediction in a bike-sharing system [C]//Proceedings of the 23rdSIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM SIGSPATIAL.2015： Article N0 33.

[14] CHRISTIAN K，GUNTHER R R Full-load route planning for balancing bike sharing systems by logic-basedbenders decomposition [J]. Wiley Periodicals. 2017， 69（3）： 270-289

[15] DIJSTRA E D A note on two problem in connexion with graphs [J]. Numerische Mathematik. 1959（1）： 269-271

[16] MAO J L，SONG Q G，JIN c Q，et al.TSCluWin： Trajectory stream clustering over sliding window[c]，/DASFAA 2016： Databases Systems for Advanced Applications. 2016： 133-148.

[17] JOSHI s，KAUR s.Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem[C]//lnternational Conference on Computing for Sustainable Global Development. 2015： 86-88.

[18] ZHAO F G，LI s J，SUN J s，et al_Genetic algorithm for the one-commodity pickup-and- delivery travelingsalesman problem[J]Computers and Industrial Engineering（COMPUT IND ENG）， 2009. 56（4）： 1642-1648.

（責(zé)任編輯：李藝）

收稿日期：2018-09-03

基金項目：國家自然科學(xué)基金（61702423）;四川省教育廳重點基金項目（17ZA0381）;西華師范大學(xué)國家培育項目（16C005）;西華師范大學(xué)英才科研基金（17YC158）

第一作者：謝青成，男，碩士研究生，研究方向為基于位置的服務(wù).E-mail： 1061109117@qq.com.

通信作者：毛嘉莉，女，副教授，碩士生導(dǎo)師，研究方向為基于位置的服務(wù).

E-mail： jlmao@dase.ecnu.edu.cn.