Demand-oriented timetable design for urban rail transit under stochastic demand

Document Type: Research Paper


1 Industrial Engineering Department, Tarbiat Modares University, Tehran, Iran.

2 Industrial Engineering Department, Tarbiat Modares University, Tehran, Iran

3 School of Railway Engineering, Iran University of Science and Technology, Tehran, Iran


In the context of public transportation system, improving the service quality and robustness through minimizing the average passengers waiting time is a real challenge. This study provides robust stochastic programming models for train timetabling problem in urban rail transit systems. The objective is minimization of the weighted summation of the expected cost of passenger waiting time, its variance and the penalty function including the capacity violation due to overcrowding. In the proposed formulations, the dynamic and uncertain travel demand is represented by the scenario-based multi-period arrival rates of passenger. Two versions of the robust stochastic programming models are developed and a comparative analysis is conducted to testify the tractability of the models. The effectiveness of the proposed stochastic programming model was demonstrated through the application to Tehran underground urban railway. The outcomes show the reductions in expected passenger waiting time of 22%, and cost variance drop of 60% compared with the baseline plans using the proposed robust optimization approach.


Main Subjects

Ahmed S, Sahinidis NV (1998) Robust process planning under uncertainty Industrial & Engineering Chemistry Research 37:1883-1892
Albrecht T (2009) Automated timetable design for demand-oriented service on suburban railways Public Transport 1:5-20
Assis WO, Milani BlE (2004) Generation of optimal schedules for metro lines using model predictive control Automatica 40:1397-1404
Avriel M, Williams A (1970) The value of information and stochastic programming Operations Research 18:947-954
Bai D, Carpenter T, Mulvey J (1997) Making a case for robust optimization models Management science 43:895-907
Barrena E, Canca D, Coelho LC, Laporte G (2014a) Exact formulations and algorithm for the train timetabling problem with dynamic demand Computers & Operations Research 44:66-74
Barrena E, Canca D, Coelho LC, Laporte G (2014b) Single-line rail rapid transit timetabling under dynamic passenger demand Transportation Research Part B: Methodological 70:134-150
Beraldi P, Musmanno R, Triki C (1998) Solving optimal power dispatch via stochastic linear programming with restricted recourse Department of Electronics, Informatics and Systems, University of Calabria, Italy, Techinical report
Birge JR (1982) The value of the stochastic solution in stochastic linear programs with fixed recourse Mathematical programming 24:314-325
Bozorgi-Amiri A, Jabalameli M, Al-e-Hashem SM (2013) A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty OR spectrum 35:905-933
Canca D, Barrena E, Algaba E, Zarzo A (2013) Design and analysis of demand-adapted railway timetables arXiv preprint arXiv:13070970
Canca D, Barrena E, Laporte G, Ortega FA (2014) A short-turning policy for the management of demand disruptions in rapid transit systems Annals of Operations Research:1-22
Carrel A, Mishalani RG, Wilson NH, Attanucci JP (2013) A framework for evaluating operations control on a metro line: integrating multiple perspectives and automatically collected train and passenger movement data Public Transport 5:149-176
Carrel A, Mishalani RG, Wilson NH, Attanucci JP, Rahbee AB (2010) Decision Factors in Service Control on High-Frequency Metro Line Transportation Research Record: Journal of the Transportation Research Board 2146:52-59
Chierici A, Cordone R, Maja R (2004) The demand-dependent optimization of regular train timetables Electronic Notes in Discrete Mathematics 17:99-104
Corman F, Meng L (2015) A Review of Online Dynamic Models and Algorithms for Railway Traffic Management Intelligent Transportation Systems, IEEE Transactions on 16:1274-1284 doi:10.1109/TITS.2014.2358392
Cury J, Gomide F, Mendes M (1980) A methodology for generation of optimal schedules for an underground railway system Automatic Control, IEEE Transactions on 25:217-222
Dou FD, Xu J, Wang L, Jia L (2013) A train dispatching model based on fuzzy passenger demand forecasting during holidays Journal of Industrial Engineering and Management 6:320-335
Eberlein XJ (1997) Real-time control strategies in transit operations: Models and analysis Transportation Research Part A 31:69-70
Eberlein XJ, Wilson NH, Barnhart C, Bernstein D (1998) The real-time deadheading problem in transit operations control Transportation Research Part B: Methodological 32:77-100
Eberlein XJ, Wilson NH, Bernstein D (1999) Modeling real-time control strategies in public transit operations. In:  Computer-aided transit scheduling. Springer, pp 325-346
Fu Y, Sun J, Lai K, Leung JW (2014) A robust optimization solution to bottleneck generalized assignment problem under uncertainty Annals of Operations Research:1-11
Goerigk M, Schöbel A (2015) Algorithm engineering in robust optimization arXiv preprint arXiv:150504901
Hassannayebi E, Sajedinejad A, Mardani S (2014) Urban rail transit planning using a two-stage simulation-based optimization approach Simulation Modelling Practice and Theory 49:151-166
Islam MK, Vandebona U (2010) Reliability analysis of public transit systems using stochastic simulation
Laguna M, Lino P, Pérez A, Quintanilla S, Valls V (2000) Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines European Journal of Operational Research 127:444-457
Leung SC, Wu Y (2004) A robust optimization model for stochastic aggregate production planning Production planning & control 15:502-514
Li X, Yang X (2013) A STOCHASTIC TIMETABLE OPTIMIZATION MODEL IN SUBWAY SYSTEMS International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 21:1-15
Liao S, Van Delft C, Vial J-P (2013) Distributionally robust workforce scheduling in call centres with uncertain arrival rates Optimization Methods and Software 28:501-522
Lin W-S, Sheu J-W (2011) Metro traffic regulation by adaptive optimal control Intelligent Transportation Systems, IEEE Transactions on 12:1064-1073
Lin W, Sheu J (2010) Automatic train regulation for metro lines using dual heuristic dynamic programming Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit 224:15-23
List GF, Wood B, Nozick LK, Turnquist MA, Jones DA, Kjeldgaard EA, Lawton CR (2003) Robust optimization for fleet planning under uncertainty Transportation Research Part E: Logistics and Transportation Review 39:209-227
Malcolm SA, Zenios SA (1994) Robust optimization for power systems capacity expansion under uncertainty Journal of the operational research society:1040-1049
Meng L, Zhou X (2011) Robust single-track train dispatching model under a dynamic and stochastic environment: a scenario-based rolling horizon solution approach Transportation Research Part B: Methodological 45:1080-1102
Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems Operations research 43:264-281
Niu H, Zhang M (2012) An Optimization to Schedule Train Operations with Phase-Regular Framework for Intercity Rail Lines Discrete Dynamics in Nature and Society 2012
Niu H, Zhou X (2013) Optimizing urban rail timetable under time-dependent demand and oversaturated conditions Transportation Research Part C: Emerging Technologies 36:212-230
O’Dell SW, Wilson NH (1999) Optimal real-time control strategies for rail transit operations during disruptions. In:  Computer-aided transit scheduling. Springer, pp 299-323
Ray PA, Watkins Jr DW, Vogel RM, Kirshen PH (2013) Performance-Based Evaluation of an Improved Robust Optimization Formulation Journal of Water Resources Planning and Management 140
Sáez D, Cortés CE, Milla F, Núñez A, Tirachini A, Riquelme M (2012) Hybrid predictive control strategy for a public transport system with uncertain demand Transportmetrica 8:61-86
Saffari H, Makui A, Mahmoodian V, Pishvaee MS (2015) Multi-objective robust optimization model for social responsible closed-loop supply chain solved by non-dominated sorting genetic algorithm Journal of Industrial and Systems Engineering 8:42-59
Saharidis GK, Dimitropoulos C, Skordilis E (2014) Minimizing waiting times at transitional nodes for public bus transportation in Greece Operational Research 14:341-359
Sahinidis NV (2004) Optimization under uncertainty: state-of-the-art and opportunities Computers & Chemical Engineering 28:971-983
Salido M, Barber F, Ingolotti L Robustness in railway transportation scheduling. In: Intelligent Control and Automation, 2008. WCICA 2008. 7th World Congress on, 2008. IEEE, pp 2880-2885
Scholz S, Strobel H, Oettich S Demand-driven automated urban rapid rail transit: A new approach to the assessment of the operational efficiency. In: APM’03, Proceedings of the 9th international conference on automated people movers, Singapore, 2003.
Shafia MA, Aghaee MP, Sadjadi SJ, Jamili A (2012) Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm Intelligent Transportation Systems, IEEE Transactions on 13:307-317
Shen S (2000) Integrated real-time disruption recovery strategies: a model for rail transit systems. Massachusetts Institute of Technology
Shen S, Wilson NH (2001) An optimal integrated real-time disruption control model for rail transit systems. In:  Computer-aided scheduling of public transport. Springer, pp 335-363
Sheu J-W, Lin W-S (2012) Adaptive Optimal Control for Designing Automatic Train Regulation for Metro Line Control Systems Technology, IEEE Transactions on 20:1319-1327
Smith S, Sheffi Y (1989) Locomotive scheduling under uncertain demand. vol 1251.
Sun L, Jin JG, Lee D-H, Axhausen KW, Erath A (2014) Demand-driven timetable design for metro services Transportation Research Part C: Emerging Technologies 46:284-299
Trozzi V, Gentile G, Bell MG, Kaparias I (2013) Dynamic user equilibrium in public transport networks with passenger congestion and hyperpaths Transportation Research Part B: Methodological 57:266-285
Wales J, Marinov M (2015) Analysis of delays and delay mitigation on a metropolitan rail network using event based simulation Simulation Modelling Practice and Theory 52:52-77
Wang Y, De Schutter B, van den Boom T, Ning B, Tang T Real-time scheduling for single lines in urban rail transit systems. In: Intelligent Rail Transportation (ICIRT), 2013 IEEE International Conference on, 2013. IEEE, pp 1-6
Xu X, Li K, Li X (2014) Research on Passenger Flow and Energy Consumption in A Subway System with Fuzzy Passenger Arrival Rates Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit:0954409714524378
Xu X, Li K, Li X (2015) A multi‚Äźobjective subway timetable optimization approach with minimum passenger time and energy consumption Journal of Advanced Transportation
Yan S, Chi C-J, Tang C-H (2006) Inter-city bus routing and timetable setting under stochastic demands Transportation Research Part A: Policy and Practice 40:572-586
Yan S, Lin J-R, Lai C-W (2013) The planning and real-time adjustment of courier routing and scheduling under stochastic travel times and demands Transportation Research Part E: Logistics and Transportation Review 53:34-48
Yang L, Li K, Gao Z (2009) Train timetable problem on a single-line railway with fuzzy passenger demand Fuzzy Systems, IEEE Transactions on 17:617-629
Yin J, Chen D, Yang L, Tang T, Ran B (2015) Efficient Real-Time Train Operation Algorithms With Uncertain Passenger Demands Intelligent Transportation Systems, IEEE Transactions on PP:1-13 doi:10.1109/TITS.2015.2478403
Yu C-S, Li H-L (2000) A robust optimization model for stochastic logistic problems International Journal of Production Economics 64:385-397