TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

Robust Algorithms for Sorting Railway Cars
Citation key Report-014-2010
Author Christina Büsing and Jens Maue
Year 2010
Number 014
Month jun
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We consider a sorting problem from railway optimization called train classification: incoming trains are split up into their single cars and reassembled to form new outgoing trains. Trains are subject to delay, which may turn a prepared sorting schedule infeasible for the disturbed situation. The classification methods applied today deal with this issue by completely disregarding the input order of cars, which provides robustness against any amount of disturbance but also wastes the potential contained in the a priori knowledge about the input. We introduce a new method that provides a feasible sorting schedule for the expected input and allows to flexibly insert additional sorting steps if the schedule has become infeasible after revealing the disturbed input. By excluding disruptions that almost never occur from our consideration, we obtain a classification process that is quicker than the current railway practice but still provides robustness against realistic delays. In fact, our algorithm allows flexibly trading off fast classification against high degrees of robustness depending on the respective need. We further explore this flexibility in experiments on real-world traffic data, underlining our algorithm improves on the methods currently applied in practice.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe