大型路網之動態最短路徑搜尋之研究

由於全球定位系統(GPS)的應用越來越普及，而目前GPS搜尋最短路徑都是依據最短距離提供給使用者一條最短路徑，如果當交通狀況壅塞，可能造成行駛的時間大幅增加，因此如何於動態環境下短時間內提供一條行駛時間可被使用者接受的最短路徑將會是本研究所關注的重點。本研究進行相關最短路徑演算法的回顧，並選擇以A*演算法最作為基礎進行改良進而提出一新演算法A* New；而本研究對於動態問題處理的方式是將一天切割為數個時段，不同時段中所儲存的道路行駛時間會依據道路尖離峰與壅塞時段而有所不同。本研究所提出的A* New演算法最重要的核心即是將路網分為數個層級，並將使用者查詢的起迄分割為多組起迄，分別依據其所在的層級來進行最短路徑搜尋，並將其分別搜尋之結果合併，提供給使用者一條行駛時間最短之最短路徑。本研究採用合作廠商所提供的路網資料以及台灣地圖資料來進行演算法搜尋效率探討，其研究結果顯示，A* New演算法只要門檻值設定得當，於各種路網下皆可於動態環境下在短時間內提供出一條路徑解給使用者進行參考。

關鍵字

大型路網；動態最短路徑； A* ； Dijkstra

並列摘要

The application of GPS has been more and more popular. Currently, the shortest path found by GPS is based on the shortest distance for the user to the destination. However, if the traffic is busy, the user might have to spend more time to reach the destination. Therefore, this study focuses on how GPS can provide the shortest path based on the dynamic travel time. This study proposed a new algorithm, A*New, solve the dynamic problem by dividing a day into several periods. The travel time of links will depend on whether it is during peak or off-peak hours. The most important core of A*New Algorithm is to divide the road network into several levels and split the OD pair inquired by the user into several sub OD pairs, so that the shortest path will be searched according to each sub problem. The results of these sub problems are combined to provide the user the shortest path in both distance and travel time. This study explores the efficiency of the new algorithm through the road network data provided by the company we cooperate with and the large scale network of whole Taiwan map. The empirical results show that as long as the threshold of A*New is set up properly, a shortest path can be provided to the user efficiently under the dynamic environment in all kinds of road networks.

並列關鍵字

Large Scale Network ； Dynamic Shortest Path ； A* ； Dijkstra

參考文獻

Berger, A., Grimmer, M., & Müller-Hannemann, M. (2010). Fully dynamic speed-up techniques for multi-criteria shortest path searches in time-dependent networks. In Experimental Algorithms, 35-46.

Chabini, I. (1998). Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record: Journal of the Transportation Research Board, 170-175.

Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest Paths Algorithms：Theory And Experimental Evaluation. Mathematical programming, 129-174.

Deng, Y., & Tony, H. (2011). Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network. JILSA, 11-16.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numische Mathematik, 269-271.

國際替代計量

大型路網之動態最短路徑搜尋之研究

未授權

主題瀏覽