Probabilistic analysis of one routing problem

A. M. Istomin<sup>ab

a</sup> Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
^b S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

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. Ill. 3, bibliogr. 7.

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

UDC: 519.8

Received: 13.12.2011
Revised: 13.02.2014

Bibliographic databases:

•