Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization

Ralf Borndörfer (), Thomas Eßer (), Patrick Frankenberger (), Andreas Huck (), Christoph Jobmann (), Boris Krostitz (), Karsten Kuchenbecker (), Kai Mohrhagen (), Philipp Nagl (), Michael Peterson (), Markus Reuther (), Thilo Schang (), Michael Schoch (), Hanno Schülldorf (), Peter Schütz (), Tobias Therolf (), Kerstin Waas () and Steffen Weider ()
Additional contact information
Ralf Borndörfer: Mathematics Department, Freie Universität Berlin, and Network Optimization Department, Zuse Institute Berlin, 14195 Berlin, Germany;
Thomas Eßer: Deutsche Bahn Cargo AG, 55116 Mainz, Germany;
Patrick Frankenberger: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Andreas Huck: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Christoph Jobmann: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Boris Krostitz: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Karsten Kuchenbecker: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Kai Mohrhagen: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Philipp Nagl: Deutsche Bahn Fernverkehr AG, 60326 Frankfurt am Main, Germany;
Michael Peterson: Deutsche Bahn Fernverkehr AG, 60326 Frankfurt am Main, Germany;
Markus Reuther: LBW Optimization GmbH, 14195 Berlin, Germany;
Thilo Schang: Deutsche Bahn Netz AG, 60486 Frankfurt am Main, Germany;
Michael Schoch: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Hanno Schülldorf: Deutsche Bahn AG, 60329 Frankfurt am Main, Germany;
Peter Schütz: Deutsche Bahn AG, 60528 Frankfurt am Main, Germany;
Tobias Therolf: Deutsche Bahn Regio AG, 68163 Mannheim, Germany;
Kerstin Waas: Deutsche Bahn Netz AG, 60326 Frankfurt am Main, Germany
Steffen Weider: LBW Optimization GmbH, 14195 Berlin, Germany;

Interfaces, 2021, vol. 51, issue 1, 42-62

Abstract: Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are addressed using a novel coarse-to-fine method that implements a hierarchical column generation over three levels of detail. This algorithm is the mathematical core of DB’s fleet employment optimization (FEO) system for rolling stock rotation planning. FEO’s impact within DB’s planning departments has been revolutionary. DB has used it to support the company’s procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for crossborder operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s planning departments appreciate FEO’s high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO 2 emissions, and the elimination of 600 coupling operations in crossborder operations to the implementation of FEO.

Keywords: ransportation; rail; scheduling; vehicles; large-scale systems; integer programming; graphs; hypergraphs; Edelman Award (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/inte.2020.1069 (application/pdf)

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:inm:orinte:v:51:y:2021:i:1:p:42-62

Access Statistics for this article

More articles in Interfaces from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().