Approximation Scheme for the Capacitated Vehicle Routing Problem with Time Windows and Non-uniform Demand

Abstract

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is the well-known combinatorial optimization problem having numerous valuable applications in operations research. Unlike the classic CVRP (without time windows constraints), approximation algorithms with theoretical guarantees for the CVRPTW are still developed much less, even for the Euclidean plane. In this paper, perhaps for the first time, we propose an approximation scheme for the planar CVRPTW with non-uniform splittable demand combining the well-known instance decomposition framework by A. Adamaszek et al. and Quasi-Polynomial Time Approximation Scheme (QPTAS) by L. Song et al. Actually, for any $\varepsilon \in (0,1)$ the scheme proposed finds a $(1+\varepsilon )$-approximate solution of the problem in polynomial time provided the capacity q and the number p of time windows does not exceed $2^{\log ^\delta n}$ for some $\delta =O(\varepsilon )$. For any fixed p and q the scheme is Efficient Polynomial Time Approximation Scheme (EPTAS) with subquadratic time complexity.

1 Introduction

The Capacitated Vehicle Routing Problem (CVRP) is the famous combinatorial optimization problem, which was introduced by Dantzig and Ramser in their seminal paper [9] and has a wide range of relevant applications in practice (see, e.g. [30]). In the simplest setting of the problem, we are given by a finite set of customers having the same unit demand and a fleet of identical capacitated vehicles located initially at a single depot. The goal is to construct a collection of vehicle routes minimizing the total transportation cost and servicing all the customers.

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) [20, 30] is an extension of the CVRP, where service of each customer should start at a specified time interval, called a time window. CVRP with hard windows is widely applicable in natural gas distribution [7], dial-ride company planning [11], continent-scale distribution of building materials [23], low-carbon economy [26], and other practical transportation problems [25].

The problem is well-investigated by specialists in the field of exact methods, heuristics, and meta-heuristics. Recently, a significant progress was achieved in solving practically important instances of the CVRPTW by local-search heuristics [13], Tabu-search [29], genetic [31], memetic [6, 21], ant colony algorithms [22], and their combinations (see, e.g. [8]).

Nevertheless, approximation results for this problem in the class of algorithms with theoretical guarantees are still extremely rare. To the best of our knowledge, they are exhausted by the Quasi-Polynomial Time Approximation Scheme (QPTAS) proposed in [28] and extended recently to the case of multiple depots [27] and our recent Efficient Polynomial-Time Approximation Schemes (EPTAS) for the CVRPTW with any fixed capacity and number of time windows. In addition, all known results relate to the special setting of the problem, where all customers have the same unit demand.

Our Contribution. In this paper, perhaps for the first time for the CVRPTW with non-uniform demand, we propose an approximation scheme with theoretically proved time complexity bounds. Our scheme extends the decomposition framework introduced by Adamaszek et al. in [1] for efficient approximation of the simplest unit-demand CVRP on the Euclidean plane to more general case of the problem to take into account additional time windows constraints and a non-uniform splittable customer demand.

The rest of this paper is structured as follows. In Sect. 2, we give a short overview of known approximation results for the CVRPTW in the class of algorithms with theoretical bounds. In Sect. 3, we recall the mathematical setting of the CVRPTW with non-uniform demand. Section 4 presents the mail idea of the proposed scheme. In subsequent sections, we discuss this scheme in detail. We start in Sect. 5 with basic known results needed for the subsequent constructions. Then, in Sect. 6 we present our approximation scheme with a proof of its accuracy bound. Time complexity bounds are proved in the Sect. 7. Finally, in Sect. 8, we summarize the results obtained and list some questions that still remain open.

2 Related Work

Being an extension of the well-known strongly NP-hard Traveling Salesman Problem (TSP) [30], the Capacitated Vehicle Routing Problem is also strongly NP-hard even in the Euclidean plane [24] provided the capacity q belongs to the input. The metric CVRP remains intractable and APX-hard even for any fixed $q\ge 3$ and for the two-valued $\{1,2\}$-metric.

For the Euclidean CVRP, the first approximation results date to the seminal paper by Haimovich and Rinnooy Kan [12], where the first PTAS for the CVRP on the plane and capacity $q=o(\log \log n)$ and first constant-factor algorithms for an arbitrary metric were introduced. Then, in [3] an improved scheme, whose running time retains polynomial for the wider range $q = O(\log n/ \log \log n)$, was proposed.

The ideas proposed by Arora in his celebrated paper [2] were used by Das and Mathieu to design their Quasi-Polynomial Time Approximation Scheme (QPTAS) [10] for the general case of the planar Euclidean CVRP. Their QPTAS finds a $(1+\varepsilon )$-approximate solution of this problem (for the case, when q is a part of the instance) in time $n^{(\log n)^{O(1/\varepsilon )}}$. Using this QPTAS as a black-box, Adamaszek, Czumaj, and Lingas [1] showed that $(1+\varepsilon )$-approximate solution of the planar CVRP can be found in polynomial time, if $q \le 2^{\log ^\delta n}$ for some $\delta = \delta (\varepsilon )$. Some aforementioned results were extended to the case of Euclidean spaces of an arbitrary finite dimension [14, 18, 19] and several special graphs [4, 5].

Unlike CVRP, approximability of the Euclidean CVRPTW is much less investigated. To the best of our knowledge, the family of known approximation algorithms for this problem is exhausted by a Quasi-Polynomial Time Approximation Scheme (QPTAS) developed in [27, 28] for the general case of the problem and approximation schemes for the case of $\max \{p,q\}=o(\log \log n)$ and $p^3q^4=O(\log n)$, where p is the number of time windows, proposed in [16] and [15, 17], respectively.

All aforementioned results for the CVRPTW relate to the simplest setting of the problem, when all customers have the same unit demand. In this paper, we try to bridge this gap and to propose an approximation scheme for the case of the CVRPTW with a non-uniform splittable demand.

3 Problem Statement

We consider the Euclidean Capacitated Vehicle Routing Problem with Time Windows and non-uniform Splittable customer Demand (CVRPTW-SD). For the sake of simplicity, we restrict ourselves to the case of the Euclidean plane, pairwise disjoint time windows, and a single depot. An instance of the CVRPTW-SD is defined by

• a set $X=\{x_1,\ldots ,x_n\}$ of customer locations (customers) on the Euclidean plane and a dedicated location y also known as depot, such that, for any locations $v_1,v_2\in X\cup \{y\}$, transportation cost associated with the direct move from $v_1$ to $v_2$ coincides with $\Vert v_1-v_2\Vert _2$

• a natural-valued function d specifying demand d(x) of any customer $x\in X$ that should be serviced by one or more vehicle routes

• an unbounded fleet of vehicles having the same integer capacity q and located initially in the depot y

• a linearly ordered set $\mathcal {T}=\{T_1,\ldots ,T_p\}$ of the consecutive time windows, such that the demand d(x) of any customer x should be fulfilled within the given time window $T(x)\in \mathcal {T}$; we assume that, for any $1\le j<p$, the time window $T_j$ precedes $T_{j+1}$ and use the notation $T_j\prec T_{j+1}$.

The goal is to satisfy the demand of each customer minimizing the total transportation cost with respect to the capacity and time windows constraints.

Mathematically, an instance of the CVRPTW-SD is given by a complete node- and edge-weighted graph $G=(X\cup {y},E,d,w)$, natural number q, and a partition

$$\begin{aligned} X_1\cup \ldots \cup X_p=X,\quad \text {where } X_j=\{x_i\in X:T(x_i)\in \mathcal T\}, \ (j\in \{1,\ldots ,p\}). \end{aligned}$$

(1)

To any customer node $x_i\in X$, the weighting function d assigns¹ the positive integer demand $d_i=d(x_i)$, while the function w defines the transportation cost $w(v_1,v_2)=\Vert v_1-v_2\Vert _2$ for any edge $e=\{v_1,v_2\}\in E$.

A feasible route is an ordered pair $\mathcal {R}_j=(R_j,D_j)$, where $R_j=y,x_{i_1},\ldots ,x_{i_s},y$ is a simple cycle in the graph G and the n-tuple $D_j=(d_{1j},\ldots ,d_{nj})$ satisfying time windows

$$ T(x_{i_l})\preceq T(x_{i_{l+1}}),\quad (1\le l<s) $$

and capacity

$$ \begin{array}{ll} 1\le d_{i_l j}\le d_{i_l},&{} \quad (1\le l\le s)\\[1ex] d_{ij}=0,&{}\quad i\not \in \{i_1,\ldots ,i_s\}\\[1ex] \displaystyle \sum _{i=1}^n d_{ij}\le q \end{array} $$

constraints, where $d_{ij}$ is a part of the i-th customer demand covered by the route $R_j$. To any feasible route $\mathcal {R}$, we assign the transportation cost

$$ w(\mathcal {R})=w(y,x_{i_1})+w(x_{i_1},x_{i_2})+\ldots +w(x_{i_s},y). $$

The goal is to find, for some $m\ge 1$, a minimum cost multi-cover $\mathcal {U}=(\mathcal {R}_1,\ldots , \mathcal {R}_m)$ of the graph G, satisfying the total customer demand, i.e.

$$ \sum _{j=1}^m d_{ij}=d_i, \quad (1\le i\le n). $$

In the sequel, we propose a novel approximation scheme for this problem, which is an Efficient Sub-Quadratic Approximation Scheme for any fixed capacity q and the number p of time windows retaining the polynomial running time, when $\max \{p,q\}\le 2^{{\log ^\delta n}}$ for some $\delta =\delta (\varepsilon )$.

4 Main Idea

Our scheme extends the approach proposed by Adamaszek et al. in [1] to the more general case of the Capacitated Vehicle Routing Problem augmented by non-uniform splittable customer demand and time windows constraints. In this section, we give a short overview of the scheme, which consists of the following stages.

Preprocessing. To any customer $x_i$, we assign the distance $r_i=w(y,x_i)$ from the depot y and relabel the customers in non-increasing order of these distances, i.e., $r_1\ge \ldots \ge r_n$. Then, given an $\varepsilon >0$, we set a tolerance threshold

$$\begin{aligned} \rho =\frac{r_1\varepsilon }{N}, \text { where }N=\sum _{i=1}^n\left\lceil \frac{d_i}{q}\right\rceil , \end{aligned}$$

(2)

and exclude all the customers $x_i$, for which $r_i\le \rho$.

Rounding. We reduce the given instance of the CVRPTW-SD to an appropriate instance of the special kind, which we call rounded. To proceed with such a reduction, we draw a number of circles centered at the depot y and separating them into equal sectors by rays spreading from this depot and introduce an accuracy dependent grid consisting of locations, which are the intersections between circles and rays. We divide each location to p slots by the number of given time windows and move any customer $x_i$ to the corresponding slot of the closest location. Finally, we show that any $(1+\varepsilon )$-approximate solution of the rounded instance obtained can be efficiently transformed to a $(1+O(\varepsilon ))$-approximate solution of the initial one. Therefore, in the sequel, we assume that the given instance is rounded.

Decomposition. At this stage, we decompose the given rounded CVRPTW-SD instance into a number of independent subinstances of two kind, we call them white and gray, which can be solved in parallel. We show that, to obtain an $(1+O(\varepsilon ))$-approximate solution of the initial instance, it is sufficient to construct $(1+\varepsilon )$-approximate solution of any white subinstance and approximate any gray subinstance by an appropriate adaptation of the well-known Iterative Tour Partition (ITP) heuristic [12]. Then, following [1], we show that any subinstance (white or gray) can be efficiently reduced to an equivalent one, whose total demand does not exceed a polynomial of the capacity q, the number of time windows p and $1/\varepsilon$.

Blackboxing. Finally, we complete our approximation scheme by employing the QPTAS proposed in [28] and our extension of the ITP heuristic [16] to find approximate solutions of all the reduced white and gray subinstances, respectively.

5 Preliminaries

We start with some necessary definitions and facts. All of them remain valid not only for the planar setting of the CVRPTW considered in this paper but also for the general metric CVRPTW defined by an arbitrary non-negative edge-weighting function w satisfying the triangle inequality.

Lemma 1

For any instance of the $\mathrm {\text {CVRPTW-SD}}$, such that $r_1\ge \ldots \ge r_n$, $r_i=w(y,x_i)$, the following inequality

$$\begin{aligned} \mathrm {OPT}\ge \max \left\{ \mathrm {TSP}^*(X\cup \{y\}), 2r_1, \frac{2}{q}\sum _{i=1}^nd_ir_i \right\} \end{aligned}$$

(3)

is valid, where $\mathrm {TSP}^*(X\cup \{y\})$ is the optimum value of the TSP instance defined by the graph $G=G(X\cup \{y\},E,w)$.

Proof

Since the inequalities $\mathrm {OPT}\ge \mathrm {TSP}^*(X\cup \{y\})\ge 2r_1$ are a straightforward consequence of the triangle inequality, we prove the bound $\mathrm {OPT}\ge \frac{2}{q}\sum _{i=1}^nd_ir_i$.

Let $\mathcal {U}=\{\mathcal {R}_1,\ldots ,\mathcal {R}_m\}$ be an arbitrary optimum solution of the given CVRPTW-SD instance. For each $j\in [m]=\{1,\ldots , m\}$, introduce the non-empty subset $X(\mathcal {R}_j)=\{x_i\in X:d_{ij}>0\}$ of customers visited by the route $\mathcal {R}_j$. Since, for any $x_i\in X(\mathcal {R}_j)$, $2r_i=w(y,x_i)+w(x_i,y)\le w(\mathcal {R}_j)$, by the triangle inequality, the following equation

$$\begin{aligned} \frac{d_{ij}}{\sum _{l=1}^nd_{lj}}w(\mathcal {R}_j)\ge \frac{2d_{ij}}{\sum _{l=1}^nd_{lj}}r_i \end{aligned}$$

is valid for each customer $x_i\in X$. Therefore,

$$\begin{aligned} w(\mathcal {R}_j)=\frac{\sum _{i=1}^nd_{ij}}{\sum _{l=1}^nd_{lj}}w(\mathcal {R}_j)\ge \frac{2\sum _{i=1}^nd_{ij}r_i}{\sum _{l=1}^nd_{lj}}\ge \frac{2}{q}\sum _{i=1}^nd_{ij}.r_i, \end{aligned}$$

since $q\ge \sum _{l=1}^n d_lj,$ and

$$\begin{aligned} w(\mathcal {U})=\sum _{j=1}^mw(\mathcal {R}_j)\ge \frac{2}{q}\sum _{j=1}^m\sum _{i=1}^nd_{ij}r_i=\frac{2}{q}\sum _{i=1}^nr_i\sum _{j=1}^md_{ij}=\frac{2}{q}\sum _{i=1}^nd_ir_i. \end{aligned}$$

Lemma is proved.

