時間相依最短路徑問題演算方法之研究

Abstract

本研究期望透過時間相依最短路徑問題演算方法之研究，提出一套完善的最短路徑演算法，在已知的現況條件下（如：出發時間、旅行時間等相關資訊），於使用者出發之前給予其一條適當的行進路線建議，提供有效的『行前資訊』服務。 在演算法研究過程中，本研究將旅行時間分為三種型態：1.旅行時間為一時間相依之隨機變數，且使用單一期望值函數即可滿足時間相依與尖離峰之特性、2.旅行時間為一時間相依之隨機變數，且期望值函數隨著出發時間所屬時段之不同而不同、3.將旅行時間視為『定性』，且將一天分為數個時段，各時段有其相對應所需之旅行時間。當旅行時間視為滿足一統計分配之『隨機變數』時，本研究利用模擬方法，得到滿足該分配之旅行時間模擬值。最後以標記設定法為基礎加以修正，發展三種旅行時間型態在是否考慮延後出發時間與繞路行進情況下，所適用的時間相依最短路徑演算法。 本研究以隨機產生的六個網路為測試例題，假設旅行時間所滿足的統計分配與各項參數已知，又當旅行時間視為『定性』時，亦自行假設各不同時間所需之旅行時間值。利用三種演算法進行求解，發現當旅行時間視為隨機變數且不考慮延後出發與繞路行進時，本研究所提之演算法可得到準確度相當高之結果；又不論旅行時間為『隨機變數』或『定性』，考慮延後出發與繞路行進之演算法所求得之總旅行時間值皆小於不考慮延後出發與繞路行進所得到的總旅行時間。因此，不論旅行時間為何種型態、或是否考慮延後出發與繞路行進，本研究所提之演算法皆能提供使用者一條有效的行前路線建議。

This paper focuses on developing an algorithm for time-dependent shortest path problems to provide travelers an efficient and an effective 「pre-trip」 information for route choice. We propose three algorithms in this study：1.the first algorithm does not consider the possibility of delay and detour. It treats travel-time as a random variable with a homogeneous expected function simulation technique is used to generate travel-time along each road segment; 2.the second algorithm takes delay and detour, treated as deterministic parameters, into account. We also divide a day into several time zones and each time zone has its own deterministic travel time; 3. The major difference of the third algorithm from the second one is travel time on each road segment is treated as a random variable and each time zone has its own travel time distribution (with different parameters). We use six random network examples to examine the efficiency and accuracy of these algorithms. The testing results shows that our proposed algorithm is valid and efficient.