Approximability of the d-dimensional euclidean capacitated vehicle routing problem / Khachay M., Dubinin R. // AIP Conference Proceedings. - 2016. - V. 1776, l. .

ISSN:

0094243X

Type:

Conference Paper

Abstract:

Capacitated Vehicle Routing Problem (CVRP) is the well known intractable combinatorial optimization problem, which remains NP-hard even in the Euclidean plane. Since the introduction of this problem in the middle of the 20th century, many researchers were involved into the study of its approximability. Most of the results obtained in this field are based on the well known Iterated Tour Partition heuristic proposed by M. Haimovich and A. Rinnoy Kan in their celebrated paper, where they construct the first Polynomial Time Approximation Scheme (PTAS) for the single depot CVRP in ℝ2. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose a EPTAS for the Euclidean CVRP for any fixed dimension.Grant: This research was supported by Russian Science Foundation, project no. 14-11-00109.

Author keywords:

Index keywords:

нет данных

DOI:

10.1063/1.4965323

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84995404437&doi=10.1063%2f1.4965323&partnerID=40&md5=42213f8081bfe2467e677e25e1382b06

Соавторы в МНС:

—

Другие поля

Поле	Значение
Art. No.	050002
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-84995404437&doi=10.1063%2f1.4965323&partnerID=40&md5=42213f8081bfe2467e677e25e1382b06
Affiliations	Krasovskii Institute of Mathematics and Mechanics, Ekaterinburg, Russian Federation; Ural Federal University, Ekaterinburg, Omsk, Russian Federation; State Technical University, Omsk, Russian Federation
References	Toth, P., Vigo, D., (2001) The Vehicle Routing Problem, , Society for Industrial and Applied Mathematics, Philadelphia, PA, USA; Dantzig, G.B., Ramser, J.H., (1959) Management Science, 6, pp. 80-91; Golden, B., Raghavan, S., Wasil, E.A., The vehicle routing problem : Latest advances and new challenges (2008) Operations Research/Computer Science Interfaces Series, 43. , Springer; Kumar, S., Panneerselvam, R., (2012) Intelligent Information Management, 4, pp. 66-74; Haimovich, M., Rinnooy Kan, A.H.G., (1985) Mathematics of Operations Research, 10, pp. 527-542; Papadimitriou, C., (1997) Theoretical Computer Science, pp. 237-244; Asano, T., Katoh, N., Tamaki, H., Tokuyama, T., (1996) IBM Tokyo Research; Arora, S., (1998) Journal of the ACM, 45; Das, A., Mathieu, C., A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing (2010) Proceedings of the Twenty-first Annual ACM- SIAM Symposium on Discrete Algorithms, SODA '10, pp. 390-403. , Society for Industrial and Applied Mathematics, Philadelphia, PA, USA; Das, A., Mathieu, C., (2015) Algorithmica, 73, pp. 115-142; Khachay, M., Zaytseva, H., (2015) Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings, pp. 178-190. , Springer International Publishing, Cham, Chap. Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem; Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem (1975) Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441; Hubbert, S., Gia, Q.T.L., Morton, T.M., (2015) Spherical Radial Basis Functions, Theory and Applications, p. 150. , 1st ed., SpringerBriefs in Mathematics Springer International Publishing; Gimadi, E.K., Rykov, I.A., (2016) Doklady Mathematics, 93, pp. 117-120; Khachay, M., Neznakhina, K., (2015) Journal of Global Optimization
Correspondence Address	Khachay, M.; Krasovskii Institute of Mathematics and MechanicsRussian Federation; email: mkhachay@imm.uran.ru
Editors	Sergeyev Y.D.Mukhametzhanov M.S.Dell'Accio F.Mukhametzhanov M.S.Kvasov D.E.Sergeyev Y.D.Kvasov D.E.
Sponsors	Department of Computer Engineering, Modeling, Electronics and Systems Science of the University of Calabria;et al.;Institute of High Performance Computing and Networking of the National Research Council;International Association "Friends of the University of Calabria";Italian National Group for Scientific Computation of the National Institute for Advanced Mathematics "F. Severi";University of Calabria
Publisher	American Institute of Physics Inc.
Conference name	2nd International Conference on Numerical Computations: Theory and Algorithms, NUMTA 2016
Conference date	19 June 2016 through 25 June 2016
Conference code	124552
ISBN	9780735414389
Language of Original Document	English
Abbreviated Source Title	AIP Conf. Proc.
Source	Scopus