基于出租車軌跡數據的最優路徑規劃方法

戚 欣，梁偉濤，馬 勇

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

基于出租車軌跡數據的最優路徑規劃方法

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

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

針對傳統的路徑規劃算法并不一定能計算得到現實中最優路徑的問題，提出一種融合了出租車駕駛經驗并以時間為度量的路徑規劃算法。該算法的實現是將路徑規劃這個以計算為中心的技術變為以數據為中心的數據驅動挖掘技術。首先，從大量的出租車軌跡數據中提取真實的載人軌跡數據，并將載人軌跡數據匹配到路網數據中；然后，根據地圖匹配結果計算路段的訪問頻次，選取前Top-k個路段作為熱點路段；其次，計算熱點路段間行車軌跡的相似度，對軌跡進行聚類分析，在路網的基礎上構建該k個路段的熱點路段圖；最后，使用一種改進的A*算法實現路徑規劃。實驗結果表明，與傳統的最短路徑規劃算法和基于駕駛經驗路網分層的路徑規劃算法相比，所提出的基于熱點路段圖的路徑規劃方法有效地縮短規劃路徑的長度及路徑行駛時間，提高路徑規劃的用時效率。

智能交通；出租車駕駛經驗；改進A*算法；熱點路段圖；路徑規劃

0 引言

隨著定位技術和移動計算技術的發展，產生了大量的出租車軌跡數據，這些軌跡數據中包含出租車司機的歷史經驗以及交通路網的車輛行駛規律等重要信息。如何從出租車歷史數據中提取有用的路徑信息，并將這些信息用于新路徑的計算是相關學者一直研究的熱點問題[1]。

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

本文從大量的出租車軌跡數據中提取真實的載人GPS軌跡數據，并將GPS軌跡數據匹配到路網數據中，然后根據地圖匹配的結果統計路段的訪問頻次，選取前k個路段作為熱點路段，在路網的基礎上構建k個路段的熱點路段圖，最后，使用一種改進的A*算法實現路徑規劃。本文的主要貢獻體現在以下兩方面，一是挖掘并充分應用軌跡數據中的隱含信息，將傳統的以側重路徑計算為中心的路徑規劃算法變為以數據為中心的數據驅動算法，進一步增加路徑規劃的合理性。這種數據驅動算法并不像之前的路徑規劃算法，在城市路網的基礎上用相應的最短路徑規劃算法去計算路網的最短路徑，而是借助于眾多的歷史軌跡數據，從歷史軌跡數據中充分提取司機的駕駛經驗智慧，并分析城市路網中存在的行車規律，將出租車司機的駕駛經驗充分融入到路網中，再結合路徑搜索策略進一步規劃更符合人們出行路線。二是對經驗路網的改進，傳統的經驗路網僅根據駕駛員的經驗獲取訪問頻次較高的路段，而本文不僅根據駕駛經驗獲取高頻路段，而且對連接高頻路段的軌跡作了進一步的聚類分析，從而得到更加精簡的經驗路網，即熱點路段圖，在熱點路段圖的基礎上，使用改進的A*算法可更高效快速地找到符合人們日常出行的路徑。

1 技術路線

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

首先，對獲取到的出租車軌跡數據進行預處理，從大量的軌跡數據中提取真實的載人軌跡數據，并剔除一些噪聲數據，包括時間數據無變化、速度為零且有載客的狀態、軌跡數據點較少、載客狀態錯誤顯示等。

其次，在現有路網數據的基礎上，進一步將獲取的出租車載人軌跡數據匹配到相應的路段上，完成出租車載人GPS軌跡到路網數據的地圖匹配工作，使得在地圖上可直觀地顯示出租車的行駛軌跡。本文采用的地圖匹配算法是IVMM算法[8]，它對低采樣率GPS軌跡點到路網的匹配有較高的準確性。

再次，根據地圖匹配的結果計算路網中路段被匹配到的次數，選取出租車司機較為傾向的路段，即熱點路段，以此構建基于經驗道路的基礎熱點路段圖。

然后，統計分析熱點路段之間的行駛路徑與時間，本文把軌跡間的編輯距離作為軌跡相似性的度量，對熱點路段之間的行駛路徑進行聚類分析，選取兩路段間最為合適的連接路徑，進一步完善熱點路段圖的構建。

最后，在熱點路段圖的基礎上，利用改進的A*算法實現基于出租車經驗軌跡的路徑規劃算法。

主要技術路線流程如圖1所示。

圖1 技術流程

2 概念定義

針對出租車行為活動軌跡進行數據挖掘的分析研究工作，在數據處理之前作如下定義。

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

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

3)路網數據。路網數據是由路段的端點和路線組成的有方向的路網圖。

4)GPS位置點。由GPS定位技術記錄的位置點，每個GPS位置點由7個字段構成，包含車牌號、采集時間點、緯度、經度、車輛狀態、車速和行駛方向基本信息，表示為p=(name,T,Lat,Lng,status,v,angle)，name為車牌號，T為時間戳，Lat為緯度，Lng為經度，status為載人狀態，v為行車速度，angle為行車方向。

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

6)熱點路段。路網中的路段被訪問頻次超過一定閾值時則稱該路段為熱點路段。

7)熱點路段圖。熱點路段圖是由熱點路段連接而成的路網。

3 出租車載人軌跡的提取

出租車的GPS軌跡信息中記錄了在當前時刻下出租車的行駛狀態，每一條軌跡信息中包含車輛的采集時間點、經緯度信息、車輛載客狀態、車速、行車方向等信息。總的軌跡數據記錄了出租車運營的整體行駛狀態，其中有載客行駛和空載行駛兩種。軌跡信息中的車輛載客狀態用0和1分別表示出租車是空載狀態還是載客狀態，可選擇載客狀態為1的軌跡信息作為提取出租車駕駛經驗的軌跡數據集。因為當載有乘客時，出租車司機為追求最大化的經濟利益會根據自己以往的駕駛經驗花費最少的精力和時間把乘客送達他們的目的地，而這種包含經驗的行車路徑正是所需要獲取的數據。

在出租車的眾多行駛軌跡中，根據車輛載客狀態對軌跡進行分割，并提取真實的載人軌跡數據，再對載人GPS軌跡數據進行地圖匹配，這在一定程度上降低了地圖匹配的工作量。圖2為從一條出租車軌跡中提取出的真實載人路段序列。ST表示出租車的載客狀態，出租車的載客狀態(STATUS,ST)為0表示空載，ST=1表示載客。圖中p0，p1，…，,p9分別表示載人軌跡中的10個GPS軌跡采樣點，它們的載客狀態ST=1。從軌跡點中提取ST=1的GPS點，因為只有真實的載人軌跡才能提取出有價值的駕駛經驗。

圖2 載人GPS軌跡的提取

圖3 候選路段和候選點集合示例圖

4 路徑規劃

4.1 熱點路段的選取

根據提取的載人GPS軌跡數據到路網匹配的結果，對城市路網各時段出租車在各路段的出現次數進行統計，并把路段訪問次數作為城市道路片段被選取為熱點路段的依據，路段訪問次數由下式計算:

(1)

(2)

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

4.2 構建基于經驗軌跡的熱點路段

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

針對熱點路段間的路徑連接問題，本文從出租車載人軌跡中統計經過兩個熱點路段且其間沒有包含其他熱點路段的所有軌跡，并截取以該兩熱點路段為起止點的軌跡片段作為用來統計連接熱點路段的軌跡集合。對這類軌跡進行聚類分析，并把軌跡間的編輯距離[14]作為軌跡間的相似性度量。若兩個熱點路段間的行駛時間遠超出租車的平均行駛時間，則認為這兩個熱點路段之間不存在比較合適的直達路徑，可通過其他路徑實現熱點路段間的連接。

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

RERP(Tr1,Tr2)=

(3)

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

(4)

delete_cost(ri,sj)=

(5)

(6)

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

(7)

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

本文選用DBSCAN聚類方法，在上述編輯距離的基礎上對經過兩個熱點路段之間的軌跡路徑集進行聚類分析，選取熱點路段間最為出租車司機認可的行駛路徑作為連接路徑。

算法描述如下。

假設T代表經過兩個熱點路段的所有行車軌跡集合。

軌跡ε空間近鄰 對于軌跡集合中的任意軌跡Tri，當其他軌跡Trj與Tri的時空距離小于ε時，認為軌跡Trj出現在軌跡Tri的ε空間近鄰，稱Trj是Tri的ε空間近鄰，D為軌跡數據集，Dis(Tri,Trj)表示軌跡Tri與Trj之間的距離，表達式如式(8)所示:

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

(8)

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

(9)

直接空間可達的軌跡 如果軌跡Trj在軌跡Tri的ε空間鄰域內，并且Tri是核心軌跡，那么稱軌跡Trj是從軌跡Tri出發直接空間可達的軌跡。

空間可達軌跡 如果軌跡Trj出現在核心軌跡Tri的ε空間鄰域內，軌跡Trm出現在核心軌跡Trj的ε空間鄰域內且不出現在Tri的空間鄰域內，則稱軌跡Trm是從軌跡Tri空間可達的。

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

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

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

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

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

算法：Trajectory Clustering based on Edit Distance。

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

1)

foreachTri,Trj∈D∧i≠jdo

2)

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

3)

CalculateEDIM(Tri,Trj);

4)

ifEDIM(Tri,Trj)≥εthen

5)

Nε(Tri)←Trj;

/*設定Tri的ε-近鄰集合*/

6)

End for

/*第2階段：對軌跡段進行聚類*/

7)

SetclusterId=0;

/*初始化聚類數標號，起初為0*/

8)

Mark all Trajectories as unclassified;

9)

foreachTri∈DandTriisunclassifieddo

10)

ifTriisvisited

/*判斷軌跡是否被分類過*/

11)

continuenexttrajectory;

12)

MarkTriasvisited;

13)

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

14)

ifsizeof(Nε(Tri))<σ

15)

MarkTriasNoise

16)

else

17)

IncreaseclusterIdby1;

/*表示聚類數加1*/ /*擴展軌跡的近鄰聚類*/

18)

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

19)

End for

/*對可達近鄰進行聚類*/

20)

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

21)

addTritoclusterId

22)

for eachTrj∈Nε(Tri)′

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

23)

if Trjisnotvisited

24)

markTrjasvisited/*計算軌跡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

基于編輯距離聚類算法的時間復雜度主要分為兩部分：第1部分是編輯距離算法的復雜度，其值是O(mn),m為軌跡Tr1的長度，即Tr1的路段個數，n為軌跡Tr2的長度，即Tr2的路段個數。第2部分是DBSCAN聚類算法的時間復雜度，最壞的情況為O(n2)，n為兩熱點路段間的軌跡片段條數。因為本文中首先進行的工作是地圖匹配，將軌跡中的軌跡點匹配到路網中相應的路段上，然后采用路段編號集合代替軌跡點集合來表示一條軌跡，用兩熱點路段間的軌跡片段集合代替軌跡點集合進行軌跡的聚類分析，因此軌跡片段的個數遠遠小于軌跡點的數目，所以在進行聚類算法時不存在計算量太大的問題。

4.3 基于熱點路段圖的路徑規劃

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

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

(10)

其中：是從起點到當前臨時標記節點i的實際路徑的量度；是從當前臨時標記節點i到終點的最短路徑的估計；i，j為鄰近節點，且j為i的前一節點，i為j的后續節點。路徑尋優算法采用的是改進的A*算法，在式(10)的基礎上構造的一個時變啟發函數：

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是車輛的行程指標；FT是車輛行駛的時間指標；FS是車輛行駛的威脅度指標；λD、λT和λS分別是行程加權系數、時間加權系數和威脅加權系數，綜合指標最優的情況下，λD=3.5，λT=1和λS=1[14]；T0是車輛出發時刻；FDE(i)和FDE(j)分別是當前節點和其父節點到終點的曼哈頓距離；FTE(i)和FSE(i)是當前節點(xi,yi)到終點(xd,yd)的估價函數；FTE(j)和FSE(j)是父節點(xj,yj)到終點(xd,yd)的估價函數。根據該啟發函數的優化結果，本文選取T0=0時，進行最優路徑的計算。

依據城市電子地圖路網數據以及熱點路段圖的信息，對于給定的起始位置數據，采用改進的A*分層算法，本文利用3段尋徑的路徑查找策略實現車輛的最短路徑規劃計算。基本步驟如下：

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

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

3)若起點S不屬于熱點路段圖中或終點D不屬于熱點路段圖，則應用路徑規劃方法計算熱點路段圖外S至S′的最優路徑L1或熱點路段圖外D′至D的最優路徑L2,以及熱點路段圖內S′至D′的最優路徑P。L1和P的連接或L2和P的連接即是始末位置間的最優路徑。

5 實驗分析與比較

5.1 基礎數據

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

當前的路徑規劃算法一般分為基于路網數據的最短路徑規劃算法或在此基礎上改進的最短路徑算法以及基于出租車駕駛經驗對路網進行分層的最短路徑規劃算法，本文分別選取最短路徑(Shortest Path, SP)算法以及基于駕駛經驗路網分層的路徑(Experience Path, EP)規劃算法與本文的基于熱點路段圖的路徑(Hot-section Path, HP)規劃算法進行對比。選取任意的20對起始-終止節點(Origin-Destination, OD)，利用這3種算法分別計算不同時間段內起點和終點間的最優路徑，并統計規劃路徑的長度與所用時間來進行相應的比較。T表示時間段，每天不同時間段的劃分如表1所示。

5.2 路徑長度對比

如圖4所示為4個不同時段內的規劃路徑長度對比。

利用SP、EP、HP這3種路徑規劃算法對隨機選擇的20個起止OD對進行路徑規劃，并統計分析規劃路徑的長度，結果如圖4所示。柱狀圖的高度表示路徑規劃算法規劃的每條路徑總長度。根據柱體的高度可以得出，在距離上，相對EP和HP算法來說，由SP算法規劃得到的路線距離較短，而EP和HP算法在計算路徑時由于趨向于所選取的經驗路段，因此容易發生繞路的現象。若OD對之間隔得很近，因為OD對之間可能存在經驗路段，EP和HP算法會將相應的經驗路段計入其中，但相較于EP算法，本文的HP算法計算得到的路徑距離略優。對于EP算法和本文的HP算法，對比柱狀體高度可以得出，兩者計算得到的路徑在距離上相差較小。綜合比較4個時間段內規劃的路徑總長度，如圖5所示，可以看出處于高峰期時，OD對之間規劃的路徑長度大于平峰期的路徑長度。晚高峰時的規劃路徑長度大于早高峰期的路徑長度，夜間的平峰期的規劃路徑長度大于日間的平峰期的規劃路徑長度。

表1 時間段劃分

圖4 不同時間段的路徑長度比

圖5 3種算法不同時間段的總路徑長度對比

如圖6所示為4個不同時段內的規劃路徑行程時間對比。

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

圖6 不同時間段的路徑行駛耗時對比

圖7 不同時間段3種算法的路徑總耗時對比

6 結語

本文通過分析出租車GPS軌跡數據的特點，提取真實的載人GPS軌跡數據，并實現軌跡數據到路網數據的地圖匹配。根據地圖匹配的結果，分析出租車行駛路線規律，并統計路網中路段的訪問頻次，據此選取訪問頻次較高的路段為熱點路段，進而對連接熱點路段間的行車軌跡實現軌跡相似度的計算，完成路段之間真實載人軌跡的聚類分析。充分利用駕駛員的行車經驗實現熱點路段間的連接，并完善熱點路段圖的建立，且在此基礎上提出融合出租車駕駛經驗的路徑規劃方法。相比之前的路徑規劃算法，本文提出的方法在經驗分析和數據統計兩方面作了進一步的研究：一是將傳統的以側重路徑計算為中心的路徑規劃方法變為以數據為中心的數據驅動方法，充分利用了軌跡數據中的隱含信息；二是對經驗路網的改進，傳統的經驗路網僅根據駕駛員的經驗獲取訪問頻次較高的路段，以此構建基礎的經驗路網，本文首先根據駕駛經驗獲取高頻路段，即熱點路段，然后對連接兩個熱點路段的軌跡進行相似度的計算并作進一步的聚類分析，以實現熱點路段圖中兩熱點路段的連接，從而得到更加精簡的熱點路段圖，熱點路段圖的建立是對出租車司機經驗智能最大化的體現，在計算最短路徑時可更加注重軌跡數據挖掘所得到的知識，減少了常規的路徑計算，提高了路徑規劃的效率，最后在熱點路段圖的基礎上，使用改進的A*算法可更高效快速地找到符合人們日常出行的路徑。

表2 路徑搜索相關參數

最后本文選取深圳市的路網數據與出租車載人軌跡數據，對路徑規劃的結果進行比較分析，結果顯示本文提出的基于熱點路段圖的路徑規劃方法在行車時間上更優，更具有出行指導意義。

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].測繪學報,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].上海交通大學學報,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] 張翼,唐國金,陳磊.時相關車輛路徑規劃問題的改進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。

國家自然科學基金資助項目(51579202)；中國博士后基金資助項目(2015T80848)。

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

1001- 9081(2017)07- 2106- 08

10.11772/j.issn.1001- 9081.2017.07.2106