10.4230/OASICS.ATMOS.2011.146
Borndörfer, Ralf
Ralf
Borndörfer
Reuther, Markus
Markus
Reuther
Schlechte, Thomas
Thomas
Schlechte
Weider, Steffen
Steffen
Weider
A Hypergraph Model for Railway Vehicle Rotation Planning
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
Rolling Stock Planning
Hypergraph Modeling
Integer Programming
Column Generation
Rapid Branching
Caprara, Alberto
Alberto
Caprara
Kontogiannis, Spyros
Spyros
Kontogiannis
2011
2011-09-19
2011-09-19
2011-09-19
en
urn:nbn:de:0030-drops-32746
10.4230/OASIcs.ATMOS.2011
978-3-939897-33-0
2190-6807
10.4230/OASIcs.ATMOS.2011
OASIcs, Volume 20, ATMOS 2011
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
2012
20
13
146
155
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Caprara, Alberto
Alberto
Caprara
Kontogiannis, Spyros
Spyros
Kontogiannis
2190-6807
Open Access Series in Informatics (OASIcs)
2011
20
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
10 pages
566275 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
OASIcs, Vol. 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pages 146-155