大眾運輸路網之行前旅次規劃方案搜尋演算法

A Heuristic Algorithm for Finding Pre-trip Planning Paths in Transit Networks

在國內積極推動大眾運輸系統之環境下，各大眾運輸主管機關及營運機構均積極發展大眾運輸旅次規劃系統（Transit Trip Planning System）；然國內目前多數之大眾運輸旅次規劃系統，由於未能將時刻表（Timetable）因素納入規劃分析中，當進行跨運具或跨路線轉乘時，即可能因為營運時間或班次的無法銜接，導致使用者之不便。網路分析乃旅次規劃分析之關鍵要素，然多數最佳化路徑演算法均是針對私人運具路網而設計，對於具有服務時間依時性、轉乘到達時間相依、不同路線包含同停靠站、起訖點來回路線非對稱等特性之大眾運輸路網而言，並無法直接將私人運具之最佳化路徑演算法應用於大眾運輸路網中。一般大眾運輸旅次規劃分析模式，可區分為考慮時刻表和未納入時刻表因素之演算法兩種型態，其中未納入時刻表因素之演算法並未考量週末可能增減班次或停靠站等服務變動因素。本研究所構建之大眾運輸旅次規劃分析方法，主要在透過對大眾運輸路網特性之考量，整合資料結構設計及旅次規劃邏輯，建立考量時刻表與跨運具轉乘之大眾運輸旅次規劃分析方法，藉此幫助大眾運輸使用者作出完整之旅次規劃資訊。經本研究以新竹市之大眾運輸路網（包括市區公車及鐵路系統）進行測試，發現本研究所構建之旅次規劃分析方法，可在短時間內完成旅次規劃分析結果，並正確搜尋出考量時刻表之跨運具轉乘資訊。

Many transport authorities and operation organizations have been actively developing transit trip planning systems to help travelers make seamless decisions about their choice of transportation mode, route, and departure time before beginning their trips. In Taiwan, most of the transit information systems do not consider transit timetables. Consequently, users may not be able to find the next transfer route in a reasonable waiting time duration. A network analysis model is the key component to provide trip itinerary planning. However, most path finding algorithms for highway vehicular network are not suitable for transit networks due to some characteristic differences between transit and highway networks, such as time-dependent services, different transit routes on the same street, non-symmetric routing with respect to an origin/destination pair, and transit transfer dependency on the arrival time of another transit system. The purpose of this research is to propose a schedule-based transit trip planning algorithm based on the characteristics of transit networks. We also tested the capability by using the Hsinchu City's transit network, considering the timetables of buses and intercity railway systems. The results showed that the proposed algorithm can generate a reasonable transfer alternative immediately.