# Capacitated Vehicle Routing in Graphic Metrics

Tobias Mömke Partially supported by DFG Grant 439522729 (Heisenberg-Grant) and
DFG Grant 439637648 (Sachbeihilfe). University of Augsburg, Germany
<EMAIL_ADDRESS>Hang Zhou Partially supported by Hi! PARIS
Grant “Efficiency in Algorithms”. École Polytechnique, IP Paris, France
<EMAIL_ADDRESS>
###### Abstract

We study the _capacitated vehicle routing problem in graphic metrics (graphic
CVRP)_. Our main contribution is a new lower bound on the cost of an optimal
solution. For graphic metrics, this lower bound is tight and significantly
stronger than the well-known bound for general metrics. The proof of the new
lower bound is simple and combinatorial. Using this lower bound, we analyze
the approximation ratio of the classical iterated tour partitioning algorithm
combined with the TSP algorithms for graphic metrics of Christofides [1976],
of Mömke-Svensson [JACM 2016], and of Sebő-Vygen [Combinatorica 2014]. In
particular, we obtain a 1.95-approximation for the graphic CVRP.

##  1 Introduction

Given a metric space with a set of $n$ _terminals_ , a _depot_ , and an
integer _tour capacity_ $k$, the _capacitated vehicle routing problem (CVRP)_
asks for a minimum length collection of tours starting and ending at the depot
such that the number of terminals covered by each tour is at most $k$ and
those tours together cover all terminals.

The CVRP was introduced by Dantzig and Ramser in 1959 [DR59]. It is a
generalization of the _traveling salesman problem (TSP)_ and is one of the
most studied problems in Operations Research. Books have been dedicated to
vehicle routing problems, e.g., [TV02, GRW08, CL12, AGM16]. Yet, these
problems remain challenging, both from a practical and a theoretical
perspective.

The most popular polynomial-time approximation for the CVRP is a _simple_
algorithm, called _iterated tour partitioning (ITP)_. The ITP algorithm was
introduced in 1985 by Haimovich and Rinnooy Kan [HR85]. Altinkemer and Gavish
[AG90] showed that, in general metric spaces, the approximation ratio of the
ITP algorithm is at most $1+\left(1-\frac{1}{k}\right)\alpha$, where
$\alpha\geq 1$ is the approximation ratio of a TSP algorithm. Bompadre, Dror,
and Orlin [BDO06] improved this bound to
$1+\left(1-\frac{1}{k}\right)\alpha-\Omega\left(\frac{1}{k^{3}}\right)$. The
ratio for the CVRP in general metric spaces was recently improved by Blauth,
Traub, and Vygen [BTV22] to $1+\alpha-\epsilon$, where $\epsilon$ is at least
$\frac{1}{3000}$. Additionally, the best-to-date approximation ratio $\alpha$
for the TSP in general metrics is $1.5-10^{-36}$ by Karlin, Klein, and Oveis
Gharan [KKO21], improving upon the ratio of $1.5$ from Christofides [Chr76]
and Serdyukov [Ser78, vBS20]. Consequently, the best-to-date approximation
ratio for the metric CVRP stands at roughly $2.5-10^{-36}-\frac{1}{3000}$.

In this work, we focus on _graphic_ metrics, where the distance between two
vertices is the length (i.e., number of edges) of a shortest path in a given
unweighted graph.111Technically, each edge in the given graph has a cost of
one and forming a shortest path metric introduces new edges of larger costs.
For TSP and CVRP, however, we may assume without loss of generality that such
edges are replaced by a shortest path of cost-one edges. When referring to an
edge, we therefore always refer to an edge in the _original_ graph. For
further details we refer to the excellent survey of Vygen [Vyg12].  The
graphic TSP has attracted much attention. It captures the difficulty of the
metric TSP in the sense that it is APX hard [GKP95] and the lower bound
$\frac{4}{3}$ on the integrality gap of the Held-Karp relaxation for the
metric TSP is established using an instance of the graphic TSP, see, e.g.,
[Vyg12]. Oveis Gharan, Saberi, and Singh [OSS11] gave the first approximation
algorithm with ratio strictly better than 1.5 for the graphic TSP. Mömke and
Svensson [MS16] obtained a 1.461-approximation for the graphic TSP by
introducing the powerful idea of _removable pairings_. Mucha [Muc14] improved
the analysis of [MS16] to achieve an approximation ratio of
$\frac{13}{9}\approx 1.444$. The best-to-date approximation for the graphic
TSP is due to Sebő and Vygen [SV14], who gave an elegant 1.4-approximation
algorithm using a special kind of ear-decomposition.

We study the capacitated vehicle routing problem in _graphic_ metrics, called
the _graphic CVRP_. The graphic CVRP is a generalization of the graphic TSP.
Combining the graphic TSP algorithm of Sebő and Vygen [SV14] and the algorithm
of Blauth, Traub, and Vygen [BTV22] for the CVRP in general metrics, the best-
to-date approximation ratio for the graphic CVRP stands at roughly
$2.4-\frac{1}{3000}$. In this work, we reduce the approximation ratio for the
graphic CVRP to 1.95.

|  _general_ metrics |  _graphic_ metrics
---|---|---
TSP |  $1.5-10^{-36}$ [KKO21] | 1.4 [SV14]
CVRP |  $2.5-10^{-36}-\frac{1}{3000}$ [BTV22] | 1.95 [this work]

###  1.1 Our Results

Our main result depends on the standard definition of the _radius cost_
introduced by Haimovich and Rinnooy Kan [HR85].

######  Definition 1 (radius cost, [HR85]).

Let $V$ be a set of terminals and let $O$ be the depot. For every vertex $v\in
V$, let $\mathrm{dist}(v)$ denote the $v$-to-$O$ distance in the graph. Let
$\mathrm{rad}$ denote the _radius cost_ , defined by
$\mathrm{rad}=\frac{2}{k}\sum_{v\in V}\mathrm{dist}(v).$

Let $\mathrm{opt}$ denote the cost of an optimal solution to the graphic CVRP.
It is well-known that $\mathrm{opt}\geq\mathrm{rad}$ in general metrics
[HR85].

Our main technical contribution is a new lower bound on $\mathrm{opt}$ in
graphic metrics, stated in the following Structure Theorem (Theorem 2). The
new lower bound is tight in graphic metrics, see Fig. 1. It is significantly
stronger than the known lower bound stated above. The proof of the new lower
bound, in Section 3, is simple and combinatorial.

######  Theorem 2 (Structure Theorem).

Consider the graphic CVRP with a set $V$ of $n$ terminals, a depot $O$, and a
tour capacity $k$. We have

$\mathrm{opt}\geq\mathrm{rad}+\frac{n}{2}-\frac{n}{2k^{2}}.$

The Structure Theorem implies easily the following theorem on the
approximation ratio of the classical iterated tour partitioning algorithm for
the graphic CVRP. The proof of Theorem 3 is in Section 4.

######  Theorem 3.

Consider the graphic CVRP with a set $V$ of $n$ terminals, a depot $O$, and an
arbitrary tour capacity $k$. Let $S$ be a traveling salesman tour on
$V\cup\\{O\\}$ of cost at most $\beta\cdot
n+\gamma\cdot\mathrm{opt}_{\mathrm{TSP}}$ with $\beta\geq\frac{1}{2}$ and
$\gamma\geq 0$, where $\mathrm{opt}_{\mathrm{TSP}}$ denotes the cost of an
optimal TSP tour. Then the iterated tour partitioning algorithm applied on $S$
yields a $\left(\beta+\gamma+\frac{1}{2}\right)$-approximate solution to the
graphic CVRP.

As a consequence of Theorem 3, in Corollary 4 we bound the approximation ratio
of the iterated tour partitioning algorithm combined with the TSP algorithms
for graphic metrics of Christofides [Chr76], of Mömke-Svensson [MS16], and of
Sebő-Vygen [SV14].

Figure 1:  A tight instance for the lower bound in the Structure Theorem
(Theorem 2). Let $k$ be an odd integer. Let $n$ be a multiple of $k$. The
graph consists of $\frac{n}{k}$ cycles going through the depot (the central
black node), each visiting exactly $k$ terminals. (In the example, $k=13$ and
$n=52$, and the graph consists of 4 cycles.) Each cycle consists of $k+1$
edges, so the cost $\mathrm{opt}$ of an optimal solution equals
$(k+1)\cdot\frac{n}{k}=n+\frac{n}{k}$. At the same time, a simple calculation
gives $\mathrm{rad}=\frac{n}{2}+\frac{n}{k}+\frac{n}{2k^{2}}$. Thus
$\mathrm{rad}+\frac{n}{2}-\frac{n}{2k^{2}}=n+\frac{n}{k}$. Hence the lower
bound in the Structure Theorem is tight.

######  Corollary 4.

Consider the graphic CVRP with a set $V$ of terminals, a depot $O$, and an
arbitrary tour capacity $k$. We have:

  1. 1.

Let $S_{1}$ be a traveling salesman tour on $V\cup\\{O\\}$ computed by the
Christofides algorithm [Chr76]. The iterated tour partitioning algorithm
applied on $S_{1}$ yields a 2-approximate solution.

  2. 2.

Let $S_{2}$ be a traveling salesman tour on $V\cup\\{O\\}$ that is the better
one of the two solutions computed by the Mömke-Svensson algorithm [MS16] and
the Christofides algorithm. The iterated tour partitioning algorithm applied
on $S_{2}$ yields a $\left(2-\frac{1}{24}\right)$-approximate solution.

  3. 3.

Let $S_{3}$ be a traveling salesman tour on $V\cup\\{O\\}$ that is the better
one of the two solutions computed by the Sebő-Vygen algorithm [SV14] and the
Christofides algorithm. The iterated tour partitioning algorithm applied on
$S_{3}$ yields a $1.95$-approximate solution.

To prove Corollary 4, the requirement $\beta\geq\frac{1}{2}$ is crucial in the
application of Theorem 3. Intuitively, the threshold $\frac{1}{2}$ comes from
the additive term $\frac{n}{2}$ in the Structure Theorem. For the Christofides
algorithm [Chr76], the requirement $\beta\geq\frac{1}{2}$ follows immediately
since in a graph with $n+1$ vertices the algorithm combines a spanning tree of
cost exactly $n$ with a matching of cost at most
$\frac{1}{2}\cdot\mathrm{opt}_{\mathrm{TSP}}$. For the Mömke-Svensson
algorithm [MS16] we may assume $\beta=\frac{1}{3}$, see Lemma 12; and for the
Sebő-Vygen algorithm [SV14] we may assume $\beta=0$, see Lemma 13. Comparing
their solutions with the solution of the Christofides algorithm and returning
the better of the solutions lead to $\beta\geq\frac{1}{2}$. The proof of
Corollary 4 is in Section 5.

######  Remark 5.

In Corollary 4, we analyze the Christofides algorithm but not the algorithm of
Karlin, Klein, and Oveis Gharan [KKO21], because of the simplicity of the
Christofides algorithm, and also because the algorithm in [KKO21] requires
computing a random spanning tree whose cost might be greater than $n$ due to
multiple edges.

Also note that the algorithm of Blauth, Traub, and Vygen [BTV22] does not seem
to yield an improved approximation for the graphic CVRP, because worst-case
instances of the ITP algorithm for graphic metrics are different from those
for general metrics.

#### Open Questions.

In our work, we obtain an approximation for the graphic CVRP of ratio $1.95$.
To that end, we combine the Sebő-Vygen algorithm [SV14], the Christofides
algorithm [Chr76], and the iterated tour partitioning algorithm. The main open
question to improve upon the 1.95 factor for the graphic CVRP. In particular,
it is an interesting open question to analyze the cost of the solution
computed by the Sebő-Vygen algorithm in terms of the number of vertices, which
might lead to an improvement over the 1.95 factor.

###  1.2 Related Work

#### Graphic TSP.

Besides the classical version of the graphic TSP mentioned previously, the
_$s$ -$t$-path_ version of the graphic TSP has also been well-studied [SV14,
MS16, Muc14, AKS15, Gao13, TV18, TVZ20], with the best-to-date approximation
ratio being $1.4+\epsilon$ due to Traub, Vygen, and Zenklusen [TVZ20].

Special cases of the graphs have been studied for the graphic TSP, e.g., cubic
graphs [GLS05, AGG18, BSvdSS14, MS16, CLS15, DL18, DKM17], cubic bipartite
graphs [KR16, vZ18], graphs of degree at most $3$ and claw-free graphs [MS16],
and graphs of degree at most $4$ [New20].

#### CVRP in Other Metrics.

The CVRP has been extensively studied in other metrics: trees and bounded
treewidth [MZ22a, JS22, BP19, Bec18, AKK01], Euclidean [HR85, AKTT97, ACL10,
DM15, JS22], planar and bounded-genus graphs [BKS17, BKS19, CFKL20], graphs of
bounded highway dimension [BKS18], and minor-free graphs [CFKL20].

#### CVRP with Arbitrary Unsplittable Demands

A natural way to generalize the unit demand version of the CVRP is to allow
terminals to have arbitrary unsplittable demands, which is called the
“unsplittable” version of the CVRP. The first constant-factor approximation
algorithm for the unsplittable CVRP in general metrics is due to Altinkemer
and Gavish [AG87] and has a ratio of $2+\alpha$, where $\alpha$ is the
approximation ratio of a TSP algorithm. The approximation ratio for the
unsplittable CVRP was only recently improved to $2+\alpha-2\epsilon$ by
Blauth, Traub, and Vygen [BTV22], where $\epsilon$ is at least
$\frac{1}{3000}$. Very recently, Friggstad et al. [FMRS22] further improved
the ratio to roughly $\ln 2+\alpha+1+\epsilon$ for any constant $\epsilon>0$.
This problem has also been studied on trees [MZ22b] and in the Euclidean space
[GMZ22].

#### Iterated Tour Partitioning.

The _iterated tour partitioning (ITP)_ algorithm is the most popular
polynomial-time approximation for the CVRP, and is very simple. 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 terminals 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 [HR85] and Altinkemer and Gavish [AG90] in the
1980s.

The approximation ratio of the ITP algorithm has been well-studied, and bounds
on the ratio have been utilized in the design of approximation algorithms,
see, e.g., [BDO06]. Li and Simchi-Levi [LSL90] showed that the ITP algorithm
cannot lead to a better-than $(2-\frac{1}{k})$-approximation in general
metrics. Blauth, Traub, and Vygen [BTV22] exploited properties of tight
instances for the ITP algorithm, and used those properties to design the best-
to-date approximation algorithm for the metric CVRP. The performance of the
ITP algorithm has also been studied in the special case when the terminals are
uniform random points in the Euclidean plane [BDO07, MZ21].

Because of its simplicity, the ITP algorithm is versatile and has been adapted
to vehicle routing problems in other settings, e.g., with pick-up and delivery
services [Mos98], or under the constraints on the total distance traveled by
each vehicle [LSLD92].

##  2 Preliminaries

In this section, we introduce some notations and we formally define the
problem.

Let $G=(V\cup\\{O\\},E)$ be a connected, unweighted, and undirected graph,
where $V$ is a set of _terminals_ , vertex $O$ is the _depot_ , and $E$ is the
set of edges. Let $n$ denote the number of terminals in $V$. Let $V(G)$ denote
$V\cup\\{O\\}$. For each $v\in V$, let $\mathrm{dist}(v)$ denote the number of
edges on a $v$-to-$O$ shortest path in $G$. A _tour_ $T$ in $G$ is a path
$z_{1}z_{2}\dots z_{p}$ for some $p\in\mathbb{N}$ such that $z_{i}\in V(G)$
for each $i\in[1,p]$; $z_{1}=z_{p}=O$; and $(z_{i},z_{i+1})\in E$ for each
$i\in[1,p-1]$. The _cost_ of the tour $T$, denoted by $\mathrm{cost}(T)$, is
the number of edges on that tour, i.e., $\mathrm{cost}(T)=p-1$. Each terminal
has _unit demand_ , which must be covered by a single tour. Let $k\in[1,n]$ be
an integer _tour capacity_ , i.e., each tour can cover the demand of at most
$k$ terminals.

######  Definition 6 (graphic CVRP).

An instance of the _capacitated vehicle routing problem in graphic metrics
(graphic CVRP)_ consists of

  * •

a connected, unweighted, and undirected graph $G=(V\cup\\{O\\},E)$ where $V$
is a set of $n$ _terminals_ and $O$ is the _depot_ ;

  * •

a positive integer _tour capacity_ $k$ such that $k\in[1,n]$.

A feasible solution is a set of tours such that

  * •

each tour starts and ends at $O$,

  * •

each tour covers the demand of at most $k$ terminals,

  * •

the demand of each terminal is covered by one tour.

The goal is to find a feasible solution such that the total cost of the tours
is minimum.

Let $\mathrm{OPT}$ denote an optimal solution to the graphic CVRP, and let
$\mathrm{opt}$ denote the cost of $\mathrm{OPT}$.

##  3 Proof of the Structure Theorem (Theorem 2)

In this section, we prove the Structure Theorem (Theorem 2). The key in the
analysis is the following Structure Lemma.

######  Lemma 7 (Structure Lemma).

Let $T:=z_{1}z_{2}\dots z_{p}$ for some $p\in\mathbb{N}$ be a tour in
$\mathrm{OPT}$. Let $U\subseteq V$ denote the set of terminals whose demands
are covered by $T$. Let $D$ denote $\sum_{v\in U}\mathrm{dist}(v)$. Then

$\mathrm{cost}(T)\geq\frac{2D}{|U|}+\frac{|U|}{2}-\frac{1}{2|U|}.$

In Section 3.1, we show how the Structure Lemma implies the Structure Theorem,
and in Section 3.2, we prove the Structure Lemma.

###  3.1 Using the Structure Lemma to prove the Structure Theorem

Let $T_{1},\dots,T_{\ell}$ denote the tours in $\mathrm{OPT}$ for some
$\ell\geq 1$. For each $i\in[1,\ell]$, let $U_{i}\subseteq V$ denote the set
of terminals whose demands are covered by $T_{i}$. Let $D_{i}$ denote
$\sum_{v\in U_{i}}\mathrm{dist}(v)$. We apply the Structure Lemma (Lemma 7) on
$T_{i}$ and obtain

$\mathrm{cost}(T_{i})\geq\frac{2D_{i}}{|U_{i}|}+\frac{|U_{i}|}{2}-\frac{1}{2|U_{i}|}.$

Summing over all tours $T_{i}$ and noting that
$\displaystyle\sum_{i=1}^{\ell}|U_{i}|=n$, we have

$\mathrm{opt}=\sum_{i=1}^{\ell}\mathrm{cost}(T_{i})\geq\frac{n}{2}+\sum_{i=1}^{\ell}\left(\frac{2D_{i}}{|U_{i}|}-\frac{1}{2|U_{i}|}\right).$

Define

$Z:=\sum_{i=1}^{\ell}\left(\frac{2D_{i}}{|U_{i}|}-\frac{1}{2|U_{i}|}\right)-\mathrm{rad}+\frac{n}{2k^{2}}.$

To show the claim in the Structure Theorem, it suffices to show that $Z$ is
non-negative. Using
$\displaystyle\mathrm{rad}=\frac{\sum_{i=1}^{\ell}2D_{i}}{k}$ and
$\displaystyle n=\sum_{i=1}^{\ell}|U_{i}|$, we have

$Z=\sum_{i=1}^{\ell}\left(\frac{2D_{i}}{|U_{i}|}-\frac{1}{2|U_{i}|}-\frac{2D_{i}}{k}+\frac{|U_{i}|}{2k^{2}}\right)=\sum_{i=1}^{\ell}\frac{2k(k-|U_{i}|)(2D_{i}-1)+(k-|U_{i}|)^{2}}{2k^{2}|U_{i}|}\geq
0,$

where the inequality follows from $|U_{i}|\leq k$ and $D_{i}\geq 1$ (since
$\mathrm{dist}(v)\geq 1$ for each $v\in U_{i}$).

This completes the proof of the Structure Theorem (Theorem 2).

###  3.2 Proof of the Structure Lemma (Lemma 7)

Let $W$ be a multi-set of terminals defined by

$W:=\\{z_{i}\mid i\in[1,p]\text{ and }z_{i}\neq O\\}.$

Let $R:=\max_{v\in W}\mathrm{dist}(v)$. Let $\Delta:=R-\frac{D}{|U|}$. It is
easy to see that $\Delta\geq 0$.

If $\Delta\geq\frac{|U|}{4}$, we have

$\displaystyle\mathrm{cost}(T)\geq 2R\geq\frac{|U|}{2}+\frac{2D}{|U|},$

the claim follows.

In the rest of the proof, we assume that $\Delta<\frac{|U|}{4}$. Let
$j\in[1,p]$ be such that $\mathrm{dist}(z_{j})=R$, breaking ties arbitrarily.
We split the tour $T$ at vertex $z_{j}$, obtaining two paths
$P_{1}:=z_{1}z_{2}\dots z_{j}$ and $P_{2}:=z_{j}z_{j+1}\dots z_{p}$. For each
$i\in[1,R-1]$, let $x_{i}$ (resp. $y_{i}$) be a vertex on $P_{1}$ (resp.
$P_{2}$), such that $\mathrm{dist}(x_{i})$ (resp. $\mathrm{dist}(y_{i})$)
equals $i$; breaking ties arbitrarily. Let $A$ denote the multi-set of
vertices $\\{z_{j},x_{1},\dots,x_{R-1},y_{1},\dots,y_{R-1}\\}$. Observe that
$A\subseteq W$. Define another multi-set $B:=W\setminus A$. Let
$U_{A}\subseteq U$ denote the set of vertices $u\in U$ such that $u$ has at
least one occurrence in $A$. Let $U_{B}:=U\setminus U_{A}$. Observe that each
element in $U_{B}$ has at least one occurrence in $B$, so

$|B|\geq|U_{B}|=|U|-|U_{A}|.$

From the definition of $W$ and since $O\notin W$, we have

$\mathrm{cost}(T)\geq|W|+1=|A|+|B|+1=2\cdot R+|B|.$

Noting that $R=\frac{D}{|U|}+\Delta$, we have

$\mathrm{cost}(T)\geq\frac{2D}{|U|}+2\Delta+|U|-|U_{A}|.$ (1)

To lower bound $\mathrm{cost}(T)$, we upper bound $|U_{A}|$ in the following
lemma, whose proof is elementary.

######  Lemma 8.

$|U_{A}|\leq\sqrt{4|U|\cdot\Delta+1}$.

###### Proof.

First, consider the case when $|U_{A}|$ is even. Suppose $|U_{A}|=2m$ for some
$m\in\mathbb{N}$. Since $U_{A}\subseteq A$ and using the definition of $A$, we
have

$\sum_{v\in U_{A}}\mathrm{dist}(v)\leq
R+2(R-1)+2(R-2)+\cdots+2(R-m+1)+(R-m)=2m\cdot R-m^{2}.$

Since $\mathrm{dist}(v)\leq R$ for each $v\in U_{B}\subseteq W$, we have

$\sum_{v\in U_{B}}\mathrm{dist}(v)\leq|U_{B}|\cdot R=(|U|-|U_{A}|)\cdot
R=|U|\cdot R-2m\cdot R.$

Thus

$D=\sum_{v\in U}\mathrm{dist}(v)\leq|U|\cdot R-m^{2}.$

Since $D=|U|\cdot(R-\Delta)$, we have

$m\leq\sqrt{|U|\cdot\Delta}.$

The claim follows since $|U_{A}|=2m$.

Next, consider the case when $|U_{A}|$ is odd. Suppose $|U_{A}|=2m+1$ for some
$m\in\mathbb{N}$. Since $U_{A}\subseteq A$ and using the definition of $A$, we
have

$\sum_{v\in U_{A}}\mathrm{dist}(v)\leq
R+2(R-1)+2(R-2)+\dots+2(R-m)=(2m+1)\cdot R-m(m+1).$

Since $\mathrm{dist}(v)\leq R$ for each $v\in U_{B}\subseteq W$, we have

$\sum_{v\in U_{B}}\mathrm{dist}(v)\leq|U_{B}|\cdot R=(|U|-|U_{A}|)\cdot
R=|U|\cdot R-(2m+1)\cdot R.$

Thus

$D=\sum_{v\in U}\mathrm{dist}(v)\leq|U|\cdot R-m(m+1).$

Since $D=|U|\cdot(R-\Delta)$, we have

$m\leq\frac{\sqrt{4|U|\cdot\Delta+1}-1}{2}.$

The claim follows since $|U_{A}|=2m+1$. ∎

From (1) and Lemma 8, we have

$\mathrm{cost}(T)\geq\frac{2D}{|U|}+2\Delta+|U|-\sqrt{4|U|\cdot\Delta+1}.$ (2)

To lower bound $\mathrm{cost}(T)$, we use the following simple fact.

######  Fact 9.

$2\Delta-\sqrt{4|U|\cdot\Delta+1}\geq-\frac{|U|}{2}-\frac{1}{2|U|}.$

###### Proof.

Define

$Y:=2\Delta-\sqrt{4|U|\cdot\Delta+1}+\frac{|U|}{2}+\frac{1}{2|U|}.$

It suffices to show that $Y\geq 0$. Let $t:=\sqrt{4|U|\cdot\Delta+1}$. Thus
$\displaystyle\Delta=\frac{t^{2}-1}{4|U|}$. We have

$Y=2\cdot\frac{t^{2}-1}{4|U|}-t+\frac{|U|}{2}+\frac{1}{2|U|}=\left(\frac{t}{\sqrt{2|U|}}-\sqrt{\frac{|U|}{2}}\right)^{2}\geq
0.$

∎

From (2) and 9, we conclude that

$\mathrm{cost}(T)\geq\frac{2D}{|U|}+\frac{|U|}{2}-\frac{1}{2|U|}.$

This completes the proof of the Structure Lemma (Lemma 7).

##  4 Proof of Theorem 3

Let $S$ be a traveling salesman tour on $V\cup\\{O\\}$. Let $\mathrm{ITP}(S)$
denote the cost of the solution computed by the iterated tour partitioning
algorithm applied on $S$. Altinkemer and Gavish [AG90] showed the following
bound.

######  Lemma 10 ([AG90]).

$\mathrm{ITP}(S)\leq\mathrm{rad}+\left(1-\frac{1}{k}\right)\cdot\mathrm{cost}(S).$

From Lemma 10 and the assumption on $\mathrm{cost}(S)$, we have

$\displaystyle\mathrm{ITP}(S)$
$\displaystyle\leq\mathrm{rad}+\left(1-\frac{1}{k}\right)\cdot\left(\beta\cdot
n+\gamma\cdot\mathrm{opt}_{\mathrm{TSP}}\right)$
$\displaystyle=\left(\mathrm{rad}+\frac{n}{2}-\frac{n}{2k^{2}}\right)+\left(\beta-\frac{1}{2}+\frac{1}{2k^{2}}-\frac{\beta}{k}\right)\cdot
n+\left(1-\frac{1}{k}\right)\cdot\gamma\cdot\mathrm{opt}_{\mathrm{TSP}}.$

From the Structure Theorem (Theorem 2),

$\mathrm{rad}+\frac{n}{2}-\frac{n}{2k^{2}}\leq\mathrm{opt}.$

Since $\beta\geq\frac{1}{2}$ and $k\geq 1$, we have

$\frac{1}{2k^{2}}-\frac{\beta}{k}\leq 0.$

Combining, we have

$\mathrm{ITP}(S)\leq\mathrm{opt}+\left(\beta-\frac{1}{2}\right)\cdot
n+\gamma\cdot\mathrm{opt}_{\mathrm{TSP}}\leq\left(\beta+\gamma+\frac{1}{2}\right)\cdot\mathrm{opt},$

where the last inequality follows from $n\leq\mathrm{opt}$ and
$\mathrm{opt}_{\mathrm{TSP}}\leq\mathrm{opt}$.

This completes the proof of Theorem 3.

##  5 Proof of Corollary 4

In this section, we analyze the approximation ratios for the graphic CVRP
using known algorithms for the graphic TSP.

######  Lemma 11 (adaptation from Christofides [Chr76]).

Given a connected graph $G$ with $n+1$ vertices, the Christofides algorithm
computes a traveling salesman tour of cost at most
$n+\frac{1}{2}\cdot\mathrm{opt}_{\mathrm{TSP}}$.

###### Proof.

Christofides algorithm [Chr76] computes a minimum spanning tree $T$ and adds a
minimum-cost perfect matching $M$ of the odd degree vertices as parity
correction. Since $G$ is connected, the cost of $T$ is exactly $n$. By
[Chr76], the cost of $M$ is at most
$\frac{1}{2}\cdot\mathrm{opt}_{\mathrm{TSP}}$. The claim follows. ∎

The first claim in Corollary 4 follows from Theorems 3 and 11.

######  Lemma 12 (adaptation from Mucha [Muc14] and Mömke and Svensson
[MS16]).

Given a connected graph $G$ with $n+1$ vertices, the Mömke-Svensson algorithm
computes a traveling salesman tour of cost at most
$\frac{n}{3}+\frac{10}{9}\cdot\mathrm{opt}_{\mathrm{TSP}}$.

###### Proof.

Letting $n^{\prime}=n+1$, it suffices to show that, given a connected graph
$G$ with $n^{\prime}$ vertices, the Mömke-Svensson algorithm computes a
traveling salesman tour of cost at most
$\frac{n^{\prime}}{3}+\frac{10}{9}\cdot\mathrm{opt}_{\mathrm{TSP}}-\frac{2}{3}$.

The proof is by induction. Let $X$ denote the cost of the traveling salesman
tour computed by the Mömke-Svensson algorithm.

First, consider the case when $G$ is $2$-vertex-connected. The Mömke-Svensson
algorithm computes some _circulation_ of cost $c$ and they show in Lemma 4.2
of [MS16]:

$X\leq\frac{4}{3}\cdot n^{\prime}+\frac{2}{3}\cdot c-\frac{2}{3}.$

Mucha shows in Corollary 1 of [Muc14]:

$c\leq\frac{5}{3}\cdot\text{opt}_{\mathrm{TSP}}-\frac{3}{2}\cdot n^{\prime}.$

The claim follows.

Next, consider the case when $G$ is not $2$-vertex-connected. There is a
vertex $v$ such that removing $v$ disconnects the graph. We therefore identify
two subgraphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ such that
$V_{1}\cup V_{2}=V(G)$, $V_{1}\cap V_{2}=\\{v\\}$ and $E=E_{1}\cup E_{2}$.
Observe that $|V_{1}|+|V_{2}|=n^{\prime}+1.$ From the induction, the claim
holds for both $G_{1}$ and $G_{2}$. Let $\text{opt}_{1}$ (resp.
$\text{opt}_{2}$) be the optimal cost of a TSP solution in $G_{1}$ (resp.
$G_{2}$). Then
$\mathrm{opt}_{\mathrm{TSP}}=\mathrm{opt}_{1}+\mathrm{opt}_{2}$. We have

$X\leq\left(\frac{|V_{1}|}{3}+\frac{10}{9}\cdot\text{opt}_{1}-\frac{2}{3}\right)+\left(\frac{|V_{2}|}{3}+\frac{10}{9}\cdot\text{opt}_{2}-\frac{2}{3}\right)=\frac{n^{\prime}+1}{3}+\frac{10}{9}\cdot\mathrm{opt}_{\mathrm{TSP}}-\frac{4}{3},$

which yields the claim. ∎

From Lemmas 11 and 12, and since $S_{2}$ is the better one of the two
solutions computed by the Christofides algorithm and by the Mömke-Svensson
algorithm, we have

$\mathrm{cost}(S_{2})\leq\frac{1}{4}\cdot\left(n+\frac{1}{2}\cdot\mathrm{opt}_{\mathrm{TSP}}\right)+\frac{3}{4}\cdot\left(\frac{n}{3}+\frac{10}{9}\cdot\mathrm{opt}_{\mathrm{TSP}}\right)=\frac{1}{2}\cdot
n+\frac{23}{24}\cdot\mathrm{opt}_{\mathrm{TSP}}.$ (3)

The second claim in Corollary 4 follows from Theorem 3 and (3).

######  Lemma 13 (Sebő and Vygen [SV14]).

Given a connected graph $G$ with $n+1$ vertices, the Sebő-Vygen algorithm
computes a traveling salesman tour of cost at most
$\frac{7}{5}\cdot\mathrm{opt}_{\mathrm{TSP}}$.

From Lemmas 11 and 13, and since $S_{3}$ is the better one of the two
solutions computed by the Christofides algorithm and by the Sebő-Vygen
algorithm, we have

$\mathrm{cost}(S_{3})\leq\frac{1}{2}\cdot\left(n+\frac{1}{2}\cdot\mathrm{opt}_{\mathrm{TSP}}\right)+\frac{1}{2}\cdot\left(\frac{7}{5}\cdot\mathrm{opt}_{\mathrm{TSP}}\right)=\frac{1}{2}\cdot
n+\frac{19}{20}\cdot\mathrm{opt}_{\mathrm{TSP}}.$ (4)

The last claim in Corollary 4 follows from Theorem 3 and (4).

#### Acknowledgments.

We thank Zipei Nie for helpful discussions in mathematics.

## References

  * [ACL10] 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.
  * [AG87] K. Altinkemer and B. Gavish.  Heuristics for unequal weight delivery problems with a fixed error guarantee.  Operations Research Letters, 6(4):149–158, 1987.
  * [AG90] K. Altinkemer and B. Gavish.  Heuristics for delivery problems with constant error guarantees.  Transportation Science, 24(4):294–297, 1990.
  * [AGG18] N. Agarwal, N. Garg, and S. Gupta.  A 4/3-approximation for TSP on cubic 3-edge-connected graphs.  Oper. Res. Lett., 46(4):393–396, 2018.
  * [AGM16] S. P. Anbuudayasankar, K. Ganesh, and S. Mohapatra.  Models for practical routing problems in logistics.  Springer, 2016.
  * [AKK01] T. Asano, N. Katoh, and K. Kawashima.  A new approximation algorithm for the capacitated vehicle routing problem on a tree.  Journal of Combinatorial Optimization, 5(2):213–231, 2001.
  * [AKS15] H. An, R. D. Kleinberg, and D. B. Shmoys.  Improving Christofides’ algorithm for the $s$-$t$ path TSP.  Journal of the ACM (JACM), 62(5):34:1–34:28, 2015.
  * [AKTT97] 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 ACM Symposium on Theory of Computing (STOC), pages 275–283, 1997\.
  * [BDO06] A. Bompadre, M. Dror, and J. B. Orlin.  Improved bounds for vehicle routing solutions.  Discrete Optimization, 3(4):299–316, 2006.
  * [BDO07] 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.
  * [Bec18] A. Becker.  A tight 4/3 approximation for capacitated vehicle routing in trees.  In Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM), volume 116, pages 3:1–3:15, 2018.
  * [BKS17] A. Becker, P. N. Klein, and D. Saulpic.  A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs.  In 25th Annual European Symposium on Algorithms (ESA), 2017.
  * [BKS18] A. Becker, P. N. Klein, and D. Saulpic.  Polynomial-time approximation schemes for $k$-center, $k$-median, and capacitated vehicle routing in bounded highway dimension.  In 26th Annual European Symposium on Algorithms (ESA), 2018.
  * [BKS19] A. Becker, P. N. Klein, and A. Schild.  A PTAS for bounded-capacity vehicle routing in planar graphs.  In Workshop on Algorithms and Data Structures, pages 99–111. Springer, 2019.
  * [BP19] A. Becker and A. Paul.  A framework for vehicle routing approximation schemes in trees.  In Workshop on Algorithms and Data Structures, pages 112–125. Springer, 2019.
  * [BSvdSS14] S. C. Boyd, R. Sitters, S. van der Ster, and L. Stougie.  The traveling salesman problem on cubic and subcubic graphs.  Mathematical Programming, 144(1-2):227–245, 2014.
  * [BTV22] J. Blauth, V. Traub, and J. Vygen.  Improving the approximation ratio for capacitated vehicle routing.  Mathematical Programming (to appear), 2022.
  * [CFKL20] V. Cohen-Addad, A. Filtser, P. N. Klein, and H. Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  In Symposium on Foundations of Computer Science (FOCS), pages 589–600. IEEE, 2020.
  * [Chr76] N. Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
  * [CL12] T. G. Crainic and G. Laporte.  Fleet management and logistics.  Springer Science & Business Media, 2012.
  * [CLS15] J. R. Correa, O. Larré, and J. A. Soto.  TSP tours in cubic graphs: beyond 4/3.  SIAM J. Discret. Math., 29(2):915–939, 2015.
  * [DKM17] Z. Dvorák, D. Král, and B. Mohar.  Graphic TSP in cubic graphs.  In STACS, volume 66, pages 27:1–27:13, 2017.
  * [DL18] B. Duník and R. Lukotka.  Cubic TSP: a 1.3-approximation.  SIAM J. Discret. Math., 32(3):2094–2114, 2018.
  * [DM15] A. Das and C. Mathieu.  A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing.  Algorithmica, 73(1):115–142, 2015.
  * [DR59] G. B. Dantzig and J. H. Ramser.  The truck dispatching problem.  Management Science, 6(1):80–91, 1959.
  * [FMRS22] Z. Friggstad, R. Mousavi, M. Rahgoshay, and M. R. Salavatipour.  Improved Approximations for Capacitated Vehicle Routing with Unsplittable Client Demands.  In Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO, 2022.
  * [Gao13] Z. Gao.  An LP-based $\frac{3}{2}$-approximation algorithm for the $s$-$t$ path graph traveling salesman problem.  Oper. Res. Lett., 41(6):615–617, 2013.
  * [GKP95] M. Grigni, E. Koutsoupias, and C. H. Papadimitriou.  An approximation scheme for planar graph TSP.  In FOCS, pages 640–645. IEEE, 1995.
  * [GLS05] D. Gamarnik, M. Lewenstein, and M. Sviridenko.  An improved upper bound for the TSP in cubic 3-edge-connected graphs.  Oper. Res. Lett., 33(5):467–474, 2005.
  * [GMZ22] F. Grandoni, C. Mathieu, and H. Zhou.  Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+\epsilon)$-Approximation Algorithm.  arXiv preprint arXiv:2209.05520, 2022.
  * [GRW08] 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.
  * [HR85] M. Haimovich and A. H. G. Rinnooy Kan.  Bounds and heuristics for capacitated routing problems.  Mathematics of Operations Research, 10(4):527–542, 1985.
  * [JS22] A. Jayaprakash and M. R. Salavatipour.  Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 877–893, 2022.
  * [KKO21] A. R. Karlin, N. Klein, and S. Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 32–45, 2021.
  * [KR16] J. Karp and R. Ravi.  A $\frac{9}{7}$-approximation algorithm for graphic TSP in cubic bipartite graphs.  Discret. Appl. Math., 209:164–216, 2016.
  * [LSL90] 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.
  * [LSLD92] C. L. Li, D. Simchi-Levi, and M. Desrochers.  On the distance constrained vehicle routing problem.  Operations research, 40(4):790–799, 1992.
  * [Mos98] G. Mosheiov.  Vehicle routing with pick-up and delivery: tour-partitioning heuristics.  Computers & Industrial Engineering, 34(3):669–684, 1998.
  * [MS16] T. Mömke and O. Svensson.  Removing and adding edges for the traveling salesman problem.  Journal of the ACM (JACM), 63(1):1–28, 2016.
  * [Muc14] M. Mucha.  $\frac{13}{9}$-approximation for graphic TSP.  Theory of computing systems, 55(4):640–657, 2014.
  * [MZ21] C. Mathieu and H. Zhou.  Probabilistic analysis of Euclidean capacitated vehicle routing.  In International Symposium on Algorithms and Computation (ISAAC), page 43:1–43:16, 2021.
  * [MZ22a] C. Mathieu and H. Zhou.  A PTAS for capacitated vehicle routing on trees.  In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), page 95:1–95:20, 2022.
  * [MZ22b] C. Mathieu and H. Zhou.  A tight $(1.5+\epsilon)$-approximation for unsplittable capacitated vehicle routing on trees.  arXiv preprint arXiv:2202.05691, 2022.
  * [New20] A. Newman.  An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs.  SIAM J. Discret. Math., 34(1):865–884, 2020.
  * [OSS11] S. Oveis Gharan, A. Saberi, and M. Singh.  A randomized rounding approach to the traveling salesman problem.  In Symposium on Foundations of Computer Science (FOCS), pages 550–559. IEEE, 2011.
  * [Ser78] A. I. Serdyukov.  On some extremal walks in graphs (in Russian).  Upravlyaemye Sistemy, 17:76–79, 1978.
  * [SV14] A. Sebő and J. Vygen.  Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs.  Combinatorica, pages 1–34, 2014.
  * [TV02] P. Toth and D. Vigo.  The Vehicle Routing Problem.  SIAM, 2002.
  * [TV18] V. Traub and J. Vygen.  Beating the integrality ratio for $s$-$t$-tours in graphs.  In FOCS, pages 766–777. IEEE, 2018.
  * [TVZ20] V. Traub, J. Vygen, and R. Zenklusen.  Reducing path TSP to TSP.  In STOC, pages 14–27. ACM, 2020.
  * [vBS20] R. van Bevern and V. A. Slugina.  A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem.  Historia Mathematica, 53:118–127, 2020.
  * [Vyg12] J. Vygen.  New approximation algorithms for the TSP.  OPTIMA, 90:1–12, 2012.
  * [vZ18] A. van Zuylen.  Improved approximations for cubic bipartite and cubic TSP.  Math. Program., 172(1-2):399–413, 2018.