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