• search hit 3 of 3
Back to Result List

A Hypergraph Model for Railway Vehicle Rotation Planning

Please always quote using this URN:urn:nbn:de:0296-matheon-10796
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider
URN:urn:nbn:de:0296-matheon-10796
Referee:Volker Mehrmann
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/02/17
Release Date:2012/02/17
Tag:Column Generation; Hypergraph Modeling; Integer Programming; Rapid Branching; Rolling Stock Planning
Institute:Research Center Matheon
Zuse Institute Berlin (ZIB)
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
Preprint Number:925
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.