An efficient heuristic method for joint optimization of train scheduling and stop planning on double-track railway systems

References

• Azadi Moghaddam Arani A, Jolai F, Nasiri MM. 2019. A multi-commodity network flow model for railway capacity optimization in case of line blockage. Int J Rail Transp. 7(4):297–224.
   Web of Science ®Google Scholar
• Bahramian Z, Bagheri M. 2015. A simulation-based optimization approach for passenger train timetabling with periodic track maintenance and stops for praying. J Mod Transp. 23(2):148–157.
   Web of Science ®Google Scholar
• Banić M, Miltenović A, Pavlović M, Ćirić I. 2019. Intelligent machine vision based railway infrastructure inspection and monitoring using UAV. Facta Univ Ser Mech Eng. 17:357–364.
   Web of Science ®Google Scholar
• Belotti P, Bonami P, Fischetti M, Lodi A, Monaci M, Nogales-Gómez A, Salvagnin D. 2016. On handling indicator constraints in mixed integer programming. Comput Optim Appl. 65(3):545–566.
   Web of Science ®Google Scholar
• Bevrani B, Burdett RL, Yarlagadda PKDV. 2015. A case study of the Iranian national railway and its absolute capacity expansion using analytical models. Transport. 32(4):398–414.
   Web of Science ®Google Scholar
• Brännlund U, Lindberg PO, Nou A, Nilsson JE. 1998. Railway timetabling using Lagrangian relaxation. Transport Sci. 32(4):358–369.
   Web of Science ®Google Scholar
• Burdett RL, Kozan E. 2010. A sequencing approach for creating new train timetables. OR Spectrum. 32(1):163–193.
   Web of Science ®Google Scholar
• Cacchiani V, Caprara A, Fischetti M. 2012. A Lagrangian heuristic for robustness, with an application to train timetabling. Transp Sci. 46(1):124–133.
   Web of Science ®Google Scholar
• Cacchiani V, Caprara A, Toth P. 2008. A column generation approach to train timetabling on a corridor. 4OR. 6(2):125–142.
   Web of Science ®Google Scholar
• Cacchiani V, Galli L, Toth P. 2015. A tutorial on non-periodic train timetabling and platforming problems. EURO J Transp Logist. 4(3):285–320.
   Web of Science ®Google Scholar
• Cacchiani V, Jiang F, Toth P. 2016. Timetable Optimization for High-Speed Trains at Chinese Railways. ElectronNotes Discre Math. 55:29–32.
   Google Scholar
• Caimi G, Kroon L, Liebchen C. 2017. Models for railway timetable optimization: Applicability and applications in practice. J Rail Transp Plan Manag. 6(4):285–312.
   Web of Science ®Google Scholar
• Caprara A, Fischetti M, Toth P. 2002. Modeling and solving the train timetabling problem. Oper Res. 50(5):851–861.
   Web of Science ®Google Scholar
• Caprara A, Monaci M, Toth P, Guida PL. 2006. A Lagrangian heuristic algorithm for a real-world train timetabling problem. Discrete Appl Math. 154(5):738–753.
   Web of Science ®Google Scholar
• Chen D, Ni S, Xu CA, Jiang X. 2019. Optimizing the draft passenger train timetable based on node importance in a railway network. Transp Lett. 11(1):20–32.
   Web of Science ®Google Scholar
• Corman F, D’Ariano A, Pacciarelli D, Sabene F, Sama M. 2015. Train Delay and Passenger Travel Time Minimization in Real-Time Railway Traffic Management. Proc. of CASPT 2015, Conference on Advanced Systems in Public Transport. p. 19–23.
   Google Scholar
• D’Ariano A, Pacciarelli D, Pranzo M. 2007. A branch and bound algorithm for scheduling trains in a railway network. Eur J Oper Res. 183(2):643–657.
   Web of Science ®Google Scholar
• Dauzère-Pérès S, DE Almeida D, Guyon O, Benhizia F. 2015. A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources. Transp Res Part B Methodol. 74:138–150.
   Web of Science ®Google Scholar
• DE Fabris S, Longo G, Medeossi G, Pesenti R. 2014. Automatic generation of railway timetables based on a mesoscopic infrastructure model. J Rail Transp Plan Manag. 4(1-2):2–13.
   Google Scholar
