基于層次式匹配的最佳路徑匹配算法

[摘 要] 提出了以分段的軌跡數據為基礎，結合時空數據挖掘技術，挖掘基于帶時效的頻繁模式。并基于這個頻繁模式給出行者提供最佳的行車路線。同時，為了提高算法效率，提出了一種基于層次式模式匹配的思想，用分層的思想來過濾大量模式之間的匹配。

[關 鍵 詞] 路徑規劃；交通控制；軌跡聚類

[中圖分類號] G642 [文獻標志碼] A [文章編號] 2096-0603（2016）07-0129-01

一、引言

隨著電子地圖和導航系統的迅速普及，城市內出行變得越來越方便。但是現有導航系統的缺陷——單純以幾條固定路徑的導航選擇并不能讓很多出行者繞開擁堵路段，而且還使得某些擁堵路段更加擁堵。另外，大量的定位系統使各個系統保存了大量的軌跡數據，如何從這些軌跡數據中挖掘有效信息，從而給不同愛好的出行者提供更加合適的出行線路是當前城市計算領域研究的熱點之一。

路徑優化是路徑規劃的核心問題，目前最有影響力的流行算法是Dijkstra在1959年提出的最短路徑算法，Dijkstra算法，用于尋找兩個點之間的最短路徑。但是由于其算法的計算復雜度太高。很多學者對該算法進行了改進，提出了基于啟發式搜索的A*算法以及基于記錄歷史路徑的D*算法。因此，在城市內汽車保有量的不斷劇增，以及影響交通情況的諸多因素影響下，上述研究方案在實際使用過程中并不能發揮很好的作用。

二、算法框架

本課題旨在以城市內的出租車定位軌跡數據為基礎進行數據挖掘，挖掘城市內兩個站點之間的最佳路徑。為了實現這個目標，本文將從兩個目標角度對出租車定位數據進行挖掘。首先，根據軌跡數據統計每個路段在不同時間段的進度和出度，并在此基礎上計算基于信息熵的聚類分析，以構成整個城市的不同交通集中區域；接著，根據區域間的相連軌跡固定每個區域之間的最短距離，結合每個區域所在位置到區域出口之間的路徑，就可以得出兩個點之間的最佳路徑規劃。

為了提高檢索效率，本文采用分層處理方式來提高檢索速度，即按不同層次對整個城市進行逐層劃分，從而使得整個城市的空間區域變成一個典型的樹結構。按照上面的實現思想，本系統的實現流程如下：

（一）數據初始化

系統先將出租車軌跡數據（定位信息）按照每個路段劃分成路徑片段，即出租車經過每個路段的信息（路段編號，進入時間，離開時間），并導入公路網絡信息。

（二）基于信息熵的區域劃分算法

每個路段都有入度和出度（由于路段內有停車場或小區，單位時間內出度并不等于入度），如果將單位時間內每個路段的出入度之差作為該路段在該單位時間的信息熵，那么一些相鄰路段之間的組合就是區域，如果將每個區域的向外的出入度之差作為該區域的信息熵，那么城市區域的劃分就是將這些路段組合起來，使得整個系統的信息熵最低，就是我們所需要的區域劃分。

（三）構建基于軌跡頻繁模式挖掘和層次匹配的最佳路徑模式庫

按照傳統的軌跡數據挖掘算法將出租車軌跡數據進行頻繁模式挖掘，然后將挖掘獲得頻繁模式來構建兩個點之間的最佳路徑。其實現過程可以分為以下幾個步驟：

1.按照上一個階段獲取的區域，結合歷史軌跡數據，挖掘任何兩個區域之間在不同時刻的最佳頻繁路徑，構建模式庫；并確定每個區域連接其他區域的出入口，將其定義為關鍵點。

2.根據軌跡數據挖掘區域內不同時刻內、每個路段到每個關鍵點的最佳頻繁路徑模式。

3.上述兩個模式集合構成整個最佳路徑模式庫。

（四）層次式最佳路徑模式庫的搜索

1.一旦用戶輸入起始位置和目標位置之后，系統會自動根據當前時間以及對應特征（比如周末、非周末等）進行路徑頻繁模式匹配。整個過程將以頂層為參數按照下面的流程遞歸調用。

2.將傳入層作為當前層，系統按照輸入的起始點和終點判斷兩個點是否處在同一個子區域。

3.如果兩個點處在同一個子區域，且該區域已經沒有子區域，那么直接對起始點和目標點進行匹配；如果匹配，則返回此兩個點的匹配路徑；如果還存在子區域，則遞歸進入下一層。

4.如果沒有找到，則直接使用百度地圖的路徑導航。

隨著電子地圖、移動設備和定位技術的迅猛發展，越來越多的導航系統開始左右人們的出行。但是當前大多導航系統還停留在一些規定好的固定路徑作為導航線路，這使一些擁堵路段變得更加擁堵。而本文則是采用歷史軌跡數據挖掘，將大多數人采用的行走路徑作為導航路徑，這種方案給出行者提供更加靈活多變的優化路徑。同時，為了提高歷史路徑的匹配效率，本文還采用層次式匹配思想來提高匹配效率，提供算法的實時性。

參考文獻：

嚴德志，于鳳芹.基于最佳路徑組合搜索策略的匹配追逐算法[J].微計算機信息，2007（15）.