Publication
Operations Research
Paper

Approximation algorithms for VRP with stochastic demands

View publication

Abstract

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]. © 2012 INFORMS.

Date

Publication

Operations Research

Authors

Topics

Share