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

Abstract

「條條大路通羅馬」，交通運輸的快速發展，使得我們要前往目的地，時常都有許多選擇，然而因為有許多不同的選擇，該如何選擇就變成了另一個困擾。市面上有許多路徑導引程式，不論「行前路徑導引」或「途中路徑導引」，多以空間最短路徑為決策目標，然而實際使用的時候，卻時常發現導引程式提供的最佳路徑車多雍塞。 為解決傳統路徑導引程式往往僅依照空間距離做為路徑導引決策的變數，未考慮實際交通路況的問題，本研究使用路段旅行時間做為路徑選擇的成本，建置一適用於國道高速公路路網的依時性A*路徑演算系統。以A* Algorithm做為路徑演算的基礎，將整合車輛偵測器(VD)與電子收費系統(ETC)資料的旅行時間資料庫做為依時性演算法之資料來源，並加入後推式演算法以配合不同使用者的需求。使用者輸入起點、訖點以及預計出發/抵達時間，系統就會根據旅行時間資料庫提供的路段旅行資料，提供建議旅行路徑與總旅行時間。 本研究驗證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.