Keywords

1 Introduction

In the Multidepot Capacitated Vehicle Routing Problem (MCVRP), we are given a complete undirected graph \(G=(V\cup D, E)\) with an edge weight w satisfying the symmetric and triangle inequality properties. The n nodes in \(V=\{v_1,\dots ,v_n\}\) represent n customers and each customer \(v\in V\) has a demand \(d(v)\in \mathbb {Z}_{\ge 1}\). The m nodes in \(D=\{u_1,\dots ,u_m\}\) represent m depots, with each containing an infinite number of vehicles with a capacity of \(k\in \mathbb {Z}_{\ge 1}\) (we can also think that each depot contains only one vehicle, which can be used many times). A tour is a walk that begins and ends at the same depot and the sum of deliveries to all customers in it is at most k. The traveling distance of a tour is the sum of the weights of edges in the tour. In MCVRP, we wish to find a set of tours to satisfy every customer’s demand with a minimum total distance of all the tours. In the unsplittable version of the problem, each customer’s demand can only be delivered by a single tour. In the splittable version, each customer’s demand can be delivered by more than one tour. Moreover, if each customer’s demand is a unit, it is called the unit-demand version.

In logistics, MCVRP is an important model that has been studied extensively in the literature (see [19] for a survey). If there is only one depot, MCVRP is known as the famous Capacitated Vehicle Routing Problem (CVRP). Since k-CVRP is APX-hard for any fixed \(k\ge 3\) [3], it also holds for k-MCVRP.

Consider approximation algorithms for k-CVRP. Haimovich and Kan proposed [11] a well-known algorithm based on a given Hamiltonian cycle, called Iterated Tour Partitioning (ITP). Given an \(\alpha \)-approximation algorithm for metric TSP, for splittable and unit-demand k-CVRP, ITP can achieve a ratio of \(\alpha +1-\alpha /k\) [11]. For unsplittable k-CVRP, Altinkemer and Gavish [1] proposed a modification of ITP, called UITP, that can achieve a ratio of \(\alpha +2-2\alpha /k\) for even k. When k is arbitrarily large, k-CVRP becomes metric TSP. For metric TSP, there is a well-known 3/2-approximation Algorithm [6, 21], and currently Karlin et al. [15, 16] has slightly improved the ratio to \(3/2-10^{-36}\). Recently, some progress has been made in approximating k-CVRP. Blauth et al. [4] improved the ratio to \(\alpha +1-\varepsilon \) for splittable and unit-demand k-CVRP and to \(\alpha +2-2\varepsilon \) for unsplittable k-CVRP, where \(\varepsilon \) is a value related to \(\alpha \) and satisfies \(\varepsilon \approx 1/3000\) when \(\alpha =3/2\). Then, for unsplittable k-CVRP, Friggstad et al. [9] further improved the ratio to \(\alpha +1+\ln 2-\varepsilon \) based on an LP rounding method, where \(\varepsilon \approx 1/3000\) is the improvement based on the method in [4]. There are other improvements for the case that the capacity k is a small fixed constant. Bompadre et al. [5] improved the classic ratios by a term of \({\Omega }(1/k^3)\) for all three versions. Zhao and Xiao [27] proposed a \((5/2-\varTheta (1/\sqrt{k}))\)-approximation algorithm for splittable and unit-demand k-CVRP and a \((5/2+\ln 2-\varTheta (1/\sqrt{k}))\)-approximation algorithm for unsplittable k-CVRP, where the improvement \(\varTheta (1/\sqrt{k})\) is larger than 1/3000 for any \(k\le 10^7\).

Consider approximation algorithms for k-MCVRP. Few results are available in the literature. Note that \(\alpha \approx 3/2\). Based on a modification of ITP, Li and Simchi-Levi [18] proposed a cycle-partition algorithm, which achieves a ratio of \(2\alpha +1-\alpha /k\approx 4-\varTheta (1/k)\) for splittable and unit-demand k-MCVRP and a ratio of \(2\alpha +2-2\alpha /k\approx 5-\varTheta (1/k)\) for unsplittable k-MCVRP. The only known improvement was made by Harks et al. [12], where they proposed a tree-partition algorithm with an improved 4-approximation ratio for unsplittable k-MCVRP. Note that their algorithm also implies a 4.38-approximation ratio for a more general problem, called Capacitated Location Routing, where we need to open some depots (with some cost) first and then satisfy customers using vehicles in the opened depots. When k is arbitrarily large, k-MCVRP becomes metric m-depot TSP. For metric m-depot TSP, Rathinam et al. [20] proposed a simple 2-approximation algorithm, and Xu et al. [25] proposed an improved \((2-1/m)\)-approximation algorithm. Then, based on an edge exchange algorithm, Xu and Rodrigues [24] obtained an improved 3/2-approximation algorithm for any fixed m. Traub et al. [22] further improved the ratio to \(\alpha +\varepsilon \) for any fixed m. Recently, Deppert et al. [8] obtained a randomized \((3/2+\varepsilon )\)-approximation algorithm with a running time of \((1/\varepsilon )^{O(d\log d)}\cdot n^{O(1)}\), and hence their algorithm even works with a variable number of depots.

If the capacity k is fixed, we will see that splittable k-MCVRP is equivalent to unit-demand k-MCVRP. Moreover, both unit-demand and unsplittable k-MCVRP can be reduced to the minimum weight k-set cover problem. In minimum weight k-set cover, we are given a set of elements (called universe), a set system with each set in it having a weight and at most k elements, and we need to find a collection of sets in the set system with a minimum total weight that covers the universe. In the reduction, customers can be seen as the elements. There are at most \(mn^{O(k)}\) feasible tours, and each tour can be seen as a set containing all customers in the tour with a weight of the tour. When k is fixed, the reduction is polynomial. It is well-known [7] that the minimum weight k-set cover problem admits an approximation ratio of \(H_k\), where \(H_k{:}{=}1+1/2+\cdots +1/k\) is the k-th harmonic number. Hassin and Levin [13] improved the ratio to \(H_k-\varTheta (1/k)\). Recently, using a non-obvious local search method, Gupta et al. [10] improved the ratio to \(H_k-\varTheta (\ln ^2 k/k)\), which is better than 4 for any fixed \(k\le 30\). So, for some \(k\le 30\), the best ratios of k-MCVRP are \(H_k-\varTheta (\ln ^2 k/k)\).

Note that each vehicle must return to the depot it starts in our setting, which is also known as the fixed-destination property [18]. Li and Simchi-Levi [18] also considered a non-fixed-destination version where each vehicle may terminate at any depot. The non-fixed-destination MCVRP can be reduced to CVRP easily with the approximation ratio preserved since one can regard all depots as a single super-depot and let the distance between a customer and the super-depot be the minimum weight of the edges between the customer and the depots.

Recently, Lai et al. [17] studied a variant of MCVRP, called m-Depot Split Delivery Vehicle Routing, where the number of depots is still m, but the number of vehicles in each depot is limited and each vehicle can be used for at most one tour (one can also think that each depot contains only one vehicle, which can be used a limited number of times). When m is fixed, they obtained a \((6-4/m)\)-approximation algorithm. Carrasco Heine et al. [14] considered a bifactor approximation algorithm for a variant of Capacitated Location Routing, where each depot has a capacity as well.

1.1 Our Contributions

Motivated by recent progress in approximating k-CVRP, we design improved approximation algorithms for k-MCVRP. For the sake of presentation, we assume that \(\alpha =3/2\). The contributions are shown as follows.

Firstly, we review the cycle-partition algorithm in [18] and then propose a refined tree-partition algorithm based on the idea in [12]. Note that our refined algorithm has a better approximation ratio for fixed k. For splittable and unit-demand k-MCVRP, both of them are 4-approximation algorithms. By making a trade-off between them and further using the result in [4], we obtain an improved \((4-1/1500)\)-approximation ratio. The cycle-partition algorithm itself may only lead to a \((4-1/3000)\)-approximation ratio.

Secondly, using the LP-rounding method in [9], we obtain an LP-based cycle-partition algorithm that can achieve a \((4+\ln 2+\delta )\)-approximation ratio for unsplittable k-MCVRP with any constant \(\delta >0\). By making a trade-off between the LP-based cycle-partition algorithm and the tree-partition algorithm and further using the result in [4], we obtain an improved \((4-1/50000)\)-approximation ratio.

