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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Katharina Beygang, Sven O. Krumke, Florian Dahms
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16709
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (132)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2010
Jahr der Veröffentlichung:2010
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):10.01.2011
Freies Schlagwort / Tag:Bell Number; Competitive Analysis; Greedy Heuristic; Online Algorithms; Train Rearrangement
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $