PTAS for the Euclidean Capacitated Vehicle Routing Problem in $R^d$

Abstract

Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem remaining NP-hard even in the Euclidean spaces of fixed dimension. Thirty years ago, in their celebrated paper, M. Haimovich and A. Rinnoy Kan proposed the first PTAS for the Planar Single Depot CVRP based on their Iterated Tour Partition heuristic. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose an EPTAS for the Euclidean CVRP for any fixed dimension.

1 Introduction

We consider the Capacitated Vehicle Routing Problem, which is the well-known special case of Vehicle Routing Problem [17] belonging to the class of combinatorial optimization models widely adopted in operations research. It is generally believed that, for the first time, as an optimization problem, the VRP was introduced by Dantzig and Ramser in their seminal paper [5]. They considered a routing problem for a fleet of gasoline delivery trucks servicing a number of gas stations supplied by a unique bulk terminal. Demands of serviced gas stations and distances between any two locations were specified. The goal was to find the least cost set of truck routes visiting all the stations.

In its simplest setting, the VRP can be defined as the combinatorial optimization problem aiming at designing the cheapest collection of delivery routes from some dedicated point (depot) to a set of customers (clients) given by their spatial locations. This problem has many known modifications [9, 14] taking into account different additional features and constraints, e.g. depots multiplicity, heterogeneity of customer demand, vehicle capacity, time windows, etc.

In this paper, we suppose that all clients have the same one unit demand and all vehicles have the same capacity, equal to some predefined number q. This specific problem is called [10] Capacitated Vehicle Routing Problem or CVRP. Complexity of this problem is determined by its closeness to some well-known intractable combinatorial problems. For instance, Traveling Salesman Problem (TSP) is just a special case of the CVRP such that a depot is collocated with one of clients and $q\ge n$. Therefore, the CVRP is strongly NP-hard even in the Euclidean plane, since the same results are proven for the TSP [15]. Almost all known special cases of the CVRP (except the case when $q\le 2$) (see, e.g. [14]) are also NP-hard even in the Euclidean spaces of finite dimension.

For these reasons, research on the CVRP is mostly focused on design of approximation algorithms and heuristics. For a general metric, the CVRP is shown to be APX-complete [2] for any fixed $q\ge 3$, i.e. there exists $\varepsilon >0$ such that the existence of a polynomial time $(1+\varepsilon )$-approximation algorithm implies $P=NP$.

Most positive approximation results for CVRP are obtained for the Euclidean plane. One of the first studies of two-dimensional Euclidean CVRP has been due to Haimovich and Rinnooy Kan [10], who presented several heuristics for this problem leading to the first PTAS for $q=O(\log \log n)$. Asano et al. [2] substantially improved this result by designing a PTAS for $q=O(\log n/\log \log n)$. Also they construct a PTAS for the case of $\Omega (n)$ based on the famous Arora’s PTAS [1] for the two-dimensional Euclidean TSP. Recently, Das and Mathieu [6, 7] proposed a quasi-polynomial time approximation scheme (QPTAS) for the two-dimensional Euclidean CVRP for every q with time complexity of $n^{(\log n)^{O(1/\varepsilon )}}$. Khachay and Zaytseva [13] applied the approach proposed in [10] to the construction a PTAS for the Single Depot CVRP in three-dimensional Euclidean space.

The extension of the latter result to the case of any fixed number m of depots and any fixed dimension $d>1$ is the main contribution of this paper. Actually, on the basis of recent geometric results describing the structure of finite $\varepsilon$-nets on the surface of the unit Euclidean sphere $S^{d-1}$, we propose a new Efficient Polynomial Time Approximation Scheme¹ (EPTAS) for the Euclidean CVRP, for which capacity q, the number of depots m and dimension $d>1$ are fixed. The algorithm proposed remains PTAS for the problem with fixed m and d and $q=O(\log \log n)^{1/d}$.

The rest of the paper is organized as follows. In Sect. 2, we recall the general statement of the CVRP along with its metric and Euclidean settings. In Sect. 3, we describe our EPTAS based on the famous Iterated Tour Partition [10] for the case of single depot. Further, in Sect. 4 we extend this result to the case of an arbitrary fixed number m of depots. Section 5 contains summarizing remarks and a short overview of future work.

2 Problem Statement

Recall the necessary definitions and notation.

1. $X=\{x_1,\ldots ,x_n\}$ is a set of clients, $Y=\{y_1,\ldots ,y_m\}$ is a set of depots. Denote by $G^0(X\cup Y,E,w)$ a complete weighted digraph, whose weight function $w:E\rightarrow \mathbb {R}_+$ defines transportation costs for any pair of locations. Hereinafter, the function w is supposed to be symmetric. For any route R consisting of arcs $e_1,\ldots ,e_p$, its cost w(R) is defined by the equation $w(R)=\sum _{i=1}^pw(e_i)$. Along with the digraph $G^0$, we consider its subgraph $G={G^0}\langle {X}\rangle$ induced by the vertex subset X.

2. To any client $x_i$, assign a number $r_i=\min \{w(y_j,x_i):j=1,\ldots ,m\}$ defining the least direct transportation cost among the depots. Breaking ties arbitrarily, define a partition $X_1\cup \ldots \cup X_m=X$ into subsets

$$\begin{aligned} X_j=\{x_i\in X:r_i=w(x_i,y_j)\}, \end{aligned}$$

(1)

such that any client $x_i$ is assigned to the nearest depot $y_j$.

3. Any feasible route has a form $y_{j_s},x_{i_1},\ldots ,x_{i_t},y_{j_f},$ where $y_{j_s}$ and $y_{j_f}$ are depots², $x_{i_1},\ldots ,x_{i_t}$ are distinct clients visited by this route, and $t\le q$.

If $m=1$ the problem in question is called the Single Depot Capacitated Vehicle Routing Problem (SDCVRP). In this case, all feasible routes are simple circuits. Otherwise, the problem is called the Multiple Depot CVRP (MDCVRP). We distinguish two special settings of this problem. In the first one, we denote it MDCVRP1, any feasible route can start and terminate at separate depots. In the second one, MDCVRP2, for any feasible route, its start and finish depots should be identical ($y_{j_s}=y_{j_f}$).

For any aforementioned setting, the goal is, for a given digraph $G^0(X\cup Y,E,w)$ and a capacity q, to find a cheapest set of routes visiting each client exactly once.

Along with the general setting of the SDCVRP and MDCVRP we consider two important their special cases defined in terms of the weight function w.

Metric CVRP. In this case, the graph $G^0$ is supposed to be undirected and w meets the triangle inequality $w(z_1,z_2)\le w(z_1,z_3)+w(z_3,z_2)$ for each $z_1,z_2,z_3\in X\cup Y$.

Euclidean CVRP. Here, $X\cup Y\subset \mathbb {R}^d$ and $w(z_1,z_2)=\Vert z_1-z_2\Vert _2$.

3 Approximability of SDCVRP

The main idea of our approach stems from the famous Iterated Tour Partition (ITP) heuristic introduced by Haimovich and Rinnooy Kan [10] and presented below as Algorithm 1. Using ITP in combination with approximation algorithms for the metric TSP, we construct polynomial time algorithms with asymptotically fixed performance guarantees for the metric SDCVRP and polynomial time approximation scheme for the d-dimensional Euclidean SDCVRP for any fixed $d>1$. Further, in Sect. 4, we extend this approach to the case of multiple depots.

For our constructions, we need the following technical claims proved for the first time in [10]. Although, all the proofs in that paper were carried out for the Euclidean plane only, it is easy to verify that they remain true in the much more general setting of the CVRP as well. For the sake of brevity, we skip the proofs (see [13] for details).

Lemma 1

For $\bar{r}=1/n\sum _{i=1}^nr_i$, the following equation

$$\begin{aligned} w(S_{\mathrm {ITP}})\le 2\left\lceil n/q\right\rceil \bar{r}+\left( 1-\frac{\lceil n/q\rceil }{n}\right) w(H)\le 2\left\lceil n/q\right\rceil \bar{r}+\left( 1-1/q\right) w(H) \end{aligned}$$

(2)

is valid.

It should be noted that the upper bound claimed in Lemma 1 is valid for the most general setting of the SDCVRP. In the metric case, for any feasible solution S of the SDCVRP, we can obtain also a lower bound on w(S) by means of the cost of the Hamiltonian circle $H_S$ induced by S in the graph G.

Indeed, let S consists of routes $C_1,\ldots ,C_t$. Excluding the depot y from each route $C_i$ and connecting arbitrarily the chains obtained to produce a single (Hamiltonian) circle $H_S$, we obtain the following bound.

Lemma 2

$$\begin{aligned} w(S)\ge \max \left\{ 2 n\bar{r}/q,w(H_S)\right\} . \end{aligned}$$

(3)

Combining the bounds given by Lemmas 1 and 2, we obtain the following equation relating the optimum value $\mathrm {VRP}^*(X,\{y\})$ of the metric SDCVRP and the weight $\mathrm {TSP}^*(X)$ of an optimal Hamiltonian circle in the corresponding TSP instance.

Theorem 1

$$ \min \left\{ 2\bar{r}n/q,\mathrm {TSP}^*(X)\right\} \le \mathrm {VRP}^*(X,\{y\})\le 2\lceil n/q\rceil \bar{r}+\left( 1-1/q\right) \mathrm {TSP}^*(X). $$

The results above give us an ability to represent a performance guarantee of any ITP-based approximation algorithm for metric SDCVRP in terms of heuristics used for obtaining approximate solutions of the inner TSP. Indeed, suppose, we obtain a Hamiltonian cycle H in the graph G, whose cost $\mathrm {TSP}^*\le w(H)\le \rho \mathrm {TSP}^*$ for some $\rho \ge 1$. Using (2) and (3), we obtain

$$\begin{aligned} \frac{w(S)}{\mathrm {VRP}^*(X,\{y\})}\le \frac{2\left\lceil n/q\right\rceil \bar{r}+\left( 1-1/q\right) \rho \,\mathrm {TSP}^*(X)}{\max \left\{ 2\bar{r}n/q,\mathrm {TSP}^*(X)\right\} }\le \frac{q}{n} + 1 +\rho . \end{aligned}$$

(4)

Since the RHS of Eq. (4) tends to $1+\rho$ any time when $q=o(n)$, an arbitrary $\rho$-approximation algorithm for the metric TSP produces asymptotically $(1+\rho )$-approximation algorithm for the metric SDCVRP.

Further, since the running time of the ITP is at most $O(n^2)$, the overall time complexity of any based-on-ITP approximation algorithm is defined by the running time of the initial approximation algorithm for the metric TSP. For instance, the famous Christofides’ 3 / 2-approximation algorithm [4] with the running time of $O(n^{3})$ produces asymptotically 5 / 2-approximation algorithm with the same time complexity bound, and the well-known Arora’s PTAS [1] for the d-dimensional Euclidean TSP, for any fixed $d>1$ and any $\varepsilon \in (0,1)$, produces asymptotically $(2+\varepsilon )$-approximation algorithm with the time complexity of $(n(\log n)^{(O(\sqrt{d}/\varepsilon ))^{d-1}}$.

To proceed with PTAS for the Euclidean SDCVRP, we recall Algorithm 2 proposed in [10].

Algorithm 2 makes a decomposition of the initial instance into two smaller instances of the SDCVRP. The first subproblem, for the outer clients, is supposed to be solved to optimality, while for the second one describing the inner clients, an approximate solution is found by Algorithm 1. Lemma 3 helps us to relate optimum values of these two subproblems.

Lemma 3

For an arbitrary $k\in \{1,\ldots ,n\}$ the equation

$$\begin{aligned} \mathrm {VRP}^*(X,\{y\})\le \mathrm {VRP}^*(X(k),\{y\})+\mathrm {VRP}^*(X\setminus X(k),\{y\})\\ \le \mathrm {VRP}^*(X,\{y\}) + 4(k-1)r_k. \end{aligned}$$

is valid.

As previous results, Lemma 3 remains true for an arbitrary metric.

Further, we restrict ourselves to finite dimensional Euclidean spaces. All remaining assertions of this section are based on the following existence lemma for a finite $\varepsilon$-net on the surface of the unit Euclidean sphere $S^{d-1}$ in terms of the angular distance

$$ dist(x_1,x_2)=\arccos (x_1,x_2),\ (x_1,x_2\in S^{d-1}) $$

(see, e.g. [11], Lemma 3.1). According to the classic definition (see, e.g. [16]), we call some finite subset $N\subset S^{d-1}$ a finite $\varepsilon$-net (on the sphere $S^{d-1}$) if, for any $x\in S^{d-1}$, there exists $\xi \in N$ such that $dist(\xi ,x)\le \varepsilon$.

Lemma 4

For an arbitrary $h\in (0,h_0)$, $h_0=\pi /(6\sqrt{d-1})$, on the sphere $S^{d-1}$ there exists an $h\sqrt{d-1}$-net $N=N(d,h)$ such that $|N|=Ch^{-(d-1)}$ for some constant $C=C(d)$.

Using the claim of Lemma 4, we obtain an upper bound for the optimum value $\mathrm {TSP}^*(X)$ of an instance of the Euclidean TSP in terms of the radius of an enclosing sphere. Suppose, a TCP instance is specified by a set $X=\{x_1,\ldots ,r_n\}$ contained within the Euclidean ball $B(y,R)\subset \mathbb {R}^d$ of radius R centered at y. As above, we assume that all the clients are numbered in non-increasing order of their distances $r_i=\Vert x_i-y\Vert _2$ from the depot y.

Lemma 5

For an arbitrary $d>1$ and a finite $X\subset B(y,R)$ the following bounds

$$ \mathrm {TSP}^*(X)\le \left\{ \begin{array}{rl} C_1R^{1/d}(\sum _{i=1}^nr_i)^{(d-1)/d},&{} \text{ if } \sum \nolimits _{i=1}^nr_i>RC(\pi /6)^{-d}(d-1)^{(d+1)/2},\\[1ex] C_2R,&{} \text{ otherwise, } \end{array}\right. $$

are valid, where

$$ C_1=2dC^{1/d}(d-1)^{(d-1)/{2d}}\ \text{ and } C_2=2dC(\pi /6)^{-(d-1)}(d-1)^{(d-1)/2}. $$

Proof

By Lemma 4, for any $h\in (0,h_0)$, $h_0=\pi /(6\sqrt{d-1})$ on the surface of the ball B(y, R) there exists a finite $h\sqrt{d-1}$-net N of $Ch^{-(d-1)}$ elements. Connect any $\xi _j\in N$ with the center y by radial segment, after that connect each client $x_i$ with the nearest radius $[y,\xi _j]$ (by the appropriate orthogonal line segment). Further, we construct a salesman tour by the well-known edge-doubling technique for the tree obtained.

Let $\Phi (h)$ be the length of the tour constructed. Again, by Lemma 4, for any $h\in (0,h_0)$,

$$\begin{aligned} \mathrm {TSP}^*(X)\le \Phi (h)= 2h\sqrt{d-1}\sum _{i=1}^n r_i+2RCh^{-{(d-1)}}. \end{aligned}$$

(5)

Minimizing the RHS of Eq. (5) subject to $0<h<\pi /(6\sqrt{d-1})$, we obtain the claimed bounds.

Indeed, $\inf \Phi (h)$ on this range coincides either with $\Phi (h_{min})$, where

$$\begin{aligned} h_{min}=\left( \frac{RC}{\sum _{i=1}^nr_i}\sqrt{d-1}\right) ^{1/d}, \end{aligned}$$

if

$$ h_{min}<h_0,\ \text{ i.e. } \sum _{i=1}^nr_i>RC(d-1)^{(d+1)/2}(\pi /6)^{-d}, $$

or with $\Phi (h_0)$, otherwise. In the first case, we obtain

$$\begin{aligned} \Phi (h_{min})&=2\left( \frac{RC}{\sum _{i=1}^nr_i}\sqrt{d-1}\right) ^{1/d}\sqrt{d-1}\sum _{i=1}^nr_i+2RC\left( \frac{RC}{\sum _{i=1}^nr_i}\sqrt{d-1}\right) ^{-(d-1)/d}\\&=\underbrace{2dC^{1/d}(d-1)^{-(d-1)/(2d)}}_{C_1}\cdot R^{1/d}(\sum _{i=1}^nr_i)^{(d-1)/d} \end{aligned}$$

If, on the other hand,

$$\begin{aligned} \sum _{i=1}^nr_i\le RC(d-1)^{(d+1)/2}(\pi /6)^{-d}, \end{aligned}$$

(6)

then

$$\begin{aligned} \Phi (h_0)&=2\sqrt{d-1}\frac{\pi }{6\sqrt{d-1}}\sum _{i=1}^nr_i+2RC\left( \frac{\pi }{6}\right) ^{d-1}(\sqrt{d-1})^{(d-1)}\\&\quad \le \frac{\pi }{3}RC(d-1)^{(d+1)/2}\left( \frac{\pi }{6}\right) ^{-d}+2RC\left( \frac{\pi }{6}\right) ^{-(d-1)}(d-1)^{(d-1)/2}\\&=RC\left( \frac{\pi }{6}\right) ^{-d}\left( \frac{\pi }{3}(d-1)+2\cdot \frac{\pi }{6}\right) (d-1)^{(d-1)/2}\\&=\underbrace{2Cd\left( \frac{\pi }{6}\right) ^{-(d-1)}(d-1)^{(d-1)/2}}_{C_2}\cdot R. \end{aligned}$$

Lemma 5 is proved.

Further, for some $d>1$, consider an instance of the SDCVRP in the d-dimension Euclidean space. By

$$\begin{aligned} e(k)&=\frac{w(S_{\mathrm {CITP}}(X))-\mathrm {VRP}^*(X)}{\mathrm {VRP}^*(X)}\\&=\frac{\mathrm {VRP}^*(X(k))+w(S_{\mathrm {ITP}}(X\setminus X(k)))-\mathrm {VRP}^*(X)}{\mathrm {VRP}^*(X)}, \end{aligned}$$

denote a relative error of the approximate solution produced by Algorithm 2, using for some $\rho$ a $\rho$-approximation algorithm for finding an approximate solution of the inner TSP.

Lemma 6

For an arbitrary $\rho \ge 1$ and $\varepsilon >0$ there exists $k=k(\varepsilon )\in \mathbb {N}$ such that $e(k)\le \varepsilon$.

Proof

Applying the claims of Lemmas 1–3 and introducing the notation

$$ \bar{r}_k=\frac{\sum _{i=k}^{n}r_i}{n-k+1}, $$

we obtain

$$\begin{aligned} e(k)\le \frac{4(k-1)r_k+2\lceil (n-k+1)/q\rceil \bar{r}_k+\rho \mathrm {TSP}^*(X\setminus X(k))-2\bar{r}_k(n-k+1)/q}{2n\bar{r}/q}\\ \le q(2k-1)\frac{r_k}{\sum _{i=1}^nr_i}+\frac{q\rho }{2\sum _{i=1}^nr_i}\mathrm {TSP}^*(X\setminus X(k)). \end{aligned}$$

By Lemma 5,

$$\begin{aligned} e(k)\le q(2k-1)\frac{r_k}{\sum _{i=1}^nr_i}+\frac{q\rho }{2}\max \left\{ C_1\left( \frac{r_k}{\sum _{i=1}^nr_i}\right) ^{1/d}\!\!\!\!\!\!\!,\ C_2\frac{r_k}{\sum _{i=1}^nr_i}\right\} \\ \le q(2k-1)\frac{r_k}{\sum _{i=1}^nr_i}+\frac{q\rho }{2}\max \{C_1,C_2\}\left( \frac{r_k}{\sum _{i=1}^nr_i}\right) ^{1/d}\!\!\!\!\!, \end{aligned}$$

since $r_k\le \sum _{i=1}^nr_i$.

Further, denote $(r_k/\sum _{i=1}^nr_i)^{1/d}$ by $s_k$. Suppose that, for any $t\in \{1,\ldots ,k\}$,

$$\begin{aligned} q(2t-1)s_t^d+\frac{q\rho }{2}C^*s_t>\varepsilon \end{aligned}$$

(7)

is valid, where $C^*=\max \{C_1,C_2\}$ depends on d ultimately.

There exist two options. In the first option, $s_t\ge \varepsilon /(q\rho \,C^*)$ for each t. Then,

$$ 1\ge \sum _{t=1}^ks_t^d\ge k\left( \frac{\varepsilon }{q\rho \,C^*}\right) ^d\!\!, $$

therefore,

$$\begin{aligned} k\le \left( \frac{q\rho \,C^*}{\varepsilon }\right) ^d\!\!. \end{aligned}$$

(8)

Consider the other option. Let $t_0$ be the smallest number, for which

$$ s_{t_0}<\varepsilon /(q\rho \,C^*). $$

By construction, the same inequality is valid also for each $t_0\le t\le k$, and, by (7), $s_t^d>\varepsilon /(2q(2t-1))$. Combining the bounds obtained, we get

$$\begin{aligned} 1\ge \sum _{t=1}^ks_t^d\ge (t_0-1)\left( \frac{\varepsilon }{q\rho \,C^*}\right) ^d+\frac{\varepsilon }{2q}\sum _{t=t_0}^k\frac{1}{2t-1}\\ \ge (t_0-1)\left( \frac{\varepsilon }{q\rho \,C^*}\right) ^d+\frac{\varepsilon }{2q}\int \limits _{t_0}^{k+1}\frac{dt}{2t-1}\\ =(t_0-1)\left( \frac{\varepsilon }{q\rho \,C^*}\right) ^d+\frac{\varepsilon }{4q}(\ln (2k+1)-\ln (2t_0-1)). \end{aligned}$$

(9)

Without loss of generality suppose that $\varepsilon \le 4q\rho$. This equation together with the obvious (for $d>1$) condition $C^*\ge 4$ implies

$$ \left( \frac{\varepsilon }{q\rho \,C^*}\right) ^d\le \frac{\varepsilon }{4q}, $$

and

$$\begin{aligned} \left( \frac{\varepsilon }{q\rho \,C^*}\right) ^{-d} \ge t_0-1+\ln (2k+1)-\ln (2t_0-1). \end{aligned}$$

(10)

Minimizing the RHS of (10) subject to $t_0\in \{1,\ldots ,k\}$, we obtain

$$\begin{aligned} k\le \frac{1}{2}e^{\left( \frac{q\rho \,C^*}{\varepsilon }\right) ^d}. \end{aligned}$$

(11)

Comparing bounds (8) and (11), come to the decision that the segment

$$\begin{aligned} \left[ 1,\frac{1}{2}e^{\left( \frac{q\rho \,C^*}{\varepsilon }\right) ^d}+1\right] \end{aligned}$$

(12)

definitely contains the required number $k=k(\varepsilon )$. Lemma is proved.

Theorem 2

Suppose that $\rho$-approximation algorithm with the running time of $O(n^c)$ is used for the inner TSP, then, for any fixed q, $\rho \ge 1$, and $d\ge 2$, Algorithm 2 is an Efficient Polynomial Time Approximation Scheme (EPTAS) for the SDCVRP.

Proof

Indeed, for a given $\varepsilon >0$, we can find $k(\varepsilon )$ such that $e(k)\le \varepsilon$ by Lemma 6. An exact solution $S^*(X(k(\varepsilon ))$ can be found by dynamic programming (see, e.g. [3]) in time $O(K^q2^K)$, where K is the upper end of the segment (12). The rest of Algorithm 2 requires $O(n^c)+O(n^2)$ time. Therefore, the overall time complexity of Algorithm 2 can be bounded from above by a polynomial function of n, whose order and all the coefficients except the constant term does not depend on $\varepsilon$. That is, Algorithm 2 is an EPTAS for the SDCVRP for any fixed q, $\rho \ge 1$, and $d\ge 2$. Theorem is proved.

It should be noted that Algorithm 2 remains a PTAS for the SDCVRP even under slightly relaxed restrictions on its parameters, e.g. for any fixed d, $\rho$, and $q=O((\log \log (n))^{1/d})$.

4 PTAS for the MDCVRP

Further, we extend the results of Sect. 3 to the case of multiple depots. The main idea of such an extension for the Euclidean plane is proposed in [3]. The authors proposed to partition the client set X according to equation (1), after that the initial MDCVRP can be decomposed into a collection of the appropriate SDCVRP instances for subsets $X_j\setminus X(k)\cup \{y_j\}$. Below, we give a short overview of this technique.

Similarly to Sect. 3, denote the relative error of Algorithm 3 by

$$\begin{aligned} e(k)&=\frac{w(S_{\mathrm {CITP}}(X))-\mathrm {VRP}^*(X)}{\mathrm {VRP}^*(X)}\\ \nonumber&=\frac{\mathrm {VRP}^*(X(k))+\sum _{j=1}^mw(S_{\mathrm {ITP}}(X_j\setminus X(k)))-\mathrm {VRP}^*(X)}{\mathrm {VRP}^*(X)}. \end{aligned}$$

(13)

Lemma 7

In the MDCVRP1, for an arbitrary $m>1$, $\rho \ge 1$, and $\varepsilon >0$, there exists a number $k=k(\varepsilon )\in \mathbb {N}$ such that $e(k)\le \varepsilon$.

Proof

Let $X'_j=X_j\setminus X(k)$, $n_j=|X'_j|$ and $\bar{r}_{jk}=\sum _{x_i\in X'_j}r_i/n_j$. Following the proof idea of Lemma 6,

$$\begin{aligned} e(k)\le \frac{4(k-1)r_k+\sum _{j=1}^m(2\lceil n_j/q\rceil \bar{r}_{jk}+\rho \mathrm {TSP}^*(X'_j)-2\bar{r}_{jk}n_j/q)}{2n\bar{r}/q}\\ \le q(2k-2+m)\frac{r_k}{\sum _{i=1}^nr_i}+\frac{q\rho }{2\sum _{i=1}^nr_i}\sum _{j=1}^m\mathrm {TSP}^*(X'_j)\\ \le q(2k-2+m)\frac{r_k}{\sum _{i=1}^nr_i}+\frac{mq\rho }{2}C^*\left( \frac{r_k}{\sum _{i=1}^nr_i}\right) ^{1/d}\!\!\!\!\!. \end{aligned}$$

Suppose that, for an arbitrary $t\in \{1,\ldots ,k\}$

$$\begin{aligned} q(2t-2+m)\frac{r_t}{\sum _{i=1}^nr_i}+\frac{mq\rho }{2}C^*\left( \frac{r_t}{\sum _{i=1}^nr_i}\right) ^{1/d}>\varepsilon \end{aligned}$$

(14)

and simultaneously

$$\begin{aligned} s^d_t=\frac{r_t}{\sum _{i=1}^nr_i}\ge \left( \frac{\varepsilon }{mq\rho \,C^*}\right) ^d, \end{aligned}$$

(15)

we get the bound

$$ k\le \left( \frac{mq\rho \,C^*}{\varepsilon }\right) ^d, $$

similar to Eq. (8). On the other hand, if the system (14) does not imply (15) and $t_0$ the smallest number, for which the opposite inequality holds. Then, similarly to (9), we obtain

$$\begin{aligned} 1\ge \sum _{t=1}^ks_t^d\ge (t_0-1)\left( \frac{\varepsilon }{mq\rho \,C^*}\right) ^d+\frac{\varepsilon }{2q}\sum _{t=t_0}^k\frac{1}{2t-2+m}\\ \ge (t_0-1)\left( \frac{\varepsilon }{mq\rho \,C^*}\right) ^d+\frac{\varepsilon }{2q}\int \limits _{t_0}^{k+1}\frac{dt}{2t-2+m}\\ \ge \left( \frac{\varepsilon }{mq\rho \,C^*}\right) ^d((t_0-1)+(\ln (2k+m)-\ln (2t_0-2+m)))\\\ge \left( \frac{\varepsilon }{mq\rho \,C^*}\right) ^d\ln ((2k+m)/m), \end{aligned}$$

and

$$ k\le \frac{m}{2}e^{\left( \frac{mq\rho \,C^*}{\varepsilon }\right) ^d}. $$

Therefore, the range

$$\begin{aligned} \left[ 1,\frac{m}{2}e^{\left( \frac{mq\rho \,C^*}{\varepsilon }\right) ^d}+1\right] \end{aligned}$$

(16)

definitely contains the required number $k(\varepsilon )$. Lemma is proved.

Lemma 7 implies that Algorithm 3 is an EPTAS for MDCVRP1. To prove that Algorithm 3 is an EPTAS for MDCVRP2 as well, we need a version of Lemma 3 proven in [3].

Lemma 8

For the MDCVRP2 and for an arbitrary $k\in \{1,\ldots ,n\}$, the equation

$$\begin{aligned} \mathrm {VRP}^*(X,Y)\le \mathrm {VRP}^*(X(k),Y)+\mathrm {VRP}^*(X\setminus X(k),Y)\\ \le \mathrm {VRP}^*(X,Y) + 2(q-1)(k-1)r_k \end{aligned}$$

is valid.

Lemma 9

For the MDCVRP2 and for an arbitrary $m>1$, $\rho \ge 1$, and $\varepsilon >0$ there exists a number $k=k(\varepsilon )\in \mathbb {N}$ such that $e(k)\le \varepsilon$.

Proof

Almost the same way that the proof of Lemma 7 was obtained from the claims of Lemmas 1–3 and Lemma 5 one can show that Lemmas 9 follows from Lemmas 1–2, 5, and 8. Finally, we obtain that the range

$$\begin{aligned} \left[ 1,(m+1)e^{\left( \frac{mq\rho \,C^*}{\varepsilon }\right) ^d}\right] \end{aligned}$$

(17)

definitely contains the required $k=k(\varepsilon )$, for which $e(k)\le \varepsilon$. Lemma is proved.

Our final results follows from Lemmas 7 and 9 and can be proved in the same way as Theorem 2.

Theorem 3

Under the conditions of Theorem 2, for any $\varepsilon >0$, for any fixed $m, d>1$, $\rho \ge 1$, and q, Algorithm 3 is an EPTAS for the MDCVRP1 and MDCVRP2, whose time complexity is $O(n^c+n^2+mK^q2^K)$, where $K=K(\varepsilon )$ coincides with right-hand ends of ranges (16) and (17), respectively.

5 Conclusion

In the paper, we show that Algorithms 2 and 3 together with an arbitrary polynomial time fixed-guarantee approximation algorithm for the TSP induce an EPTAS for the SDCVRP and MDCVRP in any fixed-dimension Euclidean spaces, respectively. Furthermore, the time complexity bounds found remain polynomial with respect to n even for less accurate³ but maybe much more fast algorithms for the inner TSP, which can be useful for tackling Big Data.

Future work can be focused on combining the results obtained with recent results on cycle covers of graphs (see, e.g. [8, 12]).