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