戚 欣，梁偉濤，馬 勇

(1.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430063； 2.武漢理工大學(xué) 航運(yùn)學(xué)院，武漢 430063) (*通信作者電子郵箱liangweitao0726@163.com)

基于出租車軌跡數(shù)據(jù)的最優(yōu)路徑規(guī)劃方法

戚 欣1，梁偉濤1*，馬 勇2

(1.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430063； 2.武漢理工大學(xué) 航運(yùn)學(xué)院，武漢 430063) (*通信作者電子郵箱liangweitao0726@163.com)

針對(duì)傳統(tǒng)的路徑規(guī)劃算法并不一定能計(jì)算得到現(xiàn)實(shí)中最優(yōu)路徑的問(wèn)題，提出一種融合了出租車駕駛經(jīng)驗(yàn)并以時(shí)間為度量的路徑規(guī)劃算法。該算法的實(shí)現(xiàn)是將路徑規(guī)劃這個(gè)以計(jì)算為中心的技術(shù)變?yōu)橐詳?shù)據(jù)為中心的數(shù)據(jù)驅(qū)動(dòng)挖掘技術(shù)。首先，從大量的出租車軌跡數(shù)據(jù)中提取真實(shí)的載人軌跡數(shù)據(jù)，并將載人軌跡數(shù)據(jù)匹配到路網(wǎng)數(shù)據(jù)中；然后，根據(jù)地圖匹配結(jié)果計(jì)算路段的訪問(wèn)頻次，選取前Top-k個(gè)路段作為熱點(diǎn)路段；其次，計(jì)算熱點(diǎn)路段間行車軌跡的相似度，對(duì)軌跡進(jìn)行聚類分析，在路網(wǎng)的基礎(chǔ)上構(gòu)建該k個(gè)路段的熱點(diǎn)路段圖；最后，使用一種改進(jìn)的A*算法實(shí)現(xiàn)路徑規(guī)劃。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的最短路徑規(guī)劃算法和基于駕駛經(jīng)驗(yàn)路網(wǎng)分層的路徑規(guī)劃算法相比，所提出的基于熱點(diǎn)路段圖的路徑規(guī)劃方法有效地縮短規(guī)劃路徑的長(zhǎng)度及路徑行駛時(shí)間，提高路徑規(guī)劃的用時(shí)效率。

智能交通；出租車駕駛經(jīng)驗(yàn)；改進(jìn)A*算法；熱點(diǎn)路段圖；路徑規(guī)劃

0 引言

隨著定位技術(shù)和移動(dòng)計(jì)算技術(shù)的發(fā)展，產(chǎn)生了大量的出租車軌跡數(shù)據(jù)，這些軌跡數(shù)據(jù)中包含出租車司機(jī)的歷史經(jīng)驗(yàn)以及交通路網(wǎng)的車輛行駛規(guī)律等重要信息。如何從出租車歷史數(shù)據(jù)中提取有用的路徑信息，并將這些信息用于新路徑的計(jì)算是相關(guān)學(xué)者一直研究的熱點(diǎn)問(wèn)題[1]。

傳統(tǒng)的路徑規(guī)劃算法并沒(méi)有將出租車軌跡數(shù)據(jù)中的經(jīng)驗(yàn)知識(shí)考慮進(jìn)來(lái)，而是在獲得城市路網(wǎng)信息后計(jì)算車輛行駛時(shí)間和車輛行駛距離的最短路徑，并將符合時(shí)間和距離最短的路徑視為最短路徑?；诔鲎廛囓壽E數(shù)據(jù)的路徑規(guī)劃算法可以從大量出租車軌跡數(shù)據(jù)中提取歷史經(jīng)驗(yàn)信息，并從中獲取考慮綜合信息后的實(shí)際行駛中的最優(yōu)路徑。文獻(xiàn)[2]在考慮司機(jī)駕駛經(jīng)驗(yàn)的基礎(chǔ)上，建立經(jīng)驗(yàn)路徑數(shù)據(jù)庫(kù)，并修正不完整和不正常的路徑。Yuan等[3-4]在考慮司機(jī)駕駛經(jīng)驗(yàn)的基礎(chǔ)上，使用基于方差的熵聚類方法估計(jì)行程時(shí)間的概率分布，并設(shè)計(jì)了兩步路徑算法去計(jì)算實(shí)際中最快和個(gè)性化的路徑。唐爐亮等[5]采用平滑方法實(shí)現(xiàn)經(jīng)驗(yàn)道路的等級(jí)劃分，并結(jié)合司機(jī)駕駛的經(jīng)驗(yàn)，提出了基于出租車經(jīng)驗(yàn)知識(shí)建模的路徑規(guī)劃算法。文獻(xiàn)[6]中通過(guò)獲取交通狀況和司機(jī)駕駛行為的信息建立一個(gè)云系統(tǒng)來(lái)計(jì)算個(gè)性化路徑和符合實(shí)際情況且可以最快到達(dá)目的地的路徑，該系統(tǒng)可以預(yù)測(cè)未來(lái)一段時(shí)間內(nèi)的交通狀況。Vincent等[7]基于用戶的軌跡數(shù)據(jù)和排序的協(xié)作張量和矩陣分解模型的方法開發(fā)了一個(gè)移動(dòng)推薦系統(tǒng)。當(dāng)存在大量的比較原始的出租車軌跡數(shù)據(jù)時(shí)，需要解決地圖匹配的問(wèn)題，文獻(xiàn)[8]中提出基于相互投票的地圖匹配算法(Interactive Voting-based Map Matching, IVMM)，解決了全球定位系統(tǒng)(Global Positioning System, GPS)跟蹤數(shù)據(jù)低采樣率的問(wèn)題。文獻(xiàn)[9]中提出使用多跟蹤地圖匹配的方法同時(shí)匹配多個(gè)地圖集。此外，Li等[10]在基于出租車歷史軌跡數(shù)據(jù)的基礎(chǔ)上提出一種分層路徑規(guī)劃算法，并結(jié)合Dijkstra算法遍歷已生成的分層路網(wǎng)。Hu等[11]利用行程頻次和速度信息分割道路，并構(gòu)建經(jīng)驗(yàn)分層路網(wǎng)，驗(yàn)證了經(jīng)驗(yàn)最優(yōu)路徑在不同時(shí)間段都可以獲得，尤其是在高峰時(shí)間段。

本文從大量的出租車軌跡數(shù)據(jù)中提取真實(shí)的載人GPS軌跡數(shù)據(jù)，并將GPS軌跡數(shù)據(jù)匹配到路網(wǎng)數(shù)據(jù)中，然后根據(jù)地圖匹配的結(jié)果統(tǒng)計(jì)路段的訪問(wèn)頻次，選取前k個(gè)路段作為熱點(diǎn)路段，在路網(wǎng)的基礎(chǔ)上構(gòu)建k個(gè)路段的熱點(diǎn)路段圖，最后，使用一種改進(jìn)的A*算法實(shí)現(xiàn)路徑規(guī)劃。本文的主要貢獻(xiàn)體現(xiàn)在以下兩方面，一是挖掘并充分應(yīng)用軌跡數(shù)據(jù)中的隱含信息，將傳統(tǒng)的以側(cè)重路徑計(jì)算為中心的路徑規(guī)劃算法變?yōu)橐詳?shù)據(jù)為中心的數(shù)據(jù)驅(qū)動(dòng)算法，進(jìn)一步增加路徑規(guī)劃的合理性。這種數(shù)據(jù)驅(qū)動(dòng)算法并不像之前的路徑規(guī)劃算法，在城市路網(wǎng)的基礎(chǔ)上用相應(yīng)的最短路徑規(guī)劃算法去計(jì)算路網(wǎng)的最短路徑，而是借助于眾多的歷史軌跡數(shù)據(jù)，從歷史軌跡數(shù)據(jù)中充分提取司機(jī)的駕駛經(jīng)驗(yàn)智慧，并分析城市路網(wǎng)中存在的行車規(guī)律，將出租車司機(jī)的駕駛經(jīng)驗(yàn)充分融入到路網(wǎng)中，再結(jié)合路徑搜索策略進(jìn)一步規(guī)劃更符合人們出行路線。二是對(duì)經(jīng)驗(yàn)路網(wǎng)的改進(jìn)，傳統(tǒng)的經(jīng)驗(yàn)路網(wǎng)僅根據(jù)駕駛員的經(jīng)驗(yàn)獲取訪問(wèn)頻次較高的路段，而本文不僅根據(jù)駕駛經(jīng)驗(yàn)獲取高頻路段，而且對(duì)連接高頻路段的軌跡作了進(jìn)一步的聚類分析，從而得到更加精簡(jiǎn)的經(jīng)驗(yàn)路網(wǎng)，即熱點(diǎn)路段圖，在熱點(diǎn)路段圖的基礎(chǔ)上，使用改進(jìn)的A*算法可更高效快速地找到符合人們?nèi)粘３鲂械穆窂健?/p>

1 技術(shù)路線

城市道路中行駛著大量的出租車，出租車的載人軌跡在一定程度上反映城市道路的行駛規(guī)律，也蘊(yùn)含著司機(jī)的駕駛經(jīng)驗(yàn)智慧。在選擇行駛路徑時(shí)，出租車司機(jī)會(huì)根據(jù)以往駕駛經(jīng)驗(yàn)，考慮道路等級(jí)、紅綠燈數(shù)量、擁堵程度及周圍環(huán)境等各種因素。本文通過(guò)分析出租車載人軌跡數(shù)據(jù)進(jìn)一步了解道路結(jié)構(gòu)，獲取駕駛員的經(jīng)驗(yàn)智慧，將道路結(jié)構(gòu)、出租車司機(jī)的駕駛經(jīng)驗(yàn)與路徑搜索策略緊密結(jié)合，實(shí)現(xiàn)更加合理化的路徑規(guī)劃。

首先，對(duì)獲取到的出租車軌跡數(shù)據(jù)進(jìn)行預(yù)處理，從大量的軌跡數(shù)據(jù)中提取真實(shí)的載人軌跡數(shù)據(jù)，并剔除一些噪聲數(shù)據(jù)，包括時(shí)間數(shù)據(jù)無(wú)變化、速度為零且有載客的狀態(tài)、軌跡數(shù)據(jù)點(diǎn)較少、載客狀態(tài)錯(cuò)誤顯示等。

其次，在現(xiàn)有路網(wǎng)數(shù)據(jù)的基礎(chǔ)上，進(jìn)一步將獲取的出租車載人軌跡數(shù)據(jù)匹配到相應(yīng)的路段上，完成出租車載人GPS軌跡到路網(wǎng)數(shù)據(jù)的地圖匹配工作，使得在地圖上可直觀地顯示出租車的行駛軌跡。本文采用的地圖匹配算法是IVMM算法[8]，它對(duì)低采樣率GPS軌跡點(diǎn)到路網(wǎng)的匹配有較高的準(zhǔn)確性。

再次，根據(jù)地圖匹配的結(jié)果計(jì)算路網(wǎng)中路段被匹配到的次數(shù)，選取出租車司機(jī)較為傾向的路段，即熱點(diǎn)路段，以此構(gòu)建基于經(jīng)驗(yàn)道路的基礎(chǔ)熱點(diǎn)路段圖。

然后，統(tǒng)計(jì)分析熱點(diǎn)路段之間的行駛路徑與時(shí)間，本文把軌跡間的編輯距離作為軌跡相似性的度量，對(duì)熱點(diǎn)路段之間的行駛路徑進(jìn)行聚類分析，選取兩路段間最為合適的連接路徑，進(jìn)一步完善熱點(diǎn)路段圖的構(gòu)建。

最后，在熱點(diǎn)路段圖的基礎(chǔ)上，利用改進(jìn)的A*算法實(shí)現(xiàn)基于出租車經(jīng)驗(yàn)軌跡的路徑規(guī)劃算法。

主要技術(shù)路線流程如圖1所示。

圖1 技術(shù)流程

2 概念定義

針對(duì)出租車行為活動(dòng)軌跡進(jìn)行數(shù)據(jù)挖掘的分析研究工作，在數(shù)據(jù)處理之前作如下定義。

1)路段。路網(wǎng)數(shù)據(jù)中的一條路段可以是有方向的，它由兩個(gè)端點(diǎn)組成。例如，一條路段road=rs→re(rs看作從路段的起始端，re看作路段的終點(diǎn)端)。

2)路線。路線是由多個(gè)路段連接而成的，例如，路線r1→r2→r3→…→rn。在這里rk+1.s=rk.e，即相鄰的兩個(gè)路段，前一個(gè)路段的終點(diǎn)也是下一個(gè)路段的起點(diǎn)。

3)路網(wǎng)數(shù)據(jù)。路網(wǎng)數(shù)據(jù)是由路段的端點(diǎn)和路線組成的有方向的路網(wǎng)圖。

4)GPS位置點(diǎn)。由GPS定位技術(shù)記錄的位置點(diǎn)，每個(gè)GPS位置點(diǎn)由7個(gè)字段構(gòu)成，包含車牌號(hào)、采集時(shí)間點(diǎn)、緯度、經(jīng)度、車輛狀態(tài)、車速和行駛方向基本信息，表示為p=(name,T,Lat,Lng,status,v,angle)，name為車牌號(hào)，T為時(shí)間戳，Lat為緯度，Lng為經(jīng)度，status為載人狀態(tài)，v為行車速度，angle為行車方向。

5)GPS軌跡。由出租車GPS位置隨著時(shí)間變化按照順序連接成的空間序列印記。其中Tpi>Tpj(j>i)，Tpi為第i個(gè)位置點(diǎn)的時(shí)間，Tpj為第j個(gè)位置點(diǎn)的時(shí)間，這樣連續(xù)的GPS位置點(diǎn)序列形成的曲線印記即為GPS軌跡。

6)熱點(diǎn)路段。路網(wǎng)中的路段被訪問(wèn)頻次超過(guò)一定閾值時(shí)則稱該路段為熱點(diǎn)路段。

7)熱點(diǎn)路段圖。熱點(diǎn)路段圖是由熱點(diǎn)路段連接而成的路網(wǎng)。

3 出租車載人軌跡的提取

出租車的GPS軌跡信息中記錄了在當(dāng)前時(shí)刻下出租車的行駛狀態(tài)，每一條軌跡信息中包含車輛的采集時(shí)間點(diǎn)、經(jīng)緯度信息、車輛載客狀態(tài)、車速、行車方向等信息?？偟能壽E數(shù)據(jù)記錄了出租車運(yùn)營(yíng)的整體行駛狀態(tài)，其中有載客行駛和空載行駛兩種。軌跡信息中的車輛載客狀態(tài)用0和1分別表示出租車是空載狀態(tài)還是載客狀態(tài)，可選擇載客狀態(tài)為1的軌跡信息作為提取出租車駕駛經(jīng)驗(yàn)的軌跡數(shù)據(jù)集。因?yàn)楫?dāng)載有乘客時(shí)，出租車司機(jī)為追求最大化的經(jīng)濟(jì)利益會(huì)根據(jù)自己以往的駕駛經(jīng)驗(yàn)花費(fèi)最少的精力和時(shí)間把乘客送達(dá)他們的目的地，而這種包含經(jīng)驗(yàn)的行車路徑正是所需要獲取的數(shù)據(jù)。

在出租車的眾多行駛軌跡中，根據(jù)車輛載客狀態(tài)對(duì)軌跡進(jìn)行分割，并提取真實(shí)的載人軌跡數(shù)據(jù)，再對(duì)載人GPS軌跡數(shù)據(jù)進(jìn)行地圖匹配，這在一定程度上降低了地圖匹配的工作量。圖2為從一條出租車軌跡中提取出的真實(shí)載人路段序列。ST表示出租車的載客狀態(tài)，出租車的載客狀態(tài)(STATUS,ST)為0表示空載，ST=1表示載客。圖中p0，p1，…，,p9分別表示載人軌跡中的10個(gè)GPS軌跡采樣點(diǎn)，它們的載客狀態(tài)ST=1。從軌跡點(diǎn)中提取ST=1的GPS點(diǎn)，因?yàn)橹挥姓鎸?shí)的載人軌跡才能提取出有價(jià)值的駕駛經(jīng)驗(yàn)。

圖2 載人GPS軌跡的提取

圖3 候選路段和候選點(diǎn)集合示例圖

4 路徑規(guī)劃

4.1 熱點(diǎn)路段的選取

根據(jù)提取的載人GPS軌跡數(shù)據(jù)到路網(wǎng)匹配的結(jié)果，對(duì)城市路網(wǎng)各時(shí)段出租車在各路段的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并把路段訪問(wèn)次數(shù)作為城市道路片段被選取為熱點(diǎn)路段的依據(jù)，路段訪問(wèn)次數(shù)由下式計(jì)算:

(1)

(2)

其中：nei(t)為路段i在時(shí)間段t內(nèi)通過(guò)的所有載人軌跡的總和，m為載人軌跡總數(shù)，n為統(tǒng)計(jì)的路段總數(shù)，nall為所有路段的統(tǒng)計(jì)總數(shù)。nei(t)的值越大，表示在該時(shí)間段內(nèi)出租車司機(jī)越傾向于選擇路段i，也表示路段i為經(jīng)驗(yàn)上較好的路段。依據(jù)nei(t)的統(tǒng)計(jì)量，選擇出城市道路中的熱點(diǎn)路段。

4.2 構(gòu)建基于經(jīng)驗(yàn)軌跡的熱點(diǎn)路段

相較于基礎(chǔ)的經(jīng)驗(yàn)路網(wǎng)的構(gòu)建，本文基于前一部分中熱點(diǎn)路段的選取工作，對(duì)選取的熱點(diǎn)路段之間的連接賦予權(quán)值與語(yǔ)義，構(gòu)建更加精簡(jiǎn)且隱含更多行駛規(guī)律信息的熱點(diǎn)路段圖?，F(xiàn)有的軌跡處理方法主要關(guān)注的是發(fā)現(xiàn)頻繁軌跡模式，從歷史軌跡數(shù)據(jù)中挖掘有效的行駛軌跡，并將軌跡數(shù)據(jù)挖掘的結(jié)果運(yùn)用到相應(yīng)的研究中。文獻(xiàn)[12]基于連續(xù)時(shí)間貝葉斯網(wǎng)絡(luò)，提出了一種軌跡預(yù)測(cè)函數(shù)(PutMode)，可預(yù)測(cè)移動(dòng)對(duì)象的不確定性行駛軌跡，該函數(shù)在處理歷史軌跡數(shù)據(jù)過(guò)程中選用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚類算法對(duì)眾多移動(dòng)軌跡進(jìn)行聚類分析，進(jìn)一步移除噪聲軌跡，確保軌跡預(yù)測(cè)的準(zhǔn)確性。傳統(tǒng)的移動(dòng)對(duì)象的軌跡預(yù)測(cè)函數(shù)僅作用于給定有約束的道路上，當(dāng)面臨不利的環(huán)境因素時(shí)，如交通擁堵、惡劣天氣等，往往表現(xiàn)不佳。文獻(xiàn)[13]針對(duì)這一問(wèn)題，提出一種三合一的軌跡預(yù)測(cè)函數(shù)(Traplan),該函數(shù)可快速地預(yù)測(cè)移動(dòng)對(duì)象的運(yùn)行軌跡，且函數(shù)中采用一種基于密度的區(qū)域探測(cè)算法對(duì)軌跡數(shù)據(jù)模式進(jìn)行處理，挖掘軌跡運(yùn)行模式，保證移動(dòng)對(duì)象軌跡預(yù)測(cè)的準(zhǔn)確性。出租車通過(guò)兩路段之間的軌跡反映了司機(jī)對(duì)于該行駛路徑的喜好程度，這是出租車司機(jī)基于以往的經(jīng)驗(yàn)知識(shí)作出的合理選擇。熱點(diǎn)路段之間的連接存在眾多的選擇，不同的司機(jī)有不同的路徑選擇，但對(duì)于路況通順、時(shí)較少的路徑會(huì)是大多數(shù)司機(jī)的選擇，因此，本文對(duì)眾多經(jīng)過(guò)熱點(diǎn)路段之間的歷史軌跡進(jìn)行相似度計(jì)算，并作相應(yīng)的軌跡聚類分析，進(jìn)一步規(guī)范熱點(diǎn)路段圖的行車路線規(guī)劃。通過(guò)聚類分析選取多數(shù)司機(jī)共同認(rèn)可的行駛路徑作為熱點(diǎn)路段之間的較優(yōu)行駛路徑，為之后經(jīng)過(guò)熱點(diǎn)路段的出租車提供路徑選擇，熱點(diǎn)路段間的軌跡聚類工作可有效地解決熱點(diǎn)路段之間行車路徑的選擇問(wèn)題，使路徑規(guī)劃更加符合歷史經(jīng)驗(yàn)規(guī)律，而不僅僅是計(jì)算得到的理論結(jié)果。

針對(duì)熱點(diǎn)路段間的路徑連接問(wèn)題，本文從出租車載人軌跡中統(tǒng)計(jì)經(jīng)過(guò)兩個(gè)熱點(diǎn)路段且其間沒(méi)有包含其他熱點(diǎn)路段的所有軌跡，并截取以該兩熱點(diǎn)路段為起止點(diǎn)的軌跡片段作為用來(lái)統(tǒng)計(jì)連接熱點(diǎn)路段的軌跡集合。對(duì)這類軌跡進(jìn)行聚類分析，并把軌跡間的編輯距離[14]作為軌跡間的相似性度量。若兩個(gè)熱點(diǎn)路段間的行駛時(shí)間遠(yuǎn)超出租車的平均行駛時(shí)間，則認(rèn)為這兩個(gè)熱點(diǎn)路段之間不存在比較合適的直達(dá)路徑，可通過(guò)其他路徑實(shí)現(xiàn)熱點(diǎn)路段間的連接。

對(duì)于軌跡相似度的計(jì)算方法中，由于本文的軌跡是由經(jīng)過(guò)地圖匹配后獲取的路網(wǎng)中的路段連接而成，所以選用軌跡間的編輯距離計(jì)算軌跡之間的相似度。為了更加準(zhǔn)確地計(jì)算軌跡的相似性，本文采用一種改進(jìn)的實(shí)數(shù)代價(jià)編輯距離[15]作為軌跡間相似性的度量。該編輯距離采用歐幾里得距離作為兩位置點(diǎn)間的距離，并使用插入和刪除操作的代價(jià)函數(shù)作為操作前后被修改軌跡之間的差異。因?yàn)镚PS軌跡中的路段連接是按時(shí)序建立的,所以用插入和刪除操作的代價(jià)作為插入或刪除的坐標(biāo)與當(dāng)前狀態(tài)前一個(gè)坐標(biāo)的距離,而替換代價(jià)就用替換的兩個(gè)GPS位置之間的距離表示。插入、刪除，替換的實(shí)數(shù)代價(jià)編輯距離(Revised Edit distance with Real Penalty):

RERP(Tr1,Tr2)=

(3)

該計(jì)算公式是一個(gè)遞歸公式，式中:m、n分別為軌跡Tr1與Tr2的長(zhǎng)度；ri為Tr1軌跡序列的第i個(gè)路段，sj為Tr2軌跡序列的第j個(gè)路段；軌跡Rest(Tr1)={r1,r2,…,rm-1}為Tr1中除去當(dāng)前比較路段以后的剩余部分，Rest(Tr2)為Tr2軌跡剩余的部分。RERP(Tr1,Tr2)表示軌跡Tr1轉(zhuǎn)化為軌跡Tr2的消耗，所有的操作都作用于軌跡Tr1。3種編輯操作即插入操作、刪除操作和替換操作的代價(jià)公式分別為：

(4)

delete_cost(ri,sj)=

(5)

(6)

symmetricRERP=(RERP(Tr1,Tr2)+RERP(Tr2,Tr1))/2

(7)

利用上述公式可計(jì)算得到任意兩條軌跡間的對(duì)稱距離，即作為軌跡間的相似性度量。本文用來(lái)計(jì)算相似度的軌跡是軌跡中的一個(gè)片段，該片段不是出租車的一整條軌跡，而是一條軌跡中經(jīng)過(guò)兩熱點(diǎn)路段間的一部分軌跡片段，且軌跡片段是用軌跡點(diǎn)的匹配路段編號(hào)序列表示，因此軌跡片段包含的路段數(shù)量不多，在計(jì)算過(guò)程中可保證較高的效率。在實(shí)際的計(jì)算過(guò)程中，暫時(shí)不考慮軌跡的長(zhǎng)度，只需要提取多條軌跡路段中共同經(jīng)過(guò)這兩個(gè)熱點(diǎn)路段間的部分，再通過(guò)聚類分析選取連接兩熱點(diǎn)路段的最佳路徑。

本文選用DBSCAN聚類方法，在上述編輯距離的基礎(chǔ)上對(duì)經(jīng)過(guò)兩個(gè)熱點(diǎn)路段之間的軌跡路徑集進(jìn)行聚類分析，選取熱點(diǎn)路段間最為出租車司機(jī)認(rèn)可的行駛路徑作為連接路徑。

算法描述如下。

假設(shè)T代表經(jīng)過(guò)兩個(gè)熱點(diǎn)路段的所有行車軌跡集合。

軌跡ε空間近鄰 對(duì)于軌跡集合中的任意軌跡Tri，當(dāng)其他軌跡Trj與Tri的時(shí)空距離小于ε時(shí)，認(rèn)為軌跡Trj出現(xiàn)在軌跡Tri的ε空間近鄰，稱Trj是Tri的ε空間近鄰，D為軌跡數(shù)據(jù)集，Dis(Tri,Trj)表示軌跡Tri與Trj之間的距離，表達(dá)式如式(8)所示:

N(Tri)={Trj∈D|Dis(Tri,Trj)≤ε}

(8)

核心軌跡 任意軌跡Tri的ε空間鄰域內(nèi)至少保證最少積累數(shù)目為MinLen的軌跡集，那么稱該軌跡為核心軌跡，表達(dá)式如式(9)所示：

(9)

直接空間可達(dá)的軌跡 如果軌跡Trj在軌跡Tri的ε空間鄰域內(nèi)，并且Tri是核心軌跡，那么稱軌跡Trj是從軌跡Tri出發(fā)直接空間可達(dá)的軌跡。

空間可達(dá)軌跡 如果軌跡Trj出現(xiàn)在核心軌跡Tri的ε空間鄰域內(nèi)，軌跡Trm出現(xiàn)在核心軌跡Trj的ε空間鄰域內(nèi)且不出現(xiàn)在Tri的空間鄰域內(nèi)，則稱軌跡Trm是從軌跡Tri空間可達(dá)的。

空間連通的軌跡 如果存在軌跡Trj和Trm都是從軌跡Tri空間可達(dá)的，那么稱Trj和Trm是空間相連的。

實(shí)現(xiàn)基于空間鄰域密度的DBSCAN聚類算法時(shí)，可以選擇從任意路段開始，計(jì)算該路段與其他路段間的空間距離；統(tǒng)計(jì)滿足空間閾值ε范圍的路段個(gè)數(shù)，并將其與最少路段積累數(shù)MinLen進(jìn)行比較；若空間鄰域范圍內(nèi)的路段數(shù)目大于給定的最少路段積累數(shù)時(shí)，該路段即為核心路段，形成一個(gè)以該路段為核心的聚類簇，其鄰域內(nèi)的直接密度可達(dá)線段也將聚到該類中，再對(duì)這些線段按照同樣的方式依次進(jìn)行聚類擴(kuò)展，得到最終的聚類結(jié)果，即通過(guò)聚類分析出熱點(diǎn)路段之間的連接路徑。

基于編輯距離的聚類算法描述：

在第1階段，首先根據(jù)編輯距離計(jì)算公式軌跡之間的編輯距離，即進(jìn)行軌跡間的相似度計(jì)算，并計(jì)算軌跡段的ε-近鄰集合(第1)行～第6)行)。第2階段是對(duì)軌跡段進(jìn)行聚類(第7)行～第19)行)，首先初始化聚類ID和軌跡段聚類標(biāo)志，接下來(lái)遍歷軌跡段，并計(jì)算軌跡的近鄰域中的軌跡數(shù)量，若滿足聚類閾值則對(duì)軌跡進(jìn)行聚類ID標(biāo)記，同時(shí)擴(kuò)展聚類(第20)行～第30)行)到結(jié)束。

軌跡聚類算法偽代碼如下。

算法：Trajectory Clustering based on Edit Distance。

輸入：軌跡集合D={Tr1,Tr2,…,Trn}，相關(guān)參數(shù)：ε(近鄰閾值)，σ(近鄰數(shù)量閾值)。 輸出：軌跡聚類集合Clus={ClusTr1,…,ClusTri,…,ClusTrn}；核心軌跡簇CoreST={CoreST1,…,CoreSTi,…,CoreSTn}。 /*第1階段：軌跡相似度計(jì)算*/

1)

foreachTri,Trj∈D∧i≠jdo

2)

/*計(jì)算基于編輯距離的軌跡相似度*/

3)

CalculateEDIM(Tri,Trj);

4)

ifEDIM(Tri,Trj)≥εthen

5)

Nε(Tri)←Trj;

/*設(shè)定Tri的ε-近鄰集合*/

6)

End for

/*第2階段：對(duì)軌跡段進(jìn)行聚類*/

7)

SetclusterId=0;

/*初始化聚類數(shù)標(biāo)號(hào)，起初為0*/

8)

Mark all Trajectories as unclassified;

9)

foreachTri∈DandTriisunclassifieddo

10)

ifTriisvisited

/*判斷軌跡是否被分類過(guò)*/

11)

continuenexttrajectory;

12)

MarkTriasvisited;

13)

Nε(Tri)=regionQuery(Tri,ε);

14)

ifsizeof(Nε(Tri))<σ

15)

MarkTriasNoise

16)

else

17)

IncreaseclusterIdby1;

/*表示聚類數(shù)加1*/ /*擴(kuò)展軌跡的近鄰聚類*/

18)

ExpandCluster(Tri,Nε(Tri),clusterId,ε,σ);

19)

End for

/*對(duì)可達(dá)近鄰進(jìn)行聚類*/

20)

ExpandCluster(Tri,Nε(Tri),clusterId,ε,σ)

21)

addTritoclusterId

22)

for eachTrj∈Nε(Tri)′

/*遍歷近鄰域中的軌跡*/

23)

if Trjisnotvisited

24)

markTrjasvisited/*計(jì)算軌跡Trj的近鄰域*/

25)

Nε(Tri)′=regionQuery(Trj,ε)

26)

ifsizeof(Nε(Tri)′)≥σ

27)

Nε(Tri)=Nε(Tri) joined withNε(Tri)′

28)

ifTrjis not yet member of any cluster /*將軌跡Trj添加到類clusterId中*/

29)

AddTrjtoclusterId

30)

End for

基于編輯距離聚類算法的時(shí)間復(fù)雜度主要分為兩部分：第1部分是編輯距離算法的復(fù)雜度，其值是O(mn),m為軌跡Tr1的長(zhǎng)度，即Tr1的路段個(gè)數(shù)，n為軌跡Tr2的長(zhǎng)度，即Tr2的路段個(gè)數(shù)。第2部分是DBSCAN聚類算法的時(shí)間復(fù)雜度，最壞的情況為O(n2)，n為兩熱點(diǎn)路段間的軌跡片段條數(shù)。因?yàn)楸疚闹惺紫冗M(jìn)行的工作是地圖匹配，將軌跡中的軌跡點(diǎn)匹配到路網(wǎng)中相應(yīng)的路段上，然后采用路段編號(hào)集合代替軌跡點(diǎn)集合來(lái)表示一條軌跡，用兩熱點(diǎn)路段間的軌跡片段集合代替軌跡點(diǎn)集合進(jìn)行軌跡的聚類分析，因此軌跡片段的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于軌跡點(diǎn)的數(shù)目，所以在進(jìn)行聚類算法時(shí)不存在計(jì)算量太大的問(wèn)題。

4.3 基于熱點(diǎn)路段圖的路徑規(guī)劃

基于熱點(diǎn)路段的查找和路徑聚類分析所建立的熱點(diǎn)路段圖，可應(yīng)用路徑規(guī)劃算法在基礎(chǔ)路網(wǎng)和熱點(diǎn)路段圖中進(jìn)行路徑檢索。在路徑規(guī)劃中引入啟發(fā)信息能夠提高搜索的效率。A*算法是目前最流行的啟發(fā)式搜索算法，它通過(guò)選擇合適的估價(jià)函數(shù)，使其尋找最優(yōu)路徑的搜索范圍比原始Dijkstra算法要少很多。本文應(yīng)用一種改進(jìn)的A*算法[16]，該算法將當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)到原點(diǎn)的最短路徑、當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑和當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)的前一點(diǎn)到目標(biāo)節(jié)點(diǎn)最短路徑的三者之和作為從臨時(shí)標(biāo)記節(jié)點(diǎn)集合中選取永久標(biāo)記節(jié)點(diǎn)的依據(jù)。改進(jìn)A*算法的當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)j的估計(jì)函數(shù)定義為：

f*(i)=g(i)+h*(i)+h*(j)

(10)

其中：是從起點(diǎn)到當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)i的實(shí)際路徑的量度；是從當(dāng)前臨時(shí)標(biāo)記節(jié)點(diǎn)i到終點(diǎn)的最短路徑的估計(jì)；i，j為鄰近節(jié)點(diǎn)，且j為i的前一節(jié)點(diǎn)，i為j的后續(xù)節(jié)點(diǎn)。路徑尋優(yōu)算法采用的是改進(jìn)的A*算法，在式(10)的基礎(chǔ)上構(gòu)造的一個(gè)時(shí)變啟發(fā)函數(shù)：

F(i,T0)=λD[FD(i)+FDE(i)+FDE(j)]+λT[FT(i,T0)+FTE(i)+FTE(j)]+λS[FS(i,T0)+FSE(i)+FSE(j)]

(11)

其中：FD是車輛的行程指標(biāo)；FT是車輛行駛的時(shí)間指標(biāo)；FS是車輛行駛的威脅度指標(biāo)；λD、λT和λS分別是行程加權(quán)系數(shù)、時(shí)間加權(quán)系數(shù)和威脅加權(quán)系數(shù)，綜合指標(biāo)最優(yōu)的情況下，λD=3.5，λT=1和λS=1[14]；T0是車輛出發(fā)時(shí)刻；FDE(i)和FDE(j)分別是當(dāng)前節(jié)點(diǎn)和其父節(jié)點(diǎn)到終點(diǎn)的曼哈頓距離；FTE(i)和FSE(i)是當(dāng)前節(jié)點(diǎn)(xi,yi)到終點(diǎn)(xd,yd)的估價(jià)函數(shù)；FTE(j)和FSE(j)是父節(jié)點(diǎn)(xj,yj)到終點(diǎn)(xd,yd)的估價(jià)函數(shù)。根據(jù)該啟發(fā)函數(shù)的優(yōu)化結(jié)果，本文選取T0=0時(shí)，進(jìn)行最優(yōu)路徑的計(jì)算。

依據(jù)城市電子地圖路網(wǎng)數(shù)據(jù)以及熱點(diǎn)路段圖的信息，對(duì)于給定的起始位置數(shù)據(jù)，采用改進(jìn)的A*分層算法，本文利用3段尋徑的路徑查找策略實(shí)現(xiàn)車輛的最短路徑規(guī)劃計(jì)算。基本步驟如下：

1)首先根據(jù)給定的始末位置S、D兩點(diǎn)的GPS數(shù)據(jù)，并計(jì)算它們到熱點(diǎn)路段圖中最近熱點(diǎn)路段的距離，若距離小于一定的距離閾值，認(rèn)為起始位置位于熱點(diǎn)路段圖中，則應(yīng)用改進(jìn)A*算法在已建立的熱點(diǎn)路段圖中計(jì)算起始位置間的最優(yōu)路徑。

2)若起點(diǎn)S和終點(diǎn)D不在熱點(diǎn)路段圖中，設(shè)定以起點(diǎn)S和終點(diǎn)D為對(duì)角線形成的矩形區(qū)域R中存在熱點(diǎn)路段，則在R中以最短路徑算法搜索離S點(diǎn)最近的熱點(diǎn)路段圖入口S′路段，并且記錄S-S′，同理，在R中范圍內(nèi)的熱點(diǎn)路段圖中搜索終點(diǎn)D的出口D′，并記錄D-D′。應(yīng)用路徑規(guī)劃算法分別計(jì)算熱點(diǎn)路段圖外S至S′的最優(yōu)路徑P1、熱點(diǎn)路段圖內(nèi)S′至D′的最優(yōu)路徑P2和熱點(diǎn)路段圖外D′至D的最優(yōu)路徑P3。P1、P2和P3依次連接即是始末位置間的最優(yōu)路徑。

3)若起點(diǎn)S不屬于熱點(diǎn)路段圖中或終點(diǎn)D不屬于熱點(diǎn)路段圖，則應(yīng)用路徑規(guī)劃方法計(jì)算熱點(diǎn)路段圖外S至S′的最優(yōu)路徑L1或熱點(diǎn)路段圖外D′至D的最優(yōu)路徑L2,以及熱點(diǎn)路段圖內(nèi)S′至D′的最優(yōu)路徑P。L1和P的連接或L2和P的連接即是始末位置間的最優(yōu)路徑。

5 實(shí)驗(yàn)分析與比較

5.1 基礎(chǔ)數(shù)據(jù)

本文構(gòu)造的熱點(diǎn)路段圖所需要的實(shí)驗(yàn)數(shù)據(jù)主要包括基礎(chǔ)路網(wǎng)數(shù)據(jù)和出租車真實(shí)載人軌跡兩部分，其中基礎(chǔ)路網(wǎng)數(shù)據(jù)選取深圳市交通道路電子地圖數(shù)據(jù)，出租車GPS數(shù)據(jù)是深圳市1.3萬(wàn)多輛出租車在2011年4月18日至4月26日內(nèi)的GPS采樣點(diǎn)數(shù)據(jù)，經(jīng)過(guò)提取得到約19萬(wàn)條有效軌跡數(shù)據(jù)。每天不同的時(shí)間段內(nèi)，城市路網(wǎng)中的交通流會(huì)有所不同，且處于時(shí)刻變化中，出租車司機(jī)根據(jù)自己的駕駛經(jīng)驗(yàn)相應(yīng)地調(diào)整自己的行車路線適應(yīng)交通流的變化，以達(dá)到較快行駛的目的，因而對(duì)于路徑的規(guī)劃需要將時(shí)間這一重要因素考慮在內(nèi)。本文根據(jù)深圳市道路交通的特征與狀況，選擇4個(gè)具有代表性的時(shí)間段作為實(shí)驗(yàn)分析的依據(jù)，分別構(gòu)造不同時(shí)間段內(nèi)的熱點(diǎn)路段圖，并計(jì)算不同時(shí)間段內(nèi)的最優(yōu)行駛路徑。

當(dāng)前的路徑規(guī)劃算法一般分為基于路網(wǎng)數(shù)據(jù)的最短路徑規(guī)劃算法或在此基礎(chǔ)上改進(jìn)的最短路徑算法以及基于出租車駕駛經(jīng)驗(yàn)對(duì)路網(wǎng)進(jìn)行分層的最短路徑規(guī)劃算法，本文分別選取最短路徑(Shortest Path, SP)算法以及基于駕駛經(jīng)驗(yàn)路網(wǎng)分層的路徑(Experience Path, EP)規(guī)劃算法與本文的基于熱點(diǎn)路段圖的路徑(Hot-section Path, HP)規(guī)劃算法進(jìn)行對(duì)比。選取任意的20對(duì)起始-終止節(jié)點(diǎn)(Origin-Destination, OD)，利用這3種算法分別計(jì)算不同時(shí)間段內(nèi)起點(diǎn)和終點(diǎn)間的最優(yōu)路徑，并統(tǒng)計(jì)規(guī)劃路徑的長(zhǎng)度與所用時(shí)間來(lái)進(jìn)行相應(yīng)的比較。T表示時(shí)間段，每天不同時(shí)間段的劃分如表1所示。

5.2 路徑長(zhǎng)度對(duì)比

如圖4所示為4個(gè)不同時(shí)段內(nèi)的規(guī)劃路徑長(zhǎng)度對(duì)比。

利用SP、EP、HP這3種路徑規(guī)劃算法對(duì)隨機(jī)選擇的20個(gè)起止OD對(duì)進(jìn)行路徑規(guī)劃，并統(tǒng)計(jì)分析規(guī)劃路徑的長(zhǎng)度，結(jié)果如圖4所示。柱狀圖的高度表示路徑規(guī)劃算法規(guī)劃的每條路徑總長(zhǎng)度。根據(jù)柱體的高度可以得出，在距離上，相對(duì)EP和HP算法來(lái)說(shuō)，由SP算法規(guī)劃得到的路線距離較短，而EP和HP算法在計(jì)算路徑時(shí)由于趨向于所選取的經(jīng)驗(yàn)路段，因此容易發(fā)生繞路的現(xiàn)象。若OD對(duì)之間隔得很近，因?yàn)镺D對(duì)之間可能存在經(jīng)驗(yàn)路段，EP和HP算法會(huì)將相應(yīng)的經(jīng)驗(yàn)路段計(jì)入其中，但相較于EP算法，本文的HP算法計(jì)算得到的路徑距離略優(yōu)。對(duì)于EP算法和本文的HP算法，對(duì)比柱狀體高度可以得出，兩者計(jì)算得到的路徑在距離上相差較小。綜合比較4個(gè)時(shí)間段內(nèi)規(guī)劃的路徑總長(zhǎng)度，如圖5所示，可以看出處于高峰期時(shí)，OD對(duì)之間規(guī)劃的路徑長(zhǎng)度大于平峰期的路徑長(zhǎng)度。晚高峰時(shí)的規(guī)劃路徑長(zhǎng)度大于早高峰期的路徑長(zhǎng)度，夜間的平峰期的規(guī)劃路徑長(zhǎng)度大于日間的平峰期的規(guī)劃路徑長(zhǎng)度。

表1 時(shí)間段劃分

圖4 不同時(shí)間段的路徑長(zhǎng)度比

圖5 3種算法不同時(shí)間段的總路徑長(zhǎng)度對(duì)比

如圖6所示為4個(gè)不同時(shí)段內(nèi)的規(guī)劃路徑行程時(shí)間對(duì)比。

如圖6所示，分別對(duì)應(yīng)4個(gè)時(shí)間段內(nèi)3種算法規(guī)劃路徑的耗時(shí)時(shí)長(zhǎng)走向，3種不同類型的曲線代表3種路徑規(guī)劃算法。4個(gè)時(shí)間段表示城市中的4種交通流狀況，對(duì)比折線圖的變化可以發(fā)現(xiàn)，當(dāng)路程距離增加時(shí)，OD對(duì)路程較近的EP算法與本文的HP算法的耗時(shí)相對(duì)可能會(huì)高于最短路徑用時(shí)。路徑長(zhǎng)度超過(guò)10 km時(shí)，EP算法與HP算法趨向于花費(fèi)更少的時(shí)間，且用時(shí)相近。對(duì)比EP算法與HP算法，兩種算法在圖中走向近似且時(shí)間長(zhǎng)度也相近，但本文的HP算法優(yōu)于EP算法，統(tǒng)計(jì)結(jié)果如表2所示。表2中給出的路徑總規(guī)劃用時(shí)表示在經(jīng)過(guò)DBSACN聚類算法得到的熱點(diǎn)路段圖的基礎(chǔ)上使用改進(jìn)的A*算法進(jìn)行路徑規(guī)劃所用的時(shí)間，SP和EP算法分別是基于基礎(chǔ)路網(wǎng)和經(jīng)驗(yàn)路網(wǎng)實(shí)現(xiàn)的路徑規(guī)劃算法。相比這兩種算法，本文的算法是在對(duì)經(jīng)驗(yàn)路網(wǎng)的進(jìn)一步改進(jìn)后得到的熱點(diǎn)路段圖的基礎(chǔ)上實(shí)現(xiàn)的，首先根據(jù)出租車司機(jī)的經(jīng)驗(yàn)獲取經(jīng)驗(yàn)路段，并把經(jīng)驗(yàn)路段看作熱點(diǎn)路段，再對(duì)熱點(diǎn)路段之間的連接作聚類分析的工作，包括對(duì)經(jīng)過(guò)熱點(diǎn)路段之間的軌跡片段進(jìn)行相似度的計(jì)算實(shí)現(xiàn)軌跡的聚類分析，以及將聚類得到的軌跡作為連接兩個(gè)熱點(diǎn)路段的路徑，進(jìn)一步提煉經(jīng)驗(yàn)路網(wǎng)得到熱點(diǎn)路段圖，并把熱點(diǎn)路段圖作為路徑規(guī)劃的依據(jù)。HP算法是在熱點(diǎn)路段圖的基礎(chǔ)上實(shí)現(xiàn)的路徑規(guī)劃算法，相較于SP和EP算法所使用的基礎(chǔ)路網(wǎng)和經(jīng)驗(yàn)路網(wǎng)，用HP算法規(guī)劃路徑時(shí)考慮的路段更少，因此計(jì)算得到的規(guī)劃時(shí)間少于SP和EP算法的規(guī)劃用時(shí)。本文選取的20個(gè)OD對(duì)在4個(gè)時(shí)間段內(nèi)的測(cè)量結(jié)果中，HP算法相較于EP算法，實(shí)際路徑總長(zhǎng)度縮幅約為18.73%,總的用時(shí)縮幅約為11.64%。對(duì)比3種算法的計(jì)算用時(shí)，運(yùn)算時(shí)間在150 s～380 s，本文的算法計(jì)算用時(shí)為152 s，在規(guī)劃路徑用時(shí)上效率較高，有較大的計(jì)算優(yōu)勢(shì)。在柱狀圖7中顯示了4個(gè)時(shí)間段以及每個(gè)時(shí)間段內(nèi)的總耗時(shí)，對(duì)比4個(gè)時(shí)間段的柱狀體高度可以得出，早、晚高峰期的用時(shí)高于平峰期的用時(shí)，且晚高峰用時(shí)相對(duì)低于早高峰期。對(duì)比3種算法總的路徑耗時(shí)柱狀圖的高度可得出本文的HP算法規(guī)劃的路徑在行程時(shí)間上優(yōu)于EP算法和SP算法所規(guī)劃的路徑行程用時(shí)。

圖6 不同時(shí)間段的路徑行駛耗時(shí)對(duì)比

圖7 不同時(shí)間段3種算法的路徑總耗時(shí)對(duì)比

6 結(jié)語(yǔ)

本文通過(guò)分析出租車GPS軌跡數(shù)據(jù)的特點(diǎn)，提取真實(shí)的載人GPS軌跡數(shù)據(jù)，并實(shí)現(xiàn)軌跡數(shù)據(jù)到路網(wǎng)數(shù)據(jù)的地圖匹配。根據(jù)地圖匹配的結(jié)果，分析出租車行駛路線規(guī)律，并統(tǒng)計(jì)路網(wǎng)中路段的訪問(wèn)頻次，據(jù)此選取訪問(wèn)頻次較高的路段為熱點(diǎn)路段，進(jìn)而對(duì)連接熱點(diǎn)路段間的行車軌跡實(shí)現(xiàn)軌跡相似度的計(jì)算，完成路段之間真實(shí)載人軌跡的聚類分析。充分利用駕駛員的行車經(jīng)驗(yàn)實(shí)現(xiàn)熱點(diǎn)路段間的連接，并完善熱點(diǎn)路段圖的建立，且在此基礎(chǔ)上提出融合出租車駕駛經(jīng)驗(yàn)的路徑規(guī)劃方法。相比之前的路徑規(guī)劃算法，本文提出的方法在經(jīng)驗(yàn)分析和數(shù)據(jù)統(tǒng)計(jì)兩方面作了進(jìn)一步的研究：一是將傳統(tǒng)的以側(cè)重路徑計(jì)算為中心的路徑規(guī)劃方法變?yōu)橐詳?shù)據(jù)為中心的數(shù)據(jù)驅(qū)動(dòng)方法，充分利用了軌跡數(shù)據(jù)中的隱含信息；二是對(duì)經(jīng)驗(yàn)路網(wǎng)的改進(jìn)，傳統(tǒng)的經(jīng)驗(yàn)路網(wǎng)僅根據(jù)駕駛員的經(jīng)驗(yàn)獲取訪問(wèn)頻次較高的路段，以此構(gòu)建基礎(chǔ)的經(jīng)驗(yàn)路網(wǎng)，本文首先根據(jù)駕駛經(jīng)驗(yàn)獲取高頻路段，即熱點(diǎn)路段，然后對(duì)連接兩個(gè)熱點(diǎn)路段的軌跡進(jìn)行相似度的計(jì)算并作進(jìn)一步的聚類分析，以實(shí)現(xiàn)熱點(diǎn)路段圖中兩熱點(diǎn)路段的連接，從而得到更加精簡(jiǎn)的熱點(diǎn)路段圖，熱點(diǎn)路段圖的建立是對(duì)出租車司機(jī)經(jīng)驗(yàn)智能最大化的體現(xiàn)，在計(jì)算最短路徑時(shí)可更加注重軌跡數(shù)據(jù)挖掘所得到的知識(shí)，減少了常規(guī)的路徑計(jì)算，提高了路徑規(guī)劃的效率，最后在熱點(diǎn)路段圖的基礎(chǔ)上，使用改進(jìn)的A*算法可更高效快速地找到符合人們?nèi)粘３鲂械穆窂健?/p>

表2 路徑搜索相關(guān)參數(shù)

最后本文選取深圳市的路網(wǎng)數(shù)據(jù)與出租車載人軌跡數(shù)據(jù)，對(duì)路徑規(guī)劃的結(jié)果進(jìn)行比較分析，結(jié)果顯示本文提出的基于熱點(diǎn)路段圖的路徑規(guī)劃方法在行車時(shí)間上更優(yōu)，更具有出行指導(dǎo)意義。

References)

[1] ZHENG Y. Trajectory data mining: an overview [J].ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 29-70.

[2] ZHUANG L J, GONG J F, HE Z C, et al. Framework of experienced route planning based on taxis’ GPS data [C]// Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ: IEEE, 2012: 1026-1031.

[3] YUAN J, XIE X, ZHENG Y, et al. T-Drive: enhancing driving directions with taxi drivers’ intelligence [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 220-233.

[4] YUAN J, ZHENG Y, ZHANG C Y, et al. T-Drive: driving directions based on taxi trajectories [C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108.

[5] 唐爐亮,常曉猛,李清泉.出租車經(jīng)驗(yàn)知識(shí)建模與路徑規(guī)劃[J].測(cè)繪學(xué)報(bào),2010,39(4):406-412.(TANG L L, CHANG X M, LI Q Q. The knowledge modeling and route planning based on taxi’ experience [J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 406-412.)

[6] YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world [C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2011: 316-324.

[7] VINCENT W Z, ZHENG Y, XIE X, et al. Towards mobile intelligence: learning from GPS history data for collaborative recommendation [J].Artificial Intelligence, 2012, 184(1): 17-37.

[8] YUAN J, ZHENG Y, ZHANG C Y. An interactive-voting based map matching algorithm [C]// Proceedings of the 11th International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2010: 43-52.

[9] LI Y, HUANG Q X, KERBER M, et al. Large-scale joint map matching of GPS traces [C]// Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 214-223.

[10] LI Q Q, ZENG Z, ZHANG T, et al. Path-finding through flexible hierarchical road networks: an experiential approach using taxi trajectory data [J]. International Journal of Applied Earth, Observation & Geoinformation, 2011, 13(1): 110-119.

[11] HU J H, HUANG Z, DENG J. A hierarchical path planning method using the experience of taxi drivers [C]// Proceedings of the 13th COTA International Conference of Transportation Professionals. Amsterdam: Elsevier, 2013: 1898-1909.

[12] QIAO S J, HAN N, ZHU W, et al. TraPlan: an effective three-in-one trajectory prediction model in transportation networks [J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3): 1188-1198.

[13] QIAO S J, TANG C J, JIN H D, et al. PutMode: prediction of uncertain trajectories in moving objects databases [J]. Applied Intelligence, 2010, 33(3): 370-386

[14] LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions and reversals [J]. Soviet Physics Doklady, 1966, 10(8): 707-710.

[15] 劉坤,楊杰.基于編輯距離的軌跡相似性度量[J].上海交通大學(xué)學(xué)報(bào),2009,43(11):1725-1729.(LIU K,YANG J. Trajectory distance metric based on edit distance[J]. Journal of Shanghai Jiao Tong University, 2009, 43(11): 1725-1729.)

[16] 張翼,唐國(guó)金,陳磊.時(shí)相關(guān)車輛路徑規(guī)劃問(wèn)題的改進(jìn)A*算法[J].控制工程，2012,19(5):750-756.(ZHANG Y, TANG G J, CHEN L. Improved A*algorithm for time-dependent vehicle routing problem [J]. Control Engineering, 2012, 19(5): 750-756.)

This work is partially supported by the National Natural Science Foundation of China (51579202), the China Postdoctoral Foundation (2015T80848).

QIXin, born in 1978, Ph. D., associate professor. His research interests include Web data mining, intelligent Web system.

LIANGWeitao, born in 1990, M. S. candidate. His research interests include Web data mining, intelligent transportation.

MAYong, born in 1983, Ph. D., associate professor. His research interests include intelligent maritime security technology, unmanned craft path planning.

Optimalpathplanningmethodbasedontaxitrajectorydata

QI Xin1, LIANG Weitao1*, MA Yong2

(1.SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,WuhanHubei430063,China;2.SchoolofNavigation,WuhanUniversityofTechnology,WuhanHubei430063,China)

Focusing on the issue that the path calculated by traditional path planning algorithm is not necessarily the optimal path in reality, a path planning algorithm which combined the experience of taxi driving and took time as a measure was proposed. The implementation of this algorithm was to transform the path planning technology which took calculation as the center into data-driven mining technology which regarded data as the center. Firstly, the real manned trajectory data were extracted from a large number of taxi trajectory data and matched to the road network data. Then, the access frequency of the road segments were calculated according to the calculation results of map-matching, and Top-kroad sections were selected as hot sections; Secondly, the similarity of road tracks between hot sections was calculated, and the trajectories were clustered to buildksections of hot road map based on the road network. Finally, an improved A*algorithm was used to calculate the optimal path. The experimental results show that compared with the traditional shortest path planning algorithm and the path planning algorithm based on hierarchical road network, the path planning method based on hot section map can shorten the length of the planning path and the travel time and improve the time efficiency of path planning.

intelligent transportation; taxi driving experience; improved A*algorithm; hot section map; path planning

TP393.027; TP391

:A

2017- 01- 13;

:2017- 02- 25。

國(guó)家自然科學(xué)基金資助項(xiàng)目(51579202)；中國(guó)博士后基金資助項(xiàng)目(2015T80848)。

戚欣(1978—)，男，湖北武漢人，副教授，博士，主要研究方向：Web數(shù)據(jù)挖掘、智能Web系統(tǒng)； 梁偉濤(1990—)，男，山東臨沂人，碩士研究生，主要研究方向：Web數(shù)據(jù)挖掘、智能交通； 馬勇(1983—)，男，湖北棗陽(yáng)人，副教授，博士，主要研究方向：智能海事保障技術(shù)、無(wú)人艇路徑規(guī)劃。

1001- 9081(2017)07- 2106- 08

10.11772/j.issn.1001- 9081.2017.07.2106