Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity

We use $G=(V\cup \{v_0\},E)$ to denote a complete graph, where the vertex $v_0$ represents the depot and vertices in $V$ represent customers. There is a non-negative weight function $w:E\to {ℝ}_{\ge 0}$ on the edges in $E$, which denotes the distance between two endpoints of the edge. The weight function $w$ is a metric function, i.e., it satisfies the symmetric and triangle inequality properties. For any weight function $w:X\to {ℝ}_{\ge 0}$, we extend it to subsets of $X$ by defining $w(Y)={\sum }_{x\in Y}w(x)$ for any $Y\subseteq X$. An itinerary is a walk starting and ending at vertex $v_0$. It can be partitioned into several minimal itineraries containing $v_0$, each of which is called a tour.

The Capacitated Vehicle Routing Problem (CVRP) can be described as follows.

We define three variants of the problem. If the demand of each customer must be delivered in one tour, we call it unsplittable CVRP. If the demand of a customer can be split into multiple tours, we call it splittable CVRP. If the demand of each customer is a unit, we call it unit-demand CVRP.

We make some assumptions which can be guaranteed by simple observations or polynomial-time reductions (see the full version of this paper).

For a customer with $d_i$ of the demand in splittable $k$-CVRP, we take it as $d_i$ customers with unit-demand. Then, we obtain an equivalent instance of unit-demand $k$-CVRP. By Assumption 2, splittable $k$-CVRP can be reduced to unit-demand $k$-CVRP in polynomial time.

Assumption 3 can be ensured by adding some dummy customers at the depot. It guarantees the existence of an optimal solution with a good structure. It will be helpful in our analysis. For unit-demand $k$-CVRP, such an itinerary consists of a set of $(k+1)$-cycles intersecting only at the depot.

The following notations are illustrated with the unit-demand case. Most of them will be used to establish some lower bounds for our problems.

• $\mathrm{■}$

  $I^{\ast }$: an optimal solution to our problem;

• $\mathrm{■}$

  $\mathrm{\Delta }$: the sum of the weight of the edges from the depot $v_0$ to the customer, i.e., ${\sum }_{v_i\in V}w(v_0,v_i)$;

• $\mathrm{■}$

  $H^{\ast }$: a minimum weight Hamiltonian cycle on $V\cup \{v_0\}$;

• $\mathrm{■}$

  $H_{CS}$: the Hamiltonian cycle on $V\cup \{v_0\}$ obtained by the Christofides-Serdyukov algorithm [9, 35];

• $\mathrm{■}$

  ${ℳ}^{\ast }$: a minimum weight perfect matching in $G[V]$;

• $\mathrm{■}$

  MST: the total weight of the edges in a minimum weight spanning tree in $G$;

• $\mathrm{■}$

  ${𝒞}^{\ast }$: a minimum weight cycle cover in $G[V]$;

• $\mathrm{■}$

  ${𝒞}_k^{\ast }$: a minimum weight $k$-cycle cover in $G[V]$;

• $\mathrm{■}$

  ${𝒞}_{modk}^{\ast }$: a minimum weight mod-$k$-cycle cover in $G[V]$.

For an instance $G=(V\cup \{v_0\},E)$ of splittable or unsplittable CVRP, we construct a corresponding unit-demand instance $G^{\prime }=(V^{\prime }\cup \{v_0\},E^{\prime })$ by replacing each customer with demand $d_i$ with $d_i$ unit-demand customers. By Assumption 2, this reduction can be done in polynomial time when $k=O(1)$. It is easy to observe that the optimal value in $G^{\prime }$ is at most the optimal value in $G$. Thus, for an instance $G$ of splittable or unsplittable CVRP, the lower bound computed in the unit-demand instance $G^{\prime }$ also constitutes a valid lower bound for $G$.

