Keywords

1 Introduction

Vehicle routing problems are among the most well known and well studied problems in Combinatorial Optimization. The goal is generally to find cost-efficient delivery routes for delivering items from depots to clients in a network using vehicles. The Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959 [12], generalizes the classic Traveling Salesman Problem and has numerous applications. In CVRP, we are given as input a complete graph \(G=(V,E)\) with metric edge weights (also referred to as costs) \(c(e)\in \mathbb {R}_{\ge 0}\), a depot \(r\in V\), and a vehicle with capacity \(Q>0\), and wish to compute a minimum weight/cost collection of tours, each starting and ending at the depot and visiting at most Q customers, whose union covers all the customers. In the more general setting, each node v is given along with a demand \(d(v)\in \mathbb {Z}_{\ge 1}\) and the goal is to find a set of tours of the minimum total cost, each of which includes r, such that the union of the tours covers the demand at every client and every tour serves at most Q demand.

There are three common versions of CVRP: unit, splittable, and unsplittable. In the splittable variant, the demand of a node can be delivered using multiple tours so each tour must also specify how much demand it serves at each clientFootnote 1. However, in the unsplittable variant the entire demand of a client must be delivered by a single tour (e.g. each demand is an indivisible good of a certain size). This obviously requires that \(d_v\le Q\) for all clients v. The unit demand case is a special case of the unsplittable case where every node has a unit demand, and the demand of a client must be delivered by a single tour. It is easy to see that the splittable demand case can be reduced to the unit demand case in pseudo-polynomial time using multiple collocated clients of unit demands. However, the unsplittable version is more challenging. For example, it contains the bin-packing problem as a special case; when all clients are have distance 1 from r and distance 0 from each other.

CVRP has also been referred to as the k-tours problem [3, 4]. Both the splittable and unsplittable versions admit constant factor approximation algorithms in polynomial-time. Haimovich and Kan [17] showed that a heuristic, called iterative partitioning, yields an \((\alpha +1(1-1/Q))\)-approximation for the unit demand case if one uses an \(\alpha \)-approximation for the Traveling Salesman Problem (TSP). A similar approach produces a \(2 + (1 - 2/Q)\alpha )\)-approximation for the unsplittable variant [2]. Despite their simplicity, these remained the best approximations for these two variants for over 35 years. Recently, Blauth et al. [10] improved these approximations giving an \((\alpha + 2 \cdot (1 - \varepsilon ))\)-approximation algorithm for unsplittable CVRP and a \((\alpha + 1 - \varepsilon )\)-approximation algorithm for unit demand CVRP and splittable CVRP where \(\varepsilon \) is a constant depending only on \(\alpha \). For \(\alpha = 3/2\), they showed \(\varepsilon > 1/3000\). All the variants are APX-hard in general metric spaces [25].

In this paper we make significant progress on improving the approximation guarantee for unsplittable CVRP. More specifically we present a simple combinatorial algorithm with ratio 3.25, and then a 3.194-approximation algorithm based on linear programming (LP). Our algorithms are completely independent of the improvements by Blauth et al. [10]. By incorporating their approach, we can further improve both ratios by a small constant \(\varepsilon ' > 0\). However, for the sake of simplicity we prefer to present our main results without factoring in this last improvement.

Theorem 1

There is an approximation algorithm for the unsplittable CVRP with ratio \(\alpha +1.75\), where \(\alpha \) is the best approximation ratio for TSP.

The running time of this algorithm is dominated by computing two \(\alpha \)-approximate TSP tours and a minimum cost matching. For example, using the simple (combinatorial) Christofides-Serdyukov 1.5-approximation we get a combinatorial 3.25-approximation for unsplittable CVRP whose running time is dominated by computing O(1) perfect matchings in graphs with O(|V|) nodes. Computing a perfect matching in a graph with n nodes can be done in \(O(n^3)\) time [15]; hence our algorithm runs in \(O(|V|^3)\) time.

If we allow greater running time, we can improve the approximation guarantee further by using linear programming.

Theorem 2

For any \(\delta >0\), there is an approximation algorithm for unsplittable CVRP with ratio \(\ln (2)+\alpha +\frac{1}{1-\delta }\) and running time \(n^{O(\frac{1}{\delta })}\), where \(\alpha \) is the best approximation ratio for TSP.

Finally, we show how combining these two results with the approach in [10] actually yields further improvements: a combinatorial \((\alpha +1.75-\varepsilon ')\)-approximation and an LP-based \((\alpha +\ln (2)+\frac{1}{1-\delta }-\varepsilon ')\)-approximation in time \(n^{O(\frac{1}{\delta })}\), where \(\varepsilon ' > 0\) is an absolute constant.

It is worth noting as the classical results on CVRP [2, 17], our results also can be extended to the asymmetric metric where c(u, v) is not necessarily equal to c(v, u). For example, the analogous of Theorem 1 in the asymmetric metric is a \((\beta +1.75)\)-approximation where \(\beta \) is the best approximation factor for Asymmetric Traveling Salesman Problem.

We discuss these further improvements and the extension to the asymmetric metric in more details in the full version of the paper [14].

1.1 Related Work

CVRP captures classic TSP when Q, the vehicle capacity, is at least the total demand of all clients. For general metrics, Haimovich and Kan [17] considered a simple heuristic, called tour partitioning, which starts from a TSP tour and then splits it into tours of size at most Q by making back-and-forth trips to r at certain points along the TSP tour. They showed this gives a \((1 + (1 - 1/Q)\alpha )\)-approximation for splittable CVRP, where \(\alpha \) is the approximation ratio for TSP. Essentially the same algorithm yields a \((2 + (1 - 2/Q)\alpha )\)-approximation for unsplittable CVRP [2]. These stood as the best-known bounds until recently, when Blauth et al. [10] showed that given a TSP approximation \(\alpha \), there is an \(\varepsilon > 0\) such that there is an \((\alpha + 2 \cdot (1 - \varepsilon ))\)-approximation algorithm for CVRP. For \(\alpha = 3/2\), they showed \(\varepsilon > 1/3000\). They also describe a \((\alpha + 1 - \varepsilon )\)-approximation algorithm for unit demand CVRP and splittable CVRP.

For the case of trees, Labbé et al. [23] showed splittable CVRP is NP-hard, and Golden et al. [16] showed unsplittable version is hard to approximate better than 1.5. This is via a simple reduction from bin packing. For splittable CVRP (again on trees), Hamaguchi et al. [18] defined a lower bound for the cost of the optimal solution and gave a 1.5 approximation with respect to the lower bound. Asano et al. [4] improved the approximation to \((\sqrt{41} - 1)/4\) with respect to the same lower bound and also showed the existence of instances whose optimal cost is exactly 4/3 times the lower bound. Later, Becker [5] gave a 4/3-approximation with respect to the lower bound. Becker and Paul [9] showed a \((1, 1+ \varepsilon )\)-bicriteria polynomial-time approximation scheme for splittable CVRP in trees, i.e. a PTAS but every tour serves at most \((1+\varepsilon )Q\) demand. Recently, Jayaprakash and Salavatirpour [19] presented a QPTAS for unit-demand CVRP for trees and more generally graphs of bounded treewidth, bounded doubling metrics, or bounded highway dimension. Even more recently, building upon ideas of [9] and [19], Mathieu and Zhou [24] have presented a PTAS for splittable CVRP on trees.

Das and Mathieu [13] gave a quasi-polynomial-time approximation scheme (QPTAS) for CVRP in the Euclidean plane (\(\mathbb {R}^2\)). A PTAS for when Q is \(O(\log n/\log \log n)\) or Q is \(\Omega (n)\) was shown by Asano et al. [4]. A PTAS for Euclidean plane \(\mathbb {R}^2\) for moderately large values of Q, i.e. \(Q \le 2^{\log ^\delta n}\) where \(\delta = \delta (\varepsilon )\), was shown by Adamaszek et al. [1], building on the work of Das and Mathieu [13]. For high dimensional Euclidean spaces \(\mathbb {R}^d\), Khachay et al. [20] showed a PTAS when Q is \(O(\log \log ^{1/d}n)\). For graphs of bounded doubling dimension, Khachay et al. [21] gave a QPTAS when the optimal number of tours is \(\mathop {\mathrm {polylog}}\nolimits (n)\) and Khachay et al. [22] gave a QPTAS when Q is \(\mathop {\mathrm {polylog}}\nolimits (n)\).

The next results we summarize are all for the case \(Q = O(1)\). CVRP remains APX-hard in general metrics in this case but is polynomial-time solvable on trees. There exists a PTAS for CVRP in the Euclidean plane (\(\mathbb {R}^2\)) (again for when Q is fixed) as shown by Khachay et al. [20]. A PTAS for planar graphs was given by Becker et al. [8] and a QPTAS for planar and bounded-genus graphs was then given by Becker et al. [6]. A PTAS for graphs of bounded highway dimension and an exact algorithm for graphs with treewidth tw with running time \(O(n^{tw\cdot Q})\) was shown by Becker et al. [7]. Cohen-Addad et al. [11] showed an efficient PTAS for graphs of bounded-treewidth, an efficient PTAS for bounded highway dimension, an efficient PTAS for bounded genus metrics and a QPTAS for minor-free metrics.

Organization of the Paper: We start with definitions and preliminaries in Sect. 2. The proof of Theorem 1 is presented in Sect. 3 and the proof of Theorem 2 is presented in Sect. 4.

2 Preliminaries

For ease of exposition, we assume we have scaled all the demands and the capacity of the vehicle so that the capacity is 1 and each \(d(v)\in (0,1]\) (so demands can be rational numbers). Also, we treat r as a separate node from the rest of the nodes. Formally:

Definition 1

( ). An instance (V, r, c, d) of Capacitated Vehicle Routing (CVRP) consists of:

  • a set of clients V, where \(|V|=n\),

  • a depot r, not in V,

  • metric travel costs/distances \(c:(V\cup \{r\})\times ( V\cup \{r\})\rightarrow \mathbb {R}_{\ge 0}\),

  • a demand \(d_v\in (0,1]\) for each customer \(v\in V\).

A feasible solution is a collection of tours \(\mathcal {T}\) such that

  • every tour \(T\in \mathcal {T}\) is a cycle containing r,

  • every client belongs to exactly one tour,

  • \(\sum \limits _{v\in T}d_v\le 1\) for all \(T\in \mathcal {T}\).

The goal is to find a feasible solution with minimum cost where the cost is the sum of costs of the edges in the solution and denoted by \(c(\mathcal {T}):=\sum \limits _{T\in \mathcal {T}}c(T):=\sum \limits _{T\in \mathcal {T}}\sum \limits _{(u,v)\in T}c(u,v)\).

Observe we are viewing a tour T as both a set of edges comprising a cycle plus the set of endpoints of these edges, so we may use notation like \(v \in T\) for a location v and also \((u,v) \in T\) for a pair of locations (u, v) appearing consecutively along the tour T. It is convenient to view the depot r as having \(d_r = 0\), for example when we sum the demand of all locations on a tour.

Fix an unsplittable CVRP instance \(\mathcal{I}=(V,r,c,d)\) for the rest of this paper. We use \(\mathrm{OPT}\) to denote an optimal solution for \(\mathcal I\) and \(\mathrm{opt}\) the value of this optimal solution.

Definition 2

(Feasible tours). A tour T that spans r and some clients is called feasible for \(\mathcal I\) if the total demand of the clients in T is at most 1, i.e., \(\sum \limits _{v\in T}d_v\le 1\).

Clients are partitioned into small and big clients based on a parameter \(\delta \in [0,\frac{1}{2}]\), which will be chosen differently for our two algorithms.

Definition 3

(Small and big clients). For a fixed \(\delta \in [0,\frac{1}{2}]\), we say a client v is small if \(d_v\in [0,\delta ]\), and big otherwise.

Let \(\mathcal {D}:=\sum \limits _{v\in V}2\cdot d_v\cdot c(r,v)\). This is historically referred to as the radial lower bound and the following simple well-known lemma has been used often in previous work.

Lemma 1

(Haimovich and Kan [17]). \(\mathcal {D}\le \mathrm{opt}\).

We also define a similar sum for small and big clients separately, i.e., \(\mathcal {D}_{small}:=\sum \limits _{\begin{array}{c} v\in V:\\ v~is~small \end{array}}2\cdot d_v\cdot c(r,v)\), and \(\mathcal {D}_{big}:=\sum \limits _{\begin{array}{c} v\in V:\\ v~is~big \end{array}}2\cdot d_v\cdot c(r,v)\). Also define \(\mathcal {D}'_{big}:=\sum \limits _{\begin{array}{c} v\in V:\\ v~is~big \end{array}}2\cdot c(r,v)\), which is the cost of serving all big clients using a separate tour for each client.

Given a TSP tour, the algorithm by Haimovich and Kan has the vehicle begin by randomily filling the “tank” of demand it carries with some value \(\theta \sim (0,1]\). It then travels about the TSP tour: if the tank has insufficient demand to serve a client it travels to the depot to get enough demand to serve the client, returns to serve the client, and then returns to the depot to refill the tank appropriately before resuming the tour. The probability that such a resupply trip is performed when trying to serve a client v is \(d_v\), so the total cost of performing these round trips is at most \(2 \cdot \mathcal {D}\le 2 \cdot \mathrm{opt}\) in expectation.

One of the main driving forces behind our improvements is the following idea. For a small client, if we think of the vehicle’s tank as only holding \(1-\delta \) demand and keep a reserved tank holding demand \(\delta \), then if we cannot serve a client with the demand in the main tank, we can serve it using the reserve tank and only make one round trip to the depot to refill both tanks before proceeding. Both of our main algorithms balance this idea with approaches to handling big clients.

We formalize this notion of using a reserve tank in Lemma 2 below. When \(\delta =0\) this gives the same result as in [2, 17].

Lemma 2

(\(\delta \)-tank Lemma). Let \(\mathcal {A}\) be a TSP tour on \(V\cup \{r\}\) and define small and big clients based on a fixed \(\delta \le 1/2\). There is an algorithm that turns \(\mathcal {A}\) into a feasible solution for the CVRP instance with cost

$$\begin{aligned} c(\mathcal {A})+\frac{1}{1-\delta }\cdot \mathcal {D}_{small}+\frac{2}{1-\delta }\cdot \mathcal {D}_{big}-\frac{\delta }{1-\delta }\cdot \mathcal {D}'_{big}, \end{aligned}$$
(1)

and running time \(O(n^2)\).

Proof

We sketch the high level idea behind the proof. See the full version of the paper [14] for the complete proof.

The idea is to reserve \(\delta \) portion of the vehicle’s tank and fill out the rest with a random amount. Then, the vehicle visits the vertices in the same order as they appear in \(\mathcal {A}\). As the vehicle visits the clients (vertices), it serves their demand. However, the vehicle might need to make some round trips to the depot to refill. Using the reserved tank and the initial random filling, we bound the cost of these round trips to the depot against different parts of \(\mathcal {D}\) as shown in (1).    \(\square \)

3 A Combinatorial 3.25-Approximation

In this section, we set \(\delta :=\frac{1}{3}\). So v is a small client if \(d_v\le \frac{1}{3}\) and big if \(d_v > \frac{1}{3}\). Note that in any feasible solution, there are at most two big clients in any single tour. Our algorithm tries two things: the first serves only big clients by pairing them up optimally to form these tours and then runs the classic 3.5-approximation on the small clients but using our \(\delta \)-tank procedure (see Lemma 2) for performing the tour splitting. The other simply runs the 3.5-approximation using \(\delta \)-tank tour splitting on all clients.

Let us first explain how we use matching. Consider an auxiliary graph \(\mathop {\mathrm {G}_{\mathrm {aux}}}\nolimits =(V_{big}, E_{aux})\) where \(V_{big}\subseteq V\) is the set of all big clients and \(E_{aux}\) constructed as follows: for any pair of big clients u, v where \(d_u+d_v\le 1\) we add and edge between u and v with cost \(c(r,u) + c(u,v) + c(v,r)\). Furthermore, for every big client v there is a loop in \(\mathop {\mathrm {G}_{\mathrm {aux}}}\nolimits \) with cost equal to \(2\cdot c(r,v)\). We compute a min-cost perfect matchingFootnote 2 which corresponds to the cheapest way to select tours to serve only the big clients. The precise details are presented in Algorithm 1.

figure a

3.1 Analysis

We begin with two simple observations.

Lemma 3

\(cost(M)\le \mathrm{opt}\).

Proof

Each tour in any feasible solution contains at most two big clients. So, after shortcutting all tours in \(\mathrm{OPT}\) past small clients, we get tours corresponding to a perfect matching \(\mathop {\mathrm {G}_{\mathrm {aux}}}\nolimits \) with cost at most \(\mathrm{opt}\).    \(\square \)

Lemma 4

\(cost(M)\le \mathcal {D}'_{big}\).

Proof

Consider all the loops in \(\mathop {\mathrm {G}_{\mathrm {aux}}}\nolimits \). The cost of all the loops is exactly \(\mathcal {D}'_{big}\) and this is a matching so it is an upper bound on the minimum cost of a perfect matching.    \(\square \)

Next, we compute the cost of the first solution in the algorithm. Note that \(c(\mathcal {T}')=cost(M)\). Using an \(\alpha \)-approximation for TSP, the cost of \(\mathcal {A}\) is at most : again we are using the metric property which shows \(\mathrm{opt}\) upper bounds the optimum TSP tour since the union of all tours in \(\mathrm{OPT}\) is connected and Eulerian. Finally, applying the \(\delta \)-tank lemma to \(\mathcal {A}\) results in a solution of cost at most \(c(\mathcal {A})+\frac{1}{1-\delta }\cdot \mathcal {D}_{small}\) since there is no big client on \(\mathcal {A}\). Overall, we have

$$\begin{aligned} \begin{aligned} c(\mathcal {T})&= c(\mathcal {T}')+c(\mathcal {T}'') \le cost(M) + \alpha \cdot \mathrm{opt}+ \frac{3}{2}\cdot \mathcal {D}_{small}. \end{aligned} \end{aligned}$$
(2)

Next, we compute the cost of the second solution. From the \(\delta \)-tank lemma,

$$\begin{aligned} c(\mathcal {F})=\alpha \cdot \mathrm{opt}+ \frac{3}{2}\cdot \mathcal {D}_{small} + 3\cdot \mathcal {D}_{big} - \frac{1}{2}\cdot \mathcal {D}'_{big}. \end{aligned}$$
(3)

Combining these, we bound the cost of the solution output by the algorithm as follows:

$$\begin{aligned} \begin{aligned} \min \{c(\mathcal {T}),c(\mathcal {F})\}&\le \frac{c(\mathcal {T})+c(\mathcal {F})}{2}\\&= \frac{2\cdot \alpha \cdot \mathrm{opt}+ 3\cdot (\mathcal {D}_{small}+\mathcal {D}_{big})+cost(M)-\frac{1}{2}\cdot \mathcal {D}'_{big}}{2}\\&\le \frac{2\cdot \alpha \cdot \mathrm{opt}+ 3\cdot \mathcal {D}+\frac{1}{2}\cdot cost(M)}{2}\\&\le \alpha \cdot \mathrm{opt}+1.5\cdot \mathrm{opt}+0.25\cdot \mathrm{opt}\\&=(\alpha +1.75)\cdot \mathrm{opt}, \end{aligned} \end{aligned}$$
(4)

where the second inequality follows from Lemma 4 and the last inequality follows from Lemmas 1 & 3. This finishes the proof of Theorem 1.

4 An Improved LP-Based Approximation

In this section let \(\delta \) be a fixed constant in the range (0, 1/2]. Smaller \(\delta \) lead to better approximations with increased, but still polynomial, running times.

Define the small and big clients for this value \(\delta \) as in Definition 3. Let \(V_{big}\) be the set of big clients. We consider the following configuration LP for big clients: Let \(\mathcal {J}\) be the set of all feasible tours where each tour consists of some big clients and the depot. Note \(|\mathcal {J}|\) is bounded by \(n^{O(\frac{1}{\delta })}\) as there can be at most \(\frac{1}{\delta }\) big clients in each tour. For each \(T\in \mathcal {J}\) let c(T) be the cost of tour T. For each tour \(T\in \mathcal {J}\), we have a variable \(x_{T}\) indicating this tour is chosen by the algorithm.

figure b

By shortcutting all tours in the optimum solution past small clients and discarding tours with no big clients, we see there is an integer solution to (Configuration-LP) with cost at most \(\mathrm{opt}\). Thus, the optimum LP value provides a lower bound on \(\mathrm{opt}\).

Our algorithm independently samples tours spanning large clients using an optimal LP solution. After this, some large clients and all small clients remain uncovered, we cover them using the classic 3.5-approximation but use the \(\delta \)-tank tour splitting approach. Algorithm 2 contains the full description of our approach. With foresight, we set \(\gamma := \ln (2)\).

figure c

It could be that some clients lie on multiple tours due to the randomized rounding step. One can shortcut the tours past repeated occurrences of clients so each client lies on exactly one tour.

4.1 Analysis

We first bound the probability of a big client not being covered in the randomized rounding step of Algorithm 2 (steps 3–4).

Lemma 5

For a \(v \in V_{big}\), \(\Pr [v~is~not~covered~by~\mathcal {T}]\le e^{-\gamma }\).

Proof

The event that a big client v is not covered is if we do not sample any tour T that contains v in the randomized rounding step. So

$$ \Pr [v~is~not~covered~by~\mathcal {T}]=\prod \limits _{T\in \mathcal {T}}(1-\gamma \cdot x_T)\le e^{-\gamma \cdot \sum \limits _{T\in \mathcal {T}:v\in T}x_T}\le e^{-\gamma }, $$

where the last bound follows from the constraint in (Configuration-LP) for v.    \(\square \)

Next, we bound the expected costs of \(\mathcal {T}\) and \(\mathcal {T}'\), separately. The cost of \(\mathcal {T}\) is bounded as follows:

(6)

Using the \(\delta \)-tank lemma, we bound the expected cost of \(\mathcal {T}'\) but with the following changes: in (1), we drop the negative term and we incorporate the fact that a big client is on \(\mathcal {A}\) with probability at most \(e^{-\gamma }\), see Lemma 5.

(7)

The second equality follows from our choice of \(\gamma = \ln 2\). From (6) and (7), the expected cost of the solution returned by Algorithm 2 is at most

(8)

where the last inequality follows from Lemma 1. This finishes the proof of Theorem 2. We briefly comment that this algorithm can be derandomized efficiently using the method of conditional expectation since the probability a big client is covered and its expected contribution to the \(\delta \)-tank upper bound can be computed efficiently even if some tours have been sampled or rejected so far. Note there is a numerical issue in that \(\gamma \cdot x_T\) may not be a rational number, but this error can be absorbed in the \(\frac{1}{1-\delta }\) part of the guarantee by choosing \(\delta \) to be slightly smaller.