1113
eng
reportzib
0
2009-02-11
2009-02-11
--
Randomized Online Algorithms for Dynamic Multi-Period Routing Problems
The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of $\frac{1+\sqrt{2}}{2}$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm.
09-03
1438-0064
1155
urn:nbn:de:0297-zib-11132
Appeared in: 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (C. Stein, M. Uetz und T. Vredeveld, Hg.), 2009
Benjamin Hiller
unknown unknown
Sven O. Krumke
Sleman Saliba
Andreas Tuchscherer
ZIB-Report
09-03
deu
uncontrolled
Online-Optimierung
deu
uncontrolled
Randomisierte Algorithmen
deu
uncontrolled
Zweistufiges Problem
deu
uncontrolled
Traveling-Salesman-Problem
eng
uncontrolled
online optimization
eng
uncontrolled
randomized algorithm
eng
uncontrolled
two-stage problem
eng
uncontrolled
traveling salesman problem
Mathematik
Analysis of algorithms [See also 68Q25]
Mathematical Optimization
Hiller, Benjamin
MATHEON-B14:Comb-Log
https://opus4.kobv.de/opus4-zib/files/1113/ZR_09_03.pdf
https://opus4.kobv.de/opus4-zib/files/1113/ZR_09_03.ps