Single-car rail freight routing

Single cars in rail freight service are bundled into trains at classification yards. On the way from their respective origins via intermediate yards to their destinations they are re-classified several times, which is a time and personal consuming procedure. The single car routing problem asks for the design of such routes for a given set of orders (origin-destination pairs with associated data) on an infrastructure network, such that the number of trains and their travel distances is minimal. A number of hard restrictions must be obeyed, such as restrictions for the train length and weight, and capacity restrictions for the yards, as well as further operational rules.

We present a mixed-integer linear programming (MILP) formulation for this car routing problem arising at Deutsche Bahn, one of the largest European railway companies. An adequate handling of the turnover waiting time for the cars in the yards leads to the inclusion of nonlinear constraint in the model. Using different linearization techniques, this model can be reduced to an MILP again. Instances of this model turn out to be hard to solve. Further techniques are thus presented to speed-up the numerical solution process, among them a tree-based reformulation and heuristic cuts. Using state-of-the-art MILP solvers, optimal or near-optimal
solutions can be computed within reasonable time.

Partners

  • TU Darmstadt & Deutsche Bahn AG, Frankfurt.

Further academic partners

  • TU Braunschweig
  • TU Chemnitz
  • Uni Dortmund

Industrial partners

  • Deutsche Bahn AG, Frankfurt.

Funding

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

Related talks

  1. Gemischt-ganzzahlige nichtlineare Optimierungsprobleme in zwei Transportanwendungen, Universität Ulm, Germany, 29.10.2012.
  2. Mixed-Integer Nonlinear Optimization Problems in Transportation Applications, RWTH Aachen, Germany, 21.5.2012.
  3. Gemischt-ganzzahlige nichtlineare Optimierungsprobleme in zwei Transportanwendungen, Helmut-Schmidt-Universität - Universität der Bundeswehr, Hamburg, Germany, 31.5.2011.
  4. Routing Cars in Rail Freight Service, Discrete Optimization Seminar, Georgia Institute of Technology, Atlanta (GA), USA, 30.8.2011.
  5. Mixed-Integer Nonlinear Problems in Transportation Applications, EngOpt 2010, Lisbon, Portugal, 8.9.2010.
  6. Routing Cars in Rail Freight Service, EURO 2010, 24rd European Conference on Operational Research, Lisbon, 13.7.2010.
  7. Leitwege- und Fahrplanoptimierung, Abschlusspräsentation der Bahn-Teilprojekte im Verbundprojekts OVERSYS, BMBF Statusseminar, Kaiserslautern, Germany, 9.6.2010.
  8. Service Network Design in Rail Freight Transportation, Warsaw Seminar on Industrial Mathematics WSIM’10, Warsaw, Poland, 19.3.2010.
  9. Routing Cars in Rail Freight Service, Institute for Mathematics, Magdeburg, Germany, 1.3.2010.
  10. Routing Cars in Rail Freight Service, International Workshop on Combinatorial Optimization, Aussois, France, 7.1.2010.
  11. Routing Cars in Rail Freight Service, Dagstuhl Seminar 09261/1: Models and Algorithms for Optimization in Logistics, Dagstuhl, Germany, 25.6.2009.

Related publications

  1. Armin Fügenschuh, Henning Homfeld, Hanno Schülldorf, Single-Car Routing in Rail Freight Transport , Transportation Science, Vol. 49, No. 1, pp. 130-148, 2015.
  2. Armin Fügenschuh, Henning Homfeld, Hanno Schülldorf, A Service Network Design Problem in Rail Freight Transportation. In: P. Grzegorzewski, T. Rzezuchowski (Eds.), Issues in Industrial Mathematics, Politechnika Warszawska, Warszawa, pp. 99-110, 2013.
  3. Armin Fügenschuh, Henning Homfeld, Hanno Schülldorf, Stefan Vigerske, Mixed-Integer Nonlinear Problems in Transportation Applications , Hélder Rodrigues et al. (Eds.), Proceedings of the 2nd International Conference on Engineering Optimization (+CD-rom), ISBN 978-989-96264-3-0, 2010.
  4. Armin Fügenschuh, Henning Homfeld, Hanno Schülldorf, Single Car Routing in Rail Freight Transport , Cynthia Barnhart, Uwe Clausen, Ulrich Lauther, Rolf H. Möhring (Eds.), Dagstuhl Seminar Proceedings 09261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Deutschland, 2009.

This website uses cookies. There are two types of cookies: The first type supports the basic functionality of our website. The second allows us to improve our content for you by saving and analyzing pseudonymised user data. Since this second type is technically not required to run the website, you can withdraw your consent to those cookies at any time. For more information please visit our pages on data protection.

Mandatory

These cookies are needed for a smooth operation of our website.

Statistic

For statistical reasons, we use the platform Matomo to analyse the user flow with the help of website users‘ pseudonymised data. This allows us to optimize website content.

Name Purpose Lifetime Type Provider
_pk_id Used to store a few details about the user such as the unique visitor ID. 13 months HTML Matomo
_pk_ref Used to store the attribution information, the referrer initially used to visit the website. 6 months HTML Matomo
_pk_ses Short lived cookie used to temporarily store data for the visit. 30 minutes HTML Matomo