• Dessouky MM, Lu Q, Zhao J, Leachman RC. 2006. An exact solution procedure to determine the optimal dispatching times for complex rail networks. IIE Trans. 38(2):141–152.
   Web of Science ®Google Scholar
• Fouilhoux P, Ibarra-Rojas OJ, Kedad-Sidhoum S, Rios-Solis YA. 2016. Valid inequalities for the synchronization bus timetabling problem. Eur J Oper Res. 251(2):442–450.
   Web of Science ®Google Scholar
• Ghoseiri K, Szidarovszky F, Asgharpour MJ. 2004. A multi-objective train scheduling model and solution. Transportation Research Part B: Methodological. 38(10):927–952.
   Web of Science ®Google Scholar
• Gleixner AM, Berthold T, Müller B, Weltge S. 2017. Three enhancements for optimization-based bound tightening. J Glob Optim. 67(4):731–757.
   Web of Science ®Google Scholar
• Goossens J-W, VAN Hoesel S, Kroon L. 2004. A branch-and-cut approach for solving railway line-planning problems. Transp Sci. 38(3):379–393.
   Web of Science ®Google Scholar
• Goverde RM, Bešinović N, Binder A, Cacchiani V, Quaglietta E, Roberti R, Toth P. 2016. A three-level framework for performance-based railway timetabling. Transp Res Part C Emerg Technol. 67:62–83
   Web of Science ®Google Scholar
• Harrod S. 2013. A Method for Robust Strategic Railway Dispatch Applied to a Single Track Line. Transportation Journal. 52:26–51.
   Web of Science ®Google Scholar
• Hassannayebi E, Boroun M, Jordehi SA, Kor H. 2019. Train schedule optimization in a high-speed railway system using a hybrid simulation and meta-model approach. Comput Ind Eng. 138:106110.
   Web of Science ®Google Scholar
• Hassannayebi E, Kiyanfar F. 2012. A greedy randomized adaptive search procedure to solve the train sequencing and stop scheduling problem in double track railway lines. J Transp Res. 9:235–257.
   Google Scholar
• Hassannayebi E, Memarpour M, Mardani S, Shakibayifar M, Bakhshayeshi I, Espahbod S. 2019. A hybrid simulation model of passenger emergency evacuation under disruption scenarios: A case study of a large transfer railway station. J Simul. 1–25. Published online: 12 Sep 2019. 10.1080/17477778.2019.1664267
   Web of Science ®Google Scholar
• Hassannayebi E, Sajedinejad A, Mardani S. 2014. Urban rail transit planning using a two-stage simulation-based optimization approach. Simul Modell Pract Theory. 49:151–166.
   Web of Science ®Google Scholar
• Hassannayebi E, Sajedinejad A, Mardani S. 2016. Disruption management in urban rail transit system: a simulation based optimization approach. Handbook of Research on Emerging Innovations in Rail Transportation Engineering. Pennsylvania: IGI Global.
   Google Scholar
• Hassannayebi E, Zegordi SH. 2017. Variable and adaptive neighbourhood search algorithms for rail rapid transit timetabling problem. Comput Oper Res. 78:439–453.
   Web of Science ®Google Scholar
• Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. 2016. Demand-oriented timetable design for urban rail transit under stochastic demand. J Ind Syst Eng. 9:28–56.
   Google Scholar
• Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. 2017. Train timetabling at rapid rail transit lines: a robust multi-objective stochastic programming approach. Oper Res Int J. 17(2):435–477.
   Web of Science ®Google Scholar
• Hassannayebi E, Zegordi SH, Amin-Naseri MR, Yaghini M. 2018. Optimizing headways for urban rail transit services using adaptive particle swarm algorithms. Public Transp. 10(1):23–62.
   Web of Science ®Google Scholar
• Hassannayebi E, Zegordi SH, Yaghini M. 2016. Train timetabling for an urban rail transit line using a Lagrangian relaxation approach. Appl Math Modell. 40(23-24):9892–9913.
   Web of Science ®Google Scholar
• Hassannayebi E, Zegordi SH, Yaghini M, Amin-Naseri MR. 2017. Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals. Transp Plan Technol. 40(3):278–304.
   Web of Science ®Google Scholar
• Higgins A, Kozan E, Ferreira L. 1996. Optimal scheduling of trains on a single line track. Transp Res Part B Methodol. 30(2):147–161.
   Web of Science ®Google Scholar
