Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

DOI10.4230/LIPICS.ISAAC.2021.43MaRDI QIDQ6147550zbMATH OpenOpenAlexFDO

Authors Claire Mathieu, Hang Zhou

Publication date 15 January 2024

Full work available at URL https://arxiv.org/abs/2109.06958

zbMATH Keywords

approximation algorithmscapacitated vehicle routingiterated tour partitioningprobabilistic analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We give a probabilistic analysis of the unit-demand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of $n$ unit-demand customers modeled as independent, identically distributed uniform random points in the two-dimensional 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 polynomial-time 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 near-optimal when $k$ is either $o(sqrtn)$ or $omega(sqrtn)$, and they asked whether the ITP algorithm was also effective in the intermediate range. In this work, we show that when $k=sqrtn$, 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.

Cited in

(2)

• Improved approximations for the capacitated vehicle routing problem with fixed capacity
• Improved approximation algorithms for capacitated vehicle routing with fixed capacity

This page was built for publication: Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6147550)