1011
eng
masterthesis
TU Ilmenau
0
2004-12-31
2004-12-31
--
Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem
This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.
1026
urn:nbn:de:0297-zib-10114
Benjamin Hiller
unknown unknown
eng
uncontrolled
Dial-a-Ride problem on trees
eng
uncontrolled
probabilistic analysis
eng
uncontrolled
online algorithms
Mathematik
Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Combinatorics (F.2.2)
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Transportation, logistics
Studienabschlussarbeiten
Mathematical Optimization
Hiller, Benjamin
ONLINE-PLANNING
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/1011/probabilistic_darp.pdf