Keywords

1 Introduction

The Capacitated Vehicle Routing Problem (CVRP) is the widely known combinatorial optimization problem introduced by Dantzig and Ramser in their seminal paper [5]. This problem has a wide range of applications in operations research (see, e.g. [4] and references within). In addition, CVRP settings stem from specific models of unsupervised learning [1]. For instance, in [7], CVRP is considered as a clustering problem, where the clusters are formed by customers serviced by the same route and intra-cluster costs are defined by lengths of the corresponding routes.

As the well-known k-means clustering problem [2, 10], CVRP remains NP-hard even in finite dimensional Euclidean spaces (see, e.g. [17]). Although the problem is hardly approximable in general, its geometric settings can be approximated rather well. Most of the known results in this field date back to the famous papers by Haimovich and Rinnooy Kan [8] and Arora [3]. To the best of our knowledge, the most recent among them are the Quasi-Polynomial Time Approximation Scheme (QPTAS) proposed in [6] for the Euclidean plane and extended in [15, 16] to the case of finite number of non-intersecting time windows, and the Efficient Polynomial Time Approximation Scheme (EPTAS) introduced in [12] for the CVRP in the Euclidean space of an arbitrary dimension \(d>1\). Although, for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) there is a significant success in development of branch-and-cut exact methods and heuristics that can solve its numerous instances coming from the practice efficiently (see surveys in [14, 17]), the known results concerning the algorithms with performance guarantees remain still very rare.

In this paper, we try to bridge this gap and propose the first EPTAS for CVRPTW extending the famous approach proposed by Haimovich and Rinnooy Kan [8] and some other previous results [11, 12, 15, 16].

The rest of the paper is structured as follows. In Sect. 2 we provide a mathematical statement of CVRPTW. In Sect. 3, we discuss the main idea of the scheme proposed, provide its rigorous description, and claim our main result. Its proof for the simplest non-trivial case of the problem defined in the Euclidean plane is presented in Sect. 4. Finally, in Sect. 5 we come to conclusions and list some open questions.

2 Problem Statement

In the simplest setting of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), we are given by a set \(X=\{x_1,\ldots ,x_n\}\) of customers and a set \(T=\{t_1,\ldots ,t_p\}\) of consecutive time windows. It is assumed that, for any \(1\le j<p\), the time window \(t_j\) precedes time window \(t_{j+1}\), i.e. the set T is ordered. In the sequel, we denote this order by \(\preceq \). Each customer \(x_i\) has the unit non-splittable demand, which should be serviced in a given time window \(t(x_i)\in T\). Service is carried out by a fleet of vehicles arranged at a given depot \(x_0\). Each vehicle has the same capacity q and visits customers assigned to it in a cyclic route starting and finishing at the depot \(x_0\). The goal is to visit all the customers minimizing the total transportation cost subject to capacity and time windows constraints.

The mathematical statement of the CVRPTW can be defined as follows. The instance is given by the weighted complete digraph \(G=(X\cup \{x_0\}, E, w)\), a partition

$$\begin{aligned} X_1\cup \ldots \cup X_p=X, \end{aligned}$$
(1)

and the capacity bound \(q\in \mathbb {N}\). Here,

  1. (i)

    the non-negative weighting function \(w:E\rightarrow \mathbb {R}_+\) defines transportation costs for location pairs \((x_i,x_j)\), such that, for any route \(R=x_{i_1},\ldots ,x_{i_s}\), its cost \(w(R)=\sum _{j=1}^{s-1}w(x_{i_j},x_{i_{j+1}})\)

  2. (ii)

    any subset \(X_j\) of partition (1) consists of customers \(x_i\), which should be serviced in time window \(t(x_i)=t_j\in T\)

  3. (iii)

    for any feasible vehicle route \(R=x_0,x_{i_1},\ldots ,x_{i_s},x_0\), the following constraints

    $$\begin{aligned} s\le q&\quad \text {(capacity)} \end{aligned}$$
    (2)
    $$\begin{aligned} t(x_{i_j})\preceq t(x_{i_{j+1}})&\quad \text {(time windows)} \end{aligned}$$
    (3)

    are valid.

It is required to find a collection of feasible routes \(S=\{R_1,\ldots ,R_l\}\) that visits each customer once and has the minimum total transportation cost \(w(S)=\sum _{i=1}^lw(R_i)\).

If the weighting function w satisfies the triangle inequality, then CVRPTW is called metric and transportation costs \(w(x_i,x_j)\) are called distances between locations \(x_i\) and \(x_j\). In this paper, we consider the Euclidean CVRPTW, where \(X\cup \{x_0\}\subset \mathbb {R}^d\) and \(w(x_i,x_j)=\Vert x_i-x_j\Vert _2\).

3 Approximation Scheme

Our scheme (Algorithm 1) extends the approach proposed in the seminal paper by Haimovich and Rinnooy-Kan [8].

figure a

Its main idea is quite simple and consists of the following points

  1. (i)

    decomposition of the initial CVRPTW instance with p time windows to a single CVRPTW subinstance induced by the outer customers and p independent subinstances of the classic CVRP that describe servicing of the inner ones

  2. (ii)

    the famous Iterated Tour Partition (ITP) heuristic (Algorithm 2) reducing the CVRP to an appropriate instance of the Traveling Salesman Problem (TSP) induced by a subset of the inner customers, which should be serviced in the fixed time window \(t_j\), \(j\in \{1,\ldots ,p\}\)

  3. (iii)

    an upper bound for the optimum \(\mathrm {TSP}^*\) of the TSP instance enclosed in the Euclidean sphere of a given radius.

At first glance, the worst case time complexity of Algorithm 1 is determined by running time of the dynamic programming procedure applied to finding the exact solution of CVRPTW (due to Step 2), i.e. the proposed scheme should be extremely inefficient.

Actually, it is not so. As we show in Sect. 4, for any \(\varepsilon >0\), \(p\ge 1\), \(\rho \ge 1\), and \(q\in \mathbb {N}\) there exist a bound \(\tilde{K}=\tilde{K}(\varepsilon ,p,\rho ,q)\) such that Eq. (4) is satisfied by at least one \(1\le k\le \tilde{K}\). Therefore, for \(n>\tilde{K}\), the solution \(S_0\) can be obtained by dynamic programming with time complexity bound \(O(qk^22^k)\) (see, e.g. [9]), which does not depend on n. Further, for finding \(\rho \)-approximate solutions for the inner Euclidean TSP problem, one can employ an arbitrary approximation algorithm. Since running time of the ITP is \(O(n^2)\), the overall time complexity is mainly determined by the complexity \(\mathrm {TIME}(\mathrm {TSP},\rho ,n)\) of such an algorithm. The main result is claimed in Theorem 1. For the sake of simplicity, we present it for the case of Euclidean plane postponing more general result to the forthcoming paper.

Theorem 1

For any \(\varepsilon >0\) an \((1+\varepsilon )\)-approximate solution for the Euclidean CVRPTW can be obtained in time \(\mathrm {TIME}(\mathrm {TSP},\rho ,n)+O(n^2)+O(qk^22^k)\), where \(k=k(\varepsilon ,p,q,\rho )=O\left( p(\rho +1)\exp \left( O(q/\varepsilon )\right) \exp \left( O(\sqrt{pq/\varepsilon })\right) \right) \).

Remark 1

As it follows from Theorem 1, the scheme proposed is EPTAS for any fixed p and q and remains PTAS for \(q=O(\log \log n)\) and \(p=O(\log \log n)\).

4 Proof Sketch

We start with description of the well-known ITP heuristic (Algorithm 2). As it is shown in [8, 13], for the cost \(w(S_{\mathrm {ITP}})\) of the ITP-produced solution \(S_{\mathrm {ITP}}\), there exists the following upper bound, which remains valid for an arbitrary non-negative weighting function w.

figure b
Fig. 1.
figure 1

Shortcutting of a Hamiltonian cycle. Triangles, squares and circles denote customers, which should be serviced in different time windows.

Full size image

Lemma 1

For \(\bar{r}=1/|X|\sum _{i=1}^{|X|}r_i\) and \(l=\lceil |X|/q\rceil \),

$$\begin{aligned} w(S_{\mathrm {ITP}})\le 2l\bar{r}+\left( 1-\frac{l}{|X|}\right) w(H)\le 2l\bar{r}+\left( 1-1/q\right) w(H). \end{aligned}$$
(5)

Lemma 1 can be easily extended to the case of metric CVRPTW. Indeed, consider an instance of the metric CVRPTW defined by the graph \(G(X\cup \{x_0\},E,w)\), partition \(X_1\cup \ldots \cup X_p=X\), and capacity q. Let H be a Hamiltonian cycle spanning all the customers X. For any j, obtain a Hamiltonian cycle \(H_j\) for the subset \(X_j\) by shortcutting the cycle H (Fig. 1). Then, for each CVRP subinstance defined by the subgraph \(G\langle X_j\cup \{x_0\}\rangle \) and capacity q and for the appropriate cycle \(H_j\), apply Algorithm 2 to construct the partial solution \(S_j\). For the combined solution \(S=S_1\cup \ldots \cup S_p\), the following upper bound is valid.

Lemma 2

$$\begin{aligned} w(S)\le {}p\left( 1-\frac{1}{q}\right) w(H)+\frac{2}{q}\sum _{i=1}^{|X|}r_i+2pr_{\max }, \end{aligned}$$
(6)

where \(r_{\max }=\max \{r_1,\ldots ,r_{|X|}\}\).

Proof

by Lemma 1, for each \(S_j\), we have

$$\begin{aligned} w(S_i)\le 2\left\lceil \frac{n_j}{q}\right\rceil \bar{r}_j+\left( 1-\frac{1}{q}\right) w(H_j), \end{aligned}$$
(7)

where \(n_j=|X_j|\) and \(\bar{r}_j=1/n_j\sum \{r_i:x_i\in X_j\}\). Since, by construction, \(w(H_j)\le w(H)\) and \(\lceil n_j/q\rceil \le n_j/q+1\),

$$\begin{aligned}&\quad w(S)=\sum _{i=1}^pw(S_j)\le \left( 1-\frac{1}{q}\right) \sum _{j=1}^pw(H_j)+2\sum _{j=1}^p\left\lceil \frac{n_j}{q}\right\rceil \bar{r}_i\le \\&\le p\left( 1-\frac{1}{q}\right) w(H)+\frac{2}{q}\sum _{j=1}^pn_j\bar{r}_j+2\sum _{j=1}^p\bar{r}_j\le p\left( 1-\frac{1}{q}\right) w(H)+\frac{2}{q}\sum _{i=1}^{|X|}r_i+2pr_{\max }. \end{aligned}$$

Lemma 2 is proved.

In particular, in the case when the cycle H is found by \(\rho \)-approximation algorithm applied to the auxiliary TSP instance (with optimum \(\mathrm {TSP}^*(X)\)) defined by the subgraph \(G\langle X\rangle \),

$$ w(S)\le p\left( 1-\frac{1}{q}\right) \rho \mathrm {TSP}^*(X) +\frac{2}{q}\sum _{i=1}^{|X|}r_i+2pr_{\max }. $$

Notice that, for an arbitrary feasible solution of the metric CVRP, the following simple lower bound

$$\begin{aligned} w(S)\ge \frac{2}{q}\sum _{i=1}^{|X|}r_i \end{aligned}$$
(8)

is also valid.

Further, let the customers \(x_1,\ldots , x_n\) (elements of the set X) be ordered by decreasing their distances \(r_1\ge r_2\ge \ldots \ge r_n\) from the depot \(x_0\). Given some \(k\in \{1,\ldots , n\}\), consider a decomposition of the initial CVRP instance to two independent subinstances induced by the subsets \(X(k)=\{x_1,\ldots ,x_{k-1}\}\) and \(X'(k)=X\setminus X(k)\) of outer and inner customers and the same depot \(x_0\). Denote by \(\mathrm {OPT}(X)\), \(\mathrm {OPT}(X(k))\), and \(\mathrm {OPT}(X'(k))\) optimum values of the initial instance and the produced subinstances, respectively. Then, the following lemma holds the metric CVRP.

Lemma 3

For any \(1\le k\le n\),

$$\begin{aligned} \mathrm {OPT}(X(k))+\mathrm {OPT}(X'(k))\le \mathrm {OPT}(X)+4(k-1)r_k. \end{aligned}$$
(9)

It is easy to verify that the claim of Lemma 3 remains valid for the case of metric CVRPTW as well.

The next step to our proof of Theorem 1 is concerned with an upper bound the optimum value of the Euclidean TSP instance enclosed in a sphere of a given radius R. As we mentioned above, in this paper we restrict ourselves to the simplest non-trivial case of the Euclidean plane described in the following lemma. As it was shown in [11, 12], the similar bounds can be obtained for any fixed-dimensional Euclidean space.

Lemma 4

Let an instance of the Euclidean TSP be given by a set \(X=\{x_1,\ldots ,\) \(x_n\}\) that be enclosed in a circle of radius \(R=\max \{r_i:i\in \{1,\ldots ,n\}\}\) centered at \(x_0\). Then, for the optimum \(\mathrm {TSP}^*(X)\),

$$\begin{aligned} \mathrm {TSP}^*(X)\le 2R+4\sqrt{\pi {}R\sum _{i=1}^nr_i}. \end{aligned}$$
(10)

Proof

For some \(h<\pi \), partition the enclosing circle to \(\lceil 2\pi /h\rceil \) sectors such that all of them, except maybe one, have h as a value of their central angle. Consider the cyclic route walking back and forth all the obtained radii and augmented by the double connection of each point \(x_i\) to the closest radius. Transform this ‘strange’ route to a Hamiltonian cycle with shortcutting by the triangle inequality. Denote the length of the tour obtained by L(h). Since the distance between \(x_i\) and the nearest radius is at most \(r_i\sin (h/2)\le r_ih/2\) and the total length of all the radii does not exceed \(R(2\pi /h+1)\), we have

$$\begin{aligned} L(h)\le 2R+\frac{4\pi {}R}{h}+h\sum _{i=1}^nr_i. \end{aligned}$$
(11)

The rhs of (11) is minimized by

$$ h^*=2\sqrt{\frac{\pi {}R}{\sum _{i=1}^nr_i}}\in (0,2\sqrt{\pi }]. $$

Therefore,

$$ \mathrm {TSP}^*(X)\le L(h^*)\le 2R+4\sqrt{\pi {}R\sum _{i=1}^nr_i}. $$

Lemma is proved.

Consider a solution \(S=S_0\cup S_1\cup \ldots \cup S_p\) provided by Algorithm 1 for some k. By construction, \(w(S_0)=\mathrm {OPT}(X_k)\). At this point, we are ready to estimate the relative approximation error of the solution S

$$\begin{aligned} e(k)=\frac{w(S)-\mathrm {OPT}(X)}{\mathrm {OPT}(X)}=\frac{\mathrm {OPT}(X(k))+\mathrm {APP}(X'(k))-\mathrm {OPT}(X)}{\mathrm {OPT}(X)}, \end{aligned}$$
(12)

where \(\mathrm {APP}(X'(k))=\sum _{i=1}^pw(S_i)\).

Lemma 5

$$\begin{aligned} e(k)\le {}q\left( 2k+p(1+\rho {})\right) \frac{r_k}{\sum _{i=1}^nr_i}+2q\sqrt{\pi }p\rho \sqrt{\frac{r_k}{\sum _{i=1}^nr_i}} \end{aligned}$$
(13)

Proof

Indeed,

$$\begin{aligned}&e(k)=\frac{\mathrm {OPT}(X(k))+\mathrm {APP}(X'(k))-\mathrm {OPT}(X)}{\mathrm {OPT}(X)}\\&=\frac{(\mathrm {OPT}(X(k))+\mathrm {OPT}(X'(k))-\mathrm {OPT}(X)) + \mathrm {APP}(X'(k))-\mathrm {OPT}(X'(k))}{\mathrm {OPT}(X)}. \end{aligned}$$

Since,

$$\mathrm {OPT}(X(k))+\mathrm {OPT}(X'(k))-\mathrm {OPT}(X)\le 4(k-1)r_k, \text { by Lemma 3},$$
$$ \mathrm {OPT}(X)\ge 2/q\sum _{i=1}^nr_i\ \text { and } \mathrm {OPT}(X'(k))\ge 2/q\sum _{i=k}^nr_i, \text { by Eq. (8)},$$
$$\mathrm {APP}(X'(k))\le p\left( 1-\frac{1}{q}\right) \rho \mathrm {TSP}^*(X'(k)) +\frac{2}{q}\sum _{i=k}^{n}r_i+2pr_k, \text { by Lemma 2, and}$$
$$ \mathrm {TSP}^*(X'(k))\le 2r_k+4\sqrt{\pi {}r_k\sum _{i=k}^nr_i}, \text { by Lemma 4}, $$

we obtain

$$\begin{aligned}&e(k)\le \left( 2q(k-1)+\rho {}pq+pq\right) \frac{r_k}{\sum _{i=1}^nr_i}+2\sqrt{\pi }p\rho {}q\sqrt{\frac{r_k}{\sum _{i=1}^nr_i}}\\&\qquad \qquad \qquad \qquad \qquad \quad \le q\left( 2k+p(1+\rho {})\right) \frac{r_k}{\sum _{i=1}^nr_i}+2q\sqrt{\pi }p\rho \sqrt{\frac{r_k}{\sum _{i=1}^nr_i}}. \end{aligned}$$

Lemma 5 is proved.

The following technical lemma is the last stair to the proof of our main result.

Lemma 6

For any \(\varepsilon >0\), \(p\ge 1\), \(\rho \ge 1\), and \(q\in \mathbb {N}\), there exists \(\tilde{K}=\tilde{K}(\varepsilon ,p,\rho , q)\), such that the equation

$$\begin{aligned} q\left( 2k+p(1+\rho {})\right) \frac{r_k}{\sum _{i=1}^nr_i}+2q\sqrt{\pi }p\rho \sqrt{\frac{r_k}{\sum _{i=1}^nr_i}}<\varepsilon \end{aligned}$$
(14)

holds at least for one \(1\le k\le \tilde{K}\).

Proof

Suppose, for some \(\tilde{K}\), Eq. (14) is violated by any natural k from the interval \([1,\tilde{K}]\), i.e., for any \(1\le k\le \tilde{K}\),

$$\begin{aligned} s_k^2+\frac{2\sqrt{\pi }p\rho }{2k+p(1+\rho )}s_k-\frac{\varepsilon }{q(2k+p(1+\rho ))}\ge 0 \end{aligned}$$
(15)

for \(s_k=\sqrt{\frac{r_k}{\sum _{i=1}^nr_i}}\). Since the lhs of Eq. (15) has the roots of different sign, Eq. (15) implies

$$ s_k\ge -\frac{\sqrt{\pi }p\rho }{2k+p(1+\rho )} + \sqrt{\frac{\pi p^2\rho ^2}{(2k+p(1+\rho ))^2}+ \frac{\varepsilon }{q(2k+p(1+\rho ))}} $$

or

$$ s_k\ge -\frac{B}{2k+A}+\sqrt{\left( \frac{B}{2k+A}\right) ^2+\frac{C}{2k+A}}\ge -\frac{B}{2k+A}+\frac{\sqrt{C}}{\sqrt{2k+A}}, $$

where \(A=p(1+\rho )\), \(B=\sqrt{\pi }p\rho \), and \(C=\varepsilon /q\).

Hence,

$$\begin{aligned} s_k^2\ge \frac{C}{2k+A}+\frac{B^2}{(2k+A)^2}-\frac{2B\sqrt{C}}{(2k+A)^{3/2}}\ge \frac{C}{2k+A}-\frac{2B\sqrt{C}}{(2k+A)^{3/2}} \end{aligned}$$
(16)

Further, we suppose that n is sufficiently large, i.e. \(\tilde{K}\le n\). Therefore,

$$ \sum _{k=1}^{\tilde{K}}s_k^2=\sum _{k=1}^{\tilde{K}}\frac{r_k}{\sum _{i=1}^n r_i}\le 1 $$

and

$$\begin{aligned}&1\ge \sum _{k=1}^{\tilde{K}}s_k^2\ge \sum _{k=1}^{\tilde{K}}\frac{C}{2k+A}-\sum _{k=1}^{\tilde{K}}\frac{2B\sqrt{C}}{(2k+A)^{3/2}}\\&\qquad \qquad \qquad \ge \int _{1}^{\tilde{K}}\frac{Cdx}{2x+A}-\frac{2B\sqrt{C}}{(2+A)^{3/2}}- \int _{1}^{\tilde{K}}\frac{2B\sqrt{C}dx}{(2x+A)^{3/2}}\\&\qquad \qquad \qquad \quad \ge \frac{C}{2}\ln \frac{2\tilde{K}+A}{2+A}-\frac{2B\sqrt{C}}{(2+A)^{3/2}}-\frac{1}{2}\frac{B\sqrt{C}}{\sqrt{2+A}}\\&\qquad \qquad \qquad \qquad \ge \frac{C}{2}\ln \frac{2\tilde{K}+A}{2+A}-\frac{5}{2}\frac{B\sqrt{C}}{\sqrt{2+A}}\ge \frac{C}{2}\ln \frac{2\tilde{K}+A}{2+A}-\frac{5B}{2}\sqrt{\frac{C}{A}}, \end{aligned}$$

since \(B\sqrt{C}>0\). Thus,

$$ \ln \frac{2\tilde{K}+A}{2+A}\le \frac{2}{C}\left( 1 + \frac{5B}{2}\sqrt{\frac{C}{A}}\right) =\frac{2}{C}+\frac{5B}{\sqrt{AC}} $$

and

$$\begin{aligned}&\tilde{K}\le A\cdot \exp \left( \frac{2}{C}+\frac{5B}{\sqrt{AC}}\right) =p(\rho +1)\cdot \exp \left( 2\cdot \frac{q}{\varepsilon } \right) \cdot \exp \left( 5\sqrt{\pi } p\rho \sqrt{\frac{1}{p(1+\rho )}}\sqrt{\frac{q}{\varepsilon }}\right) \\&\qquad \qquad \qquad \qquad \qquad \qquad \le p(\rho +1)\cdot \left( \exp \left( q/\varepsilon \right) \right) ^2\cdot \left( exp(\sqrt{(pq)/\varepsilon })\right) ^{5\sqrt{\pi \rho }}, \end{aligned}$$

since \(A=p(\rho +1)\ge 2\). Lemma 6 is proved.

The proof of Theorem 1 follows straightforward from the lemmas above.

5 Conclusion

In this paper, we proposed new approximation scheme for the Capacitated Vehicle Routing Problem with Time Windows. To the best of our knowledge, the scheme proposed is the first EPTAS for this problem for any fixed capacity q and number of time windows p. Our scheme remains PTAS with respect to n even for \(q=\log \log n\) and \(p=\log \log n\). Although the proof presented in this paper concerns the simplest case of the problem (Euclidean plane, single depot), the scheme proposed seems to be applicable to the more general setting of CVRPTW. In forthcoming paper, we are going to present the full proof for multiple depots and Euclidean spaces of an arbitrary fixed dimension \(d>1\).