以改良的A*演算法規劃較佳導引路徑之研究

The Study of Better Route Planning based on Improved A* Algorithm

張傑(Jie Chang)

指導教授 ： 蔡佳勝 ； 黃有評

大同大學/電機資訊學院/資訊工程學系所/碩士(2009年)

摘要

現有的路徑規劃演算法，多數依路徑長度來規劃出最短路徑，但最短路徑並不代表是最佳路徑，最佳路徑應是行駛時間花費最少之路徑。倘若在最短路徑上發生了壅塞或是車禍之情形，則所花費時間將會大大增加，本論文重點為規劃出行駛時間少之路徑。
偵測道路是否發生壅塞，目前已有多項技術及設備進行監控與偵測路況。因此本論文以假設目前各路段路況已知前提下，從多種路徑規劃演算法進行評估，最後針對A*演算法提出改良，與原本A*演算法相比，在搜尋時加入方向性判別，使搜尋節點時可經由方向性判別，選擇與終點同一方向且距離較近之節點，並針對在動態路況環境應用中，加入路段時速，選擇離終點近且速度快之路段，而所規劃出之路徑為行駛時間少，使本論文演算法適合用於實際路況環境中。
本論文提出改良A*演算法進行實驗，於實驗一中以隨機生成網路，尋找最短路徑為目標，以Dijkstra’s演算法、A*演算法與本論文演算法進行路徑規劃，則Dijkstra’s演算法規劃出路徑為最短路徑，因此將A*演算法與本論文演算法所規劃出路徑與Dijkstra’s演算法相比，並將此演算法執行時間一併加入相比，實驗結果在效能上本論文演算法比A*演算法更趨近於最短路徑。在實驗二與三中以隨機生成網路及模擬真實環境網路，尋找行駛時間少之路徑為目的實驗，以A*演算法加入路段時速與本論文演算法進行路徑規劃，在隨機生成網路上，加入一些特別道路，例如高架橋、地下道、圓環，而在模擬真實環境實驗上，以模擬台北市地圖為實驗環境，此二種實驗結果顯示本論文所提出演算法比A*演算法更有效率。

關鍵字

路徑規劃 ； 最短路徑 ； 動態路況環境 ； A*演算法

並列摘要

Most existing route planning algorithms based on the route length to calculate the shortest route. But the shortest path is not necessary the best route that takes the least traveling time. If a traffic jam or car accident occurred in the shortest path, then more traveling time was required. This study is aimed on finding the least traveling time for a route.
Various techniques have been proposed to monitor the traffic situations in the past. The traffic situations are assumed to be known in advance in the experiments. After assessing a variety route planning algorithms, we present a modified A* algorithm. As compared with the original A* algorithm directional discrimination is added into the new algorithm. In the dynamic road environment, transportation speed is also considered. The modified A* algorithm that takes the directional judgment into consideration is proposed to reduce the required traveling time.
This thesis presents an improved A* algorithm to conduct experiments. The first experiment with a randomly generated network is to find the shortest path. Using Dijkstra's algorithm, A* algorithm, and the proposed algorithm for route planning in the static environment, the Dijkstra's algorithm can find the shortest route. Thus, A* algorithm and the proposed algorithm are compared with the Dijkstra's algorithm in route planning to verify that the proposed algorithm outperforms the A * algorithm in finding the shortest path. The second and the third experiments with randomly generated networks and the simulated network environment are presented to find the routes with less traveling time. In the randomly generated networks a number of special roads such as the viaduct, underpass, and loop are considered, and the simulated networks are used to simulate the real Taipei City map environment. Experimental results show that the proposed algorithm is more efficient in route planning than the A* algorithm.

並列關鍵字

dynamic traffic environment ； shortest path ； Route planning ； A* algorithm.

參考文獻

[1] 陳均昇，網際地理資訊系統之互動式路徑規劃，國立成功大學測量及空間資訊

[3] 李俊銘，以Google Maps 結合WebGIS 發展具旅次路徑規畫之公車動態資訊系

[4] 張文贏，多目標巡視之飛行路徑規劃研究，國立成功大學航空太空工程學系研

[5] 陳冠璋，地圖結合與互動全景街道系統，國立成功大學資訊科學與工程學系研

[6] A. Sud, E. Andersen, S. Curtis, M.C. Lin and D. Manocha, “Real-time path