共享單車搬遷策略研究

謝青成

摘要：為滿足單車用戶的用車需求，對共享單車搬遷策略進行研究，提出兩階段共享單車搬遷策略.離線階段構建單車停放區域提取模型，采用改進的DBSCAN聚類方法（DistrictPick up Technology，DPT）獲取各時段熱門用車區域、用車頻率與行程結束后的放車區域、放車頻率;在線階段提出搬遷優化模型（RelocationOptimi-zationPlan，OMP），根據當前時段的用車區域，搜索距離其最近的前一時段K近鄰放車區域，并結合實時路況為其推薦前K條路況良好的單車搬遷路徑。相較于傳統的共享單車搬遷策略，在擁堵比例為48%時，OBJ值至少縮小52.4%，AT值至少縮小52.6%。

關鍵詞：共享單車;搬遷策略;DPT算法;搬遷優化模型DOI：10.11907/ejdk.191910開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP319文獻標識碼：A 文章編號：1672-7800（2019）010-0147-05

0引言

共享單車屬于新型城市公共自行車，傳統城市公共自行車系統開始采用固定的租賃站點，以投幣為憑證供人們匿名使用。近幾年，隨著摩拜、OFO等共享單車的廣泛使用，在方便人們出行的同時，也引發了諸多問題，如大量共享車隨意停放影響了正常交通秩序，且高峰時段用戶依然面臨無車可用的情況。目前共享單車數量已趨于飽和，基于有限數量的單車資源，要確保滿足各時段的用車需求，亟需設計出動態的單車搬遷策略、推薦有效的搬遷路徑，這涉及兩個問題：①預測各時段的用車需求;②結合實際路況的有效搬遷路徑推薦。

針對目前共享單車搬遷所面臨的問題，本文構建并實施一個兩階段的共享單車搬遷策略。在離線階段，提出DPT算法，采用改進的DBSCAN聚類方法（DPT）對各時段的用車點（放車點）聚類，找到各時段用車區域及其用車頻率（放車區域及放車頻率）;在線階段，提出搬遷優化模型（OMP）。根據用車區域的位置，搜索K近鄰放車區域，并結合實時路況推薦前K條路況良好的單車搬遷路徑，從根本上滿足實時用車需求，推進綠色智能城市建設。本文主要作如下研究：提出DPT算法，采用改進的DBSCAN聚類DPT算法，提取區別各時段的用車區域和放車區域;提出結合實時交通狀況的搬遷優化模型（OMP），以較小路徑長度和較短搬遷耗時的方式完成單車搬遷，確保各時段內的單車使用需求得到滿足。1

相關工作

1.1用車需求預測

現有用車需求預測大多數聚焦于使用單車歷史數據即取車（放車）記錄對用車區域需求進行預測，許多學者對此作了研究。米文勇采用非集計模型預測用車需求，并提出了自行車停車位置規劃方法;Eoin等研究高峰時段使用情況，通過分析共享單車系統數據，以發現單車的用車需求位置，但該方法僅考慮了高峰時段的用車需求，且工作日和節假日高峰時段未分開考慮;Dimitrios等通過識別單車使用影響因素及共享單車流動模式，進而預測單車用車需求。

1.2放車區域預測

放車區域預測相關研究大多根據歷史數據對放車區域進行提取，也有考慮時間、天氣等因素，比如Liu等采用區分工作日、節假日的高斯混合模型對固定車站的放車頻率進行預測。但目前共享單車的很多站點不固定，其雖然能很好地預測出放車區域的放車次數，但是缺乏各時段放車區域位置預測。對放車點區分工作日、節假日各時段的聚類DPT算法，可以發現各時段的放車區域和放車頻率。

1.3搬遷路徑推薦

對搬遷路徑的研究大部分是通過對用車區域和放車區域的分析進行數學建模。如Liu等運用帶約束的K中心聚類（AdaCCKC）算法對用車比例和放車比例進行聚類，將大型多車輛路徑問題簡化為內部站點集群間的路徑選擇問題，缺乏實時路況的考慮;FObio等提出一個基于迭代的局部搜索的啟發式算法，通過一條最優路徑完成所有站點之間的搬遷，但是一天僅搬遷一次，不能滿足各時段用車需求;Christian等提出了一個混合整數線性規劃方法，但未考慮實時路況，因此搬遷效率較低。

2總體框架

本文構建一個兩階段的共享單車搬遷策略，總體框架如圖1所示，整體框架分為離線階段和在線階段。在離線階段，首先對歷史軌跡使用地圖匹配技術并結合路網數據將有序路段的交點序列映射到真實路段上;然后對軌跡數據進行預處理，包括去除噪聲數據，將用車點和放車點的數據分別提取出來，再分別對用車點數據和放車點數據進行分時段基于最小閾值支持的聚類，從而實現各時段用車區域和行程結束放車區域的提取。基于最小閾值支持的聚類，是指用車需求頻次和放車頻率必須達到一定閾值α才能被視為用車區域和放車區域，聚類技術采用基于密度聚類的DBSCAN聚類，該聚類適于任意形狀的軌跡數據聚類且能進一步去噪。在區域提取過程中，使用實時軌跡對其進行增量更新，確保用車區域和放車區域提取的精準性。在線階段，首先獲取當前用車區域的位置信息和所屬時段，搜索用車區域的top-K近鄰放車區域，同時結合當前時段共享單車軌跡流完成對各路段交通擁塞情況的評測，根據各路徑擁堵比例對用車區域與初始提取的top-K近鄰放車區域之間的路徑進行評測排序，實現top-K單車搬遷路徑推薦。

2.1離線階段

本文使用單車歷史軌跡數據提取用車及放車區域，基于DPT算法對提取出的用車點和放車點分別進行聚類，通過使用兩個參數r_time和r_spatio分別作為時間維度、空間維度的半徑，給定點在E領域內成為核心對象的最小領域點數MinPts，將簇視為一系列由低密度區域（噪聲）分割開的高密度連通區域。由于在聚類過程中考慮了空間和時間相似性，使得聚類結果為在某一時段內數據點密度較大的簇，即位于同一簇中的用車點在地理位置和時間緯度上鄰近，最終達到某一連續時段內較大的聚類目標。偽代碼如算法1所示。

對當前用車區域的K近鄰放車區域推薦，即用車區域到放車區域路徑長度最短的top-K放車區域推薦，對于一個給定位置P_current、當前時間戳T_current的用車區域而言，搜索與其時空鄰近的放車區域，考慮將用車區域當前位置P_current，的簇心S_cen與放車區域之間的最短路徑作為用車區域到放車區域的路徑，并對每條路徑進行評測排序，完成用車區域的K近鄰放車區域推薦。

采用Dijkstra算法作為尋路策略，完成對基于起始位置P_start、P_termination的最短路徑計算。Dijkstra算法可以找到從一個頂點s到任何其它頂點的最低權重路徑，本文采用Dijkstra算法找到離用車區域路徑最短的top-K個放車區域，該算法通過距離權值SP找到最短距離路徑。

算法1中步驟7-10對每個在列表D中的點搜索離其在時間維度和空間維度上相鄰的點，如果相鄰點的數量小于MinPts，就把它視為噪聲點;步驟11-15是對所有未被訪問的相鄰點再次搜索時空鄰近點，如果相鄰的點數量超過MinPts就把這些點歸為同一個簇;步驟16-21是重復操作步驟11-15直至每個相鄰點都被訪問完。

2.2在線階段

獲取區分工作日、節假日中各時段的用車和放車區域集，該部分工作以離線方式處理。在線階段中，提出了搬遷優化模型（OMP），包括用車區域的K近鄰放車區域推薦、實時路況評測和搬遷路徑推薦3部分。

2.2.1K近鄰放車區域推薦

對當前用車區域的K近鄰放車區域推薦，即用車區域到放車區域路徑長度最短的top-K放車區域推薦，對于一個給定位置P_current、當前時間戳T_current的用車區域而言，搜索與其時空鄰近的放車區域，考慮將用車區域當前位置P_current的簇心S_sen與放車區域之間的最短路徑作為用車區域到放車區域的路徑，并對每條路徑進行評測排序，完成用車區域的K近鄰放車區域推薦。

采用Dijkstra算法作為尋路策略，完成對基于起始位置P_start、P_termination的最短路徑計算。Dijkstra算法可以找到從一個頂點s到任何其它頂點的最低權重路徑，本文采用Dijkstra算法找到離用車區域路徑最短的top-K個放車區域，該算法通過距離權值SP找到最短距離路徑。

2.2.2買時路況

本文通過基于滑動窗口的軌跡流聚類方法獲得各路段基于時間T_current的實時速度，需要對用車區域到搬遷源區域的每條路徑進行實時路況評測。將道路交通狀況分為3種：速度低于30km/h的將其視為交通擁塞（以紅色標記），速度在[30km/h，60km/h]范圍內定義為交通緩慢（以黃色標記），速度超過60km/h的定義為交通暢通（以綠色標記）。

2.2.3搬遷路徑推薦

每個放車區域到用車區域有眾多路徑，需要找到交通狀況良好的前K條路徑。根據擁堵比例評測交通狀況，首先需要計算出各路段的速度，采用基于滑動窗口模型的軌跡流聚類關注最近時段到達的車輛行駛軌跡，將其劃分成簇以實時提取各簇的移動行為模式，繼而實現對各簇所在路段的實時交通狀況評測，將交通擁堵和交通緩慢的路段長度和總路徑長度進行比例分析，并對所有路徑按擁堵比例排序，從而完成到用車區域各K鄰近放車區域的搬遷路徑推薦。擁堵比例計算如下：

3實驗

3.1實驗環境及數據集

本文實驗采用上海2015年4月共30天的共享單車軌跡數據集，該數據集包含近30000輛共享單車的近5萬條GPS軌跡數據。離線階段首先采用共享單車歷史軌跡數據C₁提取用車區域和放車區域，在線階段采用出租車軌跡數據C₂模擬實時到達軌跡，通過各時段內實時到達的出租車軌跡分析路網交通情況，利用C₁提取各時段內的用車區域和放車區域，并利用C₂對實時交通路況進行評測。實驗使用Java語言實現算法編寫，并在Windows 7操作系統、機器配置為2.50GHz Intel Core i5處理器和12GB物理內存的PC機上運行。

3.2對比方法

本文提出的DPT算法，是對用車點和放車點進行時空聚類，預測用車和放車頻率的方法。采用的對比方法如下：

Multi-Similarity-based Inference（MSI）法考慮天氣、溫度、風速和時間相似性預測用車需求。其相似性函數是這3個相似性的乘法，而這幾個因素的權重沒有被研究。

Historical Mean（HM）法是將自行車需求的歷史記錄作為預測值而不考慮其它因素的需求預測方法。

Muhi-Similarity-Equally-Weighted KNN（MSEWK）方法是對影響需求預測的不同因素采取相同的權值，運用混合高斯算法預測需求。

采用的性能衡量標準是對每個時段用車頻率和放車頻率預測的平均絕對誤差。評測標準表示為MAE，如下：

3.3實驗結果

3.3.1用車頻率及放車頻率預測

本文提出的預測用車頻率的DPT算法性能如圖2所示。可以看出，多源因素模型（MSI和MSEWK）雖然優于傳統單因素統計預測模型（IPPI，HM），但是對用車頻率時空聚類的DPT法的錯誤率低于其它方法。

在放車頻率預測上，本文方法優于其它結合多因素預測方法，如圖3所示，這充分證明了本文方法的有效性。

3.3.2搬遷優化

搬遷優化模型（OMP）的有效性和高效性如圖4所示。在相同路徑長度下，交通擁堵比例較小的路段可以明顯減少CPU運行時間，總路徑越長CPU運行時間越長;用OMP法則隨著總搬遷路徑長度增加，擁堵比例也越低，但是總路徑過長，CPU運行時間也會變長。因此，需要找到總路徑長度較小，擁堵比例也較小的搬遷路徑。

表1展示了優化后總的搬遷路徑長度（Optimal Objec-tives，OBJ）和CPU運行時間（CPU Running All Times，AT）。將本文優化模型與同樣是對搬遷優化的NearestNeighbor Insertion Alzorithm（NNIA）和Genetic Algorithm（GA）進行比較可知，本文車輛路徑優化策略最優。本文搬遷優化模型（OMP）比NNIA和GA的搬遷總路徑長度更小，完成搬遷的CPU運行時間更短。

4結語

為滿足不同時段共享單車用車需求并解決單車搬遷效率問題，本文提出了一個兩階段的共享單車搬遷策略框架，該框架能準確預測各時段的用車需求及放車區域，并結合實時路況推薦單車搬遷路徑。基于共享單車數據集的實驗結果表明，DPT算法能精確預測用車需求、發現放車區域，所提出的搬遷優化模型能有效提升共享單車搬遷效率。在未來工作中，擬結合包括天氣、日期、POI數據等提取多源外部特征，對軌跡數據與外部特征進行統一建模，進一步提升單車搬遷策略的有效性。