• Huang H, Li K. 2017. Train timetable optimization for both a rail line and a network with graph-based approaches. Eng Optim. 49(12):2133–2149.
   Web of Science ®Google Scholar
• Jamili A. 2017. A mathematical model and a hybrid algorithm for robust periodic single-track train-scheduling problem. Int J Civ Eng. 15(1):63–75.
   Web of Science ®Google Scholar
• Jamili A, Shafia MA, Sadjadi SJ, Tavakkoli-Moghaddam R. 2012. Solving a periodic single-track train timetabling problem by an efficient hybrid algorithm. Eng Appl Artif Intell. 25(4):793–800.
   Web of Science ®Google Scholar
• Karoonsoontawong A, Taptana A. 2017. Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network. Netw Spat Econ. 17(1):1–39.
   Web of Science ®Google Scholar
• Khan MB, Zhou X. 2010. Stochastic optimization model and solution algorithm for robust double-track train-timetabling problem. IEEE Trans Intell Transp Syst. 11:81.
   Web of Science ®Google Scholar
• Kis T, Pesch E. 2005. A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. Eur J Oper Res. 164(3):592–608.
   Web of Science ®Google Scholar
• Kovalchuk V, Sysyn M, Gerber U, Nabochenko O, Zarour J, Dehne S. 2019. Experimental investigation of the influence of train velocity and travel direction on the dynamic behavior of stiff common crossings. Facta Univ Ser Mech Eng. 17: 345–356.
   Web of Science ®Google Scholar
• Lamorgese L, Mannino C, Piacentini M. 2016. Optimal train dispatching by benders’-like reformulation. Transportation Science. 50(3):910–925.
   Web of Science ®Google Scholar
• Lin DY, Ku YH. 2014. Using genetic algorithms to optimize stopping patterns for passenger rail transportation. Comput‐Aided CivilInfrastruct Eng. 29(4):264–278.
   Web of Science ®Google Scholar
• Liu SQ, Kozan E. 2009. Scheduling trains as a blocking parallel-machine job shop scheduling problem. Comput Oper Res. 36(10):2840–2852.
   Web of Science ®Google Scholar
• Liu SQ, Kozan E. 2011. Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model. Transp Sci. 45(2):175–198.
   Web of Science ®Google Scholar
• Lusby RM, Larsen J, Ehrgott M, Ryan D. 2011. Railway track allocation: models and methods. OR Spectrum. 33(4):843–883.
   Web of Science ®Google Scholar
• Masoud M, Kozan E, Kent G, Liu SQ. 2017. A new constraint programming approach for optimising a coal rail system. Optim Lett. 11(4):725–738.
   Web of Science ®Google Scholar
• Min Y-H, Park M-J, Hong S-P, Hong S-H. 2011. An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network. Transp Res Part B Methodol. 45(2):409–429.
   Web of Science ®Google Scholar
• Movahedi MM, Saati S, Vahidi AR. 2007. Iranian railway efficiency (1971-2004): An application of DEA. IJCMS. 2:1569–1579.
   Google Scholar
• Nawaz M, Enscore EE, Ham I. 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega. 11(1):91–95.
   Web of Science ®Google Scholar
• Niu H, Zhou X, Gao R. 2015. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints. Transp Res Part B Methodol. 76:117–135.
   Web of Science ®Google Scholar
• Parbo J, Nielsen OA, Prato CG. 2018. Reducing passengers’ travel time by optimising stopping patterns in a large-scale network: A case-study in the Copenhagen Region. Transp Res Part A Policy Pract. 113:197–212.
   Web of Science ®Google Scholar
• Pavlović M, Nikolić V, Simonović M, Mitrović V, Ćirić I. 2019. Edge detection parameter optimization based on the genetic algorithm for rail track detection. Facta Univ Ser Mech Eng. 17:333–344.
   Web of Science ®Google Scholar
• Pinedo M. 2012. Scheduling: theory, algorithms, and systems, Berlin, Germany: Springer.
   Google Scholar
• Qi J, Li S, Gao Y, Yang K, Liu P. 2018. Joint optimization model for train scheduling and train stop planning with passengers distribution on railway corridors. J Oper Res Soc. 69(4):556–570.
   Web of Science ®Google Scholar
• Qi J, Yang L, Di Z, Li S, Yang K, Gao Y. 2018. Integrated optimization for train operation zone and stop plan with passenger distributions. Transp Res. Part E Logist Transp Rev. 109:151–173.
   Web of Science ®Google Scholar
