Probabilistic Analysis of Euclidean Capacitated Vehicle Routing
Abstract
We give a probabilistic analysis of the unitdemand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of $n$ unitdemand customers modeled as independent, identically distributed uniform random points in the twodimensional plane. The objective is to visit every customer using a set of routes of minimum total length, such that each route visits at most $k$ customers, where $k$ is the capacity of a vehicle. All of the following results are in the random setting and hold asymptotically almost surely. The best known polynomialtime approximation for this problem is the iterated tour partitioning (ITP) algorithm, introduced in 1985 by Haimovich and Rinnooy Kan. They showed that the ITP algorithm is nearoptimal when $k$ is either $o(\sqrt{n})$ or $\omega(\sqrt{n})$, and they asked whether the ITP algorithm was also effective in the intermediate range. In this work, we show that when $k=\sqrt{n}$, the ITP algorithm is at best a $(1+c_0)$approximation for some positive constant $c_0$. On the other hand, the approximation ratio of the ITP algorithm was known to be at most $0.995+\alpha$ due to Bompadre, Dror, and Orlin, where $\alpha$ is the approximation ratio of an algorithm for the traveling salesman problem. In this work, we improve the upper bound on the approximation ratio of the ITP algorithm to $0.915+\alpha$. Our analysis is based on a new lower bound on the optimal cost for the metric capacitated vehicle routing problem, which may be of independent interest.
 Publication:

arXiv eprints
 Pub Date:
 September 2021
 arXiv:
 arXiv:2109.06958
 Bibcode:
 2021arXiv210906958M
 Keywords:

 Computer Science  Data Structures and Algorithms