Volume 21, No 4, 2014, P. 4253
UDC 519.8
A. M. Istomin
Probabilistic analysis of one routing problem
Abstract:
We consider the unitdemand 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 2approximation 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
email: alexeyistomin@gmail.com
