Short-Term Rolling Stock Scheduling and Platform Assignment: A Branch-and-Check Method

References

• Abbink E, van den Berg B, Kroon L, Salomon M (2004) Allocation of railway rolling stock for passenger trains. Transportation Sci. 38(1):33–41.Link, Google Scholar
• Alfieri A, Groot R, Kroon L, Schrijver A (2006) Efficient circulation of railway rolling stock. Transportation Sci. 40(3):378–391.Link, Google Scholar
• Beck JC (2010) Checking-up on branch-and-check. Cohen D, ed. Principles Practice Constraint Programming – CP 2010, Lecture Notes in Computer Science, vol. 6308 (Springer, Berlin, Heidelberg), 84–98.Google Scholar
• Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4:238–252.Crossref, Google Scholar
• Billionnet A (2003) Using integer programming to solve the train-platforming problem. Transportation Sci. 37(2):213–222.Link, Google Scholar
• Bondy JA, Murty USR (2008) Graph Theory (Springer-Verlag, London).Crossref, Google Scholar
• Borndörfer R, Reuther M, Schlechte T, Waas K, Weider S (2016) Integrated optimization of rolling stock rotations for intercity railways. Transportation Sci. 50(3):863–877.Link, Google Scholar
• Borndörfer R, Eβer T, Frankenberger P, Huck A, Jobmann C, Krostitz B, Kuchenbecker K, et al. (2021) Deutsche Bahn schedules train rotations using hypergraph optimization. INFORMS J. Appl. Anal. 51(1):42–62.Link, Google Scholar
• Cacchiani V, Caprara A, Toth P (2010) Solving a real-world train-unit assignment problem. Math. Programming 124:207–231.Crossref, Google Scholar
• Cacchiani V, Caprara A, Toth P (2019) An effective peak period heuristic for railway rolling stock planning. Transportation Sci. 53(3):746–762.Abstract, 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
• Caprara A, Galli L, Toth P (2011) Solution of the train platforming problem. Transportation Sci. 45(2):246–257.Link, Google Scholar
• Caprara A, Kroon L, Monaci M, Peeters M, Toth P (2007) Passenger railway optimization. Barnhart C, Laporte G, eds. Handbooks in Operations Research and Management Science, vol. 14 (North-Holland, Amsterdam), 129–187.Google Scholar
• Cardillo DDL, Mione N (1998) k L-list λ colouring of graphs. Eur. J. Oper. Res. 106(1):160–164.Crossref, Google Scholar
• Carey M, Carville S (2003) Scheduling and platforming trains at busy complex stations. Transportation Res. Part A: Policy Practice 37(3):195–224.Crossref, Google Scholar
• Chudnovsky M, Robertson N, Seymour P, Thomas R (2006) The strong perfect graph theorem. Ann. Math. 64(1):51–229.Crossref, Google Scholar
• Diefenbach H, Emde S, Glock CH (2023) Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models. Eur. J. Oper. Res. 306(2):828–848.Crossref, Google Scholar
• Emadikhiav M, Bergman D, Day R (2020) Consistent routing and scheduling with simultaneous pickups and deliveries. Production Oper. Management 29(8):1937–1955.Crossref, Google Scholar
• Fioole PJ, Kroon L, Maróti G, Schrijver A (2006) A rolling stock circulation model for combining and splitting of passenger trains. Eur. J. Oper. Res. 174(2):1281–1297.Crossref, Google Scholar
• Fontaine P, Minner S (2023) A branch-and-repair method for three-dimensional bin selection and packing in e-commerce. Oper. Res. 71(1):273–288.Link, Google Scholar
• Fulkerson D, Gross O (1965) Incidence matrices and interval graphs. Pacific J. Math. 15(3):835–855.Crossref, Google Scholar
• Gao Y, Schmidt M, Yang L, Gao Z (2020) A branch-and-price approach for trip sequence planning of high-speed train units. Omega 92:102150.Crossref, Google Scholar
• Gao Y, Xia J, D’Ariano A, Yang L (2022) Weekly rolling stock planning in Chinese high-speed rail networks. Transportation Res. Part B: Methodological 158:295–322.Crossref, Google Scholar
• Giacco GL, D’Ariano A, Pacciarelli D (2014a) Rolling stock rostering optimization under maintenance constraints. J. Intelligent Transportation Systems 18(1):95–105.Crossref, Google Scholar
• Giacco GL, Carillo D, D’Ariano A, Pacciarelli D (2014b) Short-term rolling stock rostering and maintenance scheduling optimization. Ingegneria Ferroviaria 1:39–52.Google Scholar
• Grimm B, Hoogervorst R, Borndörfer R (2025) A comparison of two models for rolling stock scheduling. Transportation Sci. 59(5):1101–1129.Link, Google Scholar
• Grimm B, Borndörfer R, Reuther M, Schlechte T (2019) A cut separation approach for the rolling stock rotation problem with vehicle maintenance. 19th Sympos. Algorithmic Approaches Transportation Model. Optim. Systems (ATMOS 2019), Open Access Series in Informatics (OASIcs), vol. 75 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 1:1–1:12.Google Scholar
• Haahr J, Lusby RM (2017) Integrating rolling stock scheduling with train unit shunting. Eur. J. Oper. Res. 259(2):452–468.Crossref, Google Scholar
• Haahr JT, Wagenaar JC, Veelenturf LP, Kroon LG (2016) A comparison of two exact methods for passenger railway rolling stock (re) scheduling. Transportation Res. Part E: Logist. Transportation Rev. 91:15–32.Crossref, Google Scholar
• Hoogervorst R, Dollevoet T, Maróti G, Huisman D (2020) Reducing passenger delays by rolling stock rescheduling. Transportation Sci. 54(3):762–784.Link, Google Scholar
• Hoogervorst R, Dollevoet T, Maróti G, Huisman D (2021) A variable neighborhood search heuristic for rolling stock rescheduling. EURO J. Transportation Logist. 10:100032.Crossref, Google Scholar
• Hooker J (1994) Logic-based methods for optimization. Borning A, ed. Principles Practice Constraint Programming. PPCP 1994, Lecture Notes in Computer Science, vol. 874 (Springer, Berlin, Heidelberg), 336–349.Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Kroon L, Maróti G, Nielsen L (2015) Rescheduling of railway rolling stock with dynamic passenger flows. Transportation Sci. 49(2):165–184.Link, Google Scholar
• Kumar R, Sen G, Kar S, Tiwari MK (2018) Station dispatching problem for a large terminal: A constraint programming approach. Interfaces 48(6):510–528.Link, Google Scholar
• Lamorgese L, Mannino C (2015) An exact decomposition approach for the real-time train dispatching problem. Oper. Res. 63(1):48–64.Link, Google Scholar
• Lamorgese L, Mannino C (2019) A noncompact formulation for job-shop scheduling problems in traffic management. Oper. Res. 67(6):1586–1609.Link, 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
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Liao Z, Li H, Miao J, Corman F (2021) Railway capacity estimation considering vehicle circulation: Integrated timetable and vehicles scheduling on hybrid time-space networks. Transportation Res. Part C: Emerging Tech. 124:102961.Crossref, Google Scholar
• Lin Z, Kwan RSK (2013) A two-phase approach for real-world train unit scheduling. Public Transport 6(1–2):35–65.Crossref, Google Scholar
• Lin Z, Kwan RS (2016) A branch-and-price approach for solving the train unit scheduling problem. Transportation Res. Part B: Methodological 94:97–120.Crossref, Google Scholar
• Lusby RM, Haahr JT, Larsen J, Pisinger D (2017) A branch-and-price algorithm for railway rolling stock rescheduling. Transportation Res. Part B: Methodological 99:228–250.Crossref, Google Scholar
• Lusby RM, Larsen J, Ehrgott M, Ryan D (2011a) Railway track allocation: Models and methods. OR Spectrum 33:843–883.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
• Lusby R, Larsen J, Ryan D, Ehrgott M (2011b) Routing trains through railway junctions: A new set-packing approach. Transportation Sci. 45(2):228–245.Link, Google Scholar
• Maróti G, Kroon L (2005) Maintenance routing for train units: The transition model. Transportation Sci. 39(4):518–525.Link, Google Scholar
• Nielsen LK, Kroon L, Maróti G (2012) A rolling horizon approach for disruption management of railway rolling stock. Eur. J. Oper. Res. 220(2):496–509.Crossref, Google Scholar
• Nishi T, Ohno A, Inuiguchi M, Takahashi S, Ueda K (2017) A combined column generation and heuristics for railway short-term rolling stock planning with regular inspection constraints. Comput. Oper. Res. 81:14–25.Crossref, Google Scholar
• Padberg MW (1974) Perfect zero–one matrices. Math. Programming 6(1):180–196.Crossref, Google Scholar
• Pan H, Yang L, Liang Z (2023) Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach. Eur. J. Oper. Res. 305(1):184–206.Crossref, Google Scholar
• Päprer P, Joshi K, Scheffler M, Neufeld JS, Ehmke J, Buscher U, Scherr N (2025) The rolling stock circulation planning problem: A tutorial with case study. Public Transp., ePub ahead of print October 6, https://doi.org/10.1007/s12469-025-00408-8.Google Scholar
• Peeters M, Kroon L (2008) Circulation of railway rolling stock: A branch-and-price approach. Comput. Oper. Res. 35(2):538–556.Crossref, Google Scholar
• Piu F, Speranza MG (2014) The locomotive assignment problem: A survey on optimization models. Internat. Trans. Oper. Res. 21(3):327–352.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport. Urban Passenger Vehicle and Crew Scheduling (North Holland Publishing Company, London), 269–280.Google Scholar
• Scheffler M, Neufeld JS, Hölscher M (2020) An MIP-based heuristic solution approach for the locomotive assignment problem focussing on (dis-)connecting processes. Transportation Res. Part B: Methodological 139:64–80.Crossref, Google Scholar
• Schlechte T, Blome C, Gerber S, Hauser S, Kasten J, Müller G, Schulz C, Thüring M, Weider S (2023) The bouquet of features in rolling stock rotation planning. Preprint, submitted March 6, https://easychair.org/publications/preprint/Nms6.Google Scholar
• Schrijver A (1993) Minimum circulation of railway stock. CWI Quart. 6(3):205–217.Google Scholar
• Sels P, Cattrysse D, Vansteenwegen P (2016) Automated platforming & routing of trains in all Belgian railway stations. Expert Syst. Appl. 62:302–316.Crossref, Google Scholar
• Sels P, Vansteenwegen P, Dewilde T, Cattrysse D, Waquet B, Joubert A (2014) The train platforming problem: The infrastructure management company perspective. Transportation Res. Part B: Methodological 61:55–72.Crossref, Google Scholar
• Thorlacius P, Larsen J, Laumanns M (2015) An integrated rolling stock planning model for the Copenhagen suburban passenger railway. J. Rail Transport Planning Management 5(4):240–262.Crossref, Google Scholar
• Thorsteinsson ES (2001) Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming. Walsh T, ed. Principles Practice Constraint Programming — CP 2001, Lecture Notes in Computer Science, vol. 2239 (Springer, Berlin, Heidelberg), 16–30.Google Scholar
• Wagenaar JC, Kroon LG, Schmidt M (2017) Maintenance appointments in railway rolling stock rescheduling. Transportation Sci. 51(4):1138–1160.Link, Google Scholar
• Wang Y, Tang T, Ning B, Meng L (2017) Integrated optimization of regular train schedule and train circulation plan for urban rail transit lines. Transportation Res. Part E: Logist. Transportation Rev. 105:83–104.Crossref, Google Scholar
• Yang L, Gao Y, D’Ariano A, Xu S (2024) Integrated optimization of train timetable and train unit circulation for a Y-type urban rail transit system with flexible train composition mode. Omega 122:102968.Crossref, Google Scholar
• Zhang B, Zhang Y, D’Ariano A, Bosi T, Lu G, Peng Q (2023) Optimal platforming, routing, and scheduling of trains and locomotives in a rail passenger station yard. Transportation Res. Part C: Emerging Tech. 152:104160.Crossref, Google Scholar
• Zhong Q, Lusby RM, Larsen J, Zhang Y, Peng Q (2019) Rolling stock scheduling with maintenance requirements at the Chinese high-speed railway. Transportation Res. Part B: Methodological 126:24–44.Crossref, Google Scholar
• Zhou H, Qi J, Yang L, Shi J, Pan H, Gao Y (2022) Joint optimization of train timetabling and rolling stock circulation planning: A novel flexible train composition mode. Transportation Res. Part B: Methodological 162:352–385.Crossref, Google Scholar