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/

[1] Gimadi E. Kh., Glebov N. I., Serdyukov A. I., “Ob odnoi zadache vybora tsiklicheskogo marshruta i zagruzki transportnogo sredstva”, Diskret. analiz i issled. operatsii. Ser. 2, 5:1 (1998), 12–18 | MR | Zbl

[2] Gimadi E. Kh., Istomin A. M., Rykov I. A., “O zadache neskolkikh kommivoyazhërov s ogranicheniyami na propusknye sposobnosti rëber grafa”, Diskret. analiz i issled. operatsii, 20:5 (2013), 13–30 | MR

[3] Gimadi E. Kh., Shakhshneider A. V., “Priblizhënnye algoritmy s otsenkami dlya zadach marshrutizatsii na sluchainykh vkhodakh s ogranichennym chislom klientov v kazhdom marshrute”, Avtomatika i telemekhanika, 2012, no. 2, 126–140 | MR

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

[5] Beardwood J., Halton J. L., Hammersley J. M., “The shortest path through many points”, Proc. Camb. Phil. Soc., 55 (1959), 299–327 | DOI | MR | Zbl

[6] Bompadre A., Dror M., Orlin J. B., “Probabilistic analysis of unit-demand vehicle routeing problems”, J. Appl. Prob., 44 (2007), 259–278 | DOI | MR | Zbl

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