• EN
  • DA

Danish NationalResearch Database

  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the phrase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
bech{} containing the word "bech".
marie bech"{}" containing the phrase "marie bech".
orcid:0000-0002-5429-5292orcid:{} Having a particular ORCID
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Stochastic vehicle routing with recourse

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Gørtz, Inge Li ;
    Close
    Orcid logo0000-0002-8322-4952
    Department of Informatics and Mathematical Modeling, Technical University of Denmark
  • Nagarajan, Viswanath ;
    Close
    IBM Research
  • Saket, Rishi
    Close
    IBM Research
Editor:
Czumaj, Artur, Mehlhorn, Kurt, Pitts, Andrew, Wattenhofer, Roger
DOI:
10.1007/978-3-642-31594-7_35
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.
ISBN:
9783642315930
Type:
Conference paper
Language:
English
Published in:
Lecture Notes in Computer Science: 39th International Colloquium, Icalp 2012, 2012, p. 411-423
Main Research Area:
Science/technology
Publication Status:
Published
Series:
Lecture Notes in Computer Science
Review type:
Peer Review
Conference:
Automata, Languages, and Programming. 39th International Colloquium, ICALP 2012
Publisher:
Springer
Submission year:
2012
Scientific Level:
Scientific
ID:
2288131435

Full text access

  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institution

  • Technical university of dk

Metrics

Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and Personal Data
  • Open Access
    • The Danish Open Access Indicator

Copyright © 1998–2018.

Fivu en