Approximation algorithms for VRP with stochastic demands

Anupam Gupta; Viswanath Nagarajan; R. Ravi

doi:10.1287/opre.1110.0967

Approximation algorithms for VRP with stochastic demands

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Computer Science

Research output: Contribution to journal › Article › peer-review

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].

Original language	English (US)
Pages (from-to)	123-127
Number of pages	5
Journal	Operations Research
Volume	60
Issue number	1
DOIs	https://doi.org/10.1287/opre.1110.0967
State	Published - Jan 2012

Keywords

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

ASJC Scopus subject areas

Computer Science Applications
Management Science and Operations Research

Access to Document

10.1287/opre.1110.0967

Cite this

@article{c49956f3eb1a400d81c2c4b836ce8bbe,

title = "Approximation algorithms for VRP with stochastic demands",

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].",

keywords = "Analysis of algorithms: suboptimal algorithms, Networks/graphs: stochastic, Transportation: vehicle routing",

author = "Anupam Gupta and Viswanath Nagarajan and R. Ravi",

year = "2012",

month = jan,

doi = "10.1287/opre.1110.0967",

language = "English (US)",

volume = "60",

pages = "123--127",

journal = "Operations Research",

issn = "0030-364X",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

number = "1",

}

TY - JOUR

T1 - Approximation algorithms for VRP with stochastic demands

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2012/1

Y1 - 2012/1

N2 - 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].

AB - 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].

KW - Analysis of algorithms: suboptimal algorithms

KW - Networks/graphs: stochastic

KW - Transportation: vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84859575218&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84859575218&partnerID=8YFLogxK

U2 - 10.1287/opre.1110.0967

DO - 10.1287/opre.1110.0967

M3 - Article

AN - SCOPUS:84859575218

SN - 0030-364X

VL - 60

SP - 123

EP - 127

JO - Operations Research

JF - Operations Research

IS - 1

ER -

Approximation algorithms for VRP with stochastic demands

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this