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(√n) or ω(√n), and they asked whether the ITP algorithm was "also effective in the intermediate range". In this work, we show that when k = √n, the ITP algorithm is at best a (1+c₀)approximation for some positive constant c₀.
On the other hand, the approximation ratio of the ITP algorithm was known to be at most 0.995+α due to Bompadre, Dror, and Orlin, where α 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+α. 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.
BibTeX  Entry
@InProceedings{mathieu_et_al:LIPIcs.ISAAC.2021.43,
author = {Mathieu, Claire and Zhou, Hang},
title = {{Probabilistic Analysis of Euclidean Capacitated Vehicle Routing}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {43:143:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15476},
URN = {urn:nbn:de:0030drops154769},
doi = {10.4230/LIPIcs.ISAAC.2021.43},
annote = {Keywords: capacitated vehicle routing, iterated tour partitioning, probabilistic analysis, approximation algorithms}
}
Keywords: 

capacitated vehicle routing, iterated tour partitioning, probabilistic analysis, approximation algorithms 
Collection: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021) 
Issue Date: 

2021 
Date of publication: 

30.11.2021 