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.

Download full text files

Export metadata

  • Export Bibtex
Author:Ralf Borndörfer, 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)
Published in:Appeared in: Klatte, D., Lüthi, H.-J., and Schmedders, K., editors, Operations Research Proceedings 2011, pages 59–64

$Rev: 13581 $