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
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.
vehicle routing problem, approximation algorithm, probabilistic analysis, guarantee approximation ratio.
PDF file (305 kB)
A. M. Istomin, “Probabilistic analysis of one routing problem”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 42–53
Citation in format AMSBIB
\paper Probabilistic analysis of one routing problem
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|