基于出租車經(jīng)驗路徑相似性的路徑規(guī)劃方法

鄧 悅 孟俊貞 趙東保

(1. 華北水利水電大學(xué) 測繪與地理信息學(xué)院, 河南 鄭州 450046;2. 華北水利水電大學(xué) 地球科學(xué)與工程學(xué)院, 河南 鄭州 450046)

0 引言

基于位置服務(wù)技術(shù)和定位技術(shù)的快速發(fā)展,海量出租車軌跡數(shù)據(jù)被記錄下來。這些數(shù)據(jù)含有重要的歷史經(jīng)驗知識,如出租車司機在考慮路徑距離、道路等級、動態(tài)路況和周圍環(huán)境等情況下得到的行駛經(jīng)驗和城市交通網(wǎng)中出租車的行駛規(guī)律等信息。如何從出租車軌跡中提取有價值的路徑信息已成為一個研究熱點。

傳統(tǒng)路徑規(guī)劃算法沒有考慮到出租車軌跡數(shù)據(jù)的經(jīng)驗知識,一般都是通過計算車輛在基于城市路網(wǎng)的時間最短路徑和空間最短路徑[1-3],并將符合時間和空間距離最短路徑是為最流行推薦路徑。近年來,在國內(nèi)外車輛導(dǎo)航研究中,人們開始更加重視交通狀況及駕駛員經(jīng)驗等因素。一些學(xué)者[4-6]從出租車軌跡數(shù)據(jù)中提取到大量有歷史經(jīng)驗的信息,并基于出租車軌跡的路徑規(guī)劃算法,獲取實際行駛過程中的最流行路徑。文獻(xiàn)[7-8]根據(jù)大量的出租車全球定位系統(tǒng)(global positioning system，GPS)數(shù)據(jù)找出聚集區(qū),確定候選車站集并簡化為有效公交車路線,從中選取最理想交通路線。文獻(xiàn)[9]通過研究出租車司機經(jīng)驗建立經(jīng)驗知識模型并基于此模型實現(xiàn)經(jīng)驗道路等級的劃分,然后結(jié)合司機駕駛的經(jīng)驗提出基于出租車司機經(jīng)驗知識建模的路徑規(guī)劃算法。文獻(xiàn)[10]基于出租車經(jīng)驗知識利用貝葉斯分類器對路網(wǎng)分層后得到分層路網(wǎng),然后使用分層路徑規(guī)劃算法實現(xiàn)層次路徑規(guī)劃。文獻(xiàn)[11]基于潛能模型并考慮到人口分布、交通路網(wǎng)特征、興趣點分布等因素,提出城市可達(dá)性的計算方法。文獻(xiàn)[12]以交通情況和司機行駛信息為基礎(chǔ)構(gòu)建云系統(tǒng)并通過計算得到同時滿足個性化和實際情況的最短路徑,該系統(tǒng)可以預(yù)測未來一段時間內(nèi)交通情況。文獻(xiàn)[13]基于出租車經(jīng)驗知識的基礎(chǔ),提出一種深度Q-learning算法,得到不同時間段內(nèi)OD(交通起止點)間最快路徑。

本文從出租車軌跡數(shù)據(jù)中篩選到有效的軌跡數(shù)據(jù),并將其地圖匹配[14-15]到城市道路網(wǎng)中得到車輛行駛路徑,通過計算兩個道路節(jié)點間路徑相似度得到相似度均值最大的路徑。綜合行駛路徑數(shù)量、路徑通行時間和路徑長度三個影響因素分析上述路徑是否為最流行推薦路徑。

1 算法思路

人們出行一般選擇距離最短或者時間最短的路徑,但出租車司機會在考慮路徑通行時間和空間外,把路段擁堵程度、車流量、紅綠燈、道路等級等外界因素也考慮在內(nèi)。能夠選擇在某一時間段內(nèi)較通暢且到達(dá)目的地時間和路徑相對較短的路徑。本文通過分析出租車的軌跡數(shù)據(jù)進(jìn)一步了解道路網(wǎng)結(jié)構(gòu),并結(jié)合出租車司機的經(jīng)驗知識得到兩個道路節(jié)點間與其他行駛路徑相似度最大的路徑,結(jié)合行駛路徑數(shù)量、路徑通行時間和路徑長度這三個指標(biāo)綜合分析確定上述路徑是否為最流行推薦路徑。以下是技術(shù)路線:

首先,將獲取到的原始GPS軌跡點數(shù)據(jù)進(jìn)行預(yù)處理,從軌跡中剔除噪聲數(shù)據(jù)(包括定位漂移導(dǎo)致的定位異常的軌跡點、不隨時間變化的軌跡點和速度為0的軌跡點等)。

然后,在現(xiàn)有道路網(wǎng)的基礎(chǔ)上,將篩選后的出租車軌跡點數(shù)據(jù)匹配到相應(yīng)路段上,得到出租車行駛路徑。

接著,把最大公共子序列作為衡量軌跡間相似性的度量,計算道路節(jié)點間所有行駛路徑的相似度,得到與其他路徑相似度最大的路徑,將其初步定位推薦路徑。

最后,結(jié)合行駛路徑數(shù)量、路徑通行時間和路徑長度這三個指標(biāo)分析上述路徑是否為最流行推薦路徑。

技術(shù)路線如圖1所示。

圖1 技術(shù)路線

2 概念定義

出租車軌跡數(shù)據(jù)進(jìn)行挖掘分析前,給出如下定義:

(1)定義1(軌跡)。將移動對象產(chǎn)生的軌跡點按照時間先后順序排序組成序列,即軌跡Tj={P1,P2,…,Pq}。

(2)定義2(道路網(wǎng))。道路網(wǎng)是一個圖,由道路節(jié)點和路段組成。定義為G=(N,S),其中N={N1,N2,…,Nn}是道路網(wǎng)中n個道路節(jié)點的集合,S={s1,s2,…,sm}是道路網(wǎng)中m個路段的集合。

(3)定義3(行駛路徑)。由一系列連續(xù)路段所組成的車輛行駛軌跡稱為行駛路徑,即R={s1,…,sn}。

(4)定義4(地圖匹配)。將一系列有序的軌跡點關(guān)聯(lián)到道路網(wǎng)上形成行駛路徑的過程稱為地圖匹配。

3 出租車路徑相似性分析的路徑規(guī)劃

3.1 最大公共子序列計算路徑相似度

不同的出租車司機，基于經(jīng)驗知識在任意兩個道路節(jié)點間，會產(chǎn)生不同的行駛路徑,但大多數(shù)出租車司機會選擇路況較好,距離較短的行駛路徑。本文通過計算兩個道路節(jié)點間所有出租車歷史軌跡的相似度,得到除本身外與其他所有行駛路徑相似度最大的路徑,并對所有行駛路徑長度和熱點路段圖中包含的行駛路徑車流量進(jìn)行分析,進(jìn)一步判斷上述路徑是否為最流行推薦路徑。

用最長公共子序列衡量軌跡間相似性,最長公共子序列是在一個序列集合中查找所有序列中最長子序列的問題。最長公共子序列只需保持子軌跡與原字符串相對順序一致,并不要求連續(xù),如兩個字符串“abcadf”,“acbad”的最長公共子序列為“abad”。用道路節(jié)點代替字符串后得到路徑的最長公共子序列,具體步驟如下:

(1)篩選候選路徑。出租車軌跡經(jīng)地圖匹配后得到行駛路徑,從中篩選道路節(jié)點N1與道路節(jié)點N2之間的所有行駛路徑。

(2)計算任意兩個行駛路徑之間的最大公共子序列。在此使用動態(tài)規(guī)劃求解最大公共子序列,公式(1)為動態(tài)規(guī)劃的遞歸方程,二維數(shù)組dp[i][j]表示行駛路徑L1的i位路段和行駛路徑L2的j位之前的最大公共子序列的長度。

(1)

式中,dp[i][j]中最大的數(shù)便是L1,L2的最大公共子序列的長度。

(3)計算行駛路徑間相似度。兩個行駛路徑間相似度可由最大公共子序列決定,軌跡間相似性計算公式為

(2)

式中,lLCS為兩條行駛路徑的最大公共子序列長度;lL1、lL2分別為兩條路徑長度;msi為兩條路徑的相似度。

(4)初步得到最流行推薦路徑。計算每條行駛路徑與其他行駛路徑間相似度均值并排序,相似度均值較大的幾條路徑。計算公式如式(3)

(3)

式中,k為道路節(jié)點N1與道路節(jié)點N2之間所有行駛路徑數(shù)量。

3.2 可靠性分析

根據(jù)相似度得到相似度均值較大的路徑后,結(jié)合行駛路徑數(shù)量、路徑通行時間和路徑長度進(jìn)一步分析上述路徑中哪一條為最流行推薦路徑。給定兩個道路節(jié)點A,B,從A開始到B終止的路徑數(shù)量,即行駛路徑數(shù)量。路徑通行時間和路徑長度采用同一種無量綱歸一化處理,以所有路徑中第j條行駛路徑Rj={S1,…,Sh}(0

式中,TSh、TS1表示出租車在Sh、S1道路節(jié)點處時間;TRj表示兩個道路節(jié)點間所有路徑中第j條路徑的通行時間;Min(T)表示路徑中通行時間最短路徑的時間。路段長度的無量綱歸一化處理方法為

(6)

式中,li表示路徑中路段長度;Min(E)表示路徑中長度最短路徑的長度。

根據(jù)行駛路徑數(shù)量和路徑通行時間、路段長度的無量綱歸一化后的值,根據(jù)出租車在兩小時內(nèi)的數(shù)據(jù)量,設(shè)定兩個道路節(jié)點間行駛路徑數(shù)量的閾值為K,若行駛路徑數(shù)量小于K,表明這兩個道路節(jié)點間樣本數(shù)量不足,且相似度均值最大的行駛路徑不具備代表性;反之,繼續(xù)分析路徑通行時間和長度這2個影響因素,無量綱歸一化處理后路徑通行時間的值和路徑長度的值均在0～1之間,2個值越趨近1,表明路徑通行時間越少和路徑的長度越短。綜合相似度均值和無量綱歸一化處理后路徑通行時間值和路徑長度值,得到最流行推薦路徑。

4 實驗比較和分析

實驗數(shù)據(jù)主要包括道路網(wǎng)數(shù)據(jù)和出租車GPS軌跡數(shù)據(jù),本文使用的道路數(shù)據(jù)是南京市交通道路電子地圖,路段數(shù)為9 332,道路節(jié)點數(shù)為5 849。出租車GPS軌跡數(shù)據(jù)為南京市出租車2010年1月19日17:00至19:00的軌跡數(shù)據(jù),有約8 000條有效軌跡,約20 200 000個GPS軌跡點,采樣時間間隔為30 s。

根據(jù)出租車軌跡數(shù)量,將兩個道路節(jié)點間行駛路徑數(shù)量閾值定為10條。如圖2所示,任選兩個道路節(jié)點,從出租車的經(jīng)驗軌跡數(shù)據(jù)中提取到的起始和終止道路節(jié)點相同行駛路徑有10條等于閾值,表明給定的道路節(jié)點間的相似度均值最大的路徑具有代表性。圖2中路徑3、4、5表示的是同一條路徑。其余每條行駛路徑雖有不同,也存在重疊路段。

圖2 出租車行駛路徑

根據(jù)第3章中基于最大公共子序列計算出租車經(jīng)驗路徑相似度,得到這兩個道路節(jié)點內(nèi)所有行駛路徑與其他路徑的相似度均值Mavg如表1所示。由表1可以得,與Mavg值超過0.35的路徑分別為路徑3、4、5、8,其中3、4、5表示的是同一條路徑。

為得到最流行推薦路徑,需結(jié)合路徑通行時間和路徑長度進(jìn)行分析,表2為路徑行駛時間和路徑長度及兩者無量綱歸一化后結(jié)果。由表2可得,對比路徑通行時間,路徑3的通行時間最短。表示同一條路徑的路徑4,5通行時間歸一化值均大于0.85,表明相比其他路徑,路徑4,5的通行時間也相對較短。對比路徑長度,路徑8的長度最短。表示同一條路徑的3,4,5長度歸一化值為0.98趨近于1,表明路徑3,4,5的長度也較短。綜合上述影響因素,最流行推薦路徑為相似度均值最大的路徑3、4、5所表示的同一條路徑。

5 結(jié)束語

本文通過對出租車采集的歷史軌跡數(shù)據(jù)統(tǒng)計和分析,研究行駛過程中出租車司機對道路路段選擇的經(jīng)驗知識,通過計算兩個道路節(jié)點間所有路徑的相似度均值得到相似度均值較大的路徑,結(jié)合兩個道路節(jié)點間出租車行駛路徑數(shù)量、每個路徑通行時間和路段長度綜合分析得到出租車的最流行推薦路徑。本文對南京市道路網(wǎng)和出租車數(shù)據(jù)進(jìn)行實驗,結(jié)果表明,本文路徑規(guī)劃算法得到的最流行推薦路徑,代表性強,通行時間和通行距離也較短,更加符合人們認(rèn)知的出行方式。