導航系統路徑搜尋之研究

Abstract

路徑規劃問題是這幾年來被廣泛地討論的一個問題，有許多基於Dijkstra演算法的方法已被一一提出；其中優先權佇列是在 Dijkstra演算法的計算上非常重要的一個資料結構。我們針對一般平面道路圖來加以觀察，發現一般平面道路圖的節點分支度是相當地低。根據此特性我們提出一個 Lazy Heap 的資料結構。跟傳統常使用的 Binary Heap來做比較，我們的方法能夠改進效能 30%至50%。除此之外，我們針對台北大眾運輸系統，提出圖的模型和路徑規劃的系統架構；在基於不同使用者的偏好之下，我們設計不同評斷路徑好壞的方法。我們也嚐試許多不同的參數組合，來討論路徑規劃結果和運算效能上的改進的議題。

The shortest path problem has been studied for decades, and many efficient algorithms based on Dijkstra's algorithm have been developed. In this thesis, we focus on the road network graphs. Priority queue is an important data structure used in Dijkstra's algorithm. Since the road netwrok graph has low degree, we propose a lazy binary heap as the priority queue. According to our experiments, we reduce 30% to 50% running time on this kind of sparse graphs. Moreover, our implementation has better space efficiency than standard binary heap. Based on the road network, we also study the public transportation system of Taipei City. In this work, we first model it as a graph, then propose a system architecture. Because of the preference of different users, we design different metric functions for different preference. In our experiments, we have tried different metrics and parameters setting.