Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning

Olga Heismann () and Ralf Borndörfer ()
Additional contact information
Olga Heismann: Zuse Institute Berlin
Ralf Borndörfer: Zuse Institute Berlin

A chapter in Operations Research Proceedings 2011, 2012, pp 59-64 from Springer

Abstract: Abstract 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.

Keywords: Rotation Planning; Rolling Stock; Rail Transport; Railway Company; Operational Regularity (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-642-29210-1_10

Ordering information: This item can be ordered from
http://www.springer.com/9783642292101

DOI: 10.1007/978-3-642-29210-1_10

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().