依時性A*路徑演算系統開發－以國道高速公路路網為例

Development of Time-Dependent A* Route Planning System: A Case Study of Taiwan Highway System

謝伯嘉(Bor-Chia Hsieh)

指導教授 ： 張堂賢

國立臺灣大學/工學院/土木工程學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.01074

摘要

「條條大路通羅馬」，交通運輸的快速發展，使得我們要前往目的地，時常都有許多選擇，然而因為有許多不同的選擇，該如何選擇就變成了另一個困擾。市面上有許多路徑導引程式，不論「行前路徑導引」或「途中路徑導引」，多以空間最短路徑為決策目標，然而實際使用的時候，卻時常發現導引程式提供的最佳路徑車多雍塞。
為解決傳統路徑導引程式往往僅依照空間距離做為路徑導引決策的變數，未考慮實際交通路況的問題，本研究使用路段旅行時間做為路徑選擇的成本，建置一適用於國道高速公路路網的依時性A*路徑演算系統。以A* Algorithm做為路徑演算的基礎，將整合車輛偵測器(VD)與電子收費系統(ETC)資料的旅行時間資料庫做為依時性演算法之資料來源，並加入後推式演算法以配合不同使用者的需求。使用者輸入起點、訖點以及預計出發/抵達時間，系統就會根據旅行時間資料庫提供的路段旅行資料，提供建議旅行路徑與總旅行時間。
本研究驗證A* Algorithm能夠有效限制路徑搜尋的方向，以較短的時間取得令人滿意的建議路徑，這在路網龐大複雜時，能夠有效縮短運算時間，節省運算資源。本研究同時驗證，後推式演算法雖然需要較長的演算時間，但是演算結果與前推式演算法一致，能夠節省使用者欲於特定時間抵達目的地而反覆求解的時間。

關鍵字

依時性最短路徑問題 ； Dijkstra’s Algorithm ； A* Algorithm ； 後推式路徑演算法 ； 路徑導引系統

並列摘要

“All roads lead to Rome.” Because of the developing of transportation, we usually have a lot of way that we can pick to reach a destination. With the choices increasing, which way should we choose become another problem. There are kinds of route guidance program in the market. Whatever “pre-trip route guiding” or “en-route route guiding,” most of them use the length of path to make a decision. However we can usually found out that the route it provides always in a traffic jam.
To solve the problem that traditional route guidance programs usually pick out the shortest route but not the best route, this study replaces the spacing cost with traveling-time cost to build a time-dependent A* route planning system which can match highway characteristic. This program based on A* Algorithm and uses VD and ETC data as data sources. It also contain time-dependent backward algorithm to fit different travel planning demands. Users just input origin, destination, and expectation departure/arrival time, system will output recommend route and total traveling time.
This study verify that A* Algorithm can limit route-searching direction to find a satisfactory route within a short time. While the road network coming huge and complex, it can efficaciously saving calculating time. This study also verify that backward algorithm get the same result as forward algorithm, though backward algorithm take more time to solve the problem.

並列關鍵字

the time-dependent shortest path problem ； Dijkstra’s Algorithm ； A* Algorithm ； the backward route algorithm ； route guidance system

參考文獻

[43] 葉羿稚. (2007). 行前即時路徑規劃演算法之研究. 台灣大學土木工程學系碩士論文.

[42] 張堂賢、闕嘉宏. (2012). 依時性後推式路徑演算系統開發. 運輸學刊.

[1] Cherkassky, B.V., A.V. Goldberg, and T. Radzik. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 129-174.

[4] Smith, J.C. and K. Russam. (1989). Some possible effects of AUTOGUIDE on traffic in London. IEEE International Conference on Vehicle Navigation and Information Systems. Toronto, Canada.

[6] Boyce, D.E., A.M. Kirson, and J.L. Schofer. (1994). Design and implementation of ADVANCE：The Illinois dynamic navigation and route guidance demonstration program. IEEE International Conference on Vehicle Navigation and Information Systems. Ottawa, Canada.