Online Delay Management

  • We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of delta. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by delta. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays delta_1 and delta_2, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Delta a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Sven O. Krumke, Clemens Thielen, Christiane Zeck
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16394
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (127)
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):08.07.2010
Freies Schlagwort / Tag:competitive analysis; delay management; online optimization; public transportation
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 $