Although the above notations are defined for the unit-demand case, they can also be applied to the splittable and unsplittable cases. For an instance $G=(V\cup \{v_0\},E)$ of splittable or unsplittable CVRP, the above notations, including $\mathrm{\Delta }$, $H^{\ast }$, $H_{CS}$, ${ℳ}^{\ast }$, MST, ${𝒞}^{\ast }$, ${𝒞}_k^{\ast }$, and ${𝒞}_{modk}^{\ast }$, are defined based on the instance $G^{\prime }$.

Thus, in the splittable and unsplittable cases, $\mathrm{\Delta }$ becomes the sum of each customer’s demand multiplied by the weight of the edge from $v_0$ to the customer, i.e., ${\sum }_{v_i\in V}{d}_{i}w(v_0,v_i)$, ${𝒞}_k^{\ast }$ represents a minimum weight $k$-cycle cover in $G^{\prime }[V^{\prime }]$, and so on. Note that, for $H^{\ast }$, $H_{CS}$, and MST, there is no difference between $G$ and $G^{\prime }$, so we do not distinguish between them.

We also mention the following. A minimum weight perfect matching in a complete graph can be found in $O(n^3)$ time using classical algorithms [16, 27], although faster and simpler algorithms exist for other graphs; see, for example, Schrijver’s book [34]. A minimum weight spanning tree in a complete graph can be computed in $O(n^2)$ time using Prim’s algorithm [33], or in optimal time using the algorithm of Pettie and Ramachandran [32]. It is NP-hard to compute a minimum weight $k$-cycle cover for any $k\ge 3$ [26]. There exists an $O(n^2\log n)$-time 2-approximation algorithm for the minimum weight mod-$k$-cycle cover problem based on the primal-dual method [17]. Additionally, a minimum weight cycle cover can be computed via a reduction to the minimum weight perfect matching problem, for which more efficient algorithms are also known [20, 34]. These results will be used in our algorithms.

For an optimal itinerary $I^{\ast }$, the edges incident to $v_0$ in $I^{\ast }$ are called home-edges, and the set of home-edges of $I^{\ast }$ is denoted by $h(I^{\ast })$. We define $\chi$ as the proportion of the weight of home-edges in $I^{\ast }$, i.e., $\chi =\frac{w(h(I^{\ast }))}{w(I^{\ast })}$, where we assume $w(I^{\ast })\ne 0$ to exclude the trivial case.

Since $0\le \chi \le 1$, we have $\frac{k}{2}=(1+\frac{k-2}{2})\ge (\chi +\frac{k-2}{2})$, which proves the first inequality.

Now, we show the second inequality. By Assumption 3, $I^{\ast }$ consists of a set of $(k+1)$-cycles. We consider an arbitrary $(k+1)$-cycle $C=(v_0,v_1,\mathrm{\dots },v_k,v_0)$ in $I^{\ast }$. Since $k\ge 3$, the triangle inequality implies that $w(C)\ge 2w(v_0,v_i)$ for each $i\in \{2,3,\mathrm{\dots },k-1\}$. Thus, we have

Summing the above inequality over all cycles in $I^{\ast }$, we obtain

as desired. $◀$

For each tour in $I^{\ast }$, there are exactly two home-edges. We can obtain a spanning tree of the graph from $I^{\ast }$ by deleting the longer home-edge in each tour. Since $w(h(I^{\ast }))=\chi w(I^{\ast })$ by definition, the weight of this spanning tree is at least $w(I^{\ast })-\frac{1}{2}\chi w(I^{\ast })=(1-\frac{1}{2}\chi )w(I^{\ast })$, which is at least the weight of the minimum weight spanning tree. $◀$

Recall that $H_{CS}$ is obtained by the Christofides-Serdyukov algorithm.

By Lemmas 2, 4, and 5, we can obtain the following result.

We first show that there exists a $k$-cycle cover in $G[V]$ whose weight is at most $\min \{2(1-\chi ),1\}w(I^{\ast })$.

By Assumption 3, $I^{\ast }$ consists of a set of $(k+1)$-cycles. Consider an arbitrary $(k+1)$-cycle $C=(v_0,v_1,\mathrm{\dots },v_k,v_0)$ in $I^{\ast }$. Let $C^{\prime }=(v_1,\mathrm{\dots },v_k,v_1)$ be the $k$-cycle obtained by shortcutting $v_0$ from $C$. By the triangle inequality, we have $w(v_1,v_k)\le \min \{w(v_0,v_1)+w(v_0,v_k),w(C)-w(v_0,v_1)-w(v_0,v_k)\}$. Thus, we have $w(C^{\prime })=w(C)-w(v_0,v_1)-w(v_0,v_k)+w(v_1,v_k)\le \min \{w(C),2w(C)-2w(v_0,v_1)-2w(v_0,v_k)\}$. Note that the edges $(v_0,v_1)$ and $(v_0,v_k)$ are home-edges of the cycle $C$. By summing the above inequality over all cycles in $I^{\ast }$, we obtain the desired result.

Since ${𝒞}_k^{\ast }$ is the minimum weight $k$-cycle cover in $G[V]$, we have $w({𝒞}_k^{\ast })\le \min \{2(1-\chi ),1\}w(I^{\ast }).$ Moreover, since any $k$-cycle cover is a mod-$k$-cycle cover, and any mod-$k$-cycle cover is also a cycle cover, we have the relationship $w({𝒞}^{\ast })\le w({𝒞}_{modk}^{\ast })\le w({𝒞}_k^{\ast })$. $◀$

Since $H_{CS}$ is a $\frac{3}{2}$-approximate Hamiltonian cycle [9, 35], some papers [1, 19] used the inequalities $\mathrm{\Delta }\le \frac{k}{2}w(I^{\ast })$ and $w(H_{CS})\le \frac{3}{2}w(I^{\ast })$ in the analysis of ITP and UITP. However, if the upper bound of $\mathrm{\Delta }$ is tight, i.e., $\mathrm{\Delta }=\frac{k}{2}w(I^{\ast })$, we have $\chi =1$ by Lemma 3. In this case, by Lemma 6, we also have $w(H_{CS})\le w(I^{\ast })$. Therefore, our new lower bounds show that these two bounds cannot be tight simultaneously, indicating the potential for better approximation ratios. Besides, if $\chi =1$, by Lemma 7, we have $w({𝒞}_k^{\ast })=w({𝒞}_{modk}^{\ast })=w({𝒞}^{\ast })=0$. So, any $O(1)$-approximate cycle covers may outperform the optimal Hamiltonian cycle.

Before showing how these insights can lead to improved approximation ratios, we first review the ITP algorithms [1, 19] that operate with a Hamiltonian cycle, and then we will propose our EX-ITP algorithm, which works for any cycle cover.

The above two ITP algorithms are based on given Hamiltonian cycles. In fact, the requirement of Hamiltonian cycles is not necessary. We can replace the Hamiltonian cycle with a cycle cover.

Given any cycle cover $𝒞$ in the graph $G[V]$ or $G[V\cup \{v_0\}]$ (either containing the depot $v_0$ or not), for each cycle $C\in 𝒞$, we call the HR-ITP algorithm on it if $C$ does not contain the depot $v_0$, and call the AG-ITP algorithm on it if $C$ contains the depot $v_0$. By putting all toobtainher, we can obtain a feasible solution for $k$-CVRP. The quality of the solution is related to the cycle cover. We refer to this algorithm as the EX-ITP algorithm.

Define ${\mathrm{\Delta }}_C={\sum }_{v_i\in C}w(v_0,v_i)$. For the cycle $C\in 𝒞$ satisfying $v_0\in C$, the AG-ITP algorithm can generate an itinerary on $C$ with weight at most $(2/k){\mathrm{\Delta }}_C+(1-1/k)w(C)$. For each cycle $C\in 𝒞$ satisfying $v_0\notin C$, the HR-ITP algorithm can generate an itinerary on $C$ with weight at most $(2\lceil |C|/k\rceil /|C|){\mathrm{\Delta }}_C+(1-\lceil |C|/k\rceil /|C|)w(C)$.

By the triangle inequality, we have $w(C)\le 2{\mathrm{\Delta }}_C$. Then, for any $0\le x\le y$, we can obtain $2x{\mathrm{\Delta }}_C+(1-x)w(C)\le 2y{\mathrm{\Delta }}_C+(1-y)w(C)$. Since $2/k\le 2\lceil |C|/k\rceil /|C|\le 2g$, we have

Therefore, the itinerary on $C\in 𝒞$ has a weight of at most $2g{\mathrm{\Delta }}_C+(1-g)w(C)$.

Since ${\sum }_{C\in 𝒞}{\mathrm{\Delta }}_C=\mathrm{\Delta }$, EX-ITP outputs a solution with weight at most

as desired. $◀$

Intuitively, the value $1/g$ in Lemma 10 represents the maximum, over all cycles (excluding the depot), of the average number of customers per tour used to serve that cycle. Thus, a larger value of $g$ indicates that each tour serves fewer customers on average.

If the cycle cover $𝒞$ used in Lemma 10 satisfies $w(𝒞)\le \min \{2(1-\chi ),1\}w(I^{\ast })$, as in Lemma 7, and if $g\le 1/2$, we have the following corollary.

There are little improvements for 3-CVRP in the last 20 years. Only recently an improved result for the general weighted $k$-set cover problem [18] leads to the current best result for 3-CVRP. We show that we can easily improve the approximation ratio by using EX-ITP. Our algorithm computes a minimum weight cycle cover ${𝒞}^{\ast }$ in $G[V]$, and then calls EX-ITP on ${𝒞}^{\ast }$.

Since $|C|\ge 3$ for each cycle $C\in {𝒞}^{\ast }$, we have

Note that $w({𝒞}^{\ast })\le \min \{2(1-\chi ),1\}w(I^{\ast })$ by Lemma 7. Then, by Corollary 11, EX-ITP achieves an approximation ratio of at most $g(k-2)+1\le \frac{3}{2}$, where we have $\chi \ge \frac{1}{2}$ in the worst case. $◀$

The idea is similar. However, we will construct a good mod-2-cycle cover ${𝒞}_{mod2}$ on $V$, instead of using a minimum weight cycle cover ${𝒞}^{\ast }$ on $V$, and then call EX-ITP.

We compute the mod-2-cycle cover ${𝒞}_{mod2}$ in this way: first find a minimum weight perfect matching ${ℳ}^{\ast }$ in graph $G[V]$, find a minimum weight perfect matching ${ℳ}^{\ast \ast }$ in graph $G[V]\setminus {ℳ}^{\ast }$, and then let ${𝒞}_{mod2}={ℳ}^{\ast }\cup {ℳ}^{\ast \ast }$.

Note that ${𝒞}_{mod2}$ is a mod-2-cycle cover without 2-cycles since ${ℳ}^{\ast }$ and ${ℳ}^{\ast \ast }$ are two edge-disjoint perfect matchings in $G[V]$. Recall that ${𝒞}_4^{\ast }$ denotes a minimum weight 4-cycle cover in $G[V]$. We have the following result.

We first prove the following property.

For each 4-cycle $C=(v_1,v_2,v_3,v_4,v_1)\in {𝒞}_4^{\ast }$, we color its edges by considering three cases.

We color the edges $(v_1,v_2)$ and $(v_3,v_4)$ with blue and the edges $(v_1,v_4)$ and $(v_2,v_3)$ with red. Now, blue edges (resp., red edges) are vertex-disjoint.

We assume w.l.o.g. that $C\cap {ℳ}^{\ast }=\{(v_1,v_2)\}$. Then, we color the edges $(v_1,v_2)$ and $(v_3,v_4)$ with red and the edges $(v_1,v_4)$ and $(v_2,v_3)$ with blue.

We assume w.l.o.g. that $C\cap {ℳ}^{\ast }=\{(v_1,v_2),(v_3,v_4)\}$. Then, we color the edges $(v_1,v_2)$ and $(v_3,v_4)$ with red and the edges $(v_1,v_4)$ and $(v_2,v_3)$ with blue.

It is easy to see that the set of blues edges ${ℳ}_b$ and the set of red edges ${ℳ}_r$ are two perfect matchings, and ${ℳ}_b\cup {ℳ}_r={𝒞}_4^{\ast }$. Moreover, we know that ${ℳ}_b\cap {ℳ}^{\ast }=\mathrm{\varnothing }$, and hence ${ℳ}_b\cup {ℳ}^{\ast }$ is a mod-2-cycle cover without 2-cycles. Thus, the claim holds. $\mathrm{⊲}$

By the claim, we have

Since the mod-2-cycle cover ${𝒞}_{mod2}={ℳ}^{\ast }\cup {ℳ}^{\ast \ast }$ is the minimum weight mod-2-cycle cover containing the minimum weight perfect matching ${ℳ}^{\ast }$, we have

Thus, $w({𝒞}_{mod2})\le w({𝒞}_4^{\ast })$ and the lemma holds. $◀$

If we use the lower bound from Lemma 7, Lemma 13 shows that ${𝒞}_{mod2}$ performs as well as ${𝒞}^{\ast }$. By calculations, we obtain ${\max }_{C\in {𝒞}_{mod2}}\lceil |C|/4\rceil /|C|\le \frac{1}{3}$ and ${\max }_{C\in {𝒞}^{\ast }}\lceil |C|/4\rceil /|C|\le \frac{2}{5}$. Then, by Corollary 11, it is better to use ${𝒞}_{mod2}$ when invoking EX-ITP, which achieves an approximation ratio of $g(k-2)+1=\frac{5}{3}$. Thus, we have the following result.

Note that we can obtain a solution with weight at most $\frac{1}{2}\mathrm{\Delta }+\frac{3}{4}w({𝒞}_4^{\ast })$ for unit-demand 4-CVRP by calling EX-ITP on a minimum weight 4-cycle cover ${𝒞}_4^{\ast }$. However, it is NP-hard to compute ${𝒞}_4^{\ast }$ as mentioned before. Surprisingly, we can obtain a solution with the same upper bound in polynomial time without using ${𝒞}_4^{\ast }$, and hence obtain an improved $3/2$-approximation algorithm, which even matches the approximation ratio for unit-demand 3-CVRP.

The main idea is that we can use the minimum weight matching algorithm to optimally compute a minimum weight itinerary containing all edges in ${ℳ}^{\ast }$: first we construct a multi-graph $G^{\prime }=G[V]/{ℳ}^{\ast }$ by contracting every edge in ${ℳ}^{\ast }$; for each edge $e_i{e}_j$ in $G^{\prime }$ where $e_i,e_j\in {ℳ}^{\ast }$, we set its weight as the minimum weight of a tour in $G$ containing $e_i$ and $e_j$; then a minimum weight matching in $G^{\prime }$ corresponds to a minimum weight itinerary in $G$ containing all edges in ${ℳ}^{\ast }$. Next, through a property of ${𝒞}_4^{\ast }$, we prove that this solution has a weight of at most $\frac{1}{2}\mathrm{\Delta }+\frac{3}{4}w({𝒞}_4^{\ast })$.

First, the claim in Lemma 13 can be strengthened using a similar odd cycle elimination technique in [22].

Previously, we have shown that (1) and (2) holds, and ${ℳ}_b\cup {ℳ}^{\ast }$ is a mod-2-cycle cover without 2-cycles.

Then, we modify the cycle cover ${ℳ}_b\cup {ℳ}^{\ast }$ so that (1), (2), and (3) hold. By the previous coloring, we know that each cycle of ${𝒞}_4^{\ast }$ contains two blue edges and two red edges. Two blue/red edges are called matched if they fall on the same cycle of ${𝒞}_4^{\ast }$.

Consider a cycle $C_i\in {ℳ}_b\cup {ℳ}^{\ast }$ with a minimum length not divisible by 4. Since ${ℳ}_b\cup {ℳ}^{\ast }$ is a cycle cover without 2-cycles and the length of every cycle is divisible by 2, the number of blue edges on $C_i$ is odd. Hence, there must be a blue edge $e_1$ such that its matched blue edge $e_3$ falls on a different cycle $C_j\in {ℳ}_b\cup {ℳ}^{\ast }$. Moreover, there are two red edges $e_2$ and $e_3$ sharing common vertices with them. See Figure 1 for an illustration.

We can modify the colors of $\{e_1,e_2,e_3,e_4\}$ such that the new color of $\{e_1,e_3\}$ is red, and the new color of $\{e_2,e_4\}$ is blue. We can see that (1) and (2) still holds. Moreover, by repeating this, we obtain a cycle cover ${ℳ}_b\cup {ℳ}^{\ast }$ such that the length of every cycle is divisible by 4. So, (3) also holds. $\mathrm{⊲}$

Now, consider the multi-graph $G^{\prime }=G[V]/{ℳ}^{\ast }$, i.e., $G^{\prime }$ is obtained by contracting edges of ${ℳ}^{\ast }$ in $G[V]$. There are $n/2$ super-vertices in $G^{\prime }$ with each corresponding to an edge of ${ℳ}^{\ast }$. For any two super-vertices $e_i,e_j\in {ℳ}^{\ast }$, there are four parallel edges between them. Assume that $e_i=(u,u^{\prime })$ and $e_j=(v,v^{\prime })$. The augmented weights $\tilde{w}$ on the four edges are

which measure the weights of tours: $(v_0,u^{\prime },u,v,v^{\prime },v_0)$, $(v_0,u^{\prime },u,v^{\prime },v,v_0)$, $(v_0,u,u^{\prime },v,v^{\prime },v_0)$, $(v_0,u,u^{\prime },v^{\prime },v,v_0)$, respectively. Then, a matching $ℳ$ in $G^{\prime }$ corresponds to a solution of unit-demand 4-CVRP with an augmented weight of $\tilde{w}(ℳ)$. The minimum augmented weight matching in $G^{\prime }$, denoted by ${ℳ}^{\ast \ast }$, has the following property.

By Lemma 17, ${ℳ}^{\ast }\cup {ℳ}_b$ is a mod-4-cycle cover. So, the number of blue edges on each cycle $C\in {ℳ}^{\ast }\cup {ℳ}_b$ is even. All blue edges in ${ℳ}_b$ can be decomposed into two matchings ${ℳ}_1$ and ${ℳ}_2$ in $G[V]/{ℳ}^{\ast }$. Note that $\tilde{w}({ℳ}_1)+\tilde{w}({ℳ}_2)=\mathrm{\Delta }+2w({ℳ}^{\ast })+w({ℳ}_b)$. We have $\tilde{w}({ℳ}^{\ast \ast })\le \frac{1}{2}(\tilde{w}({ℳ}_1)+\tilde{w}({ℳ}_2))=\frac{1}{2}\mathrm{\Delta }+w({ℳ}^{\ast })+\frac{1}{2}w({ℳ}_b)$. Recall that ${𝒞}_4^{\ast }={ℳ}_b\cup {ℳ}_r$ and $w({ℳ}^{\ast })\le \min \{w({ℳ}_b),w({ℳ}_r)\}\le \frac{1}{2}(w({ℳ}_b)+w({ℳ}_r))=\frac{1}{2}w({𝒞}_4^{\ast })$. We have $w({ℳ}^{\ast })+\frac{1}{2}w({ℳ}_b)\le \frac{1}{2}w({ℳ}^{\ast })+\frac{1}{2}w({ℳ}_r)+\frac{1}{2}w({ℳ}_b)\le \frac{3}{4}w({𝒞}_4^{\ast })$. $\mathrm{⊲}$

Since the minimum augmented weight matching ${ℳ}^{\ast \ast }$ in $G^{\prime }$ can be found by the minimum weight matching algorithm in $O(n^3)$ time [16, 27], we can find a solution of unit-demand 4-CVRP with weight $\tilde{w}({ℳ}^{\ast \ast })$ in polynomial time. $◀$