汽車導航最短路徑搜尋法之研究

Abstract

由於近年來全球定位系統的使用率大增，加上與地理資訊系統的技術整合，使得汽車導航系統成為一個相當熱門的商品。在系統當中有一個重要的核心模組就是最短路徑演算法。在實務應用上，所面臨到的現實路網包含有數十萬個節線與節點，在汽車導航設備的執行效能與記憶體容量皆有所限制的條件下，對於傳統的最短路徑演算法來說，它於車載系統上的計算效率無法達到既時快速的反應來滿足使用者的需求。因此，本研究提出了得以改善反應速度的演算法，嘗試讓整個最短路徑的計算更快，也讓使用者能有更好的感受。 改良的方式主要是透過傳統的Dijkstra演算法、啟發式的A*演算法與路網分層概念的結合，建立出不同的最短路徑演算法以縮減路徑搜尋空間，進一步增進搜尋的速度。本研究將台灣實際的大型路網區分為上、下兩層的子路網層，上層為道路層級較高的路種，下層為道路層級較低的路種。測試所選取之起迄對分佈主要分為短、中、長程三種距離，每組起迄對皆由電腦隨機產生。求解結果所使用的衡量標準包含有「實際道路長度」以及「旅行時間」兩種。以實際道路長度作為衡量標準時，會根據起迄對間的距離而有不同的誤差。在旅行時間計算上，透過分層的概念對路種進行分類，使其近似於真實使用者行為。在此可用於比較真實道路長度與旅行時間作為衡量指標時的求解誤差。 最後透過測試結果證明，本研究提出之最短路徑演算法在執行效率方面有相當快速的提升；在路徑搜尋空間方面也較傳統演算法來得少，相對地在記憶體的需求上也比較節省，對於應用在汽車導航裝置上面具有相當大的優勢。

Combined with Geographic Information System (GIS) and Global Positioning System (GPS), the vehicle navigation system had become a quite popular product in daily life. A key component of the navigation system is the Shortest Path Algorithm. Navigation in real world must face a network consists of tens of thousands nodes and links, and even more. Under the limited computation capability of vehicle navigation equipment, it is difficult to satisfy the real-time response requirement that user expected. Hence, this study focused on shortest path algorithm that enhances the computation speed with less memory requirement. Several well-known algorithms such as Dijkstra, A* and hierarchical concepts were integrated to build hybrid algorithms that reduce searching space and improve searching speed. Numerical examples were conducted on Taiwan highway network that consists of more than four hundred thousands of links and nearly three hundred thousands of nodes. This real network was divided into two connected sub-networks (layers). The upper layer is constructed by freeways and expressways; the lower layer is constructed by local networks. Test origin-destination pairs were chosen randomly and divided into three distance categories; short, medium and long distances. The evaluation of outcome is judged by actual length and travel time.

The numerical example reveals that the hybrid algorithm proposed by this research might be tens of thousands times faster than traditional Dijkstra algorithm; the memory requirement of the hybrid algorithm is also much smaller than the tradition algorithm. This outcome shows that this proposed algorithm would have an advantage over vehicle navigation system.