Geodesic
Approximability of the optimal routing problem in finite-dimensional Euclidean spaces
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 2, pp. 292-303

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: optimal routing, approximability, EPTAS.
Mots-clés : CVRP 
@article{TIMM_2016_22_2_a30,
     author = {M. Yu. Khachai and R. D. Dubinin},
     title = {Approximability of the optimal routing problem in finite-dimensional {Euclidean} spaces},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {292--303},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_2_a30/}
}
TY  - JOUR
AU  - M. Yu. Khachai
AU  - R. D. Dubinin
TI  - Approximability of the optimal routing problem in finite-dimensional Euclidean spaces
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 292
EP  - 303
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_2_a30/
LA  - ru
ID  - TIMM_2016_22_2_a30
ER  - 
%0 Journal Article
%A M. Yu. Khachai
%A R. D. Dubinin
%T Approximability of the optimal routing problem in finite-dimensional Euclidean spaces
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 292-303
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_2_a30/
%G ru
%F TIMM_2016_22_2_a30
M. Yu. Khachai; R. D. Dubinin. Approximability of the optimal routing problem in finite-dimensional Euclidean spaces. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 2, pp. 292-303. http://geodesic.mathdoc.fr/item/TIMM_2016_22_2_a30/