caa a22 4500 445839899 CHVBK 20180317145340.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00186-011-0349-2 doi (NATIONALLICENCE)springer-10.1007/s00186-011-0349-2 Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization [Elektronische Daten] [Sven Krumke, Clemens Thielen, Christiane Zeck] 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 δ. 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 δ. 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 δ 1 and δ 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 Δ 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. Springer-Verlag, 2011 Delay management nationallicence Online optimization nationallicence Competitive analysis nationallicence Public transportation nationallicence Krumke Sven Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut Thielen Clemens Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut Zeck Christiane Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut Mathematical Methods of Operations Research Springer-Verlag 74/1(2011-08-01), 53-75 1432-2994 74:1<53 2011 74 186 https://doi.org/10.1007/s00186-011-0349-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00186-011-0349-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Krumke Sven Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut NATIONALLICENCE 700 1- Thielen Clemens Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut NATIONALLICENCE 700 1- Zeck Christiane Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany aut NATIONALLICENCE 773 0- Mathematical Methods of Operations Research Springer-Verlag 74/1(2011-08-01), 53-75 1432-2994 74:1<53 2011 74 186 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer