考量大眾運輸指派之時刻表最佳化

Timetable Scheduling considering Transit Assignment

巫驊晏(Hua-Yen Wu)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704025

摘要

時刻表訂定為大眾運輸主要研究之一，而乘客的旅行時間為服務指標之一。另外，本研究整理相關文獻發現，為了簡化問題，以往研究中對於需求的設定均為定值。此假設在現實生活中是不合理的，因此，本研究旨在建立訂定時刻表和旅行者路線時間最佳化模式。本研究提出混合整數線性規劃模式的大眾運輸時刻表訂定最佳化模式以最小化旅客旅行時間。該模式同時考量大眾運輸指派以及時刻表連接和旅客和大眾運具時間之整合。另外，因需求增加時，模式複雜度成指數上升，我們提出增量大眾運輸指派演算法以提高問題運算效率。大眾運輸指派演算法將所有旅客分群求解已得到最佳時刻表。從研究結果顯示，此研究之模式與演算法能夠有效的訂定時刻表，並且同時考量旅客對於時刻表之反應。

關鍵字

大眾運輸指派 ； 最佳化 ； 時刻表訂定 ； 混合整數線性規劃 ； 啟發式演算法

並列摘要

Travel time of passengers is one of the most important issues for public transit planning. In this study, a mixed-integer linear programming (MILP) generating an optimal timetable is proposed as an optimization framework for transit scheduling. It is realistic that the passengers choose their route choice based on the timetable, hence passenger change their route when timetables are altered. However, past studies assume that demand is constant. Therefore, the goal of this paper is to minimize total travel time of passengers while considering passenger route choice. This model is composed of the passenger network flow, the connection of timetable and the integration of passengers and buses. To enhance the solution efficiency, the proposed model is reformulated into a set-partitioning problem in purpose of reducing the scale of the problem, and an incremental assignment heuristic is developed. Through the procedure of heuristic, the route choice of passengers is determined separately in several iterations for the purpose of decreasing computational time. A case is demonstrated and the routes of passengers are analyzed. The solution shows that the proposed model is efficient. A computational study is conducted to evaluate the performance of the proposed methodology.

並列關鍵字

Scheduling ； Transit assignment ； Optimization ； set partitioning. heuristic ； Public Transit ； Timetable ； Mixed Integer Linear Programming (MILP)

參考文獻

[1] Castelli, L., Pesenti, R., & Ukovich, W. (2004). Scheduling multimodal transportation systems. European Journal of Operational Research, 155, 603-615.

[2] Ceder, A., Golany, B., & Tal, O. (2001). Creating bus timetables with maximal synchronization. Tansportation Research Part A, 35, 913-928.

[3] Chakroborty, P. (2003). Genetic Algorithms for Optimal Urban Transit Network Design. Computer-Aided Civil and Infrastructure Engineering, 18, 184-200.

[4] Cominetti, R., & Correa, J. (2001). Common-lines and passenger assignment in congested transit networks. Transportation Science, 35(3), 250-267.

[5] Chu, J. C. (2017). Mixed-integer programming model and branch-and-price-and-cut algorithm for urban bus network design and timetabling, under review.