OASIcs.ATMOS.2014.79.pdf
- Filesize: 0.67 MB
- 13 pages
Document
A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem
Authors
-
Part of:
Volume:
14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2014)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-09-19
Cite As Get BibTex
Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 79-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/OASIcs.ATMOS.2014.79
Abstract
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
Subject Classification
Keywords
- Coarse-To-Fine Linear Programming
- Rolling Stock Rotation Problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Andreas Bärmann, Frauke Liers, Alexander Martin, Maximilian Merkert, Christoph Thurner, and Dieter Weninger. Solving network design problems via iterative aggregation. Technical report, Department Mathematik, 2013.
-
Jacques Desrosiers, Jean Bertrand Gauthier, and Marco E. Lübbecke. Row-reduced column generation for degenerate master problems. European Journal of Operational Research, 236(2):453 - 460, 2014.
-
Issmail Elhallaoui, Abdelmoutalib Metrane, François Soumis, and Guy Desaulniers. Multi-phase dynamic constraint aggregation for set partitioning type problems. Mathematical Programming, 123(2):345-370, 2010.
-
Olga Heismann. The Hypergraph Assignment Problem. PhD thesis, Technische Universität Berlin, 2014.
-
M.E. Lübbecke and J. Desrosiers. Selected topics in column generation. Oper. Res., 53(6):1007-1023, 2005.
-
C. Raphael. Coarse-to-fine dynamic programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(12):1379-1390, 2001.
-
Markus Reuther, Ralf Borndoerfer, Thomas Schlechte, and Steffen Weider. Integrated optimization of rolling stock rotations for intercity railways. In Proceedings of the 5th International Seminar on Railway Operations Modelling and Analysis (RailCopenhagen), Copenhagen, Denmark, May 2013.
-
Markus Reuther, Ralf Borndörfer, and Thomas Schlechte. A coarse-to-fine approach to the railway rolling stock rotation problem. Technical Report 14-26, ZIB, Takustr.7, 14195 Berlin, 2014.
-
David F. Rogers, Robert D. Plante, Richard T. Wong, and James R. Evans. Aggregation and disaggregation techniques and methodology in optimization. Operations Research, 39(4):553-582, 1991.
-
Thomas Schlechte, Ralf Borndörfer, Berkan Erol, Thomas Graffagnino, and Elmar Swarat. Micro-Macro Transformation of Railway Networks. Journal of Rail Transport Planning & Management, 1(1):38-48, 2011.
-
J. Tang, S. MacLachlan, R. Nabben, and C. Vuik. A comparison of two-level preconditioners based on multigrid and deflation. SIAM Journal on Matrix Analysis and Applications, 31(4):1715-1739, 2010.