@article{g2012a,
title = {Stochastic vehicle routing with recourse},
language = {eng},
publisher = {Springer},
author = {Gørtz, Inge Li and Nagarajan, Viswanath and Saket, Rishi},
editor = {Czumaj, Artur, Mehlhorn, Kurt, Pitts, Andrew, Wattenhofer, Roger},
journal = {Lecture Notes in Computer Science},
pages = {411-423},
year = {2012},
issn = {16113349, 03029743},
isbn = {9783642315930},
abstract = {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.},
doi = {10.1007/978-3-642-31594-7_35}
}