Minimum Cost Hyperassignments

Please always quote using this URN: urn:nbn:de:0297-zib-13371
  • 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.

Download full text files

Export metadata

Author:Olga Heismann
Document Type:Master's Thesis
Granting Institution:Technische Universit├Ąt Berlin
Date of final exam:2010/10/18
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:2010/10/18