# Iterated Tour Partitioning for Euclidean Capacitated Vehicle Routing

Claire Mathieu, Hang Zhou

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

## To cite this version:

Claire Mathieu, Hang Zhou. Iterated Tour Partitioning for Euclidean Capacitated Vehicle Routing. Random Structures and Algorithms, 2023, 62 (4), pp.1056-1075. 10.1002/rsa.21130 . hal-04483022

HAL Id: hal-04483022

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

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
# Iterated Tour Partitioning for Euclidean Capacitated Vehicle Routing

Claire Mathieu

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

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

CNRS Paris, France

Hang Zhou

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

<figure><img src="image_6.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. The objective is to visit all customers using a set of routes of minimum total length, such that each route visits at most *k* customers.

The best known polynomial-time approximation is the iterated tour partitioning (ITP) algorithm, introduced in 1985 by Haimovich and Rinnooy Kan. They showed that the solution obtained by the ITP algorithm is arbitrarily close to the optimum 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 the ITP algorithm is at best a (1 + *c*₀)-approximation, for some positive constant *c*₀, and is at worst a 1.915-approximation.

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

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

**Related Version** An extended abstract of this paper appears in the proceedings of the International Symposium on Algorithms and Computation (ISAAC) 2021.

**Funding** This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR) and the grant on "Efficiency in Algorithms" from Hi! PARIS.

# 1 Introduction

**Unit-Demand Euclidean CVRP.** In the capacitated vehicle routing problem (CVRP), we are given a set of *n* customers and a depot. The customers and the depot are located in some metric space. 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* ≥ 3 (see [5]). Unless explicitly mentioned, all CVRP instances in this paper are assumed to be unit-demand Euclidean.

**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 as a black box, then partitions the tour into segments such that the number of customers in each segment is at most *k*, and finally, for each segment, connects the endpoints of that 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 $\alpha + 1$, 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.)* uniform random points in $[0, 1]^2$. 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})$. 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”.

## 1.1 Our Results

In our work, we study the open question in the random setting 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 (ITP) 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 $1 \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 ITP 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 in the deterministic setting is at most $\alpha + 1$ due to Altinkemer and Gavish [2]. When the points are i.i.d. uniform random in the unit square, Bompadre, Dror, and Orlin [10] showed that the approximation ratio of the ITP algorithm is at most $\alpha + 0.995$, a.a.s.<fnref n="2" /> Here, using a different approach from [10], we further improve the upper bound on the approximation ratio in this random setting to $\alpha + 0.915$, a.a.s. (Theorem 2), see Section 4.

**▶ Theorem 2.** *Consider the iterated tour partitioning (ITP) 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 ITP algorithm is at most $\alpha + 0.915$ asymptotically almost surely.*

<footnote n="1">¹ More precisely, $O = (\frac{1}{2}, -1000)$.</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 $\alpha + 0.985$ is achievable without giving the proof.</footnote>
## 1.2 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 in the deterministic setting. A series of papers designed PTAS algorithms for small $k$: Haimovich and Rinnooy Kan [15] gave a PTAS when $k$ is constant; Asano et al. [5] extended techniques in [15] to achieve a PTAS for $k = O(\log n/\log\log n)$; and Adamaszek, Czumaj, and Lingas [1] designed a PTAS for $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$ and the two-dimensional plane, 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] gave an optimal algorithm for 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 - \frac{1}{k})\alpha + 1$ 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 $\alpha + 1 - \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, and 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.

# 2 Notations and Preliminaries

In this section, we introduce some notations and we formally define the problem and the algorithm. We also recall some preliminary results on the traveling salesman problem.

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

**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} \sum_{x \in V} \ell(x). $$

**Lemma 3 ([15]).** Let $T^*$ be an optimal traveling salesman tour on $V \cup \{O\}$. Then
$$ \text{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 two phases. In the first 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 second phase, the ITP algorithm selects the best of the $k$ solutions constructed as follows. For each $i \in [1, k]$, let $n_i = \lfloor(n - i)/k\rfloor + 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 containing less than $k$ points.<fnref n="3" /> The output of the ITP algorithm is a solution among $S_1, \dots, S_k$ that achieves the minimum cost. The running time of the second phase of the ITP algorithm is $O(n)$, see [2].

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 $(\alpha + 1)$-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

$$ \text{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 uniform random setting, as follows.

**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_n^*$ denote an optimal traveling salesman tour on $V$. Then there exists a universal constant$^4$ $\beta$ such that

$$ \lim_{n \to \infty} \frac{\text{cost}(T_n^*)}{\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$.

<footnote n="3">³ The number of points on the first segment is $i$, and the number of points on the last segment is $n - i + k - \lfloor(n - i)/k\rfloor \cdot k$.</footnote>

<footnote n="4">⁴ The constant $\beta$ does not depend on the support.</footnote>
### 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 well-chosen traveling salesman tour.

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 show that an ITP solution is at best a $(1 + c_0)$-approximation for the CVRP in the random setting, we show the existence of another solution that is significantly better than the ITP solution. To construct the new 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.

Let the depot $O \in \mathbb{R}^2$ be $(\frac{1}{2}, -1000)$.

Lemmas 6 and 7 are central to the proof of Theorem 1 and contain main novelties in this section.

**Lemma 6.** Let $V$ be a set of $n$ i.i.d. uniform random points in $[0, 1]^2$. Let $\beta$ be defined as in Lemma 5. Then there exists an absolute constant $c_1 \in (0, \beta)$ such that for any fixed $\epsilon_1 > 0$, $\text{OPT} < (1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - c_1\sqrt{n}$, a.a.s.

**Lemma 7.** Let $V$ be a set of $n$ i.i.d. uniform random points in $[0, 1]^2$. 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 fixed $\epsilon_1 > 0$, $\text{ITP}(T) > (1 - \epsilon_1)(\text{rad} + \beta\sqrt{n})$, a.a.s.

**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 weak 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 $rad = \frac{2}{\sqrt{n}} \sum_{x \in V} l(x)$. Hence $(L - \epsilon_1) \cdot 2\sqrt{n} < 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.}$$

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

In the rest of the section, we prove Lemmas 6 and 7 in Sections 3.1 and 3.2, respectively.

## 3.1 Proof of 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)(rad + \beta\sqrt{n}) - c_1\sqrt{n}$, a.a.s., where the constant $c_1 > 0$ will be chosen later.

### 3.1.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$^5$ $[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.

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 rectangle 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 result relates $n_R$ with $M_R$.

**Lemma 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.

<footnote>$^5$ The decomposition is a partition except for the boundaries, that have measure 0.</footnote>
<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>

**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 - M_R \cdot n| > \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 Lemma 8.

### 3.1.2 Construction of a Solution

To construct the solution, we enable 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 rectangles, 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 a single type I rectangle and two type II rectangles. 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.

### 3.1.3 Cost of a Mixed Tour

Consider any mixed tour $T_{\text{mix}}$. We follow the same notations as in Section 3.1.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 lemma.

**Lemma 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) $$

**Proof.** Let $T'_i$ denote the subpath of $T_i$ that is between $Q_i$ and $S_i$. We have

$$ \text{cost}(T_i) = \delta(O, Q_i) + \text{cost}(T'_i) + \delta(S_i, P_1). $$

To analyze $\text{cost}(T'_i)$, recall that the Euclidean length of a segment is at most its length in the $l_1$ metric. Since $T'_i$ is monotone in the y-coordinate and stays within a rectangle of width $W$, its cost is at most $\delta(Q_i, S_i) + (n_i + 1)W$. We have

$$ \text{cost}(T_i) \le \delta(O, Q_i) + \delta(Q_i, S_i) + (n_i + 1)W + \delta(S_i, P_1). $$

Let $P_2$ denote the midpoint of the left boundary of the box $\mathcal{B}$, and let $P_3$ denote the bottom left corner of the box $\mathcal{B}$, see Figure 1c.

We have $\delta(Q_i, S_i) = \delta(P_3, P_2)$ by the construction. Since the box $\mathcal{B}$ has width $D$, we have $\delta(O, Q_i) \le \delta(O, P_3) + D$ and $\delta(S_i, P_1) \le \delta(P_2, P_1) + D$ by the triangle inequality. Using $\delta(P_3, P_2) + \delta(P_2, P_1) = \delta(P_3, P_1)$, we have

$$ \text{cost}(T_i) \le \delta(O, P_3) + \delta(P_3, P_1) + (n_i + 1)W + 2D. \qquad (4) $$
To analyze $\delta(O, P_3) + \delta(P_3, P_1)$, let $P'_3$ denote the point on the segment $OP_1$ that has the same $y$ coordinate as $P_3$. By the triangle inequality, $\delta(O, P_3) \le \delta(O, P'_3) + \delta(P_3, P'_3)$ and $\delta(P_3, P_1) \le \delta(P'_3, P_1) + \delta(P_3, P'_3)$. Using $\delta(O, P'_3) + \delta(P'_3, P_1) = \delta(O, P_1)$, we have

$$ \delta(O, P_3) + \delta(P_3, P_1) \le \delta(O, P_1) + 2\delta(P_3, P'_3). \quad (5) $$

It remains to bound $\delta(P_3, P'_3)$. Let $\Delta_x$ (resp. $\Delta_y$) denote the absolute difference of the $x$-coordinate (resp. $y$-coordinate) between $O$ and $P_3$. We observe that

$$ \delta(P_3, P'_3) = \Delta_x \cdot \frac{\delta(P_3, P_1)}{\Delta_y + \delta(P_3, P_1)}. $$

By the definition of a box, $\delta(P_3, P_1) < \frac{1}{4}$. Since $O = (\frac{1}{2}, -1000)$ and $P_3 \in [0, 1]^2$, we have $\Delta_x \le \frac{1}{2}$ and $\Delta_y \ge 1000$. Thus

$$ \delta(P_3, P'_3) < \frac{1}{8000}. \quad (6) $$

From Equations (4)–(6), we have

$$ \mathrm{cost}(T_i) < \delta(O, P_1) + \frac{1}{4000} + n_i W + (W + 2D). $$

The claim follows.

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

From Equations (1)–(3), and using the definition of $W$, we have

$$ \mathrm{cost}(T_{\mathrm{mix}}) < \mathrm{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 (7) $$

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_{\mathrm{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_{\mathrm{mix}}|} \left( \sum_{x \in V_{\mathrm{mix}}} \ell(x) \right) + \frac{1}{|V_{\mathrm{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_{\mathrm{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_{\mathrm{mix}}} \ell(x) \right) + \frac{n_1 + n_2}{4} \right] + (D + H). \quad (8) $$

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 (7) and (8), we have

$$ \mathrm{cost}(T_{\mathrm{mix}}) < \mathrm{cost}(T_A^*) + \frac{1 + \epsilon_1}{\sqrt{n}} \left[ 2 \left( \sum_{x \in V_{\mathrm{mix}}} \ell(x) \right) + \left( \frac{\beta}{10} + \frac{1}{2} \right) (n_1 + n_2) \right] + \frac{1}{2000}. \quad (9) $$
### 3.1.4 Cost of the Solution in Rectangles of Types I and II

Let $V_I$ 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}$. Let $S_{mix}$ denote the set of the mixed tours. Applying Equation (9) 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_I \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 (10) $$

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 (11) $$

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

$$ \begin{aligned} \mathbb{E}[\text{cost}(T_A^*)] &< (1 - o(1)) \cdot (1 + \frac{\epsilon_2}{2}) \cdot \beta \sqrt{M_A \cdot n_A} + o(1) \cdot C \sqrt{M_A \cdot n_A} \\ &< (1 + \epsilon_2) \cdot \beta \sqrt{M_A \cdot n_A} \\ &< (1 + \epsilon_2) \cdot \beta \left(1 - \frac{\beta}{40}\right). \end{aligned} $$

Since there are $K = \Theta(\sqrt{n})$ rectangles $A$ of type I, by the weak law of large numbers,

$$ Y = \sum_A \text{cost}(T_A^*) < (1 + \epsilon_2)^2 \cdot K \cdot \beta \left(1 - \frac{\beta}{40}\right), \quad \text{a.a.s.} $$

On the other hand, summing Equation (11) 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 (10), we have, a.a.s.,

$$ \text{cost}(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 \cdot |V_I| + \left( \frac{\beta}{10} + \frac{1}{2} \right) |V_{II}| \right] + \frac{\sqrt{n}}{400 \cdot (40 - \beta)}. \quad (12) $$

### 3.1.5 Cost of the Solution in Rectangles of Type III

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

$$ \text{cost}(S_{\text{III}}) \le \frac{2}{\sqrt{n}} \left( \sum_{x \in V_{\text{III}}} \ell(x) \right) + \text{cost}(T_{\text{III}}). $$
The cost of $T_{III}$ is at most the cost $C_{TSP}$ of an optimal traveling salesman tour on $V_{III}$ 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 $\text{cost}(T_{III}) \le C_{TSP} + O(1)$.

Next, we analyze $C_{TSP}$. Let $L$ denote the width of a type III rectangle inside a box. Then $L = D - W \cdot 2m = \Theta(n^{-1/4})$. We observe that the length of a side of any type III rectangle is either $L$ or $\Omega(1)$. 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_{TSP}$ is at most $Z$ plus the total length of the boundaries of all squares. Using the same argument from Section 3.1.4, we have

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

The boundary length of each square is $4L = \Theta(n^{-1/4})$ and the number of squares is $\Theta(\sqrt{n})$, so the total length of the boundaries of all squares is $\Theta(n^{1/4})$. We have

$$C_{TSP} < \left(1 + \frac{\epsilon_1}{3}\right) \cdot \frac{\beta \cdot |V_{III}|}{\sqrt{n}} + \Theta(n^{1/4}), \quad \text{a.a.s.}$$

Noting that $|V_{III}| = \Theta(n)$ conditional on the event $\mathcal{E}$. So we have

$$\text{cost}(T_{III}) \le C_{TSP} + O(1) < (1 + \epsilon_1) \cdot \frac{\beta \cdot |V_{III}|}{\sqrt{n}}, \quad \text{a.a.s.}$$

Therefore,

$$\text{cost}(S_{III}) \le \frac{2}{\sqrt{n}} \left( \sum_{x \in V_{III}} \ell(x) \right) + \frac{1 + \epsilon_1}{\sqrt{n}} \cdot \beta \cdot |V_{III}|, \quad \text{a.a.s.} \qquad (13)$$

### 3.1.6 Cost of the Global Solution

Let $S = S_{\text{mix}} \cup S_{\text{III}}$ denote the global solution. From Equations (12) and (13), and using $\frac{2}{\sqrt{n}} \cdot \sum_{x \in V} \ell(x) = \text{rad}$ and $V_I \cup V_{II} \cup V_{III} = V$, we have, a.a.s.,

$$\begin{aligned} \text{cost}(S) &\le (1 + \epsilon_1) \left[ \frac{2}{\sqrt{n}} \cdot \sum_{x \in V} \ell(x) + \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)} \\ &\le (1 + \epsilon_1) \left[ \text{rad} + \beta \cdot \sqrt{n} - \left(\frac{9\beta}{10} - \frac{1}{2}\right) \frac{|V_{II}|}{\sqrt{n}} \right] + \frac{\sqrt{n}}{400 \cdot (40 - \beta)}. \end{aligned}$$

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$. Therefore, we have, a.a.s.,

$$\begin{aligned} (1 + \epsilon_1)(\text{rad} + \beta\sqrt{n}) - \text{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.

## 3.2 Proof of Lemma 7

Without loss of generality, we assume that $\alpha \le 2$, since otherwise it suffices to prove the claim for the case of $\alpha = 2$. We also assume that $\epsilon_1 \le 1$ since otherwise the claim is evident.

To begin with, we construct an $\alpha$-approximate traveling salesman tour $T$ on $V \cup \{O\}$. Let $\epsilon_0 = \alpha - 1$. Note that $\epsilon_0 \in (0, 1]$. Let $\epsilon_2 = \min(\frac{\epsilon_0}{20}, \frac{\epsilon_1}{4})$. To avoid purely technical complications, we assume that $\frac{1}{\sqrt{1+\epsilon_2}} \cdot n^{1/4}$ is an integer. We divide $[0, 1]^2$ into squares of side length $D = \sqrt{1+\epsilon_2} \cdot n^{-1/4}$, resulting in $m = \frac{1}{D^2} = \frac{1}{1+\epsilon_2} \cdot \sqrt{n}$ squares. Let $A_1, \dots, A_m$ be an ordering of the resulting squares, such that for each $i \in [1, m-1]$, the squares $A_i$ and $A_{i+1}$ are adjacent in the plane. It is easy to see that such an ordering indeed exists. For each square $A_i$, let $V_i \subseteq V$ be the set of points of $V$ that are in the square $A_i$. Let $T_i$ be an optimal traveling salesman tour on $V_i$. Let $T$ be a traveling salesman tour on $V \cup \{O\}$ obtained by including $T_1, \dots, T_m$, adding a segment between the last point of $T_i$ and the first point of $T_{i+1}$ for each $i \in [1, m-1]$; and finally, adding two other segments, one connecting $O$ to the first point of $T_1$, and another one connecting $O$ to the last point of $T_m$.

For any $i \in [1, m]$, the expectation of $|V_i|$ is $D^2n = (1 + \epsilon_2)\sqrt{n}$. Let $\mathcal{E}$ denote the event that $\sqrt{n} < |V_i| < (1 + 2\epsilon_2)\sqrt{n}$, for all $i \in [1, m]$. Similarly as in the proof of Lemma 6, the Chernoff bound implies that Event $\mathcal{E}$ occurs a.a.s. From now on, we condition on the occurrence of $\mathcal{E}$.

Next, we show that $T$ is an $\alpha$-approximate traveling salesman tour, a.a.s. For each $i \in [1, m-1]$, the distance between any point in $T_i$ and any point in $T_{i+1}$ is at most $\sqrt{5} \cdot D$, since $A_i$ and $A_{i+1}$ are adjacent squares, both of side length $D$. The distance between the depot and any point in $[0, 1]^2$ is $O(1)$. Therefore,

$$\mathrm{cost}(T) \le \left( \sum_{i=1}^{m} \mathrm{cost}(T_i) \right) + (m-1)\sqrt{5} \cdot D + O(1).$$

Using the same argument from Section 3.1.4, we obtain

$$\sum_{i=1}^{m} \mathrm{cost}(T_i) < \left(1 + \frac{\epsilon_0}{3}\right) \beta\sqrt{n}, \quad \text{a.a.s.}$$

Noting that $(m-1)\sqrt{5} \cdot D = o(\sqrt{n})$, we have

$$\mathrm{cost}(T) < \left(1 + \frac{\epsilon_0}{2}\right) \beta\sqrt{n}, \quad \text{a.a.s.}$$

On the other hand, by Lemma 5, the value of an optimal traveling salesman tour on $V \cup \{O\}$ is at least $(1 - \frac{\epsilon_0}{4}) \beta\sqrt{n}$, a.a.s. Thus the approximation ratio of the solution $T$ is at most $\frac{1+\frac{\epsilon_0}{2}}{1-\frac{\epsilon_0}{4}} < 1 + \epsilon_0$, a.a.s. Since $\epsilon_0 = \alpha - 1$, $T$ is an $\alpha$-approximate traveling salesman tour on $V \cup \{O\}$, a.a.s.
It remains to lower bound ITP(T). We say that a pair of points $(u, v)$ is a splitting pair if $u$ and $v$ are consecutive points in $T$ and that $u$ is the ending point of one tour and $v$ is the starting point of another tour according to the construction in the ITP algorithm. Let $w(u, v)$ denote the weight of a splitting pair $(u, v)$ defined by $w(u, v) = \ell(u) + \ell(v) - \delta(u, v)$. Note that $w(u, v) \ge 0$ by the triangle inequality. From the definition of the ITP algorithm, the cost of the output solution satisfies

$$ \text{ITP}(T) = \text{cost}(T) + \hat{w}, \qquad (14) $$

where $\hat{w}$ denotes the total weight of the splitting pairs.

By the construction of $T$, cost($T$) is at least the overall cost of $T_i, \dots, T_m$. Again, using the same argument from Section 3.1.4, we obtain

$$ \text{cost}(T) \ge \sum_{i=1}^{m} \text{cost}(T_i) > (1 - \epsilon_1)\beta\sqrt{n}, \quad \text{a.a.s.} \qquad (15) $$

Next, we analyze the total weight $\hat{w}$ of the splitting pairs. For each $i \in [1, m]$, Event $\mathcal{E}$ implies that $|V_i| > \sqrt{n}$, so there is at least one splitting pair in $V_i$. Let $(u_i, v_i)$ denote a splitting pair in $V_i$, breaking ties arbitrarily. We have $\hat{w} \ge \sum_{i=1}^{m} w(u_i, v_i)$.

Fix some $i \in [1, m]$. In order to bound $w(u_i, v_i)$, we consider any point $x \in V_i$. Since the three points $u_i, v_i$, and $x$ belong to the same square $A_i$ of side length $D$, their pairwise distances are at most $\sqrt{2} \cdot D$. Thus both $\ell(u_i)$ and $\ell(v_i)$ are at least $\ell(x) - \sqrt{2} \cdot D$ by the triangle inequality. Hence

$$ w(u_i, v_i) = \ell(u_i) + \ell(v_i) - \delta(u_i, v_i) \ge 2\ell(x) - 3\sqrt{2} \cdot D. $$

Averaging over all points $x \in V_i$ and using $|V_i| < (1 + 2\epsilon_2)\sqrt{n}$ (Event $\mathcal{E}$), we have

$$ w(u_i, v_i) > \frac{2}{(1 + 2\epsilon_2)\sqrt{n}} \left( \sum_{x \in V_i} \ell(x) \right) - 3\sqrt{2} \cdot D. \qquad (16) $$

Summing Equation (16) over all $i \in [1, m]$ and recalling that $\text{rad} = \frac{2}{\sqrt{n}} \sum_{x \in V} \ell(x)$, we have

$$ \hat{w} \ge \sum_{i=1}^{m} w(u_i, v_i) > \frac{1}{1 + 2\epsilon_2} \cdot \text{rad} - 3\sqrt{2} \cdot D \cdot m = \frac{1 - o(1)}{1 + 2\epsilon_2} \cdot \text{rad} > (1 - \epsilon_1) \cdot \text{rad}, \qquad (17) $$

where the equality follows from the facts that $\text{rad} = \Theta(\sqrt{n})$ and $D \cdot m = o(\sqrt{n})$, and the last inequality follows from $\epsilon_2 \le \frac{\epsilon_1}{4}$.

From Equations (14), (15), and (17),

$$ \text{ITP}(T) > (1 - \epsilon_1)\beta\sqrt{n} + \hat{w} > (1 - \epsilon_1)(\beta\sqrt{n} + \text{rad}). $$

This completes the proof.

## 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 an $\alpha$-approximate traveling salesman tour on $V \cup \{O\}$.

Our proof 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
14 Iterated Tour Partitioning for Euclidean Capacitated Vehicle Routing

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.

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 a tour starting and ending at $O$, where $y_1, y_2, \dots, y_m, O$ are arbitrary points in any metric. Let $L = \frac{1}{m} \sum_{j=1}^{m} l(y_j)$. Let $\Delta = \max_{1 \le j \le m} \{l(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 $y_i$ such that $l(y_i) \ge L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$ and $y_i \ne y^*$, where $y^*$ denotes the point $y_i$ such that $l(y_i) \ge L - \frac{\lambda+\epsilon}{1-\lambda-\epsilon} \cdot \Delta$ and $i$ is maximized. 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 $l(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 $l(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} l(y_j) < m'(L + \Delta) + (m - m') \left( L - \frac{\lambda + \epsilon}{1 - \lambda - \epsilon} \cdot \Delta \right). $$

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

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 metric space. Assume that $k = \omega(1)$. For $n$ large enough, there exists a set $U \subseteq V$ which is of cardinality greater than $(\lambda + \frac{\epsilon}{2}) \cdot n$ and such that

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

**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$. If there exist two tours visiting at
most $k/2$ points each, we may combine them into a single tour, thus 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=1}^{q} |W_i| > \left( (\lambda + \epsilon) \sum_{i=1}^{q} m_i \right) - q = (\lambda + \epsilon) \cdot n - q > \left( \lambda + \frac{\epsilon}{2} \right) \cdot n$$

and

$$\sum_{i=1}^{q} \mathrm{cost}(T_i) \ge \sum_{i=1}^{q} 2 \left( L_i - \frac{\lambda + \epsilon}{1 - \lambda - \epsilon} \cdot \Delta_i \right) + \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right). \quad (18)$$

On the other hand, we trivially have

$$\sum_{i=1}^{q} \mathrm{cost}(T_i) \ge \sum_{i=1}^{q} 2(L_i + \Delta_i). \quad (19)$$

Summing Equation (18) with coefficient $(1 - \lambda - \epsilon)$ and Equation (19) with coefficient $(\lambda + \epsilon)$, we have:

$$\mathrm{OPT} = \sum_{i=1}^{q} \mathrm{cost}(T_i) \ge \left( \sum_{i=1}^{q} 2L_i \right) + (1 - \lambda - \epsilon) \left( \sum_{x \in U} \delta(x, U \setminus \{x\}) \right).$$

Observe that

$$\sum_{i=1}^{q} 2L_i = \sum_{i=1}^{q} \sum_{x \in T_i} \frac{2\ell(x)}{m_i} \ge \sum_{i=1}^{q} \sum_{x \in T_i} \frac{2\ell(x)}{k} = \sum_{x \in V} \frac{2\ell(x)}{k} = \mathrm{rad}.$$

The Lemma follows.

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

## 4.2 Probabilistic Analysis

The following result suggests that the closest point distance follows the weak law of large numbers. It is a corollary of Theorem 2.4 in [22].

**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 in $[0, 1]^2$. Then, given any bounded function $\phi: [0, \infty] \to [0, \infty)$, we have:

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

**Remark 13.** To derive Lemma 12 from 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].

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 14.** Let $V$ be a set of $n$ i.i.d. uniform random points in $[0, 1]^2$. 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} \cdot \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_P$ from Lemma 12. By definition of the Poisson point process, the probability $g(r)$ of the event $\delta_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} \cdot \ln \frac{1}{1-\lambda}}$. We apply Lemma 12 with $\phi$ equals $\phi_1$, the indicator function of whether $r \le r_0$. Observing that $\sum_{x \in V} \phi_1(\sqrt{n} \cdot \delta(x, V \setminus \{x\})) = |Z|$, we have

$$ \lim_{n \to \infty} \frac{|Z|}{n} = \mathbb{E}[\phi_1(\delta_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\}) \ge \sum_{x \in Z} \delta(x, V \setminus \{x\}), \quad \text{a.a.s.} \qquad (20) $$

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} $$

We apply Lemma 12 with $\phi = \phi_2$. Observing that $\sum_{x \in V} \phi_2(\sqrt{n} \cdot \delta(x, V \setminus \{x\})) = \sum_{x \in Z} \sqrt{n} \cdot \delta(x, V \setminus \{x\})$, we have

$$ \lim_{n \to \infty} \frac{1}{n} \sum_{x \in Z} \sqrt{n} \cdot \delta(x, V \setminus \{x\}) = \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 (21) $$

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_11.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(\sqrt{n})$, for any $\epsilon > 0$, ITP($T$) < $(1 + \epsilon)\text{OPT}$ a.a.s. according to [15], which implies the claim. In the following, we assume that $k = \Omega(\sqrt{n})$.

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 14 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}. $$

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 (22) $$

Note that the coefficient of $\sqrt{n}$ in Equation (22) must be positive, because ITP($T$) $\ge \text{OPT}$. 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 (22) 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$. Therefore, a.a.s.,

$$ \frac{\text{ITP}(T)}{\text{OPT}} < \alpha + 0.915. $$

This completes the proof.
<figure><img src="image_12.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>

**Acknowledgements.**

We want to thank the anonymous reviewers for their valuable comments, which improved
the writing of the paper.

**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.

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 routing 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.