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.

Additional Services

Author: Ralf Borndörfer, Olga Heismann ZIB-Report hyperassignments; vehicle rotation planning 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 2012/01/25 ZIB-Report (11-46) 1438-0064 Appeared in: Klatte, D., Lüthi, H.-J., and Schmedders, K., editors, Operations Research Proceedings 2011, pages 59–64 http://link.springer.com/chapter/10.1007%2F978-3-642-29210-1_10

$Rev: 13581$