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

Resumo

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/(3s³Q²))-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.

Referências

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.