Technical Note---Approximation Algorithms for VRP with Stochastic Demands

Anupam Gupta (), Viswanath Nagarajan () and R. Ravi ()
Additional contact information
Anupam Gupta: Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Viswanath Nagarajan: IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
R. Ravi: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2012, vol. 60, issue 1, 123-127

Abstract: We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + (alpha) for split-delivery VRPSD, and 2 + (alpha) for unsplit-delivery VRPSD; here (alpha) 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].

Keywords: analysis of algorithms; suboptimal algorithms; transportation; vehicle routing; networks/graphs; stochastic (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0967 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:1:p:123-127

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().