Optimization Online


The Freight Train Routing Problem

Ralf Borndörfer(borndoerfer***at***zib.de)
Armin Fügenschuh(fuegenschuh***at***zib.de)
Torsten Klug(klug***at***zib.de)
Thilo Schang(thilo.schang***at***deutschebahn.com)
Thomas Schlechte(schlechte***at***zib.de)
Hanno Schülldorf(hanno.schuelldorf***at***deutschebahn.de)

Abstract: 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.

Keywords: freight train routing, capacity restraint functions, multi-commodity flows, mixed-integer linear and nonlinear programming

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Network Optimization

Citation: ZIB Technical Report ZR-13-36, July 2013, Online available at URL http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1899

Download: [PDF]

Entry Submitted: 07/21/2013
Entry Accepted: 07/22/2013
Entry Last Modified: 07/21/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society