At last, we propose an LP-based tree-partition algorithm, which works for fixed k. Using the lower bounds of k-CVRP in [27], we obtain an improved \((3+\ln 2-\varTheta (1/\sqrt{k}))\)-approximation algorithm for all three versions of k-MCVRP, which is better than the current-best ratios for any \(k>11\). By making a trade-off between the LP-based tree-partition algorithm and the cycle-partition algorithm and further using the result in [4], we show that the ratio can be improved to \(3+\ln 2-\max \{\varTheta (1/\sqrt{k}),1/9000\}\) for splittable and unit-demand k-MCVRP.

Due to limited space, the proofs of lemmas and theorems marked with “*” were omitted and they can be found in the full version of this paper [28].

2 Preliminaries

2.1 Definitions

In MCVRP, we let \(G=(V\cup D, E)\) denote the input complete graph, where vertices in V represent customers and vertices in D represent depots. There is a non-negative weight function \(w: E\rightarrow \mathbb {R}_{\ge 0}\) on the edges in E. We often write w(u, v) to mean the weight of edge uv, instead of w(uv). Note that w(u, v) would be the same as the distance between u and v. The weight function w is a semi-metric function, i.e., it is symmetric and satisfies the triangle inequality. For any weight function \(w: X\rightarrow \mathbb {R}_{\ge 0}\), we extend it to subsets of X, i.e., we define \(w(Y) = \sum _{x\in Y} w(x)\) for \(Y\subseteq X\). There is a demand function d: \(V\rightarrow \mathbb {N}_{\ge 1}\), where d(v) is the demand required by \(v\in V\). We let \(\varDelta =\sum _{v\in V}\min _{u\in D}d(v)w(u,v)\). For a component S, we simply use \(v\in S\) (resp., \(e\in S\)) to denote a vertex (resp., an edge) of S, and let \(w(S){:}{=}\sum _{e\in S}w(e)\) and \(d(S){:}{=}\sum _{v\in S}d(v)\).

A walk in a graph is a succession of edges in the graph, where an edge may appear more than once. We will use a sequence of vertices to denote a walk. For example, \(v_1v_2v_3\dots v_l\) means a walk with edges \(v_1v_2\), \(v_2v_3\), and so on. A path in a graph is a walk such that no vertex appears more than once in the sequence, and a cycle is a walk such that only the first and the last vertices are the same. A cycle containing l edges is called an l-cycle and the length of it is l. A spanning forest in a graph is a forest that spans all vertices. A constrained spanning forest in graph G is a spanning forest where each tree contains only one depot.

An itinerary I is a walk that starts and ends at the same depot and does not pass through any other depot. It is called an empty itinerary and denote it by \(I=\emptyset \) if there are no customer vertices on I, and a non-empty itinerary otherwise. A non-empty itinerary can be split into several minimal cycles containing only one depot, and each such cycle is called a tour. The Multidepot Capacitated Vehicle Routing Problem (k-MCVRP) can be described as follows.

Definition 1

(k -MCVRP). An instance \((G=(V\cup D,E),w,d,k)\) consists of:

  • a complete graph G, where \(V=\{v_1,\dots ,v_n\}\) represents the n customers and \(D=\{u_1,\dots ,u_m\}\) represents the m depots,

  • a weight function w: \((V\cup D)\times (V\cup D)\rightarrow \mathbb {R}_{\ge 0}\), which represents the distances,

  • a demand function d: \(V\rightarrow \mathbb {N}_{\ge 1}\), where d(v) is the demand required by customer \(v\in V\),

  • the capacity \(k\in \mathbb {Z}_{\ge 1}\) of vehicles that initially stays at each depot.

A feasible solution is a set of m itineraries, with each having one different depot:

  • each tour delivers at most k of the demand to customers on the tour,

  • the union of tours over all itineraries meets every customer’s demand.

Specifically, the goal is to find a set of itineraries \(\mathcal {I}=\{I_1,\dots ,I_m\}\) where \(I_i\) contains depot \(u_i\), minimizing the total weight of the succession of edges in the walks in \(\mathcal {I}\), i.e., \(w(\mathcal {I}){:}{=}\sum _{I\in \mathcal {I}}w(I)=\sum _{I\in \mathcal {I}}\sum _{e\in I}w(e)\).

According to the property of the demand, we define three well-known versions. If each customer’s demand must be delivered in one tour, we call it unsplittable k-MCVRP. If a customer’s demand can be split into several tours, we call it splittable k-MCVRP. If each customer’s demand is a unit, we call it unit-demand k-MCVRP.

In the following, we use CVRP to denote MCVRP with \(m=1\), i.e., only one depot. Unless otherwise specified, we think that k-MCVRP satisfies the fixed-destination property. Moreover, if it holds the non-fixed-destination property, we called it non-fixed k-MCVRP.

2.2 Assumptions

Note that in our problem the demand d(v) may be very large since the capacity k may be arbitrarily larger than n. For the sake of analysis, we make several assumptions that can be guaranteed by some simple observations or polynomial-time reductions (see the full version).

Assumption 1

  For splittable and unsplittable k-MCVRP, each customer’s demand is at most k.

Assumption 2

  For splittable k-MCVRP with fixed k, each customer’s demand is a unit.

Assumption 3

  For unsplittable, splittable, and unit-demand k-MCVRP, there exists an optimal solution where each tour delivers an integer amount of demand to each customer in the tour.

By Assumption 3, in the following, we may only consider a tour that delivers an integer amount of demand to each customer in the tour. Moreover, we know that for unit-demand k-MCVRP, there is an optimal solution consisting of a set of cycles, which intersect only at the depot.

3 Lower Bounds

To connect approximation algorithms for k-MCVRP with k-CVRP, we consider non-fixed k-MCVRP. The first reason is that non-fixed k-MCVRP is a relaxation of k-MCVRP, and then an optimal solution of the former provides a lower bound for the latter. Let \(\text{ OPT }\) (resp., \(\text{ OPT }'\)) denote the weight of an optimal solution for k-MCVRP (resp., k-CVRP). We have \(\text{ OPT }'\le \text{ OPT }\). The second is that non-fixed k-MCVRP is equivalent to k-CVRP. The reduction is shown as follows.

Given \(G=(V\cup D, E)\), we obtain a new undirected complete graph \(H=(V\cup \{o\},F)\) by replacing the m depots in D with a new single depot, denoted by o. There is a weight function \(c: F\rightarrow \mathbb {R}_{\ge 0}\) on the edges in F. Moreover, it holds that \(c(o,v)=\min _{u\in D}w(u,v)\) and \(c(v,v')=\min \{c(o,v)+c(o,v'), w(v,v')\}\) for all \(v,v'\in V\). We can verify that the weight function c is a semi-metric function. Note that \(\varDelta =\sum _{v\in V}d(v)c(o,v)\). Clearly, any feasible solution of k-CVRP in H corresponds to a feasible solution for non-fixed k-MCVRP in G with the same weight. Note that an edge \(vv'\) in E with \(w(v,v')>c(o,v)+c(o,v')\) was also called a “dummy” edge in [18]. Any tour using a dummy edge \(vv'\) can be transformed into two tours with a smaller weight by replacing \(vv'\) with two edges uv and \(u'v'\) incident to depots such that \(c(o,v)=w(u,v)\) and \(c(o,v')=w(u',v')\). So, any feasible solution of non-fixed k-MCVRP in G can also be modified into a feasible solution for k-CVRP in H with a non-increasing weight.

A Hamiltonian cycle in a graph is a cycle that contains all vertices in the graph exactly once. Let \(C^*\) be a minimum cost Hamiltonian cycle in graph H. We mention three lower bounds for k-CVRP, which also works for k-MCVRP.

Lemma 1

([11]). It holds that \(\text{ OPT }\ge \text{ OPT }'\ge c(C^{*})\).

Lemma 2

([11]). It holds that \(\text{ OPT }\ge \text{ OPT }'\ge (2/k)\varDelta \).

Let \(T^*\) denote an optimal spanning tree in graph H. Clearly, its cost is a lower bound of an optimal Hamiltonian cycle in H. By Lemma 1, we have

Lemma 3

It holds that \(\text{ OPT }\ge \text{ OPT }'\ge c(T^*)\).

4 Review of the Previous Algorithms

4.1 The Cycle-Partition Algorithm

The main idea of the cycle-partition algorithm [18] is to construct a solution for non-fixed k-MCVRP based on the ITP or UITP algorithm for k-CVRP, and then modify the solution into a solution for k-MCVRP.

The ITP and UITP Algorithms. For splittable and unit-demand k-CVRP, given a Hamiltonian cycle C in graph H, the ITP algorithm is to split the cycle into segments in a good way, with each containing at most k of demand, and for each segment assign two edges between the new depot o and endpoints of the segment. The solution has a weight of at most \((2/k)\varDelta +c(C)\) [2, 11]. For unsplittable k-CVRP, the UITP algorithm is to use the ITP algorithm with a capacity of k/2 to obtain a solution for splittable and unit-demand k-CVRP, and then modify the solution into a feasible solution for unsplittable k-CVRP. Altinkemer and Gavish proved [1] that the modification does not take any additional cost.

Lemma 4

([1, 2, 11]).  Given a Hamiltonian cycle C in graph H, for splittable and unit-demand k-CVRP, the ITP algorithm can use polynomial time to output a solution of cost at most \((2/k)\varDelta +c(C)\); for unsplittable k-CVRP, the bound improves to \((4/k)\varDelta +c(C)\).

The Cycle-Partition Algorithm. For k-MCVRP, the cycle-partition algorithm uses the ITP or UITP algorithm to obtain a feasible solution for non-fixed k-MCVRP, and then modify the solution into a feasible solution for k-MCVRP using some additional cost. Li and Simchi-Levi [18] proved that the additional cost is exactly the cost of the Hamiltonian cycle used.

Lemma 5

([18]).  Given a Hamiltonian cycle C in graph H, for splittable and unit-demand k-MCVRP, there is a polynomial-time algorithm to output a solution of cost at most \((2/k)\varDelta +2c(C)\); for unsplittable k-MCVRP, the bound improves to \((4/k)\varDelta +2c(C)\).

Using the 3/2-approximate Hamiltonian cycle [6, 21], by Lemmas 1 and 2, the cycle-partition algorithm achieves a 4-approximation ratio for splittable and unit-demand k-MCVRP and a 5-approximation ratio for unsplittable k-MCVRP.

4.2 The Tree-Partition Algorithm

The tree-partition algorithm is based on an optimal spanning tree in graph H. Note that an optimal spanning tree in H corresponds to an optimal constrained spanning forest in G. The algorithm is to split the corresponding constrained spanning forest into small components in a good way such that each component has a demand of at most k, and moreover each that contains no depots in it has a demand of at least k/2. Note that each component that contains one depot can be transformed into a tour by doubling all edges in it and then shortcutting. For each component that contains no depots, the algorithm will add one edge with minimized weight connecting one depot to it. Then, it can be transformed into a tour by the same method: doubling and shortcutting.

Lemma 6

([12]).  For all three versions of k-MCVRP, there is a polynomial-time algorithm to output a solution of cost at most \((4/k)\varDelta +2c(T^*)\).

By Lemmas 2 and 3, the tree-partition algorithm achieves a 4-approximation ratio for all three versions of k-MCVRP.

5 An Improvement for Splittable MCVRP

In this section, we first propose a refined tree-partition algorithm based on the idea in [12]. Our algorithm is simpler due to the previous assumptions. Moreover, our algorithm has a better approximation ratio for the case that the capacity k is fixed. Then, based on recent progress in approximating k-CVRP [4], we obtain an improved \((4-1/1500)\)-approximation algorithm for splittable and unit-demand k-MCVRP.

A Refined Tree-Partition Algorithm. In our algorithm, we first assign a single cheapest trivial tour for each \(v\in V\) with \(d(v)>\lfloor k/2\rfloor \) since each customer’s demand is at most k by Assumption 1. Let \(V'\) denote the rest customers. To satisfy customers in \(V'\), we find an optimal spanning tree \(T'^*\) in graph \(H[V'\cup \{o\}]\). Note that \(T'^*\) corresponds to a constrained spanning forest in \(G[V'\cup D]\), denoted by \(\mathcal {F}\). Consider a tree \(T_u\in \mathcal {F}\) that is rooted at the depot \(u\in D\). Then, we will generate tours based on splitting \(T_u\), like Hark et al. did in [12]. For each \(v\in T_u\), we denote the sub-tree rooted at v and the children set of v by \(T_v\) and \(Q_v\), and let \(d(T_v)=\sum _{v'\in T_v}d(v')\).

  • If \(d(T_u)\le k\), it can be transformed into a tour by doubling and shortcutting.

  • Otherwise, we can do the following repeatedly until it satisfies that \(d(T_u)\le k\). We can find a customer \(v\in T_u\) such that \(d(T_v)>k\) and \(d(T_{v'})\le k\) for every children \(v'\in Q_v\). Consider the sub-trees \(\mathcal {T}_v{:}{=}\{T_{v'}\mid v'\in Q_v\}\). We can greedily partition them into l sets \(\mathcal {T}_1,\dots ,\mathcal {T}_l\) such that \(\lfloor k/2\rfloor <d(\mathcal {T}_i)\le k\) for each \(i\in \{2,\dots ,l\}\). For each such set, saying \(\mathcal {T}_2\), we can combine them into a component S by adding v with edges joining v and each tree in \(\mathcal {T}_2\). Note that S is a sub-tree of \(T_v\). Then, we find an edge \(e_S\) with minimized weight connecting one depot to one vertex in S. By doubling \(e_S\) with the edges in S and shortcutting (note that we also need to shortcut v), we obtain a tour satisfying all customers in trees of \(\mathcal {T}_2\). After handling \(\mathcal {T}_i\) for each \(i\in \{2,\dots ,l\}\), we only have \(\mathcal {T}_1\). If \(d(\mathcal {T}_1)> \lfloor k/2\rfloor \), we can handle it like \(\mathcal {T}_i\) with \(i>1\). Otherwise, we have \(d(\mathcal {T}_1)\le \lfloor k/2\rfloor \). The remaining tree is denoted by \(T'_u\). Note that \(d(\mathcal {T}_1)+d(v)\le k\) since \(d(v)\le \lfloor k/2\rfloor \). So, in \(T'_u\) the condition \(d(T'_v)>k\) and \(d(T'_{v'})\le k\) for every children \(v'\in Q'_v\) will no longer hold which makes sure that the algorithm will terminate in polynomial time.

The algorithm is shown in Algorithm 1.

Algorithm 1
figure a

. A refined tree-partition algorithm for k-MCVRP

Full size image

Theorem 1

(*). For all three versions of k-MCVRP, the refined tree-partition algorithm can use polynomial time to output a solution of cost at most \(\frac{2}{\lfloor k/2\rfloor +1}\varDelta +2c(T'^*)\).

Lemma 7

It holds that \(c(C^*)\ge c(T'^*)\).

Proof

Let \(C'^*\) denote an optimal Hamiltonian cycle in graph \(H[V'\cup \{o\}]\). By the proof of Lemma 3, we have \(c(C'^*)\ge c(T'^*)\). Note that we can obtain a Hamiltonian cycle in \(H[V'\cup \{o\}]\) by shortcutting the optimal Hamiltonian cycle \(C^*\) in H. By the triangle inequality, we have \(c(C^*)\ge c(C'^*)\).

By Theorem 1 and Lemmas 1 and 7, the refined tree-partition algorithm has an approximation ratio of \(\frac{k}{\lfloor k/2\rfloor +1}+2<4\). Next, we consider the improvement for general k.

The Improvement. Blauth et al. [4] made a significant progress in approximating k-CVRP. We show that it can be applied to k-MCVRP to obtain an improved \((4-1/1500)\)-approximation ratio for splittable and unit-demand k-MCVRP. The main idea is to make a trade-off between the cycle-partition algorithm and the refined tree-partition algorithm.

Lemma 8

([4]). If \((1-\varepsilon )\cdot \text{ OPT }'<(2/k)\varDelta \), there is a function \(f: \mathbb {R}_{>0}\rightarrow \mathbb {R}_{>0}\) with \(\lim _{\begin{array}{c} \varepsilon \rightarrow 0 \end{array}}f(\varepsilon )=0\) and a polynomial-time algorithm to get a Hamiltonian cycle C in H with \(c(C)\le (1+f(\varepsilon )) \cdot \text{ OPT }'\).

Theorem 2

(*). For splittable and unit-demand k-MCVRP, there is a polynomial-time \((4-1/1500)\)-approximation algorithm.

Note that if we only use the cycle-partition algorithm with a 3/2-approximate Hamiltonian cycle, we can merely get a \((4-1/3000)\)-approximation algorithm.

6 An Improvement for Unsplittable MCVRP

In this section, we consider unsplittable k-MCVRP. Recently, Friggstad et al. [9] proposed an improved LP-based approximation algorithm for unsplittable k-CVRP. We show that it can be used to obtain an LP-based cycle-partition algorithm for unsplittable k-MCVRP with an improved \((4-1/50000)\)-approximation ratio.

An LP-Based Cycle-Partition Algorithm. Recall that unsplittable k-CVRP can be reduced to the minimum weight k-set cover problem if k is fixed. The main idea of the LP-based approximation algorithm in [9] is that fixing a constant \(0<\delta <1\) they build an LP (in the form of set cover) only for customers v with \(d(v)\ge \delta k\). Then, the number of feasible tours is \(n^{O(1/\delta )}\) which is polynomially bounded. Using the well-known randomized LP-rounding method (see [23]), they obtain a set of tours that forms a partial solution with a cost of \(\ln 2\cdot \text{ OPT }\). Then, they design tours to satisfy the left customers based on a variant of UITP with an excepted cost of \(\frac{1}{1-\delta }\cdot (2/k)\varDelta +c(C)\), where C is a given Hamiltonian cycle in graph H.

Lemma 9

([9]). Given a Hamiltonian cycle C in graph H, for unsplittable k-CVRP with any constant \(\delta >0\), there is a polynomial-time algorithm to output a solution of cost at most \((\ln 2+\delta )\cdot \text{ OPT }'+(2/k)\varDelta +c(C)\).

For unsplittable k-MCVRP, we can use the same idea (see the full version). Fixing a constant \(0<\delta <1\), we build an LP (in the form of set cover) only for customers v with \(d(v)\ge \delta k\). A partial solution based on randomized LP-rounding has a weight of \(\ln 2\cdot \text{ OPT }\). For left customers, we obtain a solution for k-CVRP in H with an excepted cost of \(\frac{1}{1-\delta }\cdot (2/k)\varDelta +c(C)\). Since the latter is based on the idea of the UITP algorithm, we can modify them into a set of feasible tours for k-MCVRP using an additional cost of c(H) like Lemma 5. So, we can get the following theorem.

Theorem 3

(*). Given a Hamiltonian cycle C in graph H, for unsplittable k-MCVRP with any constant \(\delta >0\), the LP-based cycle-partition algorithm can use polynomial time to output a solution of cost at most \((\ln 2+\delta )\cdot \text{ OPT }+(2/k)\varDelta +2c(C)\).

The Improvement. By making a trade-off between the LP-based cycle-partition algorithm and the refined tree-partition algorithm, we can obtain an improved \((4-1/50000)\)-approximation ratio for unsplittable k-MCVRP.

Theorem 4

(*). For unsplittable k-MCVRP, there is a polynomial-time \((4-1/50000)\)-approximation algorithm.

7 An Improvement for k-MCVRP with Fixed Capacity

In this section, we consider further improvements for the case that the capacity k is fixed. We propose an LP-based tree-partition algorithm based on the refined tree-partition algorithm with the LP-rounding method. The algorithm admits an approximation ratio of \(3+\ln 2-\varTheta (1/\sqrt{k})\). Then, by further using the result in Lemma 8, we also obtain a \((3+\ln 2-1/9000)\)-approximation algorithm for splittable and unit-demand k-MCVRP. Note that the former is better when k is a fixed constant less than \(3\times 10^8\).

An LP-Based Tree-Partition Algorithm. Due to Assumption 3 we can only consider a tour that delivers an integer amount of demand to each customer in the tour. Since k is fixed, there are at most \(mn^{O(k)}\) feasible tours for k-MCVRP. Note that for splittable k-MCVRP each customer’s demand is a unit by Assumption 2. Denote the set of feasible tours by \(\mathcal {C}\), and define a variable \(x_C\) for each tour \(C\in \mathcal {C}\). We have the following LP.

$$\begin{aligned} &\,\,\text {minimize} \quad \sum _{C\in \mathcal {C}} w(C)\cdot x_C \\ &\text {subject to} \qquad \sum _{\begin{array}{c} C\in \mathcal {C}:\\ v\in C \end{array}}x_C \ge \ 1, \quad \forall \ v \in V, \\ &\qquad \qquad \qquad \qquad x_C \ge \ 0, \quad \,\,\, \forall \ C \in \mathcal {C}. \end{aligned}$$

The LP-based tree-partition algorithm is shown in Algorithm 2.

Algorithm 2
figure b

. An LP-based tree-partition algorithm for k-MCVRP

Full size image

Consider an optimal solution of k-CVRP in graph H. It consists of a set of simple cycles. Note that if we delete the longest edge from each cycle, we can obtain a spanning tree (by shortcutting if necessary since a customer may appear in more than one tour for the splittable case). Denote this spanning tree by \(T^{**}\).

Theorem 5

(*). For all three versions of k-MCVRP with any constant \(\gamma \ge 0\), the LP-based tree-partition algorithm can use polynomial time to output a solution with an expected cost at most \(\gamma \cdot \text{ OPT }+e^{-\gamma }\cdot \frac{2}{\lfloor k/2\rfloor +1}\varDelta +2c(T^{**})\).

The algorithm can be derandomized efficiently by conditional expectations [23].

The Analysis. Next, we show that the LP-based tree-partition algorithm achieves a ratio of \(3+\ln 2-\varTheta (1/\sqrt{k})\) for all three versions of k-MCVRP (see the full version). Note that the ratio \(H_k-\varTheta (\ln ^2 k/k)\) for k-set cover in [10] is better than ours only for \(k\le 11\).

Theorem 6

(*). For all three versions of k-MCVRP, the LP-based tree-partition algorithm achieves an approximation ratio of \(\max \{g(\lceil x_0\rceil ), g(\lfloor x_0\rfloor )\}\), where \(x_0{:}{=}\frac{\sqrt{4k+5}-1}{2}\) and \(g(x){:}{=}3+\ln (\frac{k+1-x}{\lfloor k/2\rfloor +1})-\frac{1}{x}\).

A Further Improvement for Splittable k -MCVRP. By making a trade-off between the cycle-partition algorithm and the LP-based tree-partition algorithm, we can obtain an improved \((3+\ln 2-1/9000)\)-approximation ratio for splittable and unit-demand k-MCVRP.

Theorem 7

(*). For splittable and unit-demand k-MCVRP, there is a polynomial-time \((3+\ln 2-1/9000)\)-approximation algorithm.

The result \(3+\ln 2-\varTheta (1/\sqrt{k})\) in Theorem 6 is better than \(3+\ln 2-1/9000\) for any \(k<3\times 10^8\). Note that for unsplittable k-MCVRP we cannot obtain further improvements using the same method. The reason is that even using an optimal Hamiltonian cycle the LP-based cycle-partition only achieves a ratio of about \(3+\ln 2\) by Theorem 3. So, there is no improvement compared with the LP-based tree-partition algorithm.

8 Conclusion

In this paper, we consider approximation algorithms for k-MCVRP. Previously, only a few results were available in the literature. Based on recent progress in approximating k-CVRP, we design improved approximation algorithms for k-MCVRP. When k is general, we improve the approximation ratio to \(4-1/1500\) for splittable and unit-demand k-MCVRP and to \(4-1/50000\) for unsplittable k-MCVRP; when k is fixed, we improve the approximation ratio to \(3+\ln 2-\max \{\varTheta (1/\sqrt{k}),1/9000\}\) for splittable and unit-demand k-MCVRP and to \(3+\ln 2-\varTheta (1/\sqrt{k})\) for unsplittable k-MCVRP.

We remark that for unsplittable, splittable, and unit-demand k-MCVRP with fixed \(3\le k\le 11\) the current best approximation ratios are still \(H_k-\varTheta (\ln ^2 k/k)\) [10]. In the future, one may study how to improve these results.

A more general problem than k-MCVRP is called Multidepot Capacitated Arc Routing (MCARP), where both vertices and arcs are allowed to require a demand. For MCARP, the current best-known approximation algorithms on general metric graphs are still based on the cycle-partition algorithm (see [26]). Some results in this paper could be applied to MCARP to obtain some similar improvements.