A Hypergraph Model for Railway Vehicle Rotation Planning

Authors Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2011.146.pdf
  • Filesize: 0.54 MB
  • 10 pages

Document Identifiers

Author Details

Ralf Borndörfer
Markus Reuther
Thomas Schlechte
Steffen Weider

Cite AsGet BibTex

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider. A Hypergraph Model for Railway Vehicle Rotation Planning. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 146-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/OASIcs.ATMOS.2011.146

Abstract

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.
Keywords
  • Rolling Stock Planning
  • Hypergraph Modeling
  • Integer Programming
  • Column Generation
  • Rapid Branching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail