Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
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.
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Liqun Chen, Matthias Enzmann, et al.
FC 2005
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Rolf Clauberg
IBM J. Res. Dev