Solving the Real-Time Train Dispatching Problem by Column Generation

References

• Bettinelli A , Santini A , Vigo D (2017) A real-time conflict solution algorithm for the train rescheduling problem. Transportation Res. Part B Methodological 106:237–265.Crossref, Google Scholar
• Bollapragada S , Markley R , Morgan H , Telatar E , Wills S , Samuels M , Bieringer J , et al. (2018) A novel movement planner system for dispatching trains. Interfaces 48(1):57–69.Link, Google Scholar
• Bonami P , Lodi A , Tramontani A , Wiese S (2015) On mathematical programming with indicator constraints. Math. Programming 151(1):191–223.Crossref, Google Scholar
• Borndörfer R , Schlechte T (2007) Models for railway track allocation. Seventh Workshop Algorithmic Approaches Transportation Model. Optim. Systems, vol. 7 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 62–78.Google Scholar
• Borndörfer R , Schlechte T , Weider S (2010) Railway track allocation by rapid branching. Tenth Workshop Algorithmic Approaches Transportation Model. Optim. Systems , vol. 14 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik), 13–23.Google Scholar
• Brännlund U , Lindberg PO , Nõu A , Nilsson JE (1998) Railway timetabling using Lagrangian relaxation. Transportation Sci. 32(4):358–369.Link, Google Scholar
• Bron C , Kerbosch J (1973) Algorithm 457: Finding all cliques of an undirected graph. Comm. ACM 16(9):575–577.Crossref, Google Scholar
• Cacchiani V , Caprara A , Fischetti M (2012) A Lagrangian heuristic for robustness, with an application to train timetabling. Transportation Sci. 46(1):124–133.Link, Google Scholar
• Cacchiani V , Caprara A , Toth P (2008) A column generation approach to train timetabling on a corridor. 4OR 6(2):125–142.Crossref, Google Scholar
• Cacchiani V , Huisman D , Kidd M , Kroon L , Toth P , Veelenturf L , Wagenaar J (2014) An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Res. Part B Methodological 63:15–37.Crossref, Google Scholar
• Caimi G , Fuchsberger M , Laumanns M , Lüthi M (2012) A model predictive control approach for discrete-time rescheduling in complex central railway station areas. Comput. Oper. Res. 39(11):2578–2593.Crossref, Google Scholar
• Caimi G , Chudak F , Fuchsberger M , Laumanns M , Zenklusen R (2011) A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling. Transportation Sci. 45(2):212–227.Link, Google Scholar
• Caprara A , Fischetti M , Toth P (2002) Modeling and solving the train timetabling problem. Oper. Res. 50(5):851–861.Link, 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.Crossref, Google Scholar
• Corman F , D’Ariano A , Pacciarelli D , Pranzo M (2010) A tabu search algorithm for rerouting trains during rail operations. Transportation Res. Part B Methodological 44(1):175–192.Crossref, Google Scholar
• Dahms FHW , Frank A-L , Kühn S , Pöhle D (2019) Transforming automatic scheduling in a working application for a railway infrastructure manager. Linköping Electronic Conf. Proc. 69(19):280–289.Google Scholar
• Dal Sasso V , Lamorgese L , Mannino C , Tancredi A , Ventura P (2022) Easy cases of deadlock detection in train scheduling. Oper. Res. 70(4):2101–2118.Link, 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.Crossref, Google Scholar
• D’Ariano A , Corman F , Pacciarelli D , Pranzo M (2008) Reordering and local rerouting strategies to manage train traffic in real time. Transportation Sci. 42(4):405–419.Link, Google Scholar
• DB (2023) Stammdatenaktualisierung des trassenportals (TPN). Accessed January 19, 2024, https://www.dbinfrago.com/web/aktuelles/kund-inneninformationen/kund-inneninformationen/2023-KW24-Stammdatenaktualisierung-Trassenportal-12390678.Google Scholar
• Desrosiers J , Lübbecke ME (2005) A primer in column generation. Desaulniers G , Desrosiers J , Solomon MM , eds. Column Generation (Springer, New York), 1–32.Crossref, Google Scholar
• Dyer ME , Wolsey LA (1990) Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. 26(2–3):255–270.Crossref, Google Scholar
• Fang W , Yang S , Yao X (2015) A survey on problem models and solution approaches to rescheduling in railway networks. IEEE Trans. Intelligent Transportation Systems 16(6):2997–3016.Crossref, Google Scholar
• Lamorgese L , Mannino C (2015) An exact decomposition approach for the real-time train dispatching problem. Oper. Res. 63(1):48–64.Google Scholar
• Lamorgese L , Mannino C , Piacentini M (2016) Optimal train dispatching by Benders’-like reformulation. Transportation Sci. 50(3):910–925.Link, Google Scholar
• Leutwiler F , Corman F (2023) A review of principles and methods to decompose large-scale railway scheduling problems. EURO J. Transportation Logist. 12:100107.Crossref, Google Scholar
• Lodi A (2010) Mixed integer programming computation. Jünger M , Liebling TM , Naddef D , Nemhauser GL , Pulleyblank WR , Reinelt G , Rinaldi G , Wolsey LA , eds. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art , 619–645.Crossref, Google Scholar
• Lübbecke ME (2011) Column generation. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Lusby RM , Larsen J , Ehrgott M , Ryan DM (2013) A set packing inspired method for real-time junction train routing. Comput. Oper. Res. 40(3):713–724.Crossref, Google Scholar
• Mannino C , Mascis A (2009) Optimal real-time traffic control in metro stations. Oper. Res. 57(4):1026–1039.Link, Google Scholar
• Mascis A , Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 143(3):498–517.Crossref, Google Scholar
• Meng L , Zhou X (2014) Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables. Transportation Res. Part B Methodological 67:208–234.Crossref, Google Scholar
• Nachtigall K , Opitz J (2016) Modelling and solving a train path assignment model. Lübbecke M , Koster A , Letmathe P , Madlener R , Peis B , Walther G , eds. Oper. Res. Proc. 2014 (Springer International Publishing, Cham, Switzerland), 423–428.Crossref, Google Scholar
• Pachl J (2021) Railway Signalling Principles , 2nd ed. (Technische Universität Braunschweig, Braunschweig, Germany).Google Scholar
• Pellegrini P , Marlière G , Rodriguez J (2012) Real time railway traffic management modeling track-circuits. Twelfth Workshop Algorithmic Approaches Transportation Model. Optim. Systems , vol. 25 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik), 23–34.Google Scholar
• Pellegrini P , Marlière G , Rodriguez J (2014) Optimal train routing and scheduling for managing traffic perturbations in complex junctions. Transportation Res. Part B Methodological 59:58–80.Crossref, Google Scholar
• Pellegrini P , Marlière G , Pesenti R , Rodriguez J (2015) RECIFE-MILP: An effective MILP-based heuristic for the real-time railway traffic management problem. IEEE Trans. Intelligent Transportation Systems 16(5):2609–2619.Crossref, Google Scholar
• Reynolds E , Maher SJ (2022) A data-driven, variable-speed model for the train timetable rescheduling problem. Comput. Oper. Res. 142:105719.Crossref, Google Scholar
• Reynolds E , Ehrgott M , Maher SJ , Patman A , Wang JYT (2020) A multicommodity flow model for rerouting and retiming trains in real-time to reduce reactionary delay in complex station areas. Optim. Online , 1–37.Google Scholar
• Samà M , D’Ariano A , Corman F , Pacciarelli D (2017) A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations. Comput. Oper. Res. 78:480–499.Crossref, Google Scholar
• Samà M , Pellegrini P , D’Ariano A , Rodriguez J , Pacciarelli D (2016) Ant colony optimization for the real-time train routing selection problem. Transportation Res. Part B Methodological 85:89–108.Crossref, Google Scholar
• Schwanhäußer W (1974) Die bemessung der pufferzeiten im fahrplangefüge der eisenbahn. Unpublished doctoral dissertation, Fakultät für Bauwesen der Rheinisch-Westfälischen Technischen Hochschule Aachen.Google Scholar
• Sousa JP , Wolsey LA (1992) A time indexed formulation of non-preemptive single machine scheduling problems. Math. Programming 54(1–3):353–367.Crossref, Google Scholar
• Tomita E (2017) Efficient algorithms for finding maximum and maximal cliques and their applications. Poon SH , Rahman MS , Yen HC , eds. WALCOM: Algorithms and Computation , 3–15.Crossref, Google Scholar
• UnionPacific (2021) Optrail’s advanced movement planner successfully in operation on one of the largest and most complex rail networks world-wide. Accessed January 30, 2025, https://www.up.com/media/releases/211118-optrail-successfully-in-operation.htm.Google Scholar
• VIA-Con About LUKS. LUKS Leistungsuntersuchung Knoten und Strecken. Accessed February 20, 2025, https://www.quattron.com/leistungen/software-it-digital-data-management/luks/.Google Scholar
• Zwaneveld PJ , Kroon LG , Romeijn HE , Salomon M , Dauzère-Pérès S , Van Hoesel SP , Ambergen HW (1996) Routing trains through railway stations: Model formulation and algorithms. Transportation Sci. 30(3):181–194.Link, Google Scholar