探討時間相依之可能旅行路徑問題

Abstract

探討時間相依之旅行路徑為先進旅行者資訊系統（ATIS）發展重點之一。然而過去研究多著重在求解時間相依之最短路徑問題，忽略其發生機率可能極低，因此本研究之目的在於考量具有時間相依性之節線成本情況下，探討不同時空下對於到達時間和旅行路徑之影響，以作為旅行者旅行路徑規劃之參考依據。 在網路資訊的設計上，本研究加入不同時段對於旅行時間影響之概念，並且以時間範圍和相對應之機率方式表示。首先修正Miller-Hooks and Mahmassani (1998提出的演算法，找出時間相依之最短路徑；接著，依據標記修正法，並融入旅行路徑機率之概念，求解單一路徑在相同出發時間下，不同到達時間範圍以及機率問題；最後以虛擬路網測試，驗證其可行性，並探討在給定不同相關旅行資訊之前提下，所能提供旅行者資訊之限制，確定本研究所提出之演算法適用性。

Time dependent route guidance and travel estimation are important elements in a Advanced traveler information system（APTS）. Most previous researches focus on providing shortest paths; but neglect the occurrence probability. This shortage results in the extreme low probability of the provided route.

We propose three procedures to determine possible travel routes and their associated probabilities in a time-dependent network. The first and the second algorithm generate possible travel time range of the suggested path based on the algorithm proposed by Miller-Hooks and Mahmassani (1998). The third algorithm calculates the occurrence probabilities of a given route. The computation complexity of these three algorithms is also analyzed.

We use simulated data to evaluate performance of these three algorithms. The testing results shows that these algorithms are efficient and can provide useful information to travelers.