A Multi-objective Optimization Model for Robust Skip-Stop Scheduling with Earliness and Tardiness Penalties

Abstract

Inefficient transport systems impose extra travel time for travelers, cause dissatisfaction and reduce service levels. In this study, the demand-oriented train scheduling problem is addressed using a robust skip-stop method under uncertain arrival rates during peak hours. This paper presents alternative mathematical models, including a two-stage scenario-based stochastic programming model and two robust optimization models, to minimize the total travel time of passengers and their waiting time at stations. The modeling framework accounts for the design and implementation of robust skip-stop schedules with earliness and tardiness penalties. As a case study, each of the developed models is implemented on line No. 5 of the Tehran metro, and the results are compared. To validate the skip-stop schedules, the values of the stochastic solution and the expected value of perfect information are calculated. In addition, a sensitivity analysis is conducted to test the performance of the model under different scenarios. According to the obtained results, having perfect information can reduce up to 16% of the value of the weighted objective function. The proposed skip-stop method has been shown to save about 5% in total travel time and 49% in weighted objective function, which is a summation of travel times and waiting times as against regular all-stop service. The value of stochastic solutions is about 21% of the value of the weighted objective function, which shows that the stochastic model demonstrates better performance than the deterministic model.

Keywords

Train timetabling / Demand-oriented Train Scheduling / Robust optimization / Earliness and tardiness / Demand uncertainty / Stop-skip service

References

[1] Iloglu S, Albert LA. An integrated network design and scheduling problem for network recovery and emergency response. Oper Res Perspect, 2018, 5: 218-231

[2] Kabasakal A, Kutlar A, Sarikaya M. Efficiency determinations of the worldwide railway companies via DEA and contributions of the outputs to the efficiency and TFP by panel regression. CEJOR, 2015, 23(1): 69-88

[3] Peng Q, Zhao J, Wen C. A rolling horizon-based decomposition algorithm for the railway network train timetabling problem. Int J Rail Transp, 2013, 1(3): 129-160

[4] Hassannayebi E, Zegordi SH, Yaghini M. Train timetabling for an urban rail transit line using a Lagrangian relaxation approach. Appl Math Model, 2016, 40(23): 9892-9913

[5] Castillo E, Gallego I, Ureña JM, Coronado JM. Timetabling optimization of a single railway track line with sensitivity analysis. Top, 2009, 17(2): 256-287

[6] Abril M, Barber F, Ingolotti L, Salido M, Tormos P, Lova A. An assessment of railway capacity. Transp Res E: Logist Transp Rev, 2008, 44(5): 774-806

[7] Burdett RL, Kozan E. A sequencing approach for creating new train timetables. OR Spectr, 2010, 32(1): 163-193

[8] Liu P, Han B. Optimizing the train timetable with consideration of different kinds of headway time. J Algorithm Comput Technol, 2017, 11(2): 148-162

[9] Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. Demand-oriented timetable design for urban rail transit under stochastic demand. J Ind Syst Eng, 2016, 9(3): 28-56.

[10] Shakibayifar M, Hassannayebi E, Jafary H, Sajedinejad A. Stochastic optimization of an urban rail timetable under time-dependent and uncertain demand. Appl Stoch Model Bus Ind, 2017, 33(6): 640-661

[11] Godwin T, Gopalan R, Narendran T. Freight train routing and scheduling in a passenger rail network: computational complexity and the stepwise dispatching heuristic. Asia-Pac J Oper Res, 2007, 24(04): 499-533

[12] Shi J, Yang L, Yang J, Gao Z. Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: an integer linear optimization approach. Transp Res B Methodol, 2018, 110: 26-59

[13] Botte M, D’Acierno L. Dispatching and rescheduling tasks and their interactions with travel demand and the energy domain: models and algorithms. Urban Rail Transit, 2018, 4(4): 163-197

[14] 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: IEEE international conference on intelligent rail transportation (ICIRT), 2013. IEEE, pp 1–6

[15] Jong J-C, Suen C-S, Chang S. Decision support system to optimize railway stopping patterns: application to Taiwan High-speed Rail. Transp Res Rec J Transp Res Board, 2012, 2289: 24-33

[16] Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. Optimizing headways for urban rail transit services using adaptive particle swarm algorithms. Public Transp, 2018, 10(1): 23-62

[17] Azadpeyma A, Kashi E. Level of service analysis for metro station with transit cooperative research program (TCRP) manual: a case study—Shohada Station in Iran. Urban Rail Transit, 2019, 5(1): 39-47

[18] Hassannayebi Erfan, Sajedinejad Arman, Mardani Soheil. Disruption Management in Urban Rail Transit System. Advances in Civil and Industrial Engineering, 2016 420-450.

[19] Shakibayifar M, Hassannayebi E, Mirzahossein H, Taghikhah F, Jafarpur A. An intelligent simulation platform for train traffic control under disturbance. Int J Model Simul, 2018, 39: 1-22.

[20] Furth PG. Zonal route design for transit corridors. Transp Sci, 1986, 20(1): 1-12

[21] Eberlein XJ, Wilson NH, Barnhart C, Bernstein D. The real-time deadheading problem in transit operations control. Transp Res B Methodol, 1998, 32(2): 77-100

[22] Vuchic RJHW (2005) Urban transit: operations, planning, and economics 2005

[23] Sun A, Hickman M. The real–time stop–skipping problem. J Intell Transp Syst, 2005, 9(2): 91-109

