臺灣博碩士論文加值系統

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

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.

口試委員會審定書
致謝 iii
中文摘要 iv
ABSTRACT v
CONTENTS vi
LIST OF FIGURES viii
LIST OF TABLES ix
Chapter 1 Introduction 1
1.1 Background 1
1.2 Research Objectives 1
1.3 Thesis Organization 2
Chapter 2 Literature review 4
2.1 Timetabling models 4
2.1.1 Schedule Synchronization 4
2.1.2 Utility of Passenger 5
2.2 Transit Assignment in transit planning problems 8
Chapter 3 Model Formulation 10
3.1 Problem Statement 10
3.2 MIP model 11
3.2.1 Terminology and notations 11
3.2.2 Model Formulation 15
3.2.4 Feasible Passenger Path 20
3.2.5 Integration of Passenger and Bus 25
Chapter 4 Solution Method 31
4.1 Reformulation and Route Generation 31
4.1.1 Process of Reformulation 31
4.1.2 Route Choices Tree 33
4.2 Incremental assignment 38
Chapter 5 Numerical examples 40
5.1 Case 1 40
5.2 Case 2 43
5.2.1 Case 2 High Frequency 44
5.2.2 Case 2 Low Frequency 48
5.3 Result Analysis 49
5.3.1 Scenario 1 49
5.3.2 Scenario 2 54
5.3.3 Scenario 3 57
5.3.4 Scenario 4 62
Chapter 6 Conclusions and Future Research 68
6.1 Conclusions 68
6.2 Future Work 69
Reference 71
Appendix 73

[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.
[6]Ibarra-Rojas, O. J., Giesen, R., & Rios-Solis, Y. A. (2014). An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks. Transportation Research Part B, 70, 35-46.
[7]Ibarra-Rojas, O. J., & Rios-Solis, Y. A. (2012). Synchronization of bus timetabling. Transportation Research Part B: Methodological, 46(5), 599-614.
[8]Li, Z.-C., Lam, W. H., Wong, S., & Sumalee, A. (2010). An activity-based approach for scheduling multimodal transit services. Transportation, 37(5), 751-774.
[9]Niu, H., Tian, X., & Zhou, X. (2015). Demand-driven train schedule synchronization for high-speed rail lines. IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 16(5), 2642-2652.
[10]Nuzzolo, A., Crisalli, U., & Rosati, L. (2012). A schedule-based assignment model with explicit capacity constraints for congested transit networks. Transportation Research Part C: Emerging Technologies, 20(1), 16-33.
[11]Schmöcker, J.-D., Fonzone, A., Shimamoto, H., Kurauchi, F., & Bell, M. G. (2011). Frequency-based transit assignment considering seat capacities. Transportation Research Part B: Methodological, 45(2), 392-408.
[12]Schr¨oder, M., & Solchenbach, I. (2006). Optimization of Transfer Quality in Regional Public Transit. Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM 84
[13]Szeto, W., Jiang, Y., Wong, K., & Solayappan, M. (2013). Reliability-based stochastic transit assignment with capacity constraints: Formulation and solution method. Transportation Research Part C: Emerging Technologies, 35, 286-304.
[14]Wong, R. C. W., Yuen, T. W. Y., Fung, K. W., & Leung, J. M. Y. (2008). Optimizing Timetable Synchronization for Rail Mass Transit. Transportation Science, 42( 1), 57–69.