[發明專利]基于實時交通信息的最短時間路徑規劃方法

無效

• 申請號: 200810110940.0
• 申請日: 2008-06-18
• 公開（公告）號: CN101608922A
• 公開（公告）日: 2009-12-23
• 發明（設計）人: 倪金生;王徹;于雷易;倪偉;姜航;錢曉明;龍飛;趙明偉;呂玲
• 申請（專利權）人: 北京東方泰坦科技有限公司
• 主分類號: G01C21/26
• 分類號: G01C21/26;G01C21/34;H04H20/55;G09B29/10;G09B29/00;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于導航領域的最短路徑計算方法，尤其適用于動態導航。

背景技術

最短路徑是GIS領域的主要問題之一，其關鍵是將一個物理網絡結構抽象為一個數學網絡結構，再利用數學方法進行求解。在數學和計算機領域網絡被抽象為圖，再利用圖論的方法計算最短路徑。

最短路徑算法按節點運動狀態可分為靜態最短路徑算法和動態實時最短路徑算法。靜態最短路徑是外界條件不變，計算起點到終點的最短路徑，主要有Dijkstra算法和A*算法。而動態最短路徑是外界環境不斷發生變化，無法計算預測路徑的情況下求最短路，典型的有D*算法，在機器人探路中常應用D*算法。GIS導航領域的最短路徑算法屬于靜態最短路徑的問題，本發明采用Dijkstra算法實現了基于實時交通信息的最短時間路徑規劃方法。

發明內容

本發明要解決的問題是在考慮實時交通信息的條件下，建立道路網的網絡拓撲結構，對海量空間數據進行有效的存儲、管理，提供高效的空間索引和查詢。在此基礎上，為用戶提供高效的最短時間路徑規劃服務。

本發明提出一種基于實時交通信息的最短時間路徑規劃方法，步驟如下：

(1)信息接收，中心服務器從數據源處獲取實時交通信息，通過TCP/IP協議，基于socket通信傳輸到導航中心服務器；

(2)信息解碼，導航中心服務器可對接收模塊所接收到的實時交通信息依預定的協議進行解析；

(3)提交請求，裝有電子地圖的手持端(客戶端)在地圖上選擇出發點和目的地，以坐標形式向中心服務器提交路徑規劃請求；

(4)路徑規劃，中心服務器根據解析過的實時交通信息和客戶端提交的請求，進行最短時間的路徑規劃；

(5)應答回傳，中心服務器將規劃好的路徑傳回手持端。

具體實施方式

對于動態交通信息，可以作為路段的一個權重加入到路段對應的數據表中，通過最短路徑分析的方法得到結合動態交通信息的路徑規劃結果。但是，動態交通信息是實時更新的，并且在更新的同時系統還要執行大量的查詢和分析任務，因此數據存儲和組織的形式是動態交通路徑規劃所要考慮的一個問題。

(1)網絡拓撲關系。

要想用計算機程序實現Dijkstra算法，關鍵技術是用什么樣的方式抽象出網絡拓撲結構，及節點與節點的連通關系，并對網絡拓撲結構進行高效能訪問。

a.拓撲關系的獲取

GIS中的數據(如道路、管網、水系等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在GIS中稱為構建網絡的拓撲關系。只有建立了拓撲關系，我們才能進行網絡路徑分析。GIS數據通常是圖形數據和屬性數據的有機集合。在ARC/INFO下利用命令CLEAN對道路網數據構建網絡拓撲，我們可以看到屬性表，其屬性數據中包括_Fnode(起點)和_Tnode(終點)兩個屬性項。該屬性表中包含了一個完備的網絡拓撲關系，即記錄了該圖擁有多少個節點，又記錄了節點與節點的連通關系，不同的_Fnode、_Tnode標號代表不同的節點，及一條線的起始節點和終止節點，擁有相同節點的線相連，從該表大家應該很清楚的看出道路網的拓撲結構。

b.網絡拓撲關系的高效訪問

利用上面的屬性表我們可以有效地解讀出一個網絡拓撲關系，在按標記法實現Dijkstra算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段。這是一個循環比較的過程，如果不采用任何技巧，要選擇一個權值最小的弧段就必須對屬性表進行多次掃描，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。下面主要就如何從含拓撲關系的屬性表中解析一個簡潔高效的網絡拓撲存儲結構進行討論。

在數學和計算機領域中網絡拓撲被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表表示。

(2)海量空間數據組織、存儲與查詢

空間數據的范圍非常廣泛，任何同空間位置相關的數據皆可稱為空間數據。隨著探測手段和能力的發展，空間數據正在迅速增長，應用范圍也益加廣泛，因此如何有效地存儲、管理、查詢和交換空間數據也成為日益突出的問題。

目前以數據庫為中心的海量空間數據管理已經逐漸取代了傳統的文件方式，其中典型的代表是Oracle。這些數據庫系統通常在原有的關系型數據庫之上增加空間數據庫層，應用系統必須通過該層訪問庫中的空間數據。所有的空間領域知識都封裝在該層中。