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.
- TU Darmstadt & Deutsche Bahn AG, Frankfurt.
Further academic partners
- TU Braunschweig
- TU Chemnitz
- Uni Dortmund
- Deutsche Bahn AG, Frankfurt.
Federal Ministry for Research and Education (BMBF), Project Oversys.
- Gemischt-ganzzahlige nichtlineare Optimierungsprobleme in zwei Transportanwendungen, Universität Ulm, Germany, 29.10.2012.
- Mixed-Integer Nonlinear Optimization Problems in Transportation Applications, RWTH Aachen, Germany, 21.5.2012.
- Gemischt-ganzzahlige nichtlineare Optimierungsprobleme in zwei Transportanwendungen, Helmut-Schmidt-Universität - Universität der Bundeswehr, Hamburg, Germany, 31.5.2011.
- Routing Cars in Rail Freight Service, Discrete Optimization Seminar, Georgia Institute of Technology, Atlanta (GA), USA, 30.8.2011.
- Mixed-Integer Nonlinear Problems in Transportation Applications, EngOpt 2010, Lisbon, Portugal, 8.9.2010.
- Routing Cars in Rail Freight Service, EURO 2010, 24rd European Conference on Operational Research, Lisbon, 13.7.2010.
- Leitwege- und Fahrplanoptimierung, Abschlusspräsentation der Bahn-Teilprojekte im Verbundprojekts OVERSYS, BMBF Statusseminar, Kaiserslautern, Germany, 9.6.2010.
- Service Network Design in Rail Freight Transportation, Warsaw Seminar on Industrial Mathematics WSIM’10, Warsaw, Poland, 19.3.2010.
- Routing Cars in Rail Freight Service, Institute for Mathematics, Magdeburg, Germany, 1.3.2010.
- Routing Cars in Rail Freight Service, International Workshop on Combinatorial Optimization, Aussois, France, 7.1.2010.
- Routing Cars in Rail Freight Service, Dagstuhl Seminar 09261/1: Models and Algorithms for Optimization in Logistics, Dagstuhl, Germany, 25.6.2009.
- 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.
- 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.
- 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.
- 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.