# Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Claire Mathieu, Hang Zhou

<figure><img src="image_1.png" /></figure>

► To cite this version:

Claire Mathieu, Hang Zhou. Probabilistic Analysis of Euclidean Capacitated Vehicle Routing. 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Nov 2021, Fukuoka, Japan. 10.4230/LIPIcs.ISAAC.2021.43 . hal-04482968

HAL Id: hal-04482968

https://hal.science/hal-04482968v1

Submitted on 28 Feb 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Claire Mathieu

<figure><img src="image_3.png" /></figure>

CNRS, IRIF, Université de Paris, France

Hang Zhou

<figure><img src="image_4.png" /></figure>

École Polytechnique, Institut Polytechnique de Paris, France

## 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 [15]. They showed that the ITP algorithm is near-optimal 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 [10], 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.

**2012 ACM Subject Classification** Theory of computation → Approximation algorithms analysis

**Keywords and phrases** capacitated vehicle routing, iterated tour partitioning, probabilistic analysis, approximation algorithms

**Digital Object Identifier** 10.4230/LIPIcs.ISAAC.2021.43

**Related Version** Full Version: http://arxiv.org/abs/2109.06958

**Funding** This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

## 1 Introduction

**Unit-Demand Euclidean CVRP.** In the capacitated vehicle routing problem (CVRP), we are given a set of $n$ customers and a depot. There is an unlimited number of identical vehicles, each of an integer capacity $k$. The route of a vehicle starts at the depot and returns there after visiting at most $k$ customers. The objective is to visit every customer, using a set of routes of minimum total length. Vehicle routing is a basic type of problems in operations research, and several books (see [3, 11, 14, 25] among others) have been written on those problems. We study the unit-demand Euclidean version of the problem, in which each customer has unit demand, all locations (the customers and the depot) lie in the two-dimensional plane, and distances are given by the Euclidean metric. The unit-demand Euclidean CVRP is a generalization of the Euclidean traveling salesman problem and is known to be NP-hard for all $k \ge 3$ (see [5]). Unless explicitly mentioned, all CVRP instances in this paper are assumed to be unit-demand Euclidean.

<figure><img src="image_5.png" /></figure>

© Claire Mathieu and Hang Zhou;
licensed under Creative Commons License CC-BY 4.0

32nd International Symposium on Algorithms and Computation (ISAAC 2021).

Editors: Hee-Kap Ahn and Kunihiko Sadakane; Article No. 43; pp. 43:1–43:16

Leibniz International Proceedings in Informatics

<figure><img src="image_6.png" /></figure>

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
43:2 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

**ITP Algorithm.** The best known polynomial-time approximation for the CVRP is a very simple algorithm, called *iterated tour partitioning (ITP)*. This algorithm first computes a traveling salesman tour (ignoring the capacity constraint) using some other algorithm, then partitions the tour into segments such that the number of customers in each segment is at most *k*, and finally connects the endpoints of each segment to the depot so as to make a tour. The ITP algorithm was introduced and refined by Haimovich and Rinnooy Kan [15] and Altinkemer and Gavish [2] in the 1980s. Its performance is parameterized by the choice of traveling salesman tour : the approximation ratio of the ITP algorithm is $1 + \alpha$, where $\alpha$ is the approximation ratio of the algorithm used to compute the traveling salesman tour in the first step. Since the Euclidean traveling salesman problem admits a *polynomial-time approximation scheme (PTAS)* by Arora [4] and Mitchell [20], $\alpha$ can be set to any constant strictly greater than 1.

**Random Setting.** Given the difficult challenges posed by the CVRP, researchers turned to an analysis beyond worst case, by making some probabilistic assumptions on the distribution of the input instance. In 1985, Haimovich and Rinnooy Kan [15] gave the first probabilistic analysis on the ITP algorithm for the CVRP, where the customers are *independent, identically distributed (i.i.d.)* random points. An event $\mathcal{E}$ occurs *asymptotically almost surely* (a.a.s.) if $\lim_{n\to\infty} \mathbb{P}[\mathcal{E}] = 1$. They showed that, the ITP algorithm is a.a.s. an $(\alpha + o(1))$-approximation for the CVRP when $k$ is either $o(\sqrt{n})$ or $\omega(\sqrt{n})$.<fnref n="1" /> The performance of the ITP algorithm in the intermediate range of $k = \Theta(\sqrt{n})$ was unknown. They asked in [15] whether the ITP algorithm was “also effective in the intermediate range”.

In our work, we study this question raised by Haimovich and Rinnooy Kan [15]. We give a probabilistic analysis of the ITP algorithm when the points are i.i.d. random, with a focus on the range of $k = \Theta(\sqrt{n})$. Our first main result is a lower bound: even in the random setting, the ITP algorithm is at best a $(1+c_0)$-approximation a.a.s., for some constant $c_0 > 0$ (Theorem 1), see Section 3.

**► Theorem 1.** *Consider the iterated tour partitioning algorithm for the unit-demand Euclidean capacitated vehicle routing problem. Let $V$ be a set of $n$ i.i.d. uniform random points in $[0, 1]^2$. Let $k = \sqrt{n}$. For some fixed depot $O \in \mathbb{R}^2$, there exists a constant $c_0 > 0$, such that, for any constant $\alpha > 1$, there exists an $\alpha$-approximate traveling salesman tour on $V \cup \{O\}$, such that the approximation ratio of the algorithm is at least $1 + c_0$ asymptotically almost surely.*

**► Remark.** The $\alpha$-approximate traveling salesman tour in Theorem 1 is constructed using Karp's partitioning algorithm [16].

On the other hand, the approximation ratio of the ITP algorithm is at most $1 + \alpha$ due to Altinkemer and Gavish [2]. In 2007, this ratio was improved by Bompadre, Dror, and Orlin [10] to $0.995 + \alpha$, a.a.s., when the points are i.i.d. uniform random in the unit square.<fnref n="2" /> Here, using a different approach (Theorem 4), we further improve the upper bound on the approximation ratio in this random setting to $0.915 + \alpha$, a.a.s. (Theorem 2), see Section 4. We generalize our results to multiple depots in the full version of the paper.

<footnote n="1">¹ As observed in [15], a solution of the ITP algorithm consists of two types of costs: the *radial cost* and the *local cost*. When $k$ is $o(\sqrt{n})$ or $\omega(\sqrt{n})$, one of the two types dominates, the reason for which the solution is an $(\alpha + o(1))$-approximation (or even a $(1 + o(1))$-approximation for the case of $k = o(\sqrt{n})$).</footnote>

<footnote n="2">² The analysis in [10] focused on the case of $\alpha = 1$, though that analysis can be easily generalized to any $\alpha \ge 1$. Bompadre, Dror, and Orlin [10] noted in their work that a ratio of $0.985 + \alpha$ is achievable without giving the proof.</footnote>
**► Theorem 2.** *Consider the iterated tour partitioning algorithm for the unit-demand Euclidean capacitated vehicle routing problem. Let V be a set of n i.i.d. uniform random points in $[0, 1]^2$. Let k be any integer in $[1, n]$. Let the depot O be any point in $\mathbb{R}^2$. For any constant $\alpha \ge 1$ and any $\alpha$-approximate traveling salesman tour on $V \cup \{O\}$, the approximation ratio of the algorithm is at most $0.915 + \alpha$ asymptotically almost surely.*

## 1.1 Other Related Work

**PTAS and Quasi-PTAS Results for the CVRP.** Despite the difficulty of the CVRP, there has been progress on several special cases. A series of papers designed PTAS algorithms for small $k$: work by Haimovich and Rinnooy Kan [15], when $k$ is constant; by Asano et al. [5] extending techniques in [15], for $k = O(\log n / \log \log n)$; and by Adamaszek, Czumaj, and Lingas [1], when $k \le 2^{\log_f(\epsilon)(n)}$. For higher dimensional Euclidean metrics, Khachay and Dubinin [17] gave a PTAS for fixed dimension $\ell$ and $k = O(\log^{\frac{1}{\ell}}(n))$. For unbounded $k$, Das and Mathieu [13] designed a quasi-polynomial time approximation scheme.

**Probabilistic Analyses.** The instance distribution when the customers are i.i.d. random points is perhaps the most natural probabilistic setting. In that setting, Rhee [23] and Daganzo [12] analyzed the value of an optimal solution to the CVRP for the case when $k$ is fixed. Baltz et al [6] studied the multiple depot vehicle routing problem when both the customers and the depots are i.i.d. random points and assuming unlimited tour capacity.

**Analyses of the ITP Algorithm.** Because of the popularity of the ITP algorithm, its approximation ratio has already been much studied and bounds were utilized in a design of best-to-date approximation algorithms for the CVRP, see, e.g., [9]. In the metric version of the CVRP, the approximation ratio of the ITP algorithm is at most $1 + (1 - \frac{1}{k})\alpha$ due to Altinkemer and Gavish [2]. Bompadre, Dror, and Orlin [9] reduced this bound by a factor of $\Omega(\frac{1}{k^3})$. On the other hand, Li and Simchi-Levi [18] showed that the ITP algorithm is at best a $(2 - \frac{1}{k})$-approximation algorithm on general metrics even if $\alpha = 1$. Despite a huge amount of research, the ITP algorithm by Haimovich and Rinnooy Kan [15] and Altinkemer and Gavish [2] remains the polynomial-time algorithm with the best approximation guarantee for the Euclidean CVRP.

**Other Applications of the ITP Algorithm.** Very recently, Blauth, Traub, and Vygen [8] exploited properties of tight instances in the analysis of the ITP algorithm, and used those properties in their design of the best-to-date approximation algorithm for metric CVRP with a ratio of $1 + \alpha - \epsilon$, where $\epsilon$ is roughly $\frac{1}{3000}$.

Because of its simplicity, the ITP algorithm is versatile and has been adapted to other vehicle routing problems. For example, Mosheiov [21] studied the vehicle routing with pick-up and delivery services. They showed that the ITP algorithm is efficient through worst-case analysis and numerical tests. Li, Simchi-Levi, and Desrochers [19] considered the vehicle routing problem with constraints on the total distance traveled by each vehicle. They showed that the ITP algorithm has a good worst-case performance when the number of vehicles is relatively small.

## 1.2 Overview of Techniques

To show that the ITP algorithm is at best a $(1 + c_0)$-approximation for the CVRP in the random setting (Theorem 1), we construct a significantly better solution.
43:4 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

In the random setting, one may view an ITP solution as partitioning the unit square into
small regions and dedicating one tour to each small region. The cost of the solution is then
roughly the sum of two terms: the radial cost, incurred by traveling between the depot and
the small region; and the local cost, incurred by traveling from customer to customer within
the small region.

To improve that solution, the idea is that instead of traveling straight between the depot and the small region, a smarter tour might as well make some small detours to visit some additional nearby customers en route to the small region. We call that a mixed tour. This modification of the solution has a positive effect because those nearby customers are covered at little additional cost, thus saving the local cost of covering those customers; but it also has a negative effect because visiting those nearby customers uses up some of the tour's capacity, and to account for that the definition of the small regions must be adjusted, and their area shrunk. Controlling the two competing effects so that on balance the net result is an improvement requires a delicate definition of regions. We start by decomposing the plane into regions of three types. Then we construct a solution in which a single tour may visit regions of different types, see Figure 1. The mixed structure of the tours enables us to show that the constructed solution has significantly smaller cost. See Section 3 for more details.

Our proof of the improved upper bound on the approximation ratio of the ITP algorithm in
the random setting (Theorem 2) relies on a new lower bound on the optimal cost (Theorem 11).
To achieve the new lower bound, we consider the gap between the average distance to the
depot and the maximum distance to the depot among all points in a single tour of an optimal
solution. Intuitively, if this gap is large, then the gap itself contributes to the lower bound on
the optimal cost; and if this gap is small, then there are many points whose distances to the
depot is close to the maximum distance, and the total local cost of those points contributes
to the lower bound. Our analysis for the lower bound is completely different from [10] and
enables us to obtain a better approximation ratio of 0.915 + $\alpha$.

Our new lower bound on the optimal cost also enables us to generalize our results to the
setting of multiple depots. This lower bound holds in the metric CVRP in general, and may
be of independent interest.

► **Remark.** The restriction to i.i.d. uniform random points in $[0, 1]^2$ is made to simplify the presentation. With extra work, our analysis can be extended to higher dimensional Euclidean spaces, to general density functions, and to general bounded supports (though the approximation guarantees in those settings may differ from that in Theorem 2).

2 Notations and Preliminaries

Let $\delta(\cdot, \cdot)$ denote the Euclidean distance between two points or between a point and a set of points. For any path $P$ of points $x_1, x_2, \dots, x_m$ in $\mathbb{R}^2$ where $m \in \mathbb{N}$, define cost($P$) = $\sum_{i=1}^{m-1} \delta(x_i, x_{i+1})$.

**Capacitated Vehicle Routing Problem (CVRP).** Given a set $V$ of $n$ points in $\mathbb{R}^2$, a depot $O$ in $\mathbb{R}^2$, and an integer capacity $k \in [1, n]$, the goal is to find a collection of tours covering $V$ of minimum total cost, such that each tour visits $O$ and at most $k$ points in $V$. Let OPT denote the value of an optimal solution to the CVRP.

For any point $x \in V$, let $\ell(x) = \delta(O, x)$. Let rad denote the radial cost, defined by
$$ \text{rad} = \frac{2}{k} \cdot \sum_{x \in V} \ell(x). $$

**► Lemma 3** ([15]). Let $T^*$ be an optimal traveling salesman tour on $V \cup \{O\}$. Then
OPT $\ge \max(\text{rad}, \text{cost}(T^*))$.
**Iterated Tour Partitioning (ITP).** We review the iterated tour partitioning (ITP) algorithm defined by Altinkemer and Gavish [2]. The ITP algorithm consists of a preprocessing phase and a main phase. In the preprocessing phase, it runs an approximation algorithm for the traveling salesman problem on $V \cup \{O\}$. Let $\alpha$ denote the approximation ratio of this algorithm. Let $T = (O, x_1, x_2, \dots, x_n, O)$ denote the resulting traveling salesman tour. In the main phase, the ITP algorithm selects the best of the $k$ solutions constructed as follows. For each $i \in [1, k]$, let $n_i = \lceil (n - i)/k \rceil + 1$ and define a solution $S_i$ to the CVRP to be the union of the $n_i$ tours $(O, x_1, \dots, x_i, O), (O, x_{i+1}, \dots, x_{i+k}, O), (O, x_{i+k+1}, \dots, x_{i+2k}, O), \dots, (O, x_{i+(n_i-2)k+1}, \dots, x_n, O)$. In other words, the solution $S_i$ partitions the traveling salesman tour $T$ into segments with $k$ points each, except possibly the first and the last segments. The output of the ITP algorithm is a solution among $S_1, \dots, S_k$ that achieves the minimum cost. It is easy to see that the main phase of the ITP algorithm can be carried out in $O(nk)$ time.<fnref n="3" />

Let ITP($T$) denote the cost of the output solution. The following classic bound on ITP($T$) was due to Altinkemer and Gavish [2] and, together with Lemma 3, immediately implies that the ITP algorithm is a $(1 + \alpha)$-approximation, where $\alpha$ is the approximation ratio of the traveling salesman tour $T$.

**Lemma 4 ([2]).** Let $T$ be any traveling salesman tour on $V \cup \{O\}$. Then

$$OPT \le ITP(T) \le \text{rad} + \left(1 - \frac{1}{k}\right) \cdot \text{cost}(T).$$

**Probabilistic Analysis of the Traveling Salesman Problem.** Beardwood, Halton, and Hammersley [7] analyzed the value of an optimal solution to the traveling salesman problem in the random setting.

**Lemma 5 ([7, 24]).** Let $V$ be a set of $n$ i.i.d. uniform random points with bounded support in $\mathbb{R}^2$. Let $M$ denote the measure of the support. Let $T^*$ denote an optimal traveling salesman tour on $V$. Then there exists a universal constant $\beta$ such that, for any $\epsilon > 0$, we have

$$\lim_{n \to \infty} \frac{\text{cost}(T^*)}{\sqrt{M \cdot n}} = \beta, \quad \text{with probability 1.}$$

In addition, $\beta_0 < \beta < \beta_1$, where $\beta_0 = 0.62866$ and $\beta_1 = 0.92117$.

**Remark.** Up to scaling, Lemma 5 holds for any support that is a rectangle with constant aspect ratio.

### 3 Lower Bound on the Approximation Ratio

In this section, we prove Theorem 1 by providing a lower bound on the approximation ratio ITP($T$)/OPT of the ITP algorithm, where $T$ is a traveling salesman tour. Let the depot $O = (\frac{1}{2}, -1000)$. Lemmas 6 and 7 are the key ingredients in the proof of Theorem 1.

**Lemma 6.** Let $\beta$ be defined as in Lemma 5. Then there exists a constant $c_1 \in (0, \beta)$ such that for any $\epsilon_1 > 0$, $OPT < (1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - c_1\sqrt{n}$, a.a.s.

**Lemma 7.** Let $\beta$ be defined as in Lemma 5. Then for any $\alpha > 1$, there exists an $\alpha$-approximate traveling salesman tour $T$ on $V \cup \{O\}$, such that for any $\epsilon_1 > 0$, ITP($T$) > $(1 - \epsilon_1)(\text{rad} + \beta\sqrt{n})$, a.a.s.

<footnote n="3">³ The running time of the main phase can even be improved to $O(n)$.</footnote>
43:6 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Lemma 6 contains main novelties in this section. The proof of Lemma 7 is in the full version of the paper. First, we show how Lemmas 6 and 7 imply Theorem 1.

**Proof of Theorem 1 using Lemmas 6 and 7.** Let $\epsilon_1 > 0$ be a constant to be set later. From Lemma 6, there exists an absolute constant $c_1 \in (0, \beta)$, such that $\text{OPT} < (1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - c_1\sqrt{n}$, a.a.s. From Lemma 7, for any $\alpha > 1$, there exists an $\alpha$-approximate traveling salesman tour $T$ on $V \cup \{O\}$, such that $\text{ITP}(T) > (1 - \epsilon_1)(\text{rad} + \beta\sqrt{n})$, a.a.s. Hence

$$ \frac{\text{ITP}(T)}{\text{OPT}} > \frac{(1 - \epsilon_1)(\text{rad} + \beta\sqrt{n})}{(1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - c_1\sqrt{n}}, \quad \text{a.a.s.} $$

To analyze rad, let $L$ be the expectation of $\ell(x)$ for $x \in [0, 1]^2$ with uniform distribution. Since the depot $O$ is at a constant distance from $[0, 1]^2$, $L$ is a constant. By the law of large numbers,

$$ \left| \frac{1}{n} \sum_{x \in V} \ell(x) - L \right| < \epsilon_1, \quad \text{a.a.s.} $$

Recall that $\text{rad} = \frac{2}{\sqrt{n}} \sum_{x \in V} \ell(x)$. Hence $(L - \epsilon_1) \cdot 2\sqrt{n} < \text{rad} < (L + \epsilon_1) \cdot 2\sqrt{n}$, a.a.s. Denoting the function $f$ as

$$ f(\epsilon_1) = \frac{(1 - \epsilon_1)(2L - 2\epsilon_1 + \beta)}{(1 + \epsilon_1)(2L + 2\epsilon_1 + \beta) - c_1}, $$

we have

$$ \frac{\text{ITP}(T)}{\text{OPT}} > f(\epsilon_1), \quad \text{a.a.s.} $$

Since $L$, $\beta$ and $c_1$ are positive constants and $c_1 < \beta$ (Lemma 6), we have

$$ \lim_{\epsilon_1 \to 0} f(\epsilon_1) = 1 + \frac{c_1}{2L + \beta - c_1}. $$

Let $c_0 = \frac{1}{2} \cdot \frac{c_1}{2L + \beta - c_1}$, which is a positive constant. Choosing $\epsilon_1$ small enough such that $f(\epsilon_1) > 1 + c_0$, we have

$$ \frac{\text{ITP}(T)}{\text{OPT}} > f(\epsilon_1) > 1 + c_0, \quad \text{a.a.s.} $$

The claim follows.

<figure><img src="image_7.png" /></figure>

The rest of the section is dedicated to prove Lemma 6.

Without loss of generality, we assume that $\epsilon_1 \le 1$, since otherwise it suffices to prove the claim for the case of $\epsilon_1 = 1$. We construct a solution to the CVRP whose cost is less than $(1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - c_1\sqrt{n}$, a.a.s., where the constant $c_1 > 0$ will be chosen at the end of the proof.

## 3.1 Decomposition of the Plane

In order to construct a solution to the CVRP, we describe a decomposition of $[0, 1]^2$ into rectangles of three types. Let $\epsilon_2 = \frac{\epsilon_1}{10}$. We partition$^4$ $[0, 1]^2$ into a lower part $[0, 1] \times [0, \frac{3+\epsilon_2}{4}]$ which is a rectangle of type III, and a collection of boxes of the form $[(i-1)D, iD] \times [\frac{3+\epsilon_2}{4}, 1]$, with $D = n^{-1/4}$ and $1 \le i \le 1/D$. For simplicity, assume that $1/D$ is an integer. See Figure 1a.

<footnote>$^4$ The decomposition is a partition except for the boundaries, that have measure 0.</footnote>
Next, we decompose each box, see Figure 1b. Let $m = \frac{5}{40-\beta} \cdot n^{1/4}$. For simplicity, assume that $m$ is an integer. The upper half of a box is partitioned into $m$ type I rectangles of the form $[(i-1)D, iD] \times [1-(j-1)H, 1-jH]$, where $H = \frac{1-\epsilon_2}{8m}$ and $1 \le j \le m$. The lower left part of a box is partitioned into $2m$ slices such that each slice is a type II rectangles of the form $[(i-1)D + (j-1)W, (i-1)D + jW] \times [\frac{3+\epsilon_2}{4}, \frac{7+\epsilon_2}{8}]$, with $W = \frac{\beta}{10} \cdot n^{-1/2}$ and $1 \le j \le 2m$. The rest of the box is a single type III rectangle.

For any rectangle $R$ in the resulting decomposition, let $n_R$ denote the number of points of $V$ that are in the rectangle $R$, and let $M_R$ denote the measure of the rectangle $R$. The following fact relates $n_R$ with $M_R$.

**Fact 8.** A.a.s. the following event $\mathcal{E}$ occurs: $(1 - \epsilon_2) \cdot M_R \cdot n < n_R < (1 + \epsilon_2) \cdot M_R \cdot n$ for all rectangles $R$ in the resulting decomposition.

**Proof.** Let $R$ be any rectangle in the resulting decomposition. Observe that $M_R = \Omega(1/\sqrt{n})$. The expectation of $n_R$ is $M_R \cdot n = \Omega(\sqrt{n})$. By Chernoff bound,

$$ \mathbb{P}[n_R \le (1 - \epsilon_2)M_R \cdot n] \le e^{-\Omega(\sqrt{n})} \quad \text{and} \quad \mathbb{P}[n_R \ge (1 + \epsilon_2)M_R \cdot n] \le e^{-\Omega(\sqrt{n})}. $$

Since there are $\Theta(\sqrt{n})$ rectangles in the decomposition, the event $\mathcal{E}$ occurs with probability at least $1 - \Theta(\sqrt{n}) \cdot e^{-\Omega(\sqrt{n})} = 1 - o(1)$. ◀

From now on, we condition on the occurrence of $\mathcal{E}$ in Fact 8.

## 3.2 Construction of a Solution

To construct a relative cheap solution, the main observation is that it is profitable for a tour to visit points in rectangles of both types I and II. In each box, there are $m$ rectangles of type I and $2m$ rectangles of type II. We form $m$ groups with those, such that each group contains one rectangle of type I and two rectangles of type II. For each group, we cover the points in the group by a particular tour on these points in addition to the depot $O$, in a way to be described shortly. For all points in the rectangles of type III, we construct an optimal solution to the CVRP on those points with depot $O$ and with capacity $\sqrt{n}$.

A mixed tour is a tour covering points in rectangles of types I and II. Consider a box $\mathcal{B}$ and a group in $\mathcal{B}$ consisting of a rectangle $A$ of type I and two rectangles $B_1$ and $B_2$ of type II. We construct a specific mixed tour $T_{\text{mix}}$ defined as follows.

Let $P_1$ denote the bottom left corner of the rectangle $A$. Let $T_0$ denote an optimal traveling salesman tour on the points in $A \cup \{P_1\}$. For each $i \in \{1, 2\}$, we define an $O$-to-$P_1$ path $T_i$ visiting the points in $B_i$ as follows. Let $S_i$ and $Q_i$ denote the top left and bottom left corners of the rectangle $B_i$. Let $T_i$ denote the concatenation of the segment $OQ_i$, a $Q_i$-to-$S_i$ path visiting the points in $B_i$ in non-decreasing order on the $y$-coordinate (breaking ties arbitrarily), and the segment $S_i P_1$. Finally, the tour $T_{\text{mix}}$ is defined as the concatenation of $T_0$, $T_1$, and $T_2$. See Figure 1c. This completes our construction.

Since the measure of $A$ is $D \cdot H$ and the measure of $B_i$ (for each $i \in \{1, 2\}$) is $\frac{1-\epsilon_2}{8} \cdot W$, Event $\mathcal{E}$ implies that the total number of points in $A \cup B_1 \cup B_2$ is at most

$$ (1 + \epsilon_2) \left( D \cdot H + 2 \cdot \frac{1 - \epsilon_2}{8} \cdot W \right) \cdot n = (1 + \epsilon_2)(1 - \epsilon_2) n^{-1/2} \cdot n < \sqrt{n}, $$

so the constructed solution is feasible.
<figure><img src="image_8.png" /><figcaption>■ **Figure 1** Decomposition and tour construction. Figure 1a illustrates the decomposition of $[0, 1]^2$. The highlighted area in Figure 1a represents a box. Figure 1b illustrates the decomposition of a box into rectangles of types I, II, and III. Figure 1c describes a tour covering points in one rectangle A of type I and in two rectangles $B_i$, for $i \in \{1, 2\}$, of type II.</figcaption></figure>

### 3.3 Cost of a Mixed Tour

Consider any mixed tour $T_{\text{mix}}$. We follow the same notations as in Section 3.2. From the construction,

$$ \text{cost}(T_{\text{mix}}) = \text{cost}(T_0) + \text{cost}(T_1) + \text{cost}(T_2). \qquad (1) $$

Let $T_A^*$ denote an optimal traveling salesman tour on the points in A. The cost of $T_0$ is at most $\text{cost}(T_A^*)$ plus the cost of the detour to include the point $P_1$. The cost of the detour is less than $2(D + H)$, so

$$ \text{cost}(T_0) < \text{cost}(T_A^*) + 2(D + H). \qquad (2) $$

Let $n_1$ and $n_2$ denote the number of points of V that are in $B_1$ and $B_2$, respectively. The costs of $T_1$ and $T_2$ are bounded by the following fact, whose proof is in the full version of the paper.

► **Fact 9.** For $i \in \{1, 2\}$, we have

$$ \text{cost}(T_i) < \delta(O, P_1) + \frac{1}{4000} + n_i W + (W + 2D). \qquad (3) $$
From Equations (1)–(3), and using the definition of W, we have

$$ \text{cost}(T_{\text{mix}}) < \text{cost}(T_A^*) + 2\delta(O, P_1) + \frac{1}{2000} + \frac{\beta}{10} \cdot \frac{n_1 + n_2}{\sqrt{n}} + (2W + 6D + 2H). \quad (4) $$

It remains to bound $\delta(O, P_1)$. Observe that by the definition of $\ell(\cdot)$ and the triangle inequality, and since the height of a box $\mathcal{B}$ is less than $\frac{1}{4}$,

$$ \delta(O, P_1) < \begin{cases} \ell(x) + D + H & \text{for any } x \in A, \\ \ell(x) + \frac{1}{4} + D + H & \text{for any } x \in B_1 \cup B_2. \end{cases} $$

Let $V_{\text{mix}}$ denote the set of the points of $V$ in $A \cup B_1 \cup B_2$. By averaging we have

$$ \delta(O, P_1) < \frac{1}{|V_{\text{mix}}|} \left( \sum_{x \in V_{\text{mix}}} \ell(x) \right) + \frac{1}{|V_{\text{mix}}|} \frac{n_1 + n_2}{4} + (D + H). $$

Since the measure of $A \cup B_1 \cup B_2$ is $(1 - \epsilon_2)n^{-1/2}$, Event $\mathcal{E}$ implies that $|V_{\text{mix}}| > (1 - \epsilon_2)^2 \cdot \sqrt{n}$, which is at least $\frac{\sqrt{n}}{1+\epsilon_1}$ since $\epsilon_2 = \frac{\epsilon_1}{10}$. Hence

$$ \delta(O, P_1) < \frac{1 + \epsilon_1}{\sqrt{n}} \left[ \left( \sum_{x \in V_{\text{mix}}} \ell(x) \right) + \frac{n_1 + n_2}{4} \right] + (D + H). \quad (5) $$

Since $n_1 + n_2 = \Theta(\sqrt{n})$, we have $(2W + 6D + 2H) + 2(D + H) < \frac{\epsilon_1}{\sqrt{n}} \cdot \frac{\beta}{10} \cdot (n_1 + n_2)$ when $n$ is large enough. From Equations (4) and (5), we conclude that

$$ \text{cost}(T_{\text{mix}}) < \text{cost}(T_A^*) + \frac{1 + \epsilon_1}{\sqrt{n}} \left[ 2 \left( \sum_{x \in V_{\text{mix}}} \ell(x) \right) + \left( \frac{\beta}{10} + \frac{1}{2} \right) (n_1 + n_2) \right] + \frac{1}{2000}. \quad (6) $$

## 3.4 Cost of the Solution

### 3.4.1 Solution in the Rectangles of Types I and II

Let $V_1$ and $V_{II}$ denote the subsets of the points of $V$ that are in the rectangles of type I and type II, respectively. Let $K$ denote the number of mixed tours. We have $K = n^{1/4} \cdot m = \frac{5}{40-\beta} \cdot \sqrt{n}$. Applying Equation (6) on each mixed tour and summing, we have

$$ \text{cost}(S_{\text{mix}}) \le Y + \frac{1 + \epsilon_1}{\sqrt{n}} \left[ 2 \left( \sum_{x \in V_1 \cup V_{II}} \ell(x) \right) + \left( \frac{\beta}{10} + \frac{1}{2} \right) |V_{II}| \right] + \frac{\sqrt{n}}{400 \cdot (40 - \beta)}, \quad (7) $$

where $Y$ denotes the overall cost of $T_A^*$ over all rectangles $A$ of type I.

To analyze $Y$, we consider any rectangle $A$ of type I. The measure of $A$ is $M_A = D \cdot H = (1 - \epsilon_2) \left(1 - \frac{\beta}{40}\right) \frac{1}{\sqrt{n}}$. The event $\mathcal{E}$ implies that

$$ (1 - \epsilon_2)^2 \cdot \left(1 - \frac{\beta}{40}\right) \cdot \sqrt{n} < n_A < \left(1 - \frac{\beta}{40}\right) \cdot \sqrt{n}. \quad (8) $$

We investigate the expectation of $\text{cost}(T_A^*)$. By a construction given in [7], there exists a constant $C$ such that the cost of an optimal traveling salesman tour through any $n_A$ points in $A$ is at most $C\sqrt{M_A \cdot n_A}$. Together with Lemma 5, it follows that

$$ \mathbb{E}[\text{cost}(T_A^*)] < (1 + \epsilon_2) \cdot \beta \sqrt{M_A \cdot n_A} < (1 + \epsilon_2) \cdot \beta \left(1 - \frac{\beta}{40}\right), $$
43:10 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

for $n$ large enough (and thus $n_A$ large enough). Since there are $K = \Theta(\sqrt{n})$ rectangles $A$ of type I, by the law of large numbers,

$$Y = \sum_{A} \cos(T_{A}^{*}) < (1 + \epsilon_{2}) \cdot K \cdot (1 + \epsilon_{2}) \cdot \beta \left(1 - \frac{\beta}{40}\right), \quad \text{a.a.s.}$$

On the other hand, summing Equation (8) over all $A$, we have

$$|V_I| = \sum_{A} n_A > K \cdot (1 - \epsilon_2)^2 \cdot \left(1 - \frac{\beta}{40}\right) \cdot \sqrt{n}.$$

Therefore,

$$Y < (1 + \epsilon_2)^2 \cdot \frac{1}{(1 - \epsilon_2)^2} \cdot \frac{\beta \cdot |V_I|}{\sqrt{n}} < (1 + \epsilon_1) \cdot \frac{\beta \cdot |V_I|}{\sqrt{n}}, \quad \text{a.a.s.,}$$

where the last inequality follows since $\epsilon_2 = \frac{\epsilon_1}{10}$. From Equation (7), we conclude that, a.a.s.,

$$\cos(S_{\text{mix}}) \le \frac{1 + \epsilon_1}{\sqrt{n}} \left[ 2 \left( \sum_{x \in V_I \cup V_{II}} \ell(x) \right) + \beta |V_I| + \left( \frac{\beta}{10} + \frac{1}{2} \right) |V_{II}| \right] + \frac{\sqrt{n}}{400 \cdot (40 - \beta)} \cdot (9)$$

3.4.2 Solution in the Rectangles of Type III

Let $\hat{V}$ denote the subset of the points of $V$ that are in the rectangles of types III. Let $\hat{T}$ denote an optimal traveling salesman tour on $\hat{V} \cup \{O\}$. Let $\hat{S}$ denote an optimal solution to the CVRP on $\hat{V}$ with depot $O$ and with capacity $k = \sqrt{n}$. By Lemma 4,

$$\cos(\hat{S}) \le \frac{2}{\sqrt{n}} \left( \sum_{x \in \hat{V}} \ell(x) \right) + \cos(\hat{T}).$$

The cost of $\hat{T}$ is at most the cost $C_{\text{TSP}}$ of an optimal traveling salesman tour on $\hat{V}$ plus the detour to visit $O$. Since the distance between the depot and any point in $[0, 1]^2$ is $O(1)$, the cost of the detour is $O(1)$, so $\cos(\hat{T}) \le C_{\text{TSP}} + O(1)$.

Next, we analyze $C_{\text{TSP}}$. Let $L$ denote the width of a type III rectangle inside a box. Then $L = D - W \cdot m = \Theta(n^{-1/4})$. We observe that the length of a side of any type III rectangle is either $L$ or $\omega(L)$. So we partition every type III rectangle into squares of side length $L$. For each square, consider an optimal traveling salesman tour on the points inside that square. Let $Z$ denote the overall cost of the optimal traveling salesman tours inside all squares from all rectangles of type III. Then $C_{\text{TSP}}$ is at most $Z$ plus the total lengths of the boundaries of all squares. Using the same argument from Section 3.4.1, we have

$$Z < \left(1 + \frac{\epsilon_1}{3}\right) \cdot \frac{\beta \cdot |\hat{V}|}{\sqrt{n}}, \quad \text{a.a.s.}$$

Since the boundary length of each square is negligible compared with the TSP cost inside that square, we have

$$C_{\text{TSP}} = (1 + o(1)) \cdot Z < \left(1 + \frac{\epsilon_1}{2}\right) \cdot \frac{\beta \cdot |\hat{V}|}{\sqrt{n}}, \quad \text{a.a.s.}$$

Noting that $|\hat{V}| = \Theta(n)$, we have

$$\cos(\hat{T}) \le C_{\text{TSP}} + O(1) < (1 + \epsilon_1) \cdot \frac{\beta \cdot |\hat{V}|}{\sqrt{n}}, \quad \text{a.a.s.}$$
Therefore,

$$ \mathrm{cost}(\hat{S}) \le \frac{2}{\sqrt{n}} \left( \sum_{x \in \hat{V}} \ell(x) \right) + \frac{1 + \epsilon_1}{\sqrt{n}} \cdot \beta \cdot |\hat{V}|, \quad \text{a.a.s.} \tag{10} $$

### 3.4.3 The Global Solution

Let $S = S_{\text{mix}} \cup \hat{S}$ denote the global solution. From Equations (9) and (10), and using $\frac{2}{\sqrt{n}} \cdot \sum_{x \in V} \ell(x) = \text{rad}$ and $V_1 \cup V_{II} \cup \hat{V} = V$, we have

$$ \mathrm{cost}(S) \le (1 + \epsilon_1) \left[ \mathrm{rad} + \beta \cdot \frac{|V|}{\sqrt{n}} - \left( \beta - \frac{\beta}{10} - \frac{1}{2} \right) \frac{|V_{II}|}{\sqrt{n}} \right] + \frac{\sqrt{n}}{400 \cdot (40 - \beta)}, \quad \text{a.a.s.} \tag{11} $$

Observe that the rectangles of type II have an overall measure of $(1 - \epsilon_2) \cdot \frac{\beta}{8 \cdot (40 - \beta)}$. Event $\mathcal{E}$ implies that $|V_{II}| > (1 - \epsilon_2)^2 \cdot \frac{\beta \cdot n}{8 \cdot (40 - \beta)} > \frac{1}{1 + \epsilon_1} \cdot \frac{\beta \cdot n}{8 \cdot (40 - \beta)}$ since $\epsilon_2 = \frac{\epsilon_1}{10}$. By Lemma 5, $\beta > \beta_0 = 0.62866$. Thus $\frac{9\beta}{10} - \frac{1}{2} > 0$. From Equation (11), we have, a.a.s,

$$ \begin{aligned} (1 + \epsilon_1)(\mathrm{rad} + \beta\sqrt{n}) - \mathrm{cost}(S) &\ge (1 + \epsilon_1) \cdot \left( \frac{9\beta}{10} - \frac{1}{2} \right) \cdot \frac{|V_{II}|}{\sqrt{n}} - \frac{\sqrt{n}}{400 \cdot (40 - \beta)} \\ &> \left( \frac{9\beta}{10} - \frac{1}{2} \right) \cdot \frac{\beta\sqrt{n}}{8 \cdot (40 - \beta)} - \frac{\sqrt{n}}{400 \cdot (40 - \beta)} \\ &= \frac{\sqrt{n}}{8 \cdot (40 - \beta)} \cdot \left( \left( \frac{9\beta}{10} - \frac{1}{2} \right) \cdot \beta - \frac{1}{50} \right) \\ &> \frac{\sqrt{n}}{8 \cdot (40 - \beta_0)} \cdot \left( \left( \frac{9\beta_0}{10} - \frac{1}{2} \right) \cdot \beta_0 - \frac{1}{50} \right). \end{aligned} $$

Let $c_1$ denote the leading constant in the above bound, i.e.,

$$ c_1 = \frac{1}{8 \cdot (40 - \beta_0)} \cdot \left( \left( \frac{9\beta_0}{10} - \frac{1}{2} \right) \cdot \beta_0 - \frac{1}{50} \right). $$

The value of $c_1$ is roughly 0.000068. We conclude that

$$ \mathrm{cost}(S) < (1 + \epsilon_1)(\mathrm{rad} + \beta\sqrt{n}) - c_1\sqrt{n}, \quad \text{a.a.s.} $$

We complete the proof of Lemma 6.

## 4 Upper Bound on the Approximation Ratio

In this section, we prove Theorem 2 by providing an upper bound on the approximation ratio ITP(T)/OPT of the ITP algorithm, where T is a traveling salesman tour.

Let $\lambda$ and $\epsilon$ be positive constants such that $\lambda + \epsilon < 1$. We analyze the performance of the ITP algorithm with respect to $\lambda$ and $\epsilon$. The values of $\lambda$ and $\epsilon$ will be set in the end of the proof.

### 4.1 Structural analysis

**Lemma 10.** Let $T = (O, y_1, y_2, \dots, y_m, O)$ be any tour starting and ending at O. Let $L = \frac{1}{m} \left( \sum_{j=1}^{m} \ell(y_j) \right)$. Let $\Delta = \max_{1 \le j \le m} \{\ell(y_j)\} - L$. Then there exists a set $W \subseteq \{y_1, \dots, y_m\}$ which is of cardinality greater than $(\lambda + \epsilon) \cdot m - 1$ such that

$$ \mathrm{cost}(T) \ge 2 \left( L - \frac{\lambda + \epsilon}{1 - \lambda - \epsilon} \cdot \Delta \right) + \sum_{x \in W} \delta(x, W \setminus \{x\}). $$
**Proof.** Let W denote the set of points x such that $\ell(x) \ge L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$, other than the last one in the order of traversal by T starting from O. Tour T must first travel through a path to a first point of W, paying at least $L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$, then proceed from each point x of W through a path to another point of W, paying at least $\delta(x, W \setminus \{x\})$, and finally, go to one more point such that $\ell(x) \ge L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$, and travel from there through a path back to the depot, paying at least $L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$. Hence the cost of T is at least as stated in Lemma 10.

Next, we bound the size of W. When $\Delta = 0$, we have $\ell(y_j) = L$ for all $j \in [1, m]$. Hence $|W| = m - 1$, which is greater than $(\lambda + \epsilon) \cdot m - 1$, since $\lambda + \epsilon < 1$. The claim follows.

It remains to analyze the case when $\Delta > 0$. Every point of T is at distance at most $L + \Delta$ from the depot. Letting $m'$ denote the number of points whose distance from the depot is at least $L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$, we have

$$mL = \sum_{j=1}^{m} \ell(y_j) < m'(L + \Delta) + (m - m') \left( L - \frac{\lambda + \epsilon}{1 - \lambda - \epsilon} \cdot \Delta \right).$$

Since $1 - \lambda - \epsilon > 0$, this implies $m' - (\lambda + \epsilon) \cdot m > 0$, hence $|W| = m' - 1 > (\lambda + \epsilon) \cdot m - 1$. ◀

The following result is a strengthening of the lower bound OPT $\ge$ rad from Lemma 3, and will lead to our improved analysis of the ITP algorithm.

**▶ Theorem 11.** Let $\lambda$ and $\epsilon$ be positive constants such that $\lambda + \epsilon < 1$. Let V be a set of n points in any distance metric. Let $k = \omega(1)$. There exists a set $U \subseteq V$ which is of cardinality greater than $(\lambda + \frac{\epsilon}{2}) \cdot n$ for n large enough, and such that

$$\text{OPT} \ge \text{rad} + (1 - \lambda - \epsilon) \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right).$$

**Proof.** Let $T_1, \dots, T_q$ be the tours in an optimal solution to the CVRP. Let $m_i$ be the number of points in V that are visited by the tour $T_i$. Up to combining tours that visit few points, we may assume that $m_i > \frac{k}{2}$ for all but at most one tour, so $q \le \frac{2n}{k} + 1 = o(n)$.

For each tour $T_i$, define the corresponding $L_i$, $\Delta_i$, and $W_i$ with respect to the tour $T_i$ using the notations of Lemma 10. By summation, letting $U = \bigcup_i W_i$, Lemma 10 then implies (using $q = o(n)$, n large enough, and $\delta(x, W_i \setminus \{x\}) \ge \delta(x, U \setminus \{x\})$)

$$|U| = \sum_{i \le q} |W_i| > \left( (\lambda + \epsilon) \sum_i m_i \right) - q = (\lambda + \epsilon) \cdot n - q > \left( \lambda + \frac{\epsilon}{2} \right) \cdot n$$

and

$$\sum_i \text{cost}(T_i) \ge \left( \sum_i 2 \left( L_i - \frac{\lambda + \epsilon}{1 - \lambda - \epsilon} \cdot \Delta_i \right) \right) + \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right). \quad (12)$$

On the other hand, we trivially have

$$\sum_i \text{cost}(T_i) \ge \sum_i 2(L_i + \Delta_i). \quad (13)$$

A linear combination of Equation (12) with coefficient $(1 - \lambda - \epsilon)$ and of Equation (13) with coefficient $(\lambda + \epsilon)$ leads to:

$$\text{OPT} = \sum_i \text{cost}(T_i) \ge \left( \sum_i 2L_i \right) + (1 - \lambda - \epsilon) \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right).$$
Observe that

