運用最短路徑演算法與動態資訊進行大眾運輸行前旅次規劃

Abstract

在國內積極推動大眾運輸系統之環境下，各大眾運輸主管機關及營運機構均積極發展大眾運輸旅次規劃系統(Transit Trip Planning Systems) 。然目前國內外文獻所提及之大眾運輸旅次規劃演算法，大部分皆為特定邏輯設計，如最少轉乘以及最快到達。如此一來，所規劃出的方案將無法考慮到其餘邏輯。而本研究回顧目前線上系統，發現大眾運輸行前旅次規劃追求的，無論是轉乘次數、旅行時間、票價或者步行距離都是最少成本。故本研究認為，可將最短路徑演算法的概念套入行前旅次規劃演算法，進行追求最少成本，但相較於公路路網，大眾運輸路網具有一些特殊性，導致最短路徑演算法無法直接套入。故本研究首先將大眾運輸網路重新定義，並命名為加強式的網路。且回顧目前線上系統，發現由於未將動態資訊因素納入規劃分析中，當以時刻表規劃的方案中發生誤點現象時，使用者可能因為班次誤點，必須在轉乘站等待過久的時間。若能考慮動態資訊，供使用者在出發前，以目前時間點所得知的到站資訊進行規劃。而本研究利用即時讀取到站資訊的步驟考量動態資訊。最後以修改過的最短路徑演算法進行規劃。而本研究認為，規劃某特定邏輯時，應該以該邏輯作為目標式，其餘邏輯可由使用者自行設定作為限制式，例如：當進行最少轉乘邏輯規劃時，目標式即為轉乘次數最少，而限制式則可以是在多少旅行時間內、或是在多少票價內等限制。而本研究將利用目前較為多人討論的，最少旅行時間和最少轉乘次數作為主要邏輯。而本研究利用選擇變數較少的轉乘次數，作為使用者自行設定的限制變數。故本篇論文，將求解在使用者所限定的轉乘次數上限內，最少旅行時間之方案。經本研究以虛擬網路，以及新竹市區大眾運輸網路為例，發現本研究所構建的路網以及演算法，將可在短時間內規劃出合理的方案，並正確規劃出，考慮動態資訊之行前旅次規劃方案。

Many transport authorities and operative organizations develop positively transit trip planning systems for elevating level of services, but those algorithms just for one specifically cost, that cloud be number of transfer, travel time, free or walking distance, and not take into real-time information. Given the origin/destination pair, all transit pre-trip systems will find the lowest cost way, and any costs are independent and important. However, if we just take only one cost into plan, the solution may be irrationality, so this paper modified shortest path algorithm to solve this problem. Choosing a specifically cost be an objection and the others could be subjection. In this paper, firstly, we redefined the transit network due to some study indicated shortest path algorithm can’t use on it. Secondly, when passengers use the transit trip planning systems, it will load real-time information. Finally, the transit trip planning systems use the modified shortest path algorithm for planning. The purpose of this research is develops an algorithm, that can plan a trip with minimum main cost and under the other minor cost subject. This paper use travel time as main cost and the minor cost is number of transfer. Therefore, we test the accuracy by using a network which considering the real-time information of buses. The results have shown that the algorithm can generate the reasonable alternatives immediately.