Volume 21, No 4, 2014, P. 42-53

UDC 519.8
A. M. Istomin
Probabilistic analysis of one routing problem

Abstract:
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.
Bibliogr. 7.

Keywords: vehicle routing problem, approximation algorithm, probabilistic analysis, guarantee approximation ratio.

Istomin Alexey Mikhailovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: alexeyistomin@gmail.com