Approximability of the optimal routing problem in finite-dimensional Euclidean spaces

M. Yu. Khachai   ; R. D. Dubinin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 2, pp. 292-303

Résumé

The capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem with a wide range of applications in operations research. Since the CVRP is NP-hard even in a finite-dimensional Euclidean space, special attention is traditionally paid to the issues of its approximability. A major part of the known results concerning approximation algorithms and polynomial-time approximation schemes (PTAS) for this problem are obtained for its particular instance on the Euclidean plane. In the present paper we show that the approach to the development of a PTAS in the planar problem with a single depot proposed by Haimovich and Rinnooy Kan in 1985 can be effectively applied in a more general case, for example, in spaces of arbitrary fixed dimension and for an arbitrary number of depots.

Détail

Keywords: optimal routing, approximability, EPTAS.
Mots-clés : CVRP

Bibliographie

[1] Arora S., “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, J. ACM, 45:5 (1998), 753–782 | DOI | MR | Zbl

[2] T. Asano, N. Katoh, H. Tamaki, T. Tokuyama, “Covering points in the plane by $k$-tours: a polynomial approximation scheme for fixed $k$”, IBM Tokyo Research Laboratory Research, Tokyo, 1996, Report RT0162

[3] S. Cardon, S. Dommers, C. Eksin, R. Sitters, A. Stougie, L. Stougie, “A PTAS for the multiple depot vehicle routing problem”, Tech. Rep. No. 2008.03, Eindhoven Univ. of Technology, Eindhoven, 10

[4] Christofides N., “Worst-case analysis of a new heuristic for the traveling salesman problem”, Symposium on New Directions and Recent Results in Algorithms and Complexity, Academic Press, N. Y., 1975, 441

[5] Dantzig G., Ramser J., “The truck dispatching problem”, Management Science, 6:1 (1959), 80–91 | DOI | MR | Zbl

[6] Das A., Mathieu C., “A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing”, Algorithmica, 73:1 (2015), 115–142 | DOI | MR | Zbl

[7] Gimadi E.K., Rykov I.A., “On the asymptotic optimality of a solution of the euclidean problem of covering a graph by $m$ nonadjacent cycles of maximum total weight”, Dokl. Math., 93:1 (2016), 117–120 | DOI

[8] Haimovich M., Rinnooy Kan A.H.G., “Bounds and heuristics for capacitated routing problems”, Math. Oper. Res., 10:4 (1985), 527–542 | DOI | MR | Zbl

[9] Hubbert S., Gia Q.T.L., Morton T.M., Spherical radial basis functions. Theory and Applications, SpringerBriefs in Mathematics, Springer, Cham, 2015, 150 pp. | DOI | MR | Zbl

[10] Khachay M., Neznakhina K., “Approximability of the minimum-weight $k$-size cycle cover problem”, J. Global Optim., 2015 | DOI

[11] Khachay M., Zaytseva H., “Time approximation scheme for single-depot Euclidean capacitated vehicle routing problem”, Combinatorial Optimization and Applications, 9th Internat. Conf. (COCOA 2015): Proceedings, Lecture Notes in Computer Science, Springer, Cham, 2015, 178–190 | DOI | Zbl

[12] Kumar S., Panneerselvam R., “A survey on the vehicle routing problem and its variants”, Intel. Inform. Management, 4:3 (2012), 66–74

[13] Papadimitriou C., “Euclidean TSP is $NP$-complete”, Theor. Comput. Sci., 1977, no. 4, 237–244 | DOI | MR | Zbl

[14] Song L., Huang H., Du H., “Approximation schemes for Euclidean vehicle routing problems with time windows”, J. Comb. Optim., 2015 | DOI

[15] Toth P., Vigo D., The vehicle routing problem, Discrete Math. and Appl., eds. P. Toth, D. Vigo, Society for Indust. and Appl. Math., Philadelphia, 2001, 363 pp. | MR