$$ \sum_{i} 2L_i = \sum_{i} \sum_{x \in T_i} \frac{2\ell(x)}{m_i} \geq \sum_{i} \sum_{x \in T_i} \frac{2\ell(x)}{k} = \sum_{x \in V} \frac{2\ell(x)}{k} = \text{rad.} $$

The Lemma follows.

<figure><img src="image_9.png" /></figure>

## 4.2 Probabilistic Analysis

The following result suggests that the closest point distance follows the law of large numbers. It is a corollary of Theorem 2.4 in [22].<fnref n="5" />

**Lemma 12** ([22]). Let $\mathcal{P}$ be a homogeneous Poisson point process of intensity 1 on $\mathbb{R}^2$ and $\delta_{\mathcal{P}}$ denote the distance from the origin of $\mathbb{R}^2$ to a closest point in $\mathcal{P}$ by the Euclidean norm. Let $V$ be a set of $n$ i.i.d. uniform random points. Then, given any bounded function $\phi: [0, \infty] \to [0, \infty)$, as $n \to \infty$ we have:

$$ \frac{1}{n} \sum_{x \in V} \phi(\sqrt{n} \cdot \delta(x, V \setminus \{x\})) \to \mathbb{E}[\phi(\delta_{\mathcal{P}})]. $$

Lemma 12 provides the rigorous setting enabling us to derive a new lower bound on the sum of the closest point distances over a subset of a set of i.i.d. uniform random points, which we now state.

**Lemma 13.** Let $V$ be a set of $n$ i.i.d. uniform random points. Let $U$ be any subset of $V$ such that $|U| > (\lambda + \frac{\epsilon}{2}) \cdot n$. Then, asymptotically almost surely,

$$ \sum_{x \in U} \delta(x, V \setminus \{x\}) > (\xi_{\lambda} - \epsilon) \cdot \sqrt{n}, $$

where $\xi_{\lambda}$ is a constant defined by

$$ \xi_{\lambda} := \frac{1}{2} \operatorname{erf} \left( \sqrt{\ln \frac{1}{1-\lambda}} \right) - (1-\lambda) \cdot \sqrt{\frac{1}{\pi} \ln \frac{1}{1-\lambda}} $$

in which $\operatorname{erf}(\cdot)$ is the Gauss error function $\operatorname{erf}(z) = \frac{2}{\sqrt{\pi}} \int_{0}^{z} e^{-t^2} dt$.

**Proof.** Recall the definition of $\delta_{\mathcal{P}}$ from Lemma 12. By definition of the Poisson point process, the probability $g(r)$ of the event $\delta_{\mathcal{P}} \le r$ equals $1 - e^{-\pi r^2}$.

Let $Z \subseteq V$ be the set of points $x \in V$ such that $\delta(x, V \setminus \{x\}) \le \frac{r_0}{\sqrt{n}}$, with $r_0 = \sqrt{\frac{1}{\pi} \ln \frac{1}{1-\lambda}}$. We apply Lemma 12 with $\phi$ equals $\phi_1$, the indicator function of whether $r \le r_0$, to obtain that, as $n \to \infty$,

$$ \frac{|Z|}{n} \to \mathbb{E}[\phi_1(\delta_{\mathcal{P}})] = g(r_0) = \lambda. $$

Thus $|Z| \le (\lambda + \frac{\epsilon}{2}) \cdot n < |U|$, a.a.s. Since $Z$ consists of the points $x \in V$ with the smallest values of $\delta(x, V \setminus \{x\})$, we have

$$ \sum_{x \in U} \delta(x, V \setminus \{x\}) \geq \sum_{x \in Z} \delta(x, V \setminus \{x\}), \quad \text{a.a.} \qquad (14) $$

<footnote n="5">⁵ To apply Theorem 2.4 in [22], we consider a directed graph $G$ with vertex set $V$, such that from every vertex $x \in V$, there is a unique outgoing edge, let it be $(x, y)$, where $y$ is the closest point to $x$ among the points in $V \setminus \{x\}$, breaking ties arbitrarily. Theorem 2.4 in [22] is interpreted with reference to Remark (h) in [22].</footnote>
43:14 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

To analyze $\sum_{x \in Z} \delta(x, V \setminus \{x\})$, we define a bounded function $\phi_2$ as follows.

$$ \phi_2(r) = \begin{cases} r, & r \le r_0 \\ 0, & \text{otherwise.} \end{cases} $$

Applying Lemma 12 with $\phi = \phi_2$, we have, as $n \to \infty$,

$$ \frac{1}{n} \sum_{x \in Z} \sqrt{n} \cdot \delta(x, V \setminus \{x\}) \to \mathbb{E}[\phi_2(\delta_P)], $$

thus

$$ \sum_{x \in Z} \delta(x, V \setminus \{x\}) > (\mathbb{E}[\phi_2(\delta_P)] - \epsilon) \cdot \sqrt{n}, \quad \text{a.a.s.} \qquad (15) $$

Observe that $\mathbb{E}[\phi_2(\delta_P)] = \int_0^\infty \phi_2(r) \cdot g'(r) dr = \int_0^{r_0} r \cdot g'(r) dr$, where $g'(r) = 2\pi r \cdot e^{-\pi r^2}$.

Integrating by parts, recalling the definition of the Gauss error function, and plugging in the value of $r_0$, we have

$$ \mathbb{E}[\phi_2(\delta_P)] = \left( \int_0^{r_0} e^{-\pi r^2} dr \right) - \left[ r \cdot e^{-\pi r^2} \right]_0^{r_0} = \left[ \frac{\operatorname{erf}(\sqrt{\pi} \cdot r)}{2} - r \cdot e^{-\pi r^2} \right]_0^{r_0} = \xi_\lambda. $$

The claim follows.

<figure><img src="image_10.png" /></figure>

4.3 Proof of Theorem 2

Let $T$ denote an $\alpha$-approximate traveling salesman tour on $V \cup \{O\}$, where $\alpha \ge 1$ is a constant. When $k = O(1)$, for any $\epsilon > 0$, ITP($T$) < $(1 + \epsilon)OPT$ a.a.s. according to [15], which implies the claim. In the following, we assume that $k = \omega(1)$.

According to Lemma 4, we have

$$ \text{ITP}(T) < \text{cost}(T) + \text{rad}. $$

First, we bound cost($T$). Letting $T^*$ denote an optimal traveling salesman tour on $V \cup \{O\}$, we have cost($T$) $\le \alpha \cdot \text{cost}(T^*)$. By Lemma 5, the value of an optimal traveling salesman tour on $V$ is less than $(\beta + \frac{\epsilon}{2}) \cdot \sqrt{n}$, a.a.s. Since the distance between the depot and any point in $[0, 1]^2$ is $O(1)$, we have cost($T^*) < (\beta + \frac{\epsilon}{2}) \cdot \sqrt{n} + O(1)$, which is less than $(\beta + \epsilon) \cdot \sqrt{n}$ when $n$ is large enough. Thus cost($T$) < $\alpha(\beta + \epsilon) \cdot \sqrt{n}$, a.a.s.

Next, we analyze rad. By Theorem 11, for some $U \subseteq V$ of size greater than $(\lambda + \frac{\epsilon}{2}) n$ we have

$$ \text{rad} \le \text{OPT} - (1 - \lambda - \epsilon) \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right). $$

By Lemma 13 and the fact that $\delta(x, U \setminus \{x\}) \ge \delta(x, V \setminus \{x\})$, we have a.a.s.

$$ \sum_{x \in U} \delta(x, U \setminus \{x\}) > (\xi_{\lambda} - \epsilon) \cdot \sqrt{n}. $$

Noting that $1 - \lambda - \epsilon > 0$, we have

$$ \text{rad} \le \text{OPT} - (1 - \lambda - \epsilon) \cdot (\xi_{\lambda} - \epsilon) \cdot \sqrt{n}. $$
<figure><img src="image_11.png" /><figcaption>Figure 2 Plot of the function $h(\lambda) = (1 - \lambda) \cdot \xi_{\lambda}$ for $\lambda \in [0, 1)$. The maximum value of $h(\lambda)$ is greater than 0.078674, which is achieved when $\lambda$ is roughly 0.62468.</figcaption></figure>

Combining the above bounds gives a.a.s.

$$ \text{ITP}(T) < \text{OPT} + (\alpha(\beta + \epsilon) - (1 - \lambda - \epsilon) \cdot (\xi_{\lambda} - \epsilon)) \cdot \sqrt{n}. \quad (16) $$

Note that the coefficient of $\sqrt{n}$ in Equation (16) must be positive, because $\text{ITP}(T) \ge \text{OPT}$ (Lemma 4). Using Lemmas 3 and 5, and assuming $\epsilon < \beta$, we have a.a.s. $\sqrt{n} < \frac{\text{cost}(T^*)}{\beta - \epsilon} \le \frac{\text{OPT}}{\beta - \epsilon}$, and substituting into Equation (16) gives a.a.s.

$$ \text{ITP}(T) < \left( 1 + \frac{\alpha(\beta + \epsilon) - (1 - \lambda - \epsilon) \cdot (\xi_{\lambda} - \epsilon)}{\beta - \epsilon} \right) \cdot \text{OPT}. $$

Since $\beta$ is a positive constant (Lemma 5), choosing $\lambda$ to maximize $(1 - \lambda) \cdot \xi_{\lambda}$ and $\epsilon$ small enough yields

$$ \frac{\text{ITP}(T)}{\text{OPT}} < 1 + \alpha - \frac{\max_{\lambda}\{(1 - \lambda) \cdot \xi_{\lambda}\}}{\beta} + 0.00001. $$

A numerical calculation (Figure 2) gives $\max_{\lambda}\{(1 - \lambda) \cdot \xi_{\lambda}\} > 0.078674$, and Lemma 5 tells us that $\beta < \beta_1 = 0.92117$. Substituting those values concludes the proof.

References

1. A. Adamaszek, A. Czumaj, and A. Lingas. PTAS for k-tour cover problem on the plane for moderately large values of k. *International Journal of Foundations of Computer Science*, 21(06):893-904, 2010.

2. K. Altinkemer and B. Gavish. Heuristics for delivery problems with constant error guarantees. *Transportation Science*, 24(4):294-297, 1990.

3. S. P. Anbuudayasankar, K. Ganesh, and S. Mohapatra. *Models for practical routing problems in logistics*. Springer, 2016.

4. S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. *Journal of the ACM (JACM)*, 45(5):753-782, 1998.

5. T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama. Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k. In *Proceedings of the twenty-ninth annual ACM symposium on Theory of computing*, pages 275-283, 1997.

6. A. Baltz, D. Dubhashi, A. Srivastav, L. Tansini, and S. Werth. Probabilistic analysis for a multiple depot vehicle routing problem. *Random Structures & Algorithms*, 30(1-2):206-225, 2007.
43:16 Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

7 J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. In *Mathematical Proceedings of the Cambridge Philosophical Society*, volume 55, pages 299–327. Cambridge University Press, 1959.

8 J. Blauth, V. Traub, and J. Vygen. Improving the approximation ratio for capacitated vehicle routing. In *Integer Programming and Combinatorial Optimization (IPCO)*, volume 12707. Springer, 2021.

9 A. Bompadre, M. Dror, and J. B. Orlin. Improved bounds for vehicle routing solutions. *Discrete Optimization*, 3(4):299–316, 2006.

10 A. Bompadre, M. Dror, and J. B. Orlin. Probabilistic analysis of unit-demand vehicle routeing problems. *Journal of applied probability*, 44(1):259–278, 2007.

11 T. G. Crainic and G. Laporte. *Fleet management and logistics*. Springer Science & Business Media, 2012.

12 C. F. Daganzo. The distance traveled to visit n points with a maximum of c stops per vehicle: An analytic model and an application. *Transportation science*, 18(4):331–350, 1984.

13 A. Das and C. Mathieu. A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. *Algorithmica*, 73(1):115–142, 2015.

14 B. Golden, S. Raghavan, and E. Wasil. *The vehicle routing problem: latest advances and new challenges*, volume 43 of *Operations Research/Computer Science Interfaces Series*. Springer, 2008.

15 M. Haimovich and A. H. G. Rinnooy Kan. Bounds and heuristics for capacitated routing problems. *Mathematics of operations Research*, 10(4):527–542, 1985.

16 Richard M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. *Mathematics of operations research*, 2(3):209–224, 1977.

17 M. Khachay and R. Dubinin. PTAS for the Euclidean capacitated vehicle routing problem in $\mathbb{R}^d$. In *International Conference on Discrete Optimization and Operations Research*, pages 193–205. Springer, 2016.

18 C. L. Li and D. Simchi-Levi. Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. *ORSA Journal on Computing*, 2(1):64–73, 1990.

19 C. L. Li, D. Simchi-Levi, and M. Desrochers. On the distance constrained vehicle routing problem. *Operations research*, 40(4):790–799, 1992.

20 J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. *SIAM Journal on computing*, 28(4):1298–1309, 1999.

21 G. Mosheiov. Vehicle routing with pick-up and delivery: tour-partitioning heuristics. *Computers & Industrial Engineering*, 34(3):669–684, 1998.

22 M. D. Penrose and J. E. Yukich. Weak laws of large numbers in geometric probability. *The Annals of Applied Probability*, 13(1):277–303, 2003.

23 W. T. Rhee. Probabilistic analysis of a capacitated vehicle routing problem II. *The Annals of Applied Probability*, 4(3):741–764, 1994.

24 S. Steinerberger. New bounds for the traveling salesman constant. *Advances in Applied Probability*, 47(1):27–36, 2015.

25 P. Toth and D. Vigo. *The Vehicle Routing Problem*. Society for Industrial and Applied Mathematics, 2002.