Conference paper
Stochastic vehicle routing with recourse
Department of Informatics and Mathematical Modeling, Technical University of Denmark1
Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark2
Computer Science and Engineering, Department of Informatics and Mathematical Modeling, Technical University of Denmark3
IBM Research4
We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage problem, where demand is satisfied using two routes: fixed and recourse. The fixed route is computed using only a demand distribution. Then after observing the demand instantiations, a recourse route is computed - but costs here become more expensive by a factor λ.
We present an O(log2n ·log(nλ))-approximation algorithm for this stochastic routing problem, under arbitrary distributions. The main idea in this result is relating StochVRP to a special case of submodular orienteering, called knapsack rank-function orienteering. We also give a better approximation ratio for knapsack rank-function orienteering than what follows from prior work.
Finally, we provide a Unique Games Conjecture based ω(1) hardness of approximation for StochVRP, even on star-like metrics on which our algorithm achieves a logarithmic approximation.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2012 |
Pages: | 411-423 |
Proceedings: | Automata, Languages, and Programming. 39th International Colloquium, ICALP 2012 |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 39th International Colloquium, Icalp 2012 |
ISBN: | 3642315933 , 3642315941 , 9783642315930 and 9783642315947 |
ISSN: | 03029743 |
Types: | Conference paper |
DOI: | 10.1007/978-3-642-31594-7_35 |
ORCIDs: | Gørtz, Inge Li |