A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance

epub ahead of print
  • For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Boris Grimm, Ralf Borndörfer, Markus Reuther, Thomas Schlechte
Editor:Valentina Cacchiani, Alberto Marchetti-Spaccamela
Document Type:In Proceedings
Parent Title (English):19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Volume:75
First Page:1:1
Last Page:1:12
Series:OpenAccess Series in Informatics (OASIcs)
Publisher:Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl, Germany
Fulltext Url:https://drops.dagstuhl.de/opus/volltexte/2019/11413/pdf/OASIcs-ATMOS-2019-1.pdf
Year of first publication:2019
URL:https://drops.dagstuhl.de/opus/volltexte/2019/11413/
Preprint:urn:nbn:de:0297-zib-75501
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2019.1