Approximation algorithms for VRP with stochastic demands

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Research output: Contribution to journalArticlepeer-review


We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1+α for split-delivery VRPSD, and 2+α for unsplit-delivery VRPSD; here α is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4) 149-158; Altinkemer, K., B. Gavish. 1990. Heuristics for delivery problems with constant error guarantees. Transportation Res. 24(4) 294-297]. We also show that the "cyclic heuristic" for split-delivery VRPSD achieves a constant approximation ratio, as conjectured in Bertsimas [Bertsimas, D. J. 1992. A vehicle routing problem with stochastic demand. Oper. Res. 40(3) 574-585].

Original languageEnglish (US)
Pages (from-to)123-127
Number of pages5
JournalOperations Research
Issue number1
StatePublished - Jan 2012


  • Analysis of algorithms: suboptimal algorithms
  • Networks/graphs: stochastic
  • Transportation: vehicle routing

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Approximation algorithms for VRP with stochastic demands'. Together they form a unique fingerprint.

Cite this