依時空變數性之在線路徑演算實作系統－以臺灣高速公路路網為例

路徑導引與旅行時間預測為道路使用者最關心的兩項資訊，此兩項資訊的準確程度與提供之即時性，會影響到用路人是否能以最小旅行成本完成旅次，以及作有效率的行程規劃。本研究結論以A*演算法合適應用於臺灣高速公路路網的依時空變數性路徑規劃。本研究同時開發前推式和後推式的路徑規劃系統，讓使用者輸入起迄點、預計出發時間／到達時間，系統便會即時輸出建議路徑、抵達／出發時間與總旅行時間。提供路徑演算時所需的旅行成本資料，本研究建立了融合現點車輛偵測器檢出速率與電子收費站距的空間速率資料，再依旅行者長短期旅行時間分別採用卡曼濾波器且／或傅立葉數學模型構建出旅行時間預測計算模式。路網實驗證明所擬A*演算法能夠比Dijkstra演算法更有效確立搜尋方向、成少節點搜尋量，適用於發展手機APP快速查詢系統。惟後推式演算法因為需要反覆查詢進入路段時間以得到合理的路段旅行時間則會比前推式較長的演算時間。

關鍵字

前推式路徑演算法；後推式路徑潰算法； A*演算法； Dijkstra演算法；資料融合；路徑導引系統

並列摘要

Two of traffic information with which the road users are concerned the most are real-time route guidance and accurate travel-time prediction, which correspond to whether users complete a trip in expected minimum travel cost. This study applies A* algorithm building up an online forward with backward route computing module, which works for Taiwan-freeway-network time-space variant route planning system. Users can input their OD and expected departure/ arrival time, the system will output recommended path, arrival/ departure time as well as total travel time. In order to compute reliable travel cost for possible routes, this study constructs a data integration model fusing the speed data from vehicle detectors (spot data) and electronic toll collections (space data), and then adopts Kalman Filter and Fourier Transform mathematic to process long-term and short-term travel time prediction, respectively. According to experiment, the results show that A* algorithm can work more efficiently than Dykstra algorithm, particularly in reducing route directions and nodes' searching, in order to develop mobile APP application. However, backward approach requires repeatedly querying time to enter a link, such that it needs longer time for the output.