A rolling horizon-based decomposition algorithm for the railway network train timetabling problem

References

• Cacchiani , V and Toth , P. 2012 . Nominal and robust train timetabling problems . Eur J Oper Res , 219 ( 3 ) : 727 – 737 .
   Web of Science ®Google Scholar
• Harrod , S. 2012 . A tutorial on fundamental model structures for railway timetable optimization . Surv Oper Res Manage Sci , 17 ( 2 ) : 85 – 96 .
   Google Scholar
• Serafini , P and Ukovich , W. 1989 . A mathematical model for periodic event scheduling problems . SIAM J Discrete Math , 2 ( 4 ) : 550 – 581 .
   Google Scholar
• Peeters , L and Kroon , L. Jun 21–23 2000 . A cycle based optimization model for the cyclic railway timetabling problem , Jun 21–23 , 275 – 296 . Berlin : Proceeding of the Eighth International Conference on Computer-Aided Scheduling of Public Transport (CASPT 2000) .
   Google Scholar
• Lindner , T and Zimmermann , UT. 2005 . Cost optimal periodic train scheduling . Math Method Oper Res , 62 ( 2 ) : 281 – 295 .
   Google Scholar
• 1996 . Odijk M. A constraint generation algorithm for the construction of periodic railway timetables . Transport Res B-Meth , 30 ( 6 ) : 455 – 464 .
   Web of Science ®Google Scholar
• Nachtigall , K and Voget , S. 1996 . A genetic algorithm approach to periodic railway synchronization . Comput Oper Res , 23 ( 5 ) : 453 – 463 .
   Web of Science ®Google Scholar
• Nachtigall , K and Opitz , J. Sep 18 2008 . “ Solving periodic timetable optimisation problems by modulo simplex calculations ” . In ATMOS 2008 – 8th Workshop on Algorithmic Approaches for Transportation Modeling , Sep 18 , 1 – 15 . Karlsruhe : Optimization, and Systems (ATMOS'08) .
   Google Scholar
• Goerigk , M and Schobel , A. 2013 . Improving the modulo simplex algorithm for large-scale periodic timetabling . Comput Oper Res , 40 ( 5 ) : 1363 – 1370 .
   Web of Science ®Google Scholar
• Liebchen , C , Proksch , M and Wagner , FH. Aug 9–11 2004 . Performance of algorithms for periodic timetable optimization , Aug 9–11 , 151 – 180 . San Diego : Proceeding of the Ninth International Conference on Computer-Aided Scheduling of Public Transport (CASPT 2004) .
   Google Scholar
• Caimi , G , Fuchsberger , M , Laumanns , M and Schupbach , K. 2011 . Periodic railway timetabling with event flexibility . Networks , 57 ( 1 ) : 3 – 18 .
   Google Scholar
• Caimi , G , Laumanns , M , Schupbach , K , Worner , S and Fuchsberger , M. 2011 . The periodic service intention as a conceptual framework for generating timetables with partial periodicity . Transport Plan Techn , 34 ( 4 ) : 323 – 339 .
   Web of Science ®Google Scholar
• Cai , X and Goh , CJ. 1994 . A fast heuristic for the train scheduling problem . Comput Oper Res , 21 ( 5 ) : 499 – 510 .
   Web of Science ®Google Scholar
• Cai , X , Goh , CJ and Mees , AI. 1998 . Greedy heuristics for rapid scheduling of trains on a single track . IIE Trans , 30 ( 5 ) : 481 – 493 .
   Web of Science ®Google Scholar
• Higgings , A , Kozan , E and Ferreira , L. 1997 . Heuristic techniques for single line train scheduling . J Heuristics , 3 ( 1 ) : 43 – 62 .
   Google Scholar
• Carey , M and Lockwood , D. 1995 . A model, algorithms and strategy for train pathing . J Oper Res Soc , 46 : 988 – 1005 .
   Web of Science ®Google Scholar
• Carey , M. 1994 . A model and strategy for train pathing with choice of lines, platforms and routes . Transport Res B-Meth , 28 ( 5 ) : 333 – 353 .
   Web of Science ®Google Scholar
• Carey , M. 1994 . Extending a train pathing model from one-way to two-way track . Transport Res B-Meth , 28 ( 5 ) : 395 – 400 .
   Google Scholar
• Barber , F , Ingolotti , L , Lova , A , Tormos , P and Salido , MA. 2009 . “ Meta-heuristic and constraint-based approaches for single-line railway timetabling ” . In Robust and online large-scale optimization. Lecture Notes in Computer Science 5868 , Edited by: Ahuja , RK , Möhring , RH and Zaroliagis , CD . 145 – 181 . Berlin : Springer .
   Google Scholar
• Branlund , U , Lindberg , PO , Nou , A and Nilsson , JE. 1998 . Railway timetabling using Lagrangian relaxation . Transport Sci , 32 ( 4 ) : 358 – 369 .
   Google Scholar
• Caprara , A , Fischetti , M and 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 and 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
• Cacchiani , V , Caprara , A and Toth , P. 2008 . A column generation approach to train timetabling on a corridor . 4OR-Q J Oper Res , 6 ( 2 ) : 125 – 142 .
   Web of Science ®Google Scholar
• Borndorfer , R and Schlechte , T. Nov 15–16 2007 . Models for railway track allocation , Nov 15–16 , 62 – 78 . Sevilla : Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) .
   Google Scholar
• Borndorfer , R , Schlechte , T and Weider , S. Sep 9 2010 . Railway track allocation by rapid branching , Sep 9 , 13 – 23 . Liverpool : Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) .
   Google Scholar
• Harrod , S. 2011 . Modeling network transition constraints with hypergraphs . Transport Sci , 45 ( 1 ) : 81 – 97 .
   Web of Science ®Google Scholar
• Szpigel , B. Aug 21–25 1972 . Optimal train scheduling on a single track railway , Aug 21–25 , 343 – 352 . Dublin : Proceedings of the 6th IFORS International Conference on Operational Research .
   Google Scholar
• Zhou , X and 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 and Zhong , M. 2007 . Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds . Transport Res B-Meth , 41 ( 3 ) : 320 – 341 .
   Web of Science ®Google Scholar
• Liu , SQ and 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 and Kozan , E. 2011 . Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model . Transport Sci , 45 ( 2 ) : 175 – 198 .
   Web of Science ®Google Scholar
• Burdett , RL and Kozan , E. 2010 . A disjunctive graph model and framework for constructing new train schedules . Eur J Oper Res , 200 ( 1 ) : 85 – 98 .
   Google Scholar
• Burdett , RL and Kozan , E. 2010 . A sequencing approach for creating new train timetables . OR Spectrum , 32 ( 1 ) : 163 – 193 .
   Web of Science ®Google Scholar