鄧 悅 孟俊貞 趙東保

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

0 引言

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

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

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

1 算法思路

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

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

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

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

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

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

圖1 技術(shù)路線

2 概念定義

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

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

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

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

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

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

3.1 最大公共子序列計(jì)算路徑相似度

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

3.2 可靠性分析

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

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

(6)

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

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

4 實(shí)驗(yàn)比較和分析

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

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

圖2 出租車行駛路徑

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

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

5 結(jié)束語(yǔ)

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