1899
eng
reportzib
0
2013-07-19
2013-07-19
--
The Freight Train Routing Problem
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
urn:nbn:de:0297-zib-18991
Ralf Borndörfer
Torsten Klug
Armin Fügenschuh
Torsten Klug
Thilo Schang
Thomas Schlechte
Hanno Schülldorf
ZIB-Report
13-36
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
multi-commodity flows
eng
uncontrolled
freight train routing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Fügenschuh, Armin
Klug, Torsten
Schlechte, Thomas
KOSMOS
https://opus4.kobv.de/opus4-zib/files/1899/ZR-13-36.pdf
5812
2016
eng
408
423
2
50
article
0
--
--
--
The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic
We consider the following freight train routing problem (FTRP).
Given is a transportation network with fixed routes for passenger
trains and a set of freight trains (requests), each defined by an
origin and destination station pair. The objective is to
calculate a feasible route for each freight train such that the
sum of all expected delays and all running times is minimal.
Previous research concentrated on microscopic train routings for
junctions or inside major stations. Only recently approaches were
developed to tackle larger corridors or even networks. We
investigate the routing problem from a strategic perspective,
calculating the routes in a macroscopic transportation network of
Deutsche Bahn AG. In this context, macroscopic refers to an
aggregation of complex and large real-world structures into fewer
network elements. Moreover, the departure and arrival times of
freight trains are approximated. The problem has a strategic
character since it asks only for a coarse routing through the
network without the precise timings. We provide a mixed-integer
nonlinear programming (MINLP) formulation for the FTRP, which is
a multicommodity flow model on a time-expanded graph with
additional routing constraints. The model’s nonlinearities
originate from an algebraic approximation of the delays of the
trains on the arcs of the network by capacity restraint
functions. The MINLP is reduced to a mixed-integer linear
model (MILP) by piecewise linear approximation. The latter is
solved by a state-of-the art MILP solver for various real-world
test instances.
Transportation Science
10.1287/trsc.2015.0656
yes
in press
urn:nbn:de:0297-zib-18991
Ralf Borndörfer
Torsten Klug
Armin Fügenschuh
Torsten Klug
Thilo Schang
Thomas Schlechte
Hanno Schülldorf
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Fügenschuh, Armin
Klug, Torsten
Schlechte, Thomas
KOSMOS
MODAL-RailLab
MODAL-Gesamt
8041
2021
eng
42
62
1
51
article
Institute for Operations Research and the Management Sciences (INFORMS)
0
2021-02-10
--
--
Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization
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 ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB’s fleet em-ployment 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 cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s plan-ning 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 CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO.
Informs Journal on Applied Analytics
10.1287/inte.2020.1069
yes
2020-11-05
publish
Ralf Borndörfer
Ralf Borndörfer
Thomas Eßer
Patrick Frankenberger
Andreas Huck
Christoph Jobmann
Boris Krostitz
Karsten Kuchenbecker
Kai Moorhagen
Philipp Nagl
Michael Peterson
Markus Reuther
Thilo Schang
Michael Schoch
Hanno Schülldorf
Peter Schütz
Tobias Therolf
Kerstin Waas
Steffen Weider
Mathematical Optimization
Borndörfer, Ralf
Weider, Steffen
MATHEON-B22
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
Network Optimization
EBUS
MODAL-MobilityLab