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.
Verfasser*innenangaben: | Katharina Beygang, Sven O. Krumke, Florian Dahms |
---|---|
URN: | 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 Erstverö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: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |