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 NPhard, 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 LPIP 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 largescale 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 multicommodity settings, which are relevant in rolling stock rostering models.
Publikationen
2015 

Ralf Borndörfer, Olga Heismann  The hypergraph assignment problem  Discrete Optimization, Vol.15, pp. 1525, 2015 (preprint available as ZIBReport 1214) 
PDF (ZIBReport)
PDF (ZIBReport) BibTeX DOI 
2014 

Olga Heismann, Ralf Borndörfer  A Generalization of Odd Set Inequalities for the Set Packing Problem  Operations Research Proceedings 2013, pp. 193199, 2014 (preprint available as ZIBReport 1428) 
PDF (ZIBReport)
BibTeX DOI 
Isabel Beckenbach, Ralf Borndörfer  An Approximation Result for Matchings in Partitioned Hypergraphs  ZIBReport 1430 (Appeared in: Operations Research Proceedings 2014 (2016) pp. 3136.) 
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  ZIBReport 1345 
PDF
BibTeX URN 
Isabel Beckenbach  Special cases of the hypergraph assignment problem  Masters 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. 599602, 2013 
PDF
BibTeX 
2012 

Olga Heismann, Ralf Borndörfer  Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning  Operations Research Proceedings 2011, pp. 5964, 2012 (preprint available as ZIBReport 1146) 
PDF (ZIBReport)
BibTeX 
Ralf Borndörfer, Thomas Schlechte, Elmar Swarat  Railway Track Allocation  Simulation, Aggregation, and Optimization  Proc. 1st International Workshop on Highspeed and Intercity Railways (IWHIR 2011), 2(148), pp. 5370, 2012 (preprint available as ZIBReport 1135) 
PDF (ZIBReport)
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 ZIBReport 1211) 
PDF (ZIBReport)
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. 146155, 2011 (preprint available as ZIBReport 1136) 
PDF (ZIBReport)
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. 3848, 2011 (preprint available as ZIBReport 1023) 
PDF (ZIBReport)
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. 1323, Vol.14, OpenAccess Series in Informatics (OASIcs), 2010 (preprint available as ZIBReport 1022) 
PDF (ZIBReport)
BibTeX DOI 