The well-known Iterative Tour Partition (ITP) heuristic introduced in [12] for the metric Capacitated Vehicle Routing Problem (CVRP) with unit demand can be defined as follows. Consider an instance of the metric CVRP defined by the complete edge-weighted graph $G=G(X\cup \{y\},E,w)$ and capacity q. Suppose, we are given by an arbitrary Hamiltonian cycle H in the subgraph $G\langle X\rangle$ induced by the customer subset X. Starting at some customer x, cut the cycle H onto $l=\lceil n/ q\rceil$ chains, where $n=|X|$, such that each chain, except maybe the last one, visits q customers exactly. For any chain obtained, connect its endpoints with the depot y directly constructing the set S(x) of l routes. Proceed with the similar procedure taking each other customer $x\in X$ as a staring point and output the route set

$$S_{\mathrm {ITP}}=\arg \min \{w(S(x)):x\in X\}$$

of the minimum cost. The following lemma [12] gives an upper bound for the cost of the obtained solution.

Lemma 2

$$ w(S_{\mathrm {ITP}})\le 2\left\lceil \frac{n}{q}\right\rceil \frac{\sum _{i=1}^n r_i}{n}+(1-1/q)w(H)\le \left( 1+\frac{q}{n}\right) \cdot \frac{2}{q}\sum _{i=1}^n r_i+(1-1/q)w(H). $$

In [17], we extend ITP heuristic to the case of the metric CVRPTW with uniform demand. For the sake of completeness, we present this technique in this paper in Algorithm 1, which can be easily adapted to the case of the metric CVRPTW with non-uniform splittable demand.

Indeed, to obtain an ITP-based approximate solution in this case, we represent each customer $x_i$ with demand $d_i$ by the family of $d_i$ its unit-demand copies and reduce the initial instance to the obtained instance of the metric CVRPTW with unit demand defined by the auxiliary graph on $D=1+\sum _{i=1}^n d_i$ nodes. For the weight $w(S_{\mathrm {ITP}})$ of the resulting solution, we obtain the following bound.

Lemma 3

$$\begin{aligned} w(S_{ITP})\le 2\cdot \left( \frac{2}{q}\sum _{i=1}^nd_ir_i\right) +pw(H)\le 2\cdot \left( \frac{2}{q}\sum _{i=1}^nd_ir_i\right) +p\beta \cdot \mathrm {TSP}^*(X). \end{aligned}$$

Proof

Indeed, applying Lemma 2 to each customer subset $X_j$, we obtain

$$ w(S_j)\le \left( 1+\frac{q}{D_j}\right) \cdot \frac{2}{q}\sum _{x_i\in X_j} d_i r_i+(1-1/q)w(H_j)\le 2\cdot \left( \frac{2}{q}\sum _{x_i\in X_j} d_i r_i\right) +w(H), $$

where $D_j=\sum _{x_i\in X_j}d_i$. Since $w(S_{\mathrm {ITP}})=\sum _{j=1}^pw(S_j)$ and $W(H)\le \beta \mathrm {TSP}^*(X),$ Lemma is proved.

Finally, we present the following fact taken from [1], which helps us to reduce the instance in question to the equivalent one with much less total demand and to prove a polynomial time complexity bound of the scheme proposed. Hereinafter, we call a feasible route $\mathcal {R}$ non-trivial, if it visits at least two distinct customers, i.e. $|X(\mathcal {R})|>1$. Otherwise, the route is called trivial.

Lemma 4

For any instance of the CVRPTW-SD, there exists an optimum solution $\mathcal {U}=\{\mathcal {R}_1,\ldots ,\mathcal {R}_m\}$, such that, among its m routes, at most |X| are non-trivial.

Actually, Lemma 4 was proven in [1] for a more restricted case, i.e. the unit-demand CVRP free of the time windows constraints. But this result can be easily extended to the CVRPTW with splittable non-uniform demand. For the sake of brevity, we skip the proof this claim, postponing it to the forthcoming paper.

6 Approximation Scheme

It this section, we describe our approximation scheme following the overview presented in Sect. 4 and prove its correctness.

Suppose, we are given by $\varepsilon \in (0,1)$ and an instance of the Euclidean CVRPTW-SD on the plane defined by a complete node- and edge-weighted graph $G=(X\cup \{y\}),E,d,w)$, capacity $q\in \mathbb {N}$, and partition $X_1\cup \ldots \cup X_p=X$ induced by an ordered set $\mathcal {T}=\{T_1,\ldots ,T_p\}$ of consecutive disjoint time windows (see Sect. 3 for details). In this section, we show how to construct an $(1+\varepsilon )$-approximate solution of this instance.

6.1 Instance Preprocessing

Discuss the details of an approximation scheme proposed by us. Firstly, reordering the customers X by decreasing their distances r(x) to the depot y. Then, we can notify that some customers can be ignoring with respect to the fixed $\varepsilon$. We start with assigning to each customer $x_i$ the distance $r_i=w(x_i,y)$ from the depot y and reordering them by descending the distances $r_1\ge \ldots \ge r_n$. Then, we show that, during construction an $(1+\varepsilon )$-approximate solution we can ignore the customers, which are located sufficiently close to the depot in accordance to formula (2).

Lemma 5

Demand of all customers, for which $r_i\le \rho$, can be serviced by routes of at most $\varepsilon \cdot \mathrm {OPT}$ total cost.

Proof

Indeed, for any customer $x_i$, its demand $d_i$ can be serviced by $\lceil d_i/q\rceil$ trivial routes, each of them has the cost $2r_i$. Therefore, for the total cost $C_\rho$, we have

