pith. sign in

arxiv: 2312.09697 · v1 · submitted 2023-12-15 · 🧮 math.OC

A Comparison of Models for Rolling Stock Scheduling

Boris Grimm , Rowan Hoogervorst , Ralf Bornd\"orfer This is my paper

Pith reviewed 2026-05-24 05:27 UTC · model grok-4.3

classification 🧮 math.OC
keywords rolling stock schedulingcomposition modelhypergraph modellinear programming boundsrailway optimizationNetherlands RailwaysNP-hard problem
0
0 comments X

The pith

In NS-like rolling stock scheduling, the Composition and sufficiently expressive Hypergraph models have equally strong LP bounds, yet the Composition model is more compact and faster.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper compares two optimization models for assigning train units to timetable trips in a setting modeled after Netherlands Railways. It establishes that the linear programming relaxations of the Composition model and expressive variants of the Hypergraph model provide the same bound strength. Numerical experiments on actual NS instances demonstrate that the Composition model tends to be smaller and reaches optimal solutions more quickly.

Core claim

In a rolling stock scheduling setting similar to that of NS, which is strongly NP-hard, the linear programming bounds of the Composition model and sufficiently expressive Hypergraph model variants are equally strong. On NS instances, the Composition model is generally more compact and finds optimal solutions in the shortest running time.

What carries the argument

The Composition model and tuned Hypergraph model variants for representing possible train unit compositions and their transitions between trips.

If this is right

  • The LP bounds match when the Hypergraph model is made sufficiently expressive for the NS setting.
  • The Composition model is more compact in practice for these instances.
  • The Composition model solves to optimality faster than the Hypergraph variants on NS data.
  • The problem remains strongly NP-hard even in this setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The choice between models may depend more on implementation size and solver performance than on theoretical bound quality.
  • Hypergraph models might need further customization for different operators to achieve comparable performance.
  • Exact methods based on these models could be combined with heuristics for larger instances.

Load-bearing premise

That both models can represent the NS-like setting without omitting essential constraints and that the proposed Hypergraph variants achieve the required expressiveness.

What would settle it

An instance from the NS data where an expressive Hypergraph model has a strictly weaker LP bound than the Composition model, or where the Composition model does not solve faster.

Figures

Figures reproduced from arXiv: 2312.09697 by Boris Grimm, Ralf Bornd\"orfer, Rowan Hoogervorst.

Figure 1
Figure 1. Figure 1: Example of a rolling stock circulation. is given by, among others, Huisman et al. (2005) and Caprara et al. (2007). In both of these papers, rolling stock scheduling is assumed to be performed after a timetable has been found and before the crew, i.e., drivers and guards, are scheduled. In this paper, we thus focus solely on the rolling stock scheduling step. Over the years, multiple models have been propo… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of hypergraph variants: h = small hypergraph, H = full hypergraph, D = [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Coupling situations in full and small Hypergraph models. [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the Composition model (hyper)graph. [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Omitting the flow constraints on composition changes weakens the Hypergraph models. [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Reducing 3SAT to NS-RSSP. The red and blue colors only highlight true and false [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Overview of the Dutch railway network Instance |T| |R| |P| FLIRT(-AN) 584 (+1) 2 14 SGM(-AN) 758 2 14 SLT 1681 2 14 DDZ(-AN) 419 2 6 VIRM(-AN) 1300 2 10 ICM 1222 2 30 (a) Statistics of the considered instances. Parameter Value Mileage 0.1 Seat shortage 0.2 Shunting 10 Ending deviation 10000 (b) Parameters of the objective function [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Visualization of the timetables underlying the NS instances. Each plot shows the trips [PITH_FULL_IMAGE:figures/full_fig_p021_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Model sizes for all models and instances. [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Comparing optimal solution values for all models and instances. [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Analyzing the cost components of νMph¨q and νMpH¨q. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Comparing computation times for all models and instances. [PITH_FULL_IMAGE:figures/full_fig_p027_12.png] view at source ↗
read the original abstract

A major step in the planning process of passenger railway operators is the assignment of rolling stock, i.e., train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the Composition model and the Hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in a rolling stock scheduling setting similar to that of NS, which we show to be strongly NP-hard, and propose different variants of the Hypergraph model to tune the model to the NS setting. We prove that, in this setting, the linear programming bounds of both models are equally strong as long as a Hypergraph model variant is chosen that is sufficiently expressive. However, through a numerical evaluation on NS instances, we show that the Composition model is generally more compact in practice and can find optimal solutions in the shortest running time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper compares the Composition model (developed for NS) and the Hypergraph model (for DB) for rolling stock scheduling in an NS-like setting. It establishes that this setting yields a strongly NP-hard problem, proposes variants of the Hypergraph model to match NS requirements, proves that the LP relaxation bounds of the two models are equally strong when a sufficiently expressive Hypergraph variant is used, and reports numerical experiments on NS instances showing that the Composition model is more compact and reaches optimal solutions faster.

Significance. If the bound-equivalence proof and experimental comparison hold, the work supplies a theoretical justification for selecting between these models on the basis of compactness and runtime rather than relaxation strength. The explicit NP-hardness result and the provision of model variants tuned to a concrete operational setting are useful for both theory and practice. The paper earns credit for stating and proving the LP-bound equivalence result and for including a reproducible numerical comparison on real-world NS instances.

minor comments (3)
  1. Abstract and §1: the statement that the LP bounds are 'equally strong' would be clearer if it referenced the precise theorem number establishing the equivalence under the chosen Hypergraph variant.
  2. §4 (numerical evaluation): the description of instance generation and solver settings could be expanded with a short table listing the number of trips, units, and time limits used for each NS instance to improve reproducibility.
  3. Notation section: the distinction between the different Hypergraph variants (e.g., which arcs or hyperedges are added) would benefit from an explicit tabular comparison of their variable and constraint counts.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of the bound-equivalence result and the reproducible experiments on NS instances, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's derivation consists of (i) a proof that LP bounds are equivalent when a Hypergraph variant is sufficiently expressive for the NS-like setting and (ii) a numerical comparison on NS instances showing the Composition model is more compact. Neither step reduces to a self-definition, a fitted parameter renamed as a prediction, or a load-bearing self-citation chain whose content is unverified outside the present work. The proof and evaluation are presented as independent of any author-specific fitted quantities or ansatzes imported via citation, rendering the central claims self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract; the work relies on standard integer programming modeling assumptions common to the field.

pith-pipeline@v0.9.0 · 5726 in / 1098 out tokens · 35011 ms · 2026-05-24T05:27:59.763992+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Transportation Science 40(3):378--391, ://dx.doi.org/10.1287/trsc.1060.0155

    Alfieri A, Groot R, Kroon L, Schrijver A, 2006 Efficient circulation of railway rolling stock. Transportation Science 40(3):378--391, ://dx.doi.org/10.1287/trsc.1060.0155

    work page doi:10.1287/trsc.1060.0155 2006

  2. [2]

    INFORMS Journal on Applied Analytics 51(1):42--62, ://dx.doi.org/10.1287/inte.2020.1069

    Bornd \"o rfer R, Eßer T, Frankenberger P, Huck A, Jobmann C, Krostitz B, Kuchenbecker K, Mohrhagen K, Nagl P, Peterson M, Reuther M, Schang T, Schoch M, Schülldorf H, Schütz P, Therolf T, Waas K, Weider S, 2021 Deutsche bahn schedules train rotations using hypergraph optimization. INFORMS Journal on Applied Analytics 51(1):42--62, ://dx.doi.org/10.1287/i...

    work page doi:10.1287/inte.2020.1069 2021

  3. [3]

    Public Transport 1--19, ://dx.doi.org/10.1007/s12469-017-0152-4

    Bornd \"o rfer R, Grimm B, Reuther M, Schlechte T, 2017 Template-based re-optimization of rolling stock rotations. Public Transport 1--19, ://dx.doi.org/10.1007/s12469-017-0152-4

    work page doi:10.1007/s12469-017-0152-4 2017

  4. [4]

    Transportation Science 50(3):863--877, ://dx.doi.org/10.1287/trsc.2015.0633

    Bornd \"o rfer R, Reuther M, Schlechte T, Waas K, Weider S, 2016 Integrated optimization of rolling stock rotations for intercity railways. Transportation Science 50(3):863--877, ://dx.doi.org/10.1287/trsc.2015.0633

    work page doi:10.1287/trsc.2015.0633 2016

  5. [5]

    Solutions of Schr\"odinger Equation with Generalized Inverted Hyperbolic Potential

    Cacchiani V, Caprara A, Galli L, Kroon L, Maróti G, Toth P, 2012 Railway rolling stock planning: Robustness against large disruptions. Transportation Science 46(2):217--232, ://dx.doi.org/10.1287/trsc.1110.0388

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1287/trsc.1110.0388 2012

  6. [6]

    Mathematical Programming 124(1):207--231, ://dx.doi.org/10.1007/s10107-010-0361-y

    Cacchiani V, Caprara A, Toth P, 2010 Solving a real-world train-unit assignment problem. Mathematical Programming 124(1):207--231, ://dx.doi.org/10.1007/s10107-010-0361-y

    work page doi:10.1007/s10107-010-0361-y 2010

  7. [7]

    Discrete Applied Mathematics 161(12):1707--1718, ://dx.doi.org/10.1016/j.dam.2011.10.035, 9th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)

    Cacchiani V, Caprara A, Toth P, 2013 A Lagrangian heuristic for a train-unit assignment problem . Discrete Applied Mathematics 161(12):1707--1718, ://dx.doi.org/10.1016/j.dam.2011.10.035, 9th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)

    work page doi:10.1016/j.dam.2011.10.035 2013

  8. [8]

    Transportation Science 53(3):746--762, ://dx.doi.org/10.1287/trsc.2018.0858

    Cacchiani V, Caprara A, Toth P, 2019 An effective peak period heuristic for railway rolling stock planning. Transportation Science 53(3):746--762, ://dx.doi.org/10.1287/trsc.2018.0858

    work page doi:10.1287/trsc.2018.0858 2019

  9. [9]

    Computers & Operations Research 38(8):1131--1142, ://dx.doi.org/10.1016/j.cor.2010.10.029

    Cadarso L, Mar \' n \'A , 2011 Robust rolling stock in rapid transit networks. Computers & Operations Research 38(8):1131--1142, ://dx.doi.org/10.1016/j.cor.2010.10.029

    work page doi:10.1016/j.cor.2010.10.029 2011

  10. [10]

    Computers & Operations Research 51:146--159, ://dx.doi.org/10.1016/j.cor.2014.05.007

    Cadarso L, Mar \' n \'A , 2014 Improving robustness of rolling stock circulations in rapid transit networks. Computers & Operations Research 51:146--159, ://dx.doi.org/10.1016/j.cor.2014.05.007

    work page doi:10.1016/j.cor.2014.05.007 2014

  11. [11]

    Barnhart C, Laporte G, eds., Transportation, volume 14 of Handbooks in Operations Research and Management Science, 129--187 (Elsevier), ://dx.doi.org/10.1016/S0927-0507(06)14003-7

    Caprara A, Kroon L, Monaci M, Peeters M, Toth P, 2007 Passenger railway optimization. Barnhart C, Laporte G, eds., Transportation, volume 14 of Handbooks in Operations Research and Management Science, 129--187 (Elsevier), ://dx.doi.org/10.1016/S0927-0507(06)14003-7

    work page doi:10.1016/s0927-0507(06)14003-7 2007

  12. [12]

    European Journal of Operational Research 174(2):1281--1297, ://dx.doi.org/10.1016/j.ejor.2005.03.032

    Fioole PJ, Kroon L, Maróti G, Schrijver A, 2006 A rolling stock circulation model for combining and splitting of passenger trains. European Journal of Operational Research 174(2):1281--1297, ://dx.doi.org/10.1016/j.ejor.2005.03.032

    work page doi:10.1016/j.ejor.2005.03.032 2006

  13. [13]

    Omega 92:102150, ://dx.doi.org/https://doi.org/10.1016/j.omega.2019.102150

    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, ://dx.doi.org/https://doi.org/10.1016/j.omega.2019.102150

    work page doi:10.1016/j.omega.2019.102150 2020

  14. [14]

    Transportation Research Part B: Methodological 158:295--322, ://dx.doi.org/https://doi.org/10.1016/j.trb.2022.02.005

    Gao Y, Xia J, D’Ariano A, Yang L, 2022 Weekly rolling stock planning in chinese high-speed rail networks. Transportation Research Part B: Methodological 158:295--322, ://dx.doi.org/https://doi.org/10.1016/j.trb.2022.02.005

    work page doi:10.1016/j.trb.2022.02.005 2022

  15. [15]

    Journal of Intelligent Transportation Systems 18(1):95--105, ://dx.doi.org/10.1080/15472450.2013.801712

    Giacco GL, D’Ariano A, Pacciarelli D, 2014 Rolling stock rostering optimization under maintenance constraints. Journal of Intelligent Transportation Systems 18(1):95--105, ://dx.doi.org/10.1080/15472450.2013.801712

    work page doi:10.1080/15472450.2013.801712 2014

  16. [16]

    Grimm B, Bornd \"o rfer R, Bushe J, 2023 Assignment based resource constrained path generation for railway rolling stock optimization. 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), volume 115, 13:1 -- 13:15, ://dx.doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2023.13, epub ahead of print

    work page doi:10.4230/oasics.atmos.2023.13 2023

  17. [17]

    7th International Conference on railway operations modelling and Analysis (RailLille 2017), 688--698, ://nbn-resolving.org/urn:nbn:de:0297-zib-63930

    Grimm B, Bornd \"o rfer R, Reuther M, Schade S, Schlechte T, 2017 A propagation approach to acyclic rolling stock rotation optimization. 7th International Conference on railway operations modelling and Analysis (RailLille 2017), 688--698, ://nbn-resolving.org/urn:nbn:de:0297-zib-63930

    work page 2017

  18. [18]

    Grimm B, Bornd \"o rfer R, Reuther M, Schlechte T, 2019 A cut separation approach for the rolling stock rotation problem with vehicle maintenance. Cacchiani V, Marchetti-Spaccamela A, eds., 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), volume 75, 1:1 -- 1:12, ://dx.doi.org/10.4230/OASIcs.ATM...

    work page doi:10.4230/oasics.atmos.2019.1 2019

  19. [19]

    Transportation Research Part E: Logistics and Transportation Review 91:15--32, ://dx.doi.org/10.1016/j.tre.2016.03.019

    Haahr JT, Wagenaar JC, Veelenturf LP, Kroon LG, 2016 A comparison of two exact methods for passenger railway rolling stock (re)scheduling. Transportation Research Part E: Logistics and Transportation Review 91:15--32, ://dx.doi.org/10.1016/j.tre.2016.03.019

    work page doi:10.1016/j.tre.2016.03.019 2016

  20. [20]

    EURO Journal on Transportation and Logistics 100032, ://dx.doi.org/10.1016/j.ejtl.2021.100032

    Hoogervorst R, Dollevoet T, Maróti G, Huisman D, 2021 A variable neighborhood search heuristic for rolling stock rescheduling. EURO Journal on Transportation and Logistics 100032, ://dx.doi.org/10.1016/j.ejtl.2021.100032

    work page doi:10.1016/j.ejtl.2021.100032 2021

  21. [21]

    Statistica Neerlandica 59(4):467--497, ://dx.doi.org/10.1111/j.1467-9574.2005.00303.x

    Huisman D, Kroon LG, Lentink RM, Vromans MJCM, 2005 Operations research in passenger railway transportation. Statistica Neerlandica 59(4):467--497, ://dx.doi.org/10.1111/j.1467-9574.2005.00303.x

    work page doi:10.1111/j.1467-9574.2005.00303.x 2005

  22. [22]

    INFORMS Journal on Applied Analytics 39(1):6--17, ://dx.doi.org/10.1287/inte.1080.0409

    Kroon L, Huisman D, Abbink E, Fioole PJ, Fischetti M, Maróti G, Schrijver A, Steenbeek A, Ybema R, 2009 The new Dutch timetable: The OR revolution . INFORMS Journal on Applied Analytics 39(1):6--17, ://dx.doi.org/10.1287/inte.1080.0409

    work page doi:10.1287/inte.1080.0409 2009

  23. [23]

    Transportation Science 49(2):165--184, ://dx.doi.org/10.1287/trsc.2013.0502

    Kroon L, Maróti G, Nielsen L, 2015 Rescheduling of railway rolling stock with dynamic passenger flows. Transportation Science 49(2):165--184, ://dx.doi.org/10.1287/trsc.2013.0502

    work page doi:10.1287/trsc.2013.0502 2015

  24. [24]

    Transportation Research Part B: Methodological 94:97--120, ://dx.doi.org/10.1016/j.trb.2016.09.007

    Lin Z, Kwan RS, 2016 A branch-and-price approach for solving the train unit scheduling problem. Transportation Research Part B: Methodological 94:97--120, ://dx.doi.org/10.1016/j.trb.2016.09.007

    work page doi:10.1016/j.trb.2016.09.007 2016

  25. [25]

    Public Transport 6(1):35--65, ://dx.doi.org/10.1007/s12469-013-0073-9

    Lin Z, Kwan RSK, 2014 A two-phase approach for real-world train unit scheduling. Public Transport 6(1):35--65, ://dx.doi.org/10.1007/s12469-013-0073-9

    work page doi:10.1007/s12469-013-0073-9 2014

  26. [26]

    Transportation Research Part B: Methodological 99:228--250, ://dx.doi.org/10.1016/j.trb.2017.03.003

    Lusby RM, Haahr JT, Larsen J, Pisinger D, 2017 A branch-and-price algorithm for railway rolling stock rescheduling. Transportation Research Part B: Methodological 99:228--250, ://dx.doi.org/10.1016/j.trb.2017.03.003

    work page doi:10.1016/j.trb.2017.03.003 2017

  27. [27]

    Transportation Science 39(4):518--525, ://dx.doi.org/10.1287/trsc.1050.0116

    Maróti G, Kroon L, 2005 Maintenance routing for train units: The transition model. Transportation Science 39(4):518--525, ://dx.doi.org/10.1287/trsc.1050.0116

    work page doi:10.1287/trsc.1050.0116 2005

  28. [28]

    European Journal of Operational Research 220(2):496--509, ://dx.doi.org/10.1016/j.ejor.2012.01.037

    Nielsen LK, Kroon L, Maróti G, 2012 A rolling horizon approach for disruption management of railway rolling stock. European Journal of Operational Research 220(2):496--509, ://dx.doi.org/10.1016/j.ejor.2012.01.037

    work page doi:10.1016/j.ejor.2012.01.037 2012

  29. [29]

    Computers & Operations Research 35(2):538--556, ://dx.doi.org/10.1016/j.cor.2006.03.019

    Peeters M, Kroon L, 2008 Circulation of railway rolling stock: a branch-and-price approach. Computers & Operations Research 35(2):538--556, ://dx.doi.org/10.1016/j.cor.2006.03.019

    work page doi:10.1016/j.cor.2006.03.019 2008

  30. [30]

    Reuther M, 2017 Mathematical Optimization of Rolling Stock Rotations. Ph.D. thesis, Technical University Berlin, ://depositonce.tu-berlin.de/handle/11303/6309

    work page 2017

  31. [31]

    u ller G, Schulz C, Th \

    Schlechte T, Blome C, Gerber S, Hauser S, Kasten J, M \"u ller G, Schulz C, Th \"u ring M, Weider S, 2023 The bouquet of features in rolling stock rotation planning. Technical report, EasyChair

    work page 2023

  32. [32]

    Journal of Rail Transport Planning & Management 5(4):240--262, ://dx.doi.org/10.1016/j.jrtpm.2015.11.001

    Thorlacius P, Larsen J, Laumanns M, 2015 An integrated rolling stock planning model for the Copenhagen suburban passenger railway . Journal of Rail Transport Planning & Management 5(4):240--262, ://dx.doi.org/10.1016/j.jrtpm.2015.11.001

    work page doi:10.1016/j.jrtpm.2015.11.001 2015

  33. [33]

    Transportation Research Part B: Methodological 101:140--161, ://dx.doi.org/10.1016/j.trb.2017.03.013

    Wagenaar J, Kroon L, Fragkos I, 2017 Rolling stock rescheduling in passenger railway transportation using dead-heading trips and adjusted passenger demand. Transportation Research Part B: Methodological 101:140--161, ://dx.doi.org/10.1016/j.trb.2017.03.013

    work page doi:10.1016/j.trb.2017.03.013 2017

  34. [34]

    Transportation Science 51(4):1138--1160, ://dx.doi.org/10.1287/trsc.2016.0701

    Wagenaar JC, Kroon LG, Schmidt M, 2017 Maintenance appointments in railway rolling stock rescheduling. Transportation Science 51(4):1138--1160, ://dx.doi.org/10.1287/trsc.2016.0701

    work page doi:10.1287/trsc.2016.0701 2017

  35. [35]

    Transportation Research Part B: Methodological 126:24--44, ://dx.doi.org/10.1016/j.trb.2019.05.013

    Zhong Q, Lusby RM, Larsen J, Zhang Y, Peng Q, 2019 Rolling stock scheduling with maintenance requirements at the Chinese high-speed railway . Transportation Research Part B: Methodological 126:24--44, ://dx.doi.org/10.1016/j.trb.2019.05.013

    work page doi:10.1016/j.trb.2019.05.013 2019