Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 4 von 6
Zurück zur Trefferliste

Minimum Cost Hyperassignments

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Olga Heismann
Dokumentart:Masterarbeit
Titel verleihende Institution:Technische Universität Berlin
Datum der Abschlussprüfung:18.10.2010
Veröffentlichende Institution:Zuse Institute Berlin (ZIB)
Datum der Erstveröffentlichung:18.10.2010
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.