Rolling Stock Roster Planning for Railways
Rolling stock rostering is one of the basic planning problems in rail transport. It deals with the construction of rotations for individual units of rolling stock and, simultaneously, the composition of trains from these units. We focus on (long distance) passenger transport. Here, units of different types are arranged to form trains in particular sequences and orientations, and in a "regular" way.
Our approach to rolling stock rostering is based on a novel directed hypergraph model of the problem, which serves as a universal tool to handle several types of rules.
Poster (PDF)
We distinguish four types of regularity:
- Operational regularity: Train turns should be regular, i.e., if train 4711 ends in Frankfurt and continues as 4712 on Monday, this should also be the case on Tuesday, Wednesday, etc., if possible.
- Sequence regularity: Train compositions should be regular, i.e., train 4711 consists of the same types of rolling stock, in the same sequence and orientation, every day of the week. This type of regularity is well known from car position indicators.
- Representational regularity: In the visualization of vehicle rotation plans similar weekdays of operation should be grouped into one rotation day.
- Rotation regularity: Rotations of units of rolling stock should not be subdivided into many parts. This aims at a uniform wear and tear.
Regularity makes the operation of a railroad easier and more transparent by creating a routine way of handling all matters involved.
Our approach to rolling stock rostering is based on a novel hypergraph model of the problem, which serves as a universal tool to handle all types of train composition rules including sequencing, orientation, operational, and sequence regularity. In this model, vehicle rotations can be expressed in terms of hyperassignments.
Hyperassignments are generalizations of assignments. Our research dealt with hyperassignments in general and hyperassignments on what we call partitioned hypergraphs. The latter have a special hyperarc structure that applies to vehicle rotation planning models. We proved the hyperassignment problem to be NP-hard, even for partitioned hypergraphs with hyperarcs of maximum size two. Further, the canonical integer linear programming formulation results in large integrality gaps and arbitrarily high basis matrix determinants.
Calculations with practical data showed that clique inequalities highly reduce the LP-IP gap when added to the canonical integer program and therefore are of great importance. We proposed an extended formulation of the hypergraph assignment problem, which provably implies all clique inequalities and can be solved by column generation. Building on these results, we started a polyhedral investigation that has so far identified a number of interesting classes of cut inequalities.
Hyperassignment polyhedra have a complex structure even for small problems. We have classified the facets for the partitioned case with hyperarc size at most two and at most 6 vertices. We plan to expand and generalize our insights from this study to hyperassignment problem polyhedra for problems with more vertices and greater maximum hyperarc sizes. Developing graph decomposition, shrinking, and lifting procedures, we want to make these results usable to solve large-scale problems. Our experiments also indicate that hyperassignment problems can be approximated well by using a small number of important facets. We are therefore trying to identify special structures that give rise to approximation results, and that would also be useful in practical implementations.
Further, it would be helpful to find classes of directed hypergraphs for which the hyperassignment problem can be solved in polynomial time. This could lead to approximation algorithms using modification of the objective function. Moreover, we want to broaden our research to hyperassignments in multi-commodity settings, which are relevant in rolling stock rostering models.
Publications
2021 |
|||
Ralf Borndörfer, Thomas Eßer, Patrick Frankenberger, Andreas Huck, Christoph Jobmann, Boris Krostitz, Karsten Kuchenbecker, Kai Moorhagen, Philipp Nagl, Michael Peterson, Markus Reuther, Thilo Schang, Michael Schoch, Hanno Schülldorf, Peter Schütz, Tobias Therolf, Kerstin Waas, Steffen Weider | Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization | Informs Journal on Applied Analytics, 51(1), pp. 42-62, 2021 |
BibTeX
DOI |
2015 |
|||
Ralf Borndörfer, Olga Heismann | The hypergraph assignment problem | Discrete Optimization, Vol.15, pp. 15-25, 2015 (preprint available as ZIB-Report 12-14) |
PDF (ZIB-Report)
PDF (ZIB-Report) BibTeX DOI |
2014 |
|||
Olga Heismann, Ralf Borndörfer | A Generalization of Odd Set Inequalities for the Set Packing Problem | Operations Research Proceedings 2013, pp. 193-199, 2014 (preprint available as ZIB-Report 14-28) |
PDF (ZIB-Report)
BibTeX DOI |
Isabel Beckenbach, Ralf Borndörfer | An Approximation Result for Matchings in Partitioned Hypergraphs | ZIB-Report 14-30 (Appeared in: Operations Research Proceedings 2014 (2016) pp. 31-36.) |
PDF
BibTeX URN DOI |
Olga Heismann | The Hypergraph Assignment Problem | Doctoral thesis, Technische Universität Berlin, Ralf Borndörfer, Martin Grötschel (Advisors), 2014 |
BibTeX
|
2013 |
|||
Olga Heismann, Achim Hildenbrandt, Francesco Silvestri, Gerhard Reinelt, Ralf Borndörfer | HUHFA: A Framework for Facet Classification | ZIB-Report 13-45 |
PDF
BibTeX URN |
Isabel Beckenbach | Special cases of the hypergraph assignment problem | Master's thesis, Technische Universität Berlin, Martin Grötschel, Ralf Borndörfer (Advisors), 2013 |
PDF
BibTeX URN |
Olga Heismann, Ralf Borndörfer | The Random Hypergraph Assignment Problem | Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013, pp. 599-602, 2013 |
PDF
BibTeX |
2012 |
|||
Olga Heismann, Ralf Borndörfer | Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning | Operations Research Proceedings 2011, pp. 59-64, 2012 (preprint available as ZIB-Report 11-46) |
PDF (ZIB-Report)
BibTeX |
Ralf Borndörfer, Thomas Schlechte, Elmar Swarat | Railway Track Allocation -- Simulation, Aggregation, and Optimization | Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011), 2(148), pp. 53-70, 2012 (preprint available as ZIB-Report 11-35) |
PDF (ZIB-Report)
BibTeX DOI |
Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider | Vehicle Rotation Planning for Intercity Railways | Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12), 2012 (preprint available as ZIB-Report 12-11) |
PDF (ZIB-Report)
BibTeX |
2011 |
|||
Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider | A Hypergraph Model for Railway Vehicle Rotation Planning | 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs)(20), pp. 146-155, 2011 (preprint available as ZIB-Report 11-36) |
PDF (ZIB-Report)
BibTeX DOI |
Thomas Schlechte, Ralf Borndörfer, Berkan Erol, Thomas Graffagnino, Elmar Swarat | Micro–macro transformation of railway networks | Journal of Rail Transport Planning & Management, 1(1), pp. 38-48, 2011 (preprint available as ZIB-Report 10-23) |
PDF (ZIB-Report)
BibTeX DOI |
2010 |
|||
Ralf Borndörfer, Thomas Schlechte, Steffen Weider | Railway Track Allocation by Rapid Branching | Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Thomas Erlebach, Marco Lübbecke (Eds.), pp. 13-23, Vol.14, OpenAccess Series in Informatics (OASIcs), 2010 (preprint available as ZIB-Report 10-22) |
PDF (ZIB-Report)
BibTeX DOI |