|
Diskretnyi Analiz i Issledovanie Operatsii, 2014, Volume 21, Issue 4, Pages 42–53
(Mi da784)
|
|
|
|
Probabilistic analysis of one routing problem
A. M. Istominab a 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.
Received: 13.12.2011 Revised: 13.02.2014
Citation:
A. M. Istomin, “Probabilistic analysis of one routing problem”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 42–53
Linking options:
https://www.mathnet.ru/eng/da784 https://www.mathnet.ru/eng/da/v21/i4/p42
|
|