90C10 Integer programming
Refine
Year of publication
- 2012 (3) (remove)
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3) (remove)
Keywords
- combinatorial optimization (1)
- hyperassignments (1)
- ideal matrices (1)
- integer programming (1)
- line planning (1)
- transfers (1)
- vehicle rotation planning (1)
Institute
- Mathematics of Transportation and Logistics (3) (remove)
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
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.