[24] Kroon L, Maróti G, Helmrich MR, Vromans M, Dekker R. Stochastic improvement of cyclic railway timetables. Transp Res B Methodol, 2008, 42(6): 553-570

[25] Kroon L, Huisman D, Abbink E, Fioole P-J, Fischetti M, Maróti G, Schrijver A, Steenbeek A, Ybema R. The new Dutch timetable: the OR revolution. Interfaces, 2009, 39(1): 6-17

[26] Yang L, Gao Z, Li K. Passenger train scheduling on a single-track or partially double-track railway with stochastic information. Eng Optim, 2010, 42(11): 1003-1022

[27] Paolucci M, Pesenti R. An object-oriented approach to discrete-event simulation applied to underground railway systems. Simulation, 1999, 72(6): 372-383

[28] Eberlein XJ, Wilson NHM, Bernstein D. The holding problem with real–time information available. Transp Sci, 2001, 35(1): 1-18

[29] Koutsopoulos HN, Wang Z. Simulation of urban rail operations: application framework. Transp Res Rec J Transp Res Board, 2007, 1: 84-91

[30] Niu H. Determination of the skip-stop scheduling for a congested transit line by bilevel genetic algorithm. Int J Comput Intell Syst, 2011, 4(6): 1158-1167

[31] Canca D, Barrena E, Zarzo A, Ortega F, Algaba E. Optimal train reallocation strategies under service disruptions. Procedia Soc Behav Sci, 2012, 54: 402-413

[32] Hassannayebi E, Sajedinejad A, Mardani S. Urban rail transit planning using a two-stage simulation-based optimization approach. Simul Model Pract Theory, 2014, 49: 151-166

[33] Cao Z, Yuan Z, Li D. Estimation method for a skip-stop operation strategy for urban rail transit in China. J Mod Transp, 2014, 22(3): 174-182

[34] Niu H, Zhou X, Gao R. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: nonlinear integer programming models with linear constraints. Transp Res B Methodol, 2015, 76: 117-135

[35] Cao Z, Yuan Z, Zhang S. Performance analysis of stop-skipping scheduling plans in rail transit under time-dependent demand. Int J Environ Res Public Health, 2016, 13(7): 707

[36] Yang L, Qi J, Li S, Gao Y. Collaborative optimization for train scheduling and train stop planning on high-speed railways. Omega, 2016, 64: 57-76

[37] Nesheli MM, Ceder A. Use of real-time operational tactics to synchronize transfers in headway-based public transport service. Transp Res Rec, 2016, 2539(1): 103-112

[38] Abdelhafiez EA, Salama MR, Shalaby MA. Minimizing passenger travel time in URT system adopting skip-stop strategy. J Rail Transp Plan Manage, 2017, 7(4): 277-290.

[39] Hassannayebi E, Zegordi SH. Variable and adaptive neighbourhood search algorithms for rail rapid transit timetabling problem. Comput Oper Res, 2017, 78: 439-453

[40] Altazin E, Dauzère-Pérès S, Ramond F, Tréfond S. Rescheduling through stop-skipping in dense railway systems. Transp Res C: Emerg Technol, 2017, 79: 73-84

[41] Shakibayifar M, Hassannayebi E, Mirzahossein H, Shahabi A. An integrated train scheduling and infrastructure development model in railway networks. Sci Iran, 2017, 24(6): 3409-3422.

[42] Jiang F, Cacchiani V, Toth P. Train timetabling by skip-stop planning in highly congested lines. Transp Res B Methodol, 2017, 104: 149-174

[43] Hassannayebi E, Zegordi SH, Yaghini M, Amin-Naseri MR. Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals. Transp Plan Technol, 2017, 40(3): 278-304

[44] Qi J, Li S, Gao Y, Yang K, Liu P. Joint optimization model for train scheduling and train stop planning with passengers distribution on railway corridors. J Oper Res Soc, 2018, 69(4): 556-570

[45] Shang P, Li R, Liu Z, Yang L, Wang Y. Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network. Transp Res C: Emerg Technol, 2018, 89: 321-343

[46] Shafia MA, Aghaee MP, Sadjadi SJ, Jamili A. Robust train timetabling problem: mathematical model and branch and bound algorithm. IEEE Trans Intell Transp Syst, 2012, 13(1): 307-317

[47] Jamili A, Aghaee MP. Robust stop-skipping patterns in urban railway operations under traffic alteration situation. Transp Res C: Emerg Technol, 2015, 61: 63-74

[48] Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. Train timetabling at rapid rail transit lines: a robust multi-objective stochastic programming approach. Oper Res Int J, 2017, 17(2): 435-477

[49] Shakibayifar M, Sheikholeslami A, Corman F, Hassannayebi E. An integrated rescheduling model for minimizing train delays in the case of line blockage. Oper Res Int J, 2017, 10: 1-29

[50] Qi J, Cacchiani V, Yang L. Robust train timetabling and stop planning with uncertain passenger demand. Electron Notes Discret Math, 2018, 69: 213-220

[51] Lee EH, Lee I, Cho S-H, Kho S-Y, Kim D-K. A travel behavior-based skip-stop strategy considering train choice behaviors based on smartcard data. Sustainability, 2019, 11(10): 2791

[52] Mulvey JM, Vanderbei RJ, Zenios SA. Robust optimization of large-scale systems. Oper Res, 1995, 43(2): 264-281