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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Author:Katharina Beygang, Sven O. Krumke, Florian Dahms
URN (permanent link):urn:nbn:de:hbz:386-kluedo-16709
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (132)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of Publication:2010
Publishing Institute:Technische Universität Kaiserslautern
Tag:Bell Number; Competitive Analysis; Greedy Heuristic; Online Algorithms; Train Rearrangement
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $