Geodesic
Probabilistic analysis of one routing problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 42-53

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

We consider the unit-demand Euclidean vehicle routing problem (VRP), where $n$ customers are modeled as independent identically distributed points on the plane and have unit demand. The Iterated Tour Partitioning heuristic (ITP) for VRP is known. The ITP heuristic is a $2$-approximation algorithm in a general case. But if customers are modeled as i.i.d. points with uniform distribution on the unit square, then it is shown that ITP is a $(2-c)$-approximation algorithm ($c>0$). In the paper, the same result is proved in the case when customers are i.i.d. points with uniform distribution on the circle of the unit area. Ill. 3, bibliogr. 7.
Keywords: vehicle routing problem, approximation algorithm, probabilistic analysis, guarantee approximation ratio. 
@article{DA_2014_21_4_a4,
     author = {A. M. Istomin},
     title = {Probabilistic analysis of one routing problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {42--53},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_4_a4/}
}
TY  - JOUR
AU  - A. M. Istomin
TI  - Probabilistic analysis of one routing problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 42
EP  - 53
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_4_a4/
LA  - ru
ID  - DA_2014_21_4_a4
ER  - 
%0 Journal Article
%A A. M. Istomin
%T Probabilistic analysis of one routing problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 42-53
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_4_a4/
%G ru
%F DA_2014_21_4_a4
A. M. Istomin. Probabilistic analysis of one routing problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 42-53. http://geodesic.mathdoc.fr/item/DA_2014_21_4_a4/