Stochastic vehicle routing with recourse

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

View graph of relations

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.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming : 39th International Colloquium, ICALP 2012
EditorsArtur Czumaj, Kurt Mehlhorn , Andrew Pitts, Roger Wattenhofer
PublisherSpringer
Publication date2012
Pages411-423
ISBN (print)978-3-642-31593-0
DOIs
StatePublished

Conference

ConferenceAutomata, Languages, and Programming. 39th International Colloquium, ICALP 2012
CityWarwick
Period01/01/12 → …
NameLecture Notes in Computer Science
Volume7391
ISSN (Print)0302-9743
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 10197667