Tighter Analysis of an Approximation for the Cumulative VRP

  • Mauro Henrique Mulati UNICAMP / UNICENTRO
  • Flávio Keidi Miyazawa UNICAMP
DOI: https://doi.org/10.5753/etc.2017.3202

Abstract


We deal with the cumulative vehicle routing problem (VRP), a generalization of the capacitated VRP, which objective is to minimize the fuel consumption. Gaur et al. in 2013 gave a 4-approximation based on a well-known partition heuristic to the traveling salesperson problem (TSP). We present a tighter analysis obtaining a (4 - 4/(3s3Q2))-approximation, where Q is the capacity of the vehicle and s is a scaling factor. To the best of our knowledge, this is the best proved approximation for the cumulative VRP so far.

References

Altinkemer, K. and Gavish, B. (1987). Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters, 6(4):149 – 158.

Gaur, D. R., Mudgal, A., and Singh, R. R. (2013). Routing vehicles to minimize fuel consumption. Operations Research Letters, 41(6):576 – 580.

Haimovich, M. and Rinnooy Kan, A. H. G. (1985). Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, 10(4):527–542.

Kara, I., Kara, B. Y., and Yetiş, M. K. (2008). Cumulative Vehicle Routing Problems, pages 85–98. InTech Education and Publishing KG, Vienna, Austria.
Published
2017-07-02
How to Cite

Select a Format
MULATI, Mauro Henrique; MIYAZAWA, Flávio Keidi. Tighter Analysis of an Approximation for the Cumulative VRP. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . p. 100-103. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3202.