• Rajabighamchi F, Hajlou EMH, Hassannayebi E. 2019. A Multi-objective Optimization Model for Robust Skip-Stop Scheduling with Earliness and Tardiness Penalties. Urban Rail Transit. 5(3):172–185.
   Web of Science ®Google Scholar
• Rajendran C, Chaudhuri D. 1992. An efficient heuristic approach to the scheduling of jobs in a flowshop. Eur J Oper Res. 61(3):318–325.
   Web of Science ®Google Scholar
• Robenek T, Maknoon Y, Azadeh SS, Chen J, Bierlaire M. 2016. Passenger centric train timetabling problem. Transp Res Part B Methodol. 89:107–126.
   Web of Science ®Google Scholar
• Rodriguez J. 2007. A constraint programming model for real-time train scheduling at junctions. Transp Res Part B Methodol. 41(2):231–245.
   Web of Science ®Google Scholar
• Sajedinejad A, Mardani S, Hasannayebi E, Mir Mohammadi K S, Kabirian A. 2011. SIMARAIL: simulation based optimization software for scheduling railway network. Simulation Conference (WSC), Proceedings of the 2011 Winter, IEEE, 3730–3741.
   Google Scholar
• Shakibayifar M, Hassannayebi E, Jafary H, Sajedinejad A. 2017. Stochastic optimization of an urban rail timetable under time‐dependent and uncertain demand. Appl Stochastic Models Bus Ind. 33(6):640–661.
   Web of Science ®Google Scholar
• Shakibayifar M, Hassannayebi E, Mirzahossein H, Taghikhah F, Jafarpur A. 2019. An intelligent simulation platform for train traffic control under disturbance. Int J Model Simul. 39(3):135–156.
   Google Scholar
• Shakibayifar M, Hassannayebi E, Mirzahossein H, Zohrabnia S, Shahabi A. 2017. An integrated train scheduling and infrastructure development model in railway networks. Sci Iran. 0(0):0–3422.
   Google Scholar
• Shakibayifar M, Sheikholeslami A, Corman F, Hassannayebi E. 2020. An integrated rescheduling model for minimizing train delays in the case of line blockage. Oper Res Int J. 20(1):59–87.
   Web of Science ®Google Scholar
• Sparing D, Goverde RM. 2017. A cycle time optimization model for generating stable periodic railway timetables. Transp Res Part B Methodol. 98:198–223.
   Web of Science ®Google Scholar
• Szpigel B. 1973. Optimal train scheduling on a single track railway. Oper Res. 72:343–351.
   Google Scholar
• Xu X, Li K, Yang L, Gao Z. 2019. An efficient train scheduling algorithm on a single-track railway system. J Sched. 22(1):85–21.
   Web of Science ®Google Scholar
• Yan X, Yue Y, Li D. 2018. A New Train Timetable Optimization Model Using a Lagrangian Relaxation Guided Heuristic for a Real-World High-Speed Railway Line. Proceedings of the 2018 8th International Conference on Management, Education and Information (MEICI 2018). Atlantis Press.
   Google Scholar
• Yang L, Gao Z, Li K. 2010. Passenger train scheduling on a single-track or partially double-track railway with stochastic information. Eng Optim. 42(11):1003–1022.
   Web of Science ®Google Scholar
• Yu W, Hoogeveen H, Lenstra JK. 2004. Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. J Sched. 7(5):333–348.
   Web of Science ®Google Scholar
• Yue Y, Wang S, Zhou L, Tong L, Saat MR. 2016. Optimizing train stopping patterns and schedules for high-speed passenger rail corridors. Transp Res Part C Emerg Technol. 63:126–146.
   Web of Science ®Google Scholar
• Zhong J-H, Shen M, Zhang J, Chung HS-H, Shi Y-H, Li Y. 2013. A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem. IEEE Trans Evol Computat. 17(4):512–527.
   Web of Science ®Google Scholar
• Zhou X, Zhong M. 2005. Bicriteria train scheduling for high-speed passenger railroad planning applications. Eur J Oper Res. 167(3):752–771.
   Web of Science ®Google Scholar
• Zhou X, Zhong M. 2007. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds. Transp Res Part B Methodol. 41(3):320–341.
   Web of Science ®Google Scholar