Publication Date:
2020-08-05
Description:
Vehicle rotation planning for long distance passenger railways is a fundamental
problem in rail transport. It deals with the allocation of vehicles to trips
in a cyclic weekly schedule. Its result is an assignment of each trip to a follow-on
trip which will be serviced by the same vehicle.
To take so-called regularity, which is an important requirement, into account,
vehicle rotation planning can be modeled as a hyperassignment problem. This is
a generalization of the assignment problem to directed hypergraphs we propose.
We prove that the hyperassignment problem is NP-hard for the practically
relevant cases and that the canonical integer linear programming (ILP)
formulation results in large integrality gaps and arbitrarily high basis matrix
determinants.
Our main contribution is an extended ILP formulation, which provably
implies important classes of inequalities, e. g., all clique inequalities. Clique inequalities
are of great importance, because as calculations with practical data show they highly reduce the LP-IP gap. The extended
formulation can be solved by column generation. We propose fast combinatorial
algorithms for the pricing subproblem.
Language:
English
Type:
masterthesis
,
doc-type:masterThesis
Format:
application/pdf
