The freight train routing problem (FTRP) is formulated as follows: Given is a transportation network with fixed routes for passenger trains and a set of freight train 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 recent approaches 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 by time slices. 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 timeexpanded graph with additional routing constraints. The model's nonlinearities are due to an algebraic approximation of the delays of the trains on the arcs and in the nodes of the network. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. We use different state of the art MILP solvers and compare their results with a greedy-type best insertion start heuristic.

Partners

• Zuse Institute Berlin
• Deutsche Bahn AG, Frankfurt
• FAU Erlangen & Deutsche Bahn AG, Frankfurt

Further academic partners

• TU Braunschweig
• TU Chemnitz
• Universität Dortmund
• FAU Erlangen

Industrial partners

• Deutsche Bahn AG, Frankfurt.

Funding

• Federal Ministry for Research and Education (BMBF), Project Kosmos.

Related publications

• Ralf Borndörfer, Armin Fügenschuh, Torsten Klug, Thilo Schang, Thomas Schlechte, Hanno Schülldorf, The Freight Train Routing Problem , ZIB Technical Report ZR-13-36, 2013.
• Ralf Borndörfer, Armin Fügenschuh, Torsten Klug, Thomas Schlechte, Freight Train Routing , International Conference on Models and Technologies for ITS, 2011.