Train Marshalling Problem - Algorithms and Bounds -

  • The Train Marshalling Problem consists of rearranging an incoming train in a marshalling yard in such a way that cars with the same destinations appear consecutively in the final train and the number of needed sorting tracks is minimized. Besides an initial roll-in operation, just one pull-out operation is allowed. This problem was introduced by Dahlhaus et al. who also showed that the problem is NP-complete. In this paper, we provide a new lower bound on the optimal objective value by partitioning an appropriate interval graph. Furthermore, we consider the corresponding online problem, for which we provide upper and lower bounds on the competitiveness and a corresponding optimal deterministic online algorithm. We provide an experimental evaluation of our lower bound and algorithm which shows the practical tightness of the results.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Katharina Beygang, Sven O. Krumke, Florian Dahms
URN:urn:nbn:de:hbz:386-kluedo-16709
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (132)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2011/01/10
Tag:Bell Number; Competitive Analysis; Greedy Heuristic; Online Algorithms; Train Rearrangement
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011