Approximation and Polynomial Algorithms for Multi-depot Capacitated Arc Routing Problems

Abstract

We study the multi-depot capacitated arc routing problem (MCARP), which generalizes the classical arc routing problem to the more realistic situation with multiple depots. We propose approximation and polynomial algorithms for different variants of the MCARP. First, we present the first constant-factor approximation algorithms for the MCARP and the nonfixed destination variant. Second, for a restricted case of the MCARP with infinite vehicle capacity, called the multi-depot rural postman problem, we devise a $(2-\frac{1}{2k+1})$-approximation algorithm with k indicating the number of depots. Lastly, we show that the equal-demand MCARP defined on a line graph is polynomially solvable and develop a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.

1 Introduction

Given an undirected graph $G=(V,E)$, which may be a multigraph, with vertex set V and edge set E. Each edge $e\in E$ is associated with a nonnegative cost c(e) and a nonnegative integer demand d(e). There is a fleet of homogeneous vehicles with capacity Q located at a specified vertex $o\in V$, called the depot. The Capacitated Arc Routing Problem (CARP) is to find a set of routes (or closed walks), starting from and ending at the depot, for the vehicles to serve the edges with positive demands such that each vehicle serves a total demand of at most Q (capacity constraint) and the total cost of the routes is minimized. If the demands are defined for the vertices instead of the edges in the CARP, we obtain the Capacitated Vehicle Routing Problem (CVRP).

As noted by Golden and Wong [13], the CVRP can be seen as a special case of the CARP. Because we can split the vertices in the CVRP into two vertices which are connected by a zero-cost edge with a demand equal to the original vertex demand. The CARP occurs frequently in practice applications, including the inspection of electric power lines [9], distribution service [16], garbage collection [10], school bus routing problem [24], and so on.

A natural extension of the CARP/CVRP is the Multi-Depot Capacitated Arc/Vehicle Routing Problem (MCARP/MCVRP) where there are multiple depots instead of a single depot and the routes are required to start from and end at the same depot (but different routes may use different depots). The motivation to study the MCARP/MCVRP lies not only in their theoretical interest, but also in their wide-spread applications. For the CARP/CVRP, when the service area is large, multiple depots are usually setting up to meet the service requirements [11]. Such depots correspond to vehicle stations, warehouses, dumping places, supply points or relay boxes. For example, the online shopping business usually operates at multiple depots to improve the customers experience and satisfaction in cities [19]. Other applications of the MCARP/MCVRP encompass mail delivery [17], explosive waste recycling [27], police patrolling [7], etc.

One can see that the CARP (resp. CVRP) is NP-hard, since it contains the well-known Rural Postman Problem (resp. Metric Traveling Salesman Problem) as a special case where the vehicle capacity is infinite. In turn, as a generalization of the CARP/CVRP, the MCARP/MCVRP is also NP-hard. Therefore, the existing literature on the MCARP/MCVRP has centered on branch-and-cut approach (e.g. see [12, 20]) and meta-heuristics (e.g., see [17, 19, 23]). However, we address the multi-depot CARP from the point view of approximation algorithms. As far as we know, there are few approximability results on multi-depot variants for the CARP/CVRP. In particular, we have not aware any approximation algorithm for the MCARP.

The research of approximation algorithms for the CARP/CVRP was initiated by Haimovich and Rinnooy Kan [14], who studied the equal-demand CVRP, which is a special case of the CVRP with $d(v)=1$ for each vertex v. They gave the well-known Iterated Tour Partition heuristic, denoted by $ITP(\alpha )$, where $\alpha$ indicates the approximation ratio of the metric TSP ($\alpha \le \frac{3}{2}$ due to the results in [5, 8]), and proved that $ITP(\alpha )$ achieves an approximation ratio of $1+(1-\frac{1}{Q})\alpha$ if the number $n=|V|$ of vertices is a multiple of Q. Later, Haimovich et al. [15] and Altinkemer and Gavish [2] removed the condition that n is a multiple of Q while achieving the same result¹. For the general CVRP, Altinkemer and Gavish [1] obtained a $(2+(1-\frac{2}{Q})\alpha )$-approximation algorithm, called $UITP(\alpha )$, which is an extension of $ITP(\alpha )$ to the general case of unequal demands. A simplified proof of this result can be found in [15]. Recently, Blauth et al. [6] have managed to improve the longstanding ratio for the CVRP to $2+\alpha -2\epsilon$ for some absolute constant $\epsilon >0$. For the equal-demand case, they also devised an improved $(1+\alpha -\epsilon )$-approximation algorithm.

Besides the results on the CVRP defined on general graphs, there are also approximation algorithms tailored for the CVRP defined on special graphs. Labbe et al. [21] devised a 2-approximation for the CVRP on trees. If the graph is a line, Wu and Lu [26] further improved the ratio to $\frac{5}{3}$. Note that the CVRP on a half-line (i.e. the depot is located at one of the end point of the line) is already NP-hard [3]. What’s worse, the CVRP on a half-line cannot be approximated within ratio 3/2 unless P = NP [26].

As for the CARP, Jansen [18] showed how to generalize the above $ITP(\alpha )$ and $UITP(\alpha )$ heuristics for the CVRP to obtain approximation algorithms with ratios $1+(1-\frac{1}{Q})\alpha _0$ and $2+(1-\frac{2}{Q})\alpha _0$ for the CARP with triangle inequality, where $\alpha _0$ is the approximation ratio for the Rural Postman Problem (due to the results in [4, 9], $\alpha _0\le \frac{3}{2}$). Wohlk [25] presented an alternative $(2+(1-\frac{2}{Q})\alpha _0)$-approximation algorithm for the CARP with triangle inequality. Interestingly, van Bevern [4] proved that any factor $\beta$ approximation algorithm for the CARP with triangle inequality yields a factor $\beta$ approximation algorithm for the general CARP (without the triangle inequality). As a result, the (equal-demand) CARP admits an approximation algorithm of ratio $2+(1-\frac{2}{Q})\alpha _0$ ($1+(1-\frac{1}{Q})\alpha _0$).

For the multi-depot CVRP, Li and Simchi-Levi [22] developed approximation algorithms with ratios $1+(2-\frac{1}{Q})\alpha$ and $2+(2-\frac{2}{Q})\alpha$ for the equal-demand case and the general case, respectively. In addition, they also considered the nonfixed destination MCVRP, i.e. a variant of the MCVRP where the vehicles are allowed to depart from one depot but end at another depot, and gave two approximation algorithms with ratios $1+(1-\frac{1}{Q})\alpha$ and $2+(1-\frac{2}{Q})\alpha$ for the equal-demand case and the general case, respectively.

In this paper, we mainly obtain the following results. First, we present the first approximation algorithms for the MCARP and the nonfixed destination variant, which have constant approximation ratios. Second, for the multi-depot Rural Postman Problem (MRPP), which is a restricted case of the MCARP with infinite vehicle capacity, we devise a better approximation algorithm with ratio $2-\frac{1}{2k+1}$, where k indicates the number of depots. Lastly, we investigate the MCARP/MCVRP defined on a line graph and show that the equal-demand MCARP on a line is polynomially solvable and propose a 2-approximation algorithm for the MCVRP on a line.

The rest of the paper is organized as follows. We give some notations used throughout the paper in Sect. 2. In Sect. 3 we deal with the approximation algorithms for the nonfixed destination MCARP. Subsequently, we discuss the (fixed destination) MCARP in Sect. 4. Approximation algorithms for the MRPP are presented in Sect. 5. At last, we give approximation and polynomial algorithms for the MCARP/MCVRP defined on a line graph in Sect. 6.

2 Notations

Throughout the paper, we analyze algorithms on different versions of the MCARP/MCVRP. For the MCARP, we denote by $Z^*$ the optimal value. $Z^*_n$ indicates the optimal value of the nonfixed destination MCARP. $Z^A$ denotes the objective value of the solution obtained by some algorithm A.

Let $G=(V,E)$ be the underlying graph with vertex set V and edge set E, $c(e)\ge 0$ indicates the cost (or length) of edge $e\in E$. If $e=(u,v)$, we call u, v the end vertices of e. The nonnegative integer demand of vertex v (edge e) is denoted by d(v) (d(e)). The edges with $d(e)>0$ are called required edges. The set of all required edges is denoted by R. Q is the capacity of the vehicles. For any $u,v\in V$, $c_s(u,v)$ denote the length of the shortest path between u and v. For a subgraph H of G, V(H) and E(H) denote the vertex set and edge (multi)set of H, respectively. The cost of H is defined as $c(H)=\sum _{e\in E(H)}c(e)$. Let $c_R(H)$ be the sum of the costs of the required edges in H. Consequently, the sum of the costs of the non-required edges in H equals $c(H)-c_R(H)$.

3 The Nonfixed Destination MCARP

In this section, we extend the algorithm for the nonfixed destination MCVRP in [22] to solve the nonfixed destination MCARP. Our algorithm, called $NMCARP(\beta )$, also has a simple description by using the result for the CARP (without triangle inequality) in [4]. Here $\beta$ indicates the approximation ratio for the CARP.

Let $G=(V,E)$ be the original graph for the nonfixed destination MCARP and $D\subseteq V$ is the depot set. $NMCARP(\beta )$ uses a $\beta$-approximation algorithm for the CARP as a subroutine and consists of two stages. The first stage is to contract the set D of depots in G into a single depot d to generate a new graph $G'$ and use the $\beta$-approximation for the corresponding CARP to derive a solution composed of a series of routes starting from and ending at d. The second stage of the algorithm is to uncontract d back to the original set D of depots, which produces a feasible solution of the original MCARP. The following is the formal description of the algorithm.

Algorithm ${\boldsymbol{NMCARP}}(\boldsymbol{\beta })$ 

• Step 1. Obtain a new graph $G'=(V', E')$ from $G=(V,E)$, where $V'=\left\{ d \right\} \cup (V\setminus D)$ and each edge $(u,v)\in E$ corresponds to an edge $(u',v')\in E'$ with the same cost and demand such that

  $$\left\{ \begin{array}{ll} u'=u,v'=v, &{} \text{ if } u,v\in V\setminus D;\\ u'=u,v'=d, &{} \text{ if } u\in V\setminus D, v\in D;\\ u'=d,v'=v, &{} \text{ if } u\in D, v\in V\setminus D;\\ u'=v'=d, &{} \text{ if } u,v \in D. \end{array}\right. $$

  Note that the last case indicates that $(u',v')$ is a self-loop in $G'$.

• Step 2. Apply a $\beta$-approximation algorithm for the CARP defined on $G'$ to generate a solution consisting of l routes $C'_1,\ldots ,C'_l$ starting from and ending at the depot d. Moreover, we assume w.l.o.g that each $C'_i$ contains d exactly twice².

• Step 3. For each $C'_i$ ($i=1,\ldots ,l$), replacing each edge $(u',v')$ of $C'_i$ by the original edge (u, v) corresponding to $(u',v')$. This will result in a route $P_i$ in G whose both end points are depots in D (but may be different).

• Step 4. Return the routes in $P_1,\ldots ,P_l$.

Lemma 1

$Z^{NMCARP(\beta )}\le \beta Z_n^*$.

Proof

Let $Z^*(G')$ be the optimal value of the CARP defined on $G'$ in Step 2. It can seen that any feasible solution to the nonfixed destination MCVRP induces a feasible solution to the CARP defined on $G'$ of no greater cost after contracting the depots in D into a single depot d. This implies that $Z^*(G')\le Z_n^*$. By definition, the total cost of the routes $C'_1,\ldots ,C'_l$ is at most $\beta Z^*(G')$. Observe that in Step 3 the total cost of the routes in $P_1,\ldots ,P_l$ is the same as the total cost of the routes $C'_1,\ldots ,C'_l$. Therefore, $Z^{NMCARP(\beta )}\le \beta Z^*(G')\le \beta Z_n^*$.    $\square$

Due to the results in [4, 18, 25], there exists an approximation algorithm, say $UITP(\alpha _0)$, with ratio $2+(1-\frac{2}{Q})\alpha _0$ for the CARP and another approximation algorithm, which we call $ITP(\alpha _0)$, with ratio $1+(1-\frac{1}{Q})\alpha _0$ for the equal-demand problem. Recall that $\alpha _0$ is the approximation ratio for the Rural Postman Problem. Using Lemma 1, this yields the following result.

Theorem 1

The nonfixed destination MCARP admits a $(2+(1-\frac{2}{Q})\alpha _0)$-approximation algorithm. If the demands are equal, there is a $(1+(1-\frac{1}{Q})\alpha _0)$-approximation algorithm.

Remark 1

One can see that our algorithm has a very simple description, which thanks to the adoption of the $\beta$-approximation algorithm for the CARP without triangle inequality. In particular, when constructing the graph $G'$ we need not alter the costs and demands of the edges except for contracting the depot set. In contrast, the $UITP_n(\alpha )$ heuristic for the nonfixed destination CVRP, given by Li and Simchi-Levi [22], has to further revise the edge costs by computing the all-pairs shortest path between the vertices in $G'$ and add some dummy edges. Because their algorithm invokes the $UITP(\alpha )$ heuristic for the CVRP, which need the triangle inequality, and $G'$ may not respect the triangle inequality.

4 The (Fixed Destination) MCARP

We now discuss the (fixed destination) MCARP where all the routes are required to start from and end at the same depot.

We give an algorithm, called $MUITP(\alpha _0)$, for the MCARP by modifying the algorithm $NMCARP(\beta )$ as follows. First, we replace the $\beta$-approximation algorithm in Step 2 by the above-mentioned algorithm $UITP(\alpha _0)$. Then we modify the solution generated in Step 4 to derive a feasible solution for the MCARP. Let $P_i=d_1^{(i)},v_1^{(i)},\dots ,v_r^{(i)},d_2^{(i)}$ be the ith route with

$$c(P_i)=c_s(d_1^{(i)},v_1^{(i)})+\sum _{h=1}^{r-1} c_s(v_h^{(i)},v_{h+1}^{(i)}) +c_s(v_r^{(i)},d_2^{(i)}),$$

where $d_1^{(i)},d_2^{(i)}\in D$ are the depots and $v_h^{(i)}\in V\setminus D$ ($h=1,\dots ,r$). The modification of $P_i$ ($i=1,\dots ,l$) to $C_i$ is defined as below: if $d_1^{(i)}=d_2^{(i)}$ then $P_i$ is already feasible and we set $C_i=P_i$, otherwise $C_i$ is replaced by

$$ C_i=\left\{ \begin{array}{ll} d_1^{(i)},v_1^{(i)},\dots ,v_r^{(i)},d_1^{(i)},&{} \text{ if } c_s(d_1^{(i)},v_1^{(i)})+c_s(v_r^{(i)},d_1^{(i)})\le c_s(d_2^{(i)},v_1^{(i)})+c_s(v_r^{(i)},d_2^{(i)});\\ d_2^{(i)},v_1^{(i)},\dots ,v_r^{(i)},d_2^{(i)},&{} \text{ if } c_s(d_1^{(i)},v_1^{(i)})+c_s(v_r^{(i)},d_1^{(i)})> c_s(d_2^{(i)},v_1^{(i)})+c_s(v_r^{(i)},d_2^{(i)})\,. \end{array}\right. $$

To analyze the performance of the algorithm $MUITP(\alpha _0)$, we define $L^*$ as the cost of the optimal rural postman tour with respect to $G'$ in Step 2. In other words, $L^*$ is the length of the shortest closed walk in $G'$ going through 0 and all required edges. $L(\alpha _0)$ is the cost of an $\alpha _0$-approximate rural postman tour used by $UITP(\alpha _0)$. Clearly, $L(\alpha _0)\le \alpha _0 L^*$. Moreover, according to $UITP(\alpha _0)$ it holds that $\sum _{i=1}^l \sum _{h=1}^{r-1} c_s(v_h^{(i)},v_{h+1}^{(i)})\le L(\alpha _0)$.

We proceed to show the following result.

Lemma 2

$Z^{MUITP(\alpha _0)}\le \left( 2+\left( 2-\frac{2}{Q}\right) \alpha _0\right) Z^*$.

Proof

Similarly to the analysis of the $ITP_f(\alpha )$ heuristic for the MCVRP in [22], we can show that $c(C_i)\le c(P_i)+\sum _{h=1}^{r-1} c_s(v_h^{(i)},v_{h+1}^{(i)})$ and hence

$$Z^{MUITP(\alpha _0)}=\sum _{i=1}^l C_i \le \left( 2+\left( 1-\frac{2}{Q}\right) \alpha _0\right) Z_n^*+L(\alpha _0)\,.$$

Since $Z_n^*\le Z^*$ and $L(\alpha _0)\le \alpha _0 L^* \le \alpha _0 Z^*$, the proof of is completed.    $\square$

By substituting $ITP(\alpha _0)$ for $UITP(\alpha _0)$ in the above algorithm $MUITP(\alpha _0)$, we can obtain an approximation algorithm for the equal-demand MCARP with ratio $1+(2-\frac{1}{Q})\alpha _0$. To sum up, we have the following result for the MCARP.

Theorem 2

There exists a $(2+(2-\frac{2}{Q})\alpha _0)$-approximation algorithm for the MCARP. Moreover, for the equal-demand problem there is a $(1+(2-\frac{1}{Q})\alpha _0)$-approximation algorithm.

5 The Multi-depot Rural Postman Problem

In this section, we consider the multi-depot Rural Postman Problem (MRPP), which is a restricted case of the MCARP with infinite vehicle capacity, i.e., $Q=+\infty$. Suppose that there are $k=|D|$ depots. Then the MRPP is essentially to find at most k closed walks, each of which starts from and ends at a distinct depot, such that these walks cover all the required edges and the total cost of the walks is minimized.

Theorem 3

There exists a $(2-\frac{1}{2k+1})$-approximation algorithm for the MRPP.

6 Multi-depot CARP on a Line

In this section, we deal with the MCARP/MCVRP defined on a line graph. We show that the equal-demand MCARP on a line can be solved in $O(n^2)$ time. For the MCVRP on a line, we give the first 2-approximation algorithm.

Theorem 4

The equal-demand MCARP on a line can be solved in $O(n^2)$ time.

Theorem 5

The MCVRP on a line admits a 2-approximation algorithm.