Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
BibTeX  Entry
@InProceedings{boeuf_et_al:OASIcs:2014:4751,
author = {Vianney Boeuf and Fr{\'e}d{\'e}ric Meunier},
title = {{Online Train Shunting}},
booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {3445},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897750},
ISSN = {21906807},
year = {2014},
volume = {42},
editor = {Stefan Funke and Mat{\'u}{\v{s}} Mihal{\'a}k},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4751},
URN = {urn:nbn:de:0030drops47512},
doi = {10.4230/OASIcs.ATMOS.2014.34},
annote = {Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
Keywords: 

Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover 
Collection: 

14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 
Issue Date: 

2014 
Date of publication: 

19.09.2014 