謝青成

摘要：為滿(mǎn)足單車(chē)用戶(hù)的用車(chē)需求，對(duì)共享單車(chē)搬遷策略進(jìn)行研究，提出兩階段共享單車(chē)搬遷策略.離線階段構(gòu)建單車(chē)停放區(qū)域提取模型，采用改進(jìn)的DBSCAN聚類(lèi)方法（DistrictPick up Technology，DPT）獲取各時(shí)段熱門(mén)用車(chē)區(qū)域、用車(chē)頻率與行程結(jié)束后的放車(chē)區(qū)域、放車(chē)頻率;在線階段提出搬遷優(yōu)化模型（RelocationOptimi-zationPlan，OMP），根據(jù)當(dāng)前時(shí)段的用車(chē)區(qū)域，搜索距離其最近的前一時(shí)段K近鄰放車(chē)區(qū)域，并結(jié)合實(shí)時(shí)路況為其推薦前K條路況良好的單車(chē)搬遷路徑。相較于傳統(tǒng)的共享單車(chē)搬遷策略，在擁堵比例為48%時(shí)，OBJ值至少縮小52.4%，AT值至少縮小52.6%。

關(guān)鍵詞：共享單車(chē);搬遷策略;DPT算法;搬遷優(yōu)化模型DOI：10.11907/ejdk.191910開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類(lèi)號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）010-0147-05

0引言

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

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

相關(guān)工作

1.1用車(chē)需求預(yù)測(cè)

現(xiàn)有用車(chē)需求預(yù)測(cè)大多數(shù)聚焦于使用單車(chē)歷史數(shù)據(jù)即取車(chē)（放車(chē)）記錄對(duì)用車(chē)區(qū)域需求進(jìn)行預(yù)測(cè)，許多學(xué)者對(duì)此作了研究。米文勇采用非集計(jì)模型預(yù)測(cè)用車(chē)需求，并提出了自行車(chē)停車(chē)位置規(guī)劃方法;Eoin等研究高峰時(shí)段使用情況，通過(guò)分析共享單車(chē)系統(tǒng)數(shù)據(jù)，以發(fā)現(xiàn)單車(chē)的用車(chē)需求位置，但該方法僅考慮了高峰時(shí)段的用車(chē)需求，且工作日和節(jié)假日高峰時(shí)段未分開(kāi)考慮;Dimitrios等通過(guò)識(shí)別單車(chē)使用影響因素及共享單車(chē)流動(dòng)模式，進(jìn)而預(yù)測(cè)單車(chē)用車(chē)需求。

1.2放車(chē)區(qū)域預(yù)測(cè)

放車(chē)區(qū)域預(yù)測(cè)相關(guān)研究大多根據(jù)歷史數(shù)據(jù)對(duì)放車(chē)區(qū)域進(jìn)行提取，也有考慮時(shí)間、天氣等因素，比如Liu等采用區(qū)分工作日、節(jié)假日的高斯混合模型對(duì)固定車(chē)站的放車(chē)頻率進(jìn)行預(yù)測(cè)。但目前共享單車(chē)的很多站點(diǎn)不固定，其雖然能很好地預(yù)測(cè)出放車(chē)區(qū)域的放車(chē)次數(shù)，但是缺乏各時(shí)段放車(chē)區(qū)域位置預(yù)測(cè)。對(duì)放車(chē)點(diǎn)區(qū)分工作日、節(jié)假日各時(shí)段的聚類(lèi)DPT算法，可以發(fā)現(xiàn)各時(shí)段的放車(chē)區(qū)域和放車(chē)頻率。

1.3搬遷路徑推薦

對(duì)搬遷路徑的研究大部分是通過(guò)對(duì)用車(chē)區(qū)域和放車(chē)區(qū)域的分析進(jìn)行數(shù)學(xué)建模。如Liu等運(yùn)用帶約束的K中心聚類(lèi)（AdaCCKC）算法對(duì)用車(chē)比例和放車(chē)比例進(jìn)行聚類(lèi)，將大型多車(chē)輛路徑問(wèn)題簡(jiǎn)化為內(nèi)部站點(diǎn)集群間的路徑選擇問(wèn)題，缺乏實(shí)時(shí)路況的考慮;FObio等提出一個(gè)基于迭代的局部搜索的啟發(fā)式算法，通過(guò)一條最優(yōu)路徑完成所有站點(diǎn)之間的搬遷，但是一天僅搬遷一次，不能滿(mǎn)足各時(shí)段用車(chē)需求;Christian等提出了一個(gè)混合整數(shù)線性規(guī)劃方法，但未考慮實(shí)時(shí)路況，因此搬遷效率較低。

2總體框架

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

2.1離線階段

本文使用單車(chē)歷史軌跡數(shù)據(jù)提取用車(chē)及放車(chē)區(qū)域，基于DPT算法對(duì)提取出的用車(chē)點(diǎn)和放車(chē)點(diǎn)分別進(jìn)行聚類(lèi)，通過(guò)使用兩個(gè)參數(shù)r_time和r_spatio分別作為時(shí)間維度、空間維度的半徑，給定點(diǎn)在E領(lǐng)域內(nèi)成為核心對(duì)象的最小領(lǐng)域點(diǎn)數(shù)MinPts，將簇視為一系列由低密度區(qū)域（噪聲）分割開(kāi)的高密度連通區(qū)域。由于在聚類(lèi)過(guò)程中考慮了空間和時(shí)間相似性，使得聚類(lèi)結(jié)果為在某一時(shí)段內(nèi)數(shù)據(jù)點(diǎn)密度較大的簇，即位于同一簇中的用車(chē)點(diǎn)在地理位置和時(shí)間緯度上鄰近，最終達(dá)到某一連續(xù)時(shí)段內(nèi)較大的聚類(lèi)目標(biāo)。偽代碼如算法1所示。

對(duì)當(dāng)前用車(chē)區(qū)域的K近鄰放車(chē)區(qū)域推薦，即用車(chē)區(qū)域到放車(chē)區(qū)域路徑長(zhǎng)度最短的top-K放車(chē)區(qū)域推薦，對(duì)于一個(gè)給定位置P_current、當(dāng)前時(shí)間戳T_current的用車(chē)區(qū)域而言，搜索與其時(shí)空鄰近的放車(chē)區(qū)域，考慮將用車(chē)區(qū)域當(dāng)前位置P_current，的簇心S_cen與放車(chē)區(qū)域之間的最短路徑作為用車(chē)區(qū)域到放車(chē)區(qū)域的路徑，并對(duì)每條路徑進(jìn)行評(píng)測(cè)排序，完成用車(chē)區(qū)域的K近鄰放車(chē)區(qū)域推薦。

采用Dijkstra算法作為尋路策略，完成對(duì)基于起始位置P_start、P_termination的最短路徑計(jì)算。Dijkstra算法可以找到從一個(gè)頂點(diǎn)s到任何其它頂點(diǎn)的最低權(quán)重路徑，本文采用Dijkstra算法找到離用車(chē)區(qū)域路徑最短的top-K個(gè)放車(chē)區(qū)域，該算法通過(guò)距離權(quán)值SP找到最短距離路徑。

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

2.2在線階段

獲取區(qū)分工作日、節(jié)假日中各時(shí)段的用車(chē)和放車(chē)區(qū)域集，該部分工作以離線方式處理。在線階段中，提出了搬遷優(yōu)化模型（OMP），包括用車(chē)區(qū)域的K近鄰放車(chē)區(qū)域推薦、實(shí)時(shí)路況評(píng)測(cè)和搬遷路徑推薦3部分。

2.2.1K近鄰放車(chē)區(qū)域推薦

對(duì)當(dāng)前用車(chē)區(qū)域的K近鄰放車(chē)區(qū)域推薦，即用車(chē)區(qū)域到放車(chē)區(qū)域路徑長(zhǎng)度最短的top-K放車(chē)區(qū)域推薦，對(duì)于一個(gè)給定位置P_current、當(dāng)前時(shí)間戳T_current的用車(chē)區(qū)域而言，搜索與其時(shí)空鄰近的放車(chē)區(qū)域，考慮將用車(chē)區(qū)域當(dāng)前位置P_current的簇心S_sen與放車(chē)區(qū)域之間的最短路徑作為用車(chē)區(qū)域到放車(chē)區(qū)域的路徑，并對(duì)每條路徑進(jìn)行評(píng)測(cè)排序，完成用車(chē)區(qū)域的K近鄰放車(chē)區(qū)域推薦。

采用Dijkstra算法作為尋路策略，完成對(duì)基于起始位置P_start、P_termination的最短路徑計(jì)算。Dijkstra算法可以找到從一個(gè)頂點(diǎn)s到任何其它頂點(diǎn)的最低權(quán)重路徑，本文采用Dijkstra算法找到離用車(chē)區(qū)域路徑最短的top-K個(gè)放車(chē)區(qū)域，該算法通過(guò)距離權(quán)值SP找到最短距離路徑。

2.2.2買(mǎi)時(shí)路況

本文通過(guò)基于滑動(dòng)窗口的軌跡流聚類(lèi)方法獲得各路段基于時(shí)間T_current的實(shí)時(shí)速度，需要對(duì)用車(chē)區(qū)域到搬遷源區(qū)域的每條路徑進(jìn)行實(shí)時(shí)路況評(píng)測(cè)。將道路交通狀況分為3種：速度低于30km/h的將其視為交通擁塞（以紅色標(biāo)記），速度在[30km/h，60km/h]范圍內(nèi)定義為交通緩慢（以黃色標(biāo)記），速度超過(guò)60km/h的定義為交通暢通（以綠色標(biāo)記）。

2.2.3搬遷路徑推薦

每個(gè)放車(chē)區(qū)域到用車(chē)區(qū)域有眾多路徑，需要找到交通狀況良好的前K條路徑。根據(jù)擁堵比例評(píng)測(cè)交通狀況，首先需要計(jì)算出各路段的速度，采用基于滑動(dòng)窗口模型的軌跡流聚類(lèi)關(guān)注最近時(shí)段到達(dá)的車(chē)輛行駛軌跡，將其劃分成簇以實(shí)時(shí)提取各簇的移動(dòng)行為模式，繼而實(shí)現(xiàn)對(duì)各簇所在路段的實(shí)時(shí)交通狀況評(píng)測(cè)，將交通擁堵和交通緩慢的路段長(zhǎng)度和總路徑長(zhǎng)度進(jìn)行比例分析，并對(duì)所有路徑按擁堵比例排序，從而完成到用車(chē)區(qū)域各K鄰近放車(chē)區(qū)域的搬遷路徑推薦。擁堵比例計(jì)算如下：

3實(shí)驗(yàn)

3.1實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

本文實(shí)驗(yàn)采用上海2015年4月共30天的共享單車(chē)軌跡數(shù)據(jù)集，該數(shù)據(jù)集包含近30000輛共享單車(chē)的近5萬(wàn)條GPS軌跡數(shù)據(jù)。離線階段首先采用共享單車(chē)歷史軌跡數(shù)據(jù)C₁提取用車(chē)區(qū)域和放車(chē)區(qū)域，在線階段采用出租車(chē)軌跡數(shù)據(jù)C₂模擬實(shí)時(shí)到達(dá)軌跡，通過(guò)各時(shí)段內(nèi)實(shí)時(shí)到達(dá)的出租車(chē)軌跡分析路網(wǎng)交通情況，利用C₁提取各時(shí)段內(nèi)的用車(chē)區(qū)域和放車(chē)區(qū)域，并利用C₂對(duì)實(shí)時(shí)交通路況進(jìn)行評(píng)測(cè)。實(shí)驗(yàn)使用Java語(yǔ)言實(shí)現(xiàn)算法編寫(xiě)，并在Windows 7操作系統(tǒng)、機(jī)器配置為2.50GHz Intel Core i5處理器和12GB物理內(nèi)存的PC機(jī)上運(yùn)行。

3.2對(duì)比方法

本文提出的DPT算法，是對(duì)用車(chē)點(diǎn)和放車(chē)點(diǎn)進(jìn)行時(shí)空聚類(lèi)，預(yù)測(cè)用車(chē)和放車(chē)頻率的方法。采用的對(duì)比方法如下：

Multi-Similarity-based Inference（MSI）法考慮天氣、溫度、風(fēng)速和時(shí)間相似性預(yù)測(cè)用車(chē)需求。其相似性函數(shù)是這3個(gè)相似性的乘法，而這幾個(gè)因素的權(quán)重沒(méi)有被研究。

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

Muhi-Similarity-Equally-Weighted KNN（MSEWK）方法是對(duì)影響需求預(yù)測(cè)的不同因素采取相同的權(quán)值，運(yùn)用混合高斯算法預(yù)測(cè)需求。

采用的性能衡量標(biāo)準(zhǔn)是對(duì)每個(gè)時(shí)段用車(chē)頻率和放車(chē)頻率預(yù)測(cè)的平均絕對(duì)誤差。評(píng)測(cè)標(biāo)準(zhǔn)表示為MAE，如下：

3.3實(shí)驗(yàn)結(jié)果

3.3.1用車(chē)頻率及放車(chē)頻率預(yù)測(cè)

本文提出的預(yù)測(cè)用車(chē)頻率的DPT算法性能如圖2所示。可以看出，多源因素模型（MSI和MSEWK）雖然優(yōu)于傳統(tǒng)單因素統(tǒng)計(jì)預(yù)測(cè)模型（IPPI，HM），但是對(duì)用車(chē)頻率時(shí)空聚類(lèi)的DPT法的錯(cuò)誤率低于其它方法。

在放車(chē)頻率預(yù)測(cè)上，本文方法優(yōu)于其它結(jié)合多因素預(yù)測(cè)方法，如圖3所示，這充分證明了本文方法的有效性。

3.3.2搬遷優(yōu)化

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

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

4結(jié)語(yǔ)

為滿(mǎn)足不同時(shí)段共享單車(chē)用車(chē)需求并解決單車(chē)搬遷效率問(wèn)題，本文提出了一個(gè)兩階段的共享單車(chē)搬遷策略框架，該框架能準(zhǔn)確預(yù)測(cè)各時(shí)段的用車(chē)需求及放車(chē)區(qū)域，并結(jié)合實(shí)時(shí)路況推薦單車(chē)搬遷路徑?；诠蚕韱诬?chē)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，DPT算法能精確預(yù)測(cè)用車(chē)需求、發(fā)現(xiàn)放車(chē)區(qū)域，所提出的搬遷優(yōu)化模型能有效提升共享單車(chē)搬遷效率。在未來(lái)工作中，擬結(jié)合包括天氣、日期、POI數(shù)據(jù)等提取多源外部特征，對(duì)軌跡數(shù)據(jù)與外部特征進(jìn)行統(tǒng)一建模，進(jìn)一步提升單車(chē)搬遷策略的有效性。