Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning

  • Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Olga Heismann, Ralf BorndörferORCiD
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2011
First Page:59
Last Page:64
Year of first publication:2012
Preprint:urn:nbn:de:0297-zib-14564
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.