$$C_\rho \le \sum _{i=1}^n 2r_i\left\lceil \frac{d_i}{q}\right\rceil \le 2\rho \cdot N\le 2N\frac{\varepsilon r_1}{N}\le 2\varepsilon r_1\le \varepsilon \cdot \mathrm {OPT},$$

where the last inequality follows from Lemma 1. Lemma is proved.

In the sequel, without loss of generality we assume that the equation $\rho \le r_i\le r_1$ holds for any customer $x_i\in X$.

6.2 Rounding

In this section, we reduce the given instance to a special one, which we call rounded. To proceed with this reduction, we introduce the accuracy dependent grid induced by the circles centered at the depot y of radii

$$\begin{aligned} \rho _i=\rho \left( 1+\frac{\varepsilon }{q}\right) ^i,\ 0\le i \le \lceil \log _{1+\frac{\varepsilon }{q}}N/\varepsilon \rceil \end{aligned}$$

(4)

and rays spreading from y dividing each disk into $s=\lceil 2\pi q/\varepsilon \rceil$ equal circular sectors with central angle $2\pi /s$. We call locations the obtained intersection points between rays and circles. To any location, we assign p slots, by the number of different time windows. Then, we move each customer $x_i\in X_j$ to the j-th slot of the nearest location such that, each slot accumulates the total demand of all customers that are moved to it. Since the number of circles and rays are

$$\log _{1+\frac{\varepsilon }{q}}\frac{N}{\varepsilon }= \varTheta \left( \frac{q}{\varepsilon }\log \frac{N}{\varepsilon }\right) \text { and } \varTheta \left( \frac{q}{\varepsilon }\right) , $$

respectively, the total number of slots is $\varTheta \left( p\cdot \left( \frac{q}{\varepsilon }\right) ^2\log \frac{N}{\varepsilon }\right)$.

Thus, we reduce the initial instance to the special instance of the Euclidean CVRPTW-SD (we call it rounded), whose customers are slots assigned to grid locations.

Lemma 6

The proposed reduction changes the cost of any solution by at most $\varepsilon \cdot \mathrm {OPT}$.

Proof

Indeed, consider an arbitrary customer x with demand d(x) located at a distance r(x) from the depot y, between two neighboring circles of radii $\rho _i$ and $\rho _{i+1}$ (Fig. 1). It is easy to verify that the distance between x and the nearest location l has the following upper bound

Fig. 1.

Moving the customer x to the slot at the nearest location l

$$ \Vert x-l\Vert _2\le p_1+p_2\le r(x)\alpha /2+(\rho _{i+1}-\rho _i)/2. $$

Therefore,

$$ \Vert x-l\Vert _2\le r(x)\frac{\varepsilon }{q}, $$

since $\alpha \le \varepsilon /q$, $\rho _{i+1}=\rho _i(1+\varepsilon /q)$, and $r(x)\ge r(x)$, by construction. Since an arbitrary feasible solution visits each customer $x_i$ by at most $d_i$ routes, the total change of its cost induced by moving all the customers to slots at the closest locations does not exceed

$$ \varepsilon \cdot \frac{2}{q}\sum _{i=1}^nd_ir_i\le \varepsilon \cdot \mathrm {OPT}, $$

by Lemma 1. Lemma is proved.

Thanks to Lemma 6, in the rest of this paper, we can assume without loss of generality that each CVRPTW-SD instance considered is rounded.

6.3 Instance Decomposition

In this section, we show that any rounded instance of the CVRPTW-SD can be decomposed into an appropriate collection of subinstances, which can be solved in parallel, such that $(1+\varepsilon )$-approximate solution of the initial instance can be combined from the approximate solutions of the subinstances obtained.

We start this decomposition with partitioning the enclosing disk (of radius $r_1$) to rings, such that each ring (except maybe the most inner one) consists of $k=\lceil \log _{1+\frac{\varepsilon }{q}}\frac{5}{\varepsilon }\rceil$ consecutive circles. Then, each regular ring K has an inner radius $r_{in}=\rho (1+\varepsilon /q)^i$ for some $0\le i \le \lceil \log _{1+\frac{\varepsilon }{q}}N/\varepsilon \rceil$ and the outer one $r_{out}=r_{in}(1+\varepsilon /q)^k$. By W(K) we denote a width of the ring K. Since

$$\begin{aligned} W(K)&=r_{in}\left( \left( 1+\frac{\varepsilon }{q}\right) ^{\lceil \log _{1+\frac{\varepsilon }{q}}\frac{5}{\varepsilon }\rceil }-1\right) \ge r_{in}\left( \left( 1+\frac{\varepsilon }{q}\right) ^{\log _{1+\frac{\varepsilon }{q}}\frac{5}{\varepsilon }}-1\right) \\&=r_{in}\left( \frac{5}{\varepsilon }-1\right) \ge r_{in}\left( \frac{5}{\varepsilon }-\frac{1}{\varepsilon }\right) =2r_{in}\frac{2}{\varepsilon }, \end{aligned}$$

we obtain the following upper bound

$$\begin{aligned} 2r_{in}\le \frac{\varepsilon }{2}\cdot W(K) \end{aligned}$$

(5)

for the length of the inner radius of any ring K in terms of its width W(K), which is important for the subsequent constructions.

At the second step, for a positive integer $a=\lceil (20p\beta +4)/\varepsilon \rceil$ and some number $b\in \{0,\ldots ,a-1\}$, whose choice will be explained later, we color all the rings obtained in white and gray, starting from the outer one, such that the ring $K_i$ is painted gray, if . Here $\beta$ is an approximation factor of the algorithm used for solving the auxiliary TSP instances and the choice of b will be explained later, in Lemma 10.

In the sequel, we show that such a coloring leads to a successful decomposition of the initial rounded CVRPTW-SD instance. Let us discuss it in detail. First, we prove Lemma 7 that holds for much more general white-gray ring colorings. Indeed, by $\mathfrak {F}_1,\ldots ,\mathfrak {F}_\alpha$ and $\mathrm {OPT}(\mathfrak {F}_i)$ denote the maximal (by inclusion) families of consecutive white rings and the optimum value of the CVRPTW-SD subinstance induced by slots located in rings of the family $\mathfrak {F}_i$, respectively.

Lemma 7

For any white-gray coloring of rings obtained by the following rules: (i) any monochromatic pair of the adjacent rings is white; (ii) the outer ring is white as well, the following equation

$$\begin{aligned} \sum _{i=1}^{\alpha }\mathrm {OPT}(\mathfrak {F}_i)\le \left( 1+\frac{\varepsilon }{2}\right) \mathrm {OPT}\end{aligned}$$

is valid.

Proof

Indeed, let $\mathcal {U}=\{\mathcal {R}_1,\ldots \mathcal {R}_m\}$ be an arbitrary optimum solution of the initial rounded instance of the CVRPTW-SD. By the following recurrent procedure, transform any route $\mathcal {R}\in \mathcal {U}$ to an appropriate collection of routes, such that each new route visits the slots located in a single family of white rings exclusively. For the given route $\mathcal {R}$, consider the outermost white ring family visited by this route, say $\mathfrak {F}_1$, and the adjacent gray ring K (Fig. 2). Including $2\cdot l$ inner radii $r_{in}$ and l chords of the ring K, split the route $\mathcal {R}$ into subroutes $\mathcal {R}_g(1),\ldots ,\mathcal {R}_g(l)$, each of them visits no slots outside $\mathfrak {F}_1$ and a single subroute $\mathcal {R}_b$ located in the interior of the ring K. Thanks to Eq. (5) and the triangle inequality, such a transformation results in the increase of the transportation cost by at most

Fig. 2.

Splitting of the route $\mathcal {R}$ into $\mathcal {R}_g(1),\ldots ,\mathcal {R}_g(l)$ and $\mathcal {R}_b$ subroutes

$$ 4\cdot r_{in}\cdot l\le 2l\cdot \varepsilon /2\cdot W(K)\le \varepsilon /2\cdot w(\mathcal {R}\cap K), $$

where $w(\mathcal {R}\cap K)$ denotes the partial cost of the route $\mathcal {R}$ related to its intersection with the ring K. Continuing this transformation procedure recursively (proceeding with the subroute $\mathcal {R}_b$ and so on), we obtain that the total cost increasing caused by such a transformation for the route $\mathcal {R}$ does not exceed

$$ \frac{\varepsilon }{2}\cdot \sum _{j=1}^\alpha w(\mathcal {R}\cap K_j), $$

where the summation is performed over all gray rings $K_1\ldots ,K_\alpha$. Therefore, the total cost of the obtained routes is at most

$$ w(\mathcal {U})+\frac{\varepsilon }{2}\sum _{i=1}^m\sum _{j=1}^\alpha w(\mathcal {R}_i\cap K_j)\le (1+\varepsilon /2)w(\mathcal {U}). $$

Lemma follows from the obvious observation that, for any family $\mathfrak {F}_i$, the optimum value $\mathrm {OPT}(\mathfrak {F}_i)$ does not exceed the total cost of the subroutes produced by the above recursive procedure that visit this family.

For any gray ring K, by $\mathrm {TSP}^*(K)$ we denote the optimum value of the Euclidean TSP for the slots located in this ring. Evidently, each $\mathrm {TSP}^*(K)$ does not exceeds the optimum value of the TSP instance induced by all slots and the depot, we denote this value by $\mathrm {TSP}^*$. The following lemma gives much more accurate bound.

Lemma 8

Let $K_1,\ldots ,K_\alpha$ be gray rings. Then,

$$\begin{aligned} \sum _{i=1}^\alpha \mathrm {TSP}^*(K_i)\le \left( 1+\pi \varepsilon \right) \mathrm {TSP}^*. \end{aligned}$$

Proof

Let H be an arbitrary minimum cost Hamiltonian cycle passing through all the slots and the depot, such that $w(H)=\mathrm {TSP}^*$ (Fig. 3a). To obtain the desired bound, we employ the following recursive tour splitting procedure similar to the procedure provided in the proof of Lemma 7. We start with the outermost gray ring K and cut out segments of the cycle H that belong to this ring and its exterior (Fig. 3b). By $W_{ext}(K)$ denote their total cost. Further, without loss of generality, we can assume that each such a segment touches the inner circle of the ring K in two points. Therefore, the number of such points is even.

Fig. 3.

(a) the initial cycle (b) cutting out the outer segments

Connecting the adjacent points by chords and including the perfect matching as it is done in Fig. 4a, we construct the auxiliary 4-regular multi-graph having the Eulerian cycle E(K), which admits shortcutting to the Hamiltonian cycle H(K) containing all the aforementioned outer segments of the cycle H (Fig. 4b).

Fig. 4.

(a) constructing the Eulerian cycle (b) shortcutting to the Hamiltonian cycle

Again, taking into account Eq. (5) and the triangle inequality, obtain the upper bound for the cost w(H(K)) of the constructed cycle H(K)

$$\begin{aligned} w(H(K))&\le w(E(K))\le W_{ext}(K)+4\pi \cdot r_{in}\\&\le W_{ext}(K)+\pi \varepsilon \cdot W(K)\le W_{ext}(K)+\pi \varepsilon \cdot w(H\cap K), \end{aligned}$$

where $w(H\cap K)$ denotes the cost of the segment of the cycle H that belongs to the ring K. Proceeding with this procedure recursively and summing over all the gray rings, we obtain the final bound

$$ \sum _{i=1}^\alpha \mathrm {TSP}^*(K_i)\le \sum _{i=1}^\alpha w(H(K_i))\le \left( 1+\pi \varepsilon \right) w(H)=\left( 1+\pi \varepsilon \right) \mathrm {TSP}^*. $$

Lemma is proved.

Further, applying Lemma 8 twice to the alternating coloring, where each family $\mathfrak {F}_i$ consists of a single ring, we estimate the total cost of the optimum Hamiltonan cycles for all rings obtained at the first step of instance decomposition.

Lemma 9

Let $\mathrm {TSP}^*(K_i)$ be the optimum value for the Euclidean TSP instance enclosed in the ring $K_i$. Then, the following equation holds:

$$\begin{aligned} \sum _{i=1}^k\mathrm {TSP}^*(K_i)\le 10\cdot \mathrm {TSP}^*. \end{aligned}$$

Proof

Indeed. Consider two alternative colorings. In the first one, we color gray each even ring, whilst, in the second one, each odd. Employing Lemma 8, and taking into account the additional assumption that the outermost ring $K_1$ cannot be gray, we obtain the following equation

since $\varepsilon <1$. Lemma is proved.

In the sequel, for any gray ring, we will solve the associated subinstance by the ITP heuristic. The following lemma gives an upper bound for the total cost of these solutions.

Lemma 10

There exists a number $b\in \{1,\ldots ,a\}$, such that the total cost of all ITP solutions for the subinstances enclosed in the gray rings is at most $\frac{\varepsilon }{2}\cdot \mathrm {OPT}$.

Proof

Indeed, for any ring K, by $X_{slots}(K)$ and $S_{\mathrm {ITP}}(K)$ denote the subset of slots enclosed in the ring K and the ITP-solution of the corresponding subinstance, respectively. Then,

$$ w(S_{\mathrm {ITP}}(K))\le 2\cdot \frac{2}{q}\sum _{x\in X_{slots}(K)}d(x)r(x)+p\beta \cdot \mathrm {TSP}^*(K) $$

Therefore, by Lemmas 3, 9, and 1,

Hence, there exists b, such that

by construction. Lemma is proved.

To complete the decomposition of the given instance, we perform white-gray coloring of the rings driven by the parameters a and b and obtain subinstances defined by white families $\mathfrak {F}_i$ and gray rings $K_j$. Hereinafter, we call them white and gray, respectively. Then, by Lemma 4, we reduce each subinstance with $\sigma$ slots and an arbitrarily large demand to the equivalent one, whose total demand does not exceed $\sigma ^2q$. Finally, we find a $(1+\varepsilon /2)$-approximate solution and an ITP-solution of any reduced white and gray subinstance, respectively. Our first result follows straightforwardly from Lemmas 7 and 10.

Theorem 1

For any $\varepsilon \in (0,1)$, the proposed decomposition provides $(1+\varepsilon )$-approximate solution for the initial rounded CVRPTW-SD instance.

6.4 Approximate Algorithms for Subinstances

As we mentioned in Sect. 4, to find an approximate solution for an arbitrary white subinstance we apply as a black box the quasi-polynomial approximation scheme (QPTAS) proposed by Song et al. in [28], whilst, each gray subinstance we approximate with our recent modification [16, 17] of the well-known ITP heuristic.

7 Time Complexity Bounds

As shown in Sect. 6, the proposed scheme consists of the following stages: preprocessing, rounding, instance decomposition and the main stage dealing with the approximation of white and gray subinstances.

It can be easily verified that the first three stages can be carried out in time $O(n\log n)$, where n is the number of distinct customers. To estimate time complexity of the final stage, recall that the Song’s QPTAS and our modification of the ITP are developed for the case of CVRPTW with unit demand. Therefore, in our case, their complexity bounds should be represented in terms of the total customer demand D defining the instance in question, i.e. $O\left( D^{\log ^{O(1/\varepsilon )}D}\right)$ and $O(D^3)$, respectively (see [16, 28]).

Thanks to Lemma 4, for any subinstance (white or gray) obtained during the decomposition of the given rounded instance, its total demand $D=\sigma ^2q$, where $\sigma$ is the number of slots engaged, which in turn is determined by the number of circles included into an appropriate family of white rings or to the gray ring. By construction, each ring contains

$$O\left( \log _{1+\frac{\varepsilon }{q}}\frac{1}{\varepsilon }\right) =O\left( \frac{q}{\varepsilon }\cdot \log \frac{1}{\varepsilon }\right) $$

circles, each of them consists of $O(pq/\varepsilon )$ slots. Therefore, for any gray subinstance,

$$ \sigma =\sigma _g=O\left( \frac{pq^2}{\varepsilon ^2}\cdot \log \frac{1}{\varepsilon }\right) , $$

while any white instance is determined by

$$ \sigma =\sigma _w=a\cdot \sigma _g=O\left( \frac{(pq)^2}{\varepsilon ^3}\cdot \log \frac{1}{\varepsilon }\right) $$

slots. Further, the number I of white (or gray) subinstances is

$$ I=O\left( \frac{\log \frac{N}{\varepsilon }}{a\log \frac{1}{\varepsilon }}\right) =O\left( \frac{\varepsilon }{p}\frac{\log \frac{N}{\varepsilon }}{\log \frac{1}{\varepsilon }}\right) , $$

where N is defined by Eq. (2). Thus, we proved our second result.

Theorem 2

Time complexity of the proposed scheme is

$$\begin{aligned} O\left( I\cdot \mathcal {K}(p,q,\varepsilon )+n\log n\right) , \end{aligned}$$

(6)

where

$$\begin{aligned} \mathcal {K}(p,q,\varepsilon )=\left( \sigma ^2_wq\right) ^{(\log (\sigma _w^2q))^{O(1/\varepsilon )}}+(\sigma _g^2q)^3. \end{aligned}$$

(7)

Notice that the proposed scheme admits near to linear parallel speedup, since all the subinstances obtained at the stage of instance decomposition can be solved independently.

Corollary 1

For any fixed $\varepsilon \in (0,1)$, the running time of the proposed scheme does not exceed $O(n\log N)$, if $p=\varOmega (1)$, $q=\varOmega (1)$, and

$$\begin{aligned} \max \{p,q\}\le 2^{\log ^\delta n} \end{aligned}$$

(8)

for some $\delta =O(\varepsilon )$.

Proof

Fix an arbitrary $\varepsilon \in (0,1)$ and obtain an upper bound for (6). Indeed, $I=O(\log N)$, $\sigma _w^2q=Cp^4q^5$ for some constant $C>0$, and the first term in (7) dominates the second one. Then, Eq. (8) implies that, for $n\gg 1$

$$\begin{aligned} \log {\sigma _w^2q}=\log C+4\log p + 5\log q\le 10\log ^{\delta }n\le \log ^{2\delta }n. \end{aligned}$$

Therefore,

$$\begin{aligned} \mathcal {K}(p,q,\varepsilon )=2^{(\log (Cp^4q^5))^{O(1/\varepsilon )}}&\le 2^{(\log ^{2\delta } n)^{O(1/\varepsilon )}}\\&=2^{(\log n)^{C_1\delta /\varepsilon }}=\left( 2^{\log n}\right) ^{\frac{\log ^{C_1\delta /\varepsilon }n}{\log n}}\le 2^{\log n}=n \end{aligned}$$

any time, when $C_1\delta /\varepsilon \le 1$, where $C_1$ is some positive constant, and $n>1$. Hence, for the fixed $\varepsilon$,

$$ I\cdot \mathcal {K}(p,q,\varepsilon )+n\log n=O(n\log N). $$

Corollary is proved.

Corollary 2

For any fixed p and q the proposed scheme is EPTAS with time complexity $O\left( \left( \frac{1}{\varepsilon ^8}\right) ^{\left( \log \frac{1}{\varepsilon }\right) ^{O(1/\varepsilon )}}\cdot \log N+n\log n\right)$.

8 Conclusion

In this paper, perhaps for the first time for the Euclidean Capacitated Vehicle Routing Problem with Time Windows and non-uniform splittable demand, a polynomial time approximation scheme is proposed. The scheme is based on the instance decomposition framework developed in [1] and uses the QPTAS from [28] and our modification [16] of the Iterative Tour Partition as a black box. For any fixed $\varepsilon \in (0,1)$ and the total customer demand D, the scheme finds a $(1+\varepsilon )$-approximate solution of the problem in time $O(n\log D)$ any time provided that $\max \{p,q\}\le 2^{\log ^\delta n}$ for some $\delta =O(\varepsilon )$. Furthermore, for any fixed capacity q and the number p of time windows, the proposed scheme is an EPTAS, which significantly outperforms by the time complexity bound the previous best result [17] for the CVRPTW on the Euclidean plane.

For future work we left the open questions related to a possible extension of the proposed scheme to an arbitrary finite dimension Euclidean space and to the case of non-splittable demand.