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.
