Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning
Please always quote using this URN: urn:nbn:de:0297-zib-14564
- 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.
Author: | Ralf BorndörferORCiD, Olga Heismann |
---|---|
Document Type: | ZIB-Report |
Tag: | hyperassignments; vehicle rotation planning |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C65 Hypergraphs |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming | |
Date of first Publication: | 2012/01/25 |
Series (Serial Number): | ZIB-Report (11-46) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 11-46 |
Published in: | Appeared in: Klatte, D., Lüthi, H.-J., and Schmedders, K., editors, Operations Research Proceedings 2011, pages 59–64 |
URL: | http://link.springer.com/chapter/10.1007%2F978-3-642-29210-1_10 |