Improved Approximation Algorithms for Capacitated Location Routing

1 Introduction

In the fields of logistics, vehicle routing and facility location are two major problems that have been widely studied in both theory and application. Given a set of depots, vehicle routing aims to route capacitated vehicles in the depots to deliver goods for customers to satisfy their demand using the minimum cost. Facility location concerns the opening cost of depots and the connection cost between customers and the opened depots. Location routing can be seen as a combination of these two problems, and is more natural in real life. It involves first opening a set of depots at some cost, and then routing the vehicles from the opened depots. Location routing problems have been studied for decades since the idea of combining vehicle routing and facility location was introduced in [Von Boventer, 1961; Maranzana, 1964; Webb, 1968]. Recent surveys of location routing problems can be found in [Prodhon and Prins, 2014; Drexl and Schneider, 2015].

∗Contact Author

In Capacitated Location Routing (CLR), we are given an undirected complete graph G = (V ∪U, E, w, ϕ, d, k), where V is the set of customers, U is the set of depots (or facilities), and there is one travel cost function w : E → R≥0 on edges, an opening cost function ϕ : U → R≥0 on depots, and a demand function d : V → R≥0 on customers. Each depot u ∈ U has an opening cost ϕ(u) and contains an unbounded fleet of vehicles with the same capacity k > 0, each customer v ∈ V has a demand d(v) > 0, and we need to determine a set of depots O ⊆ U to open and a set of tours I such that (1) each tour starts and ends at the same (opened) depot, (2) each tour delivers at most k of demand to customers on the tour, and (3) the union of tours in I satisfies all customers' demand. The total cost is defined as ∑I∈I w(I)+ ∑u∈O ϕ(u), where w(I), the cost of tour I, is defined to be the total cost of edges in I, i.e., w(I) = ∑e∈I w(e). We consider two variants of CLR: splittable and unsplittable, where the demand of each customer is allowed to be delivered by multiple tours (resp., only one tour) in splittable (resp., unsplittable) CLR. This definition also captures the case where each tour incurs an extra depot-dependent fixed cost [Tuzun and Burke, 1999; Barreto et al., 2007], i.e., each vehicle departing from depot u ∈ U incurs an additional cost of Fu ∈ R≥0. This can be represented by adding Fu/2 to the cost of all edges incident to u, as each tour originating at u uses only two of these edges.

CLR generalizes many famous NP-hard problems. If ϕ ≡ 0, we can open all depots in U at no cost, and in this case CLR is the Multidepot Capacitated Vehicle Routing Problem (MCVRP). If ϕ ≡ 0 and k = ∞, CLR becomes the metric m-depot traveling salesman problem (TSP). Hence, CLR also includes the (single depot) Capacitated Vehicle Routing Problem (CVRP) and metric TSP as special cases. Moreover, CLR with k being the greatest common divisor of the demands also generalizes Uncapacitated Facility Location (UFL), where we choose to open some depots and assign each customer v to its nearest opened depot u with a cost of d(v)w(v, u). These problems have been extensively studied both in terms of approximation algorithms and experimental algorithms [Toth and Vigo, 2014; Montoya-Torres et al., 2015; An et al., 2017; Zhang et al., 2015; Xin et al., 2021; Zhou et al., 2023].

1.1 RelatedWork

We focus on approximation algorithms. Next, we give a brief review of literature on TSP, Vehicle Routing, UFL, and CLR.

TSP. For metric TSP, the Christofides-Serdyukov algorithm [1976; 1978] is a well-known 1.5-approximation algorithm, and the ratio has been recently improved to 1.5-10-36 by Karlin et al. [2021; 2023]. For metric m-deopot TSP, Rathinam et al. [2007] proposed a simple 2-approximation algorithm, and Xu et al. [2011] improved the ratio to 2-1/m. There are also some works for the case that m is fixed [Xu and Rodrigues, 2015; Traub et al., 2022; Deppert et al., 2023].

Vehicle Routing. For the case of single depot, Haimovich and Kan [1985] proposed a 2.5-approximation algorithm for splittable CVRP, and Altinkemer and Gavish [1987] proposed a 3.5-approximation algorithm for unsplittable CVRP. For the case of multidepot, Li and Simchi-Levi [1990] proposed a 4-approximation algorithm for splittable MCVRP, and Harks et al. [2013] proposed a 4-approximation algorithm for unsplittable MCVRP. These results got improved only very recently. For CVRP, Blauth et al. [2022] improved the ratio to 2.5- 1 3000 for the splittable case, and Friggstad et al. [2022] improved the ratio to about 3.164 for the unsplittable case. For MCVRP, Zhao and Xiao [2023] obtained a ratio of 4- 1 1500 for the splittable case and a ratio of 4- 1 50000 for the unsplittable case.

UFL. UFL has a rather rich history on approximation algorithms (see the book [Williamson and Shmoys, 2011]), where many new techniques were developed. We mention the following results: Jain et al. [2003] proposed a practical 1.861approximation algorithm based on the greedy method with a running time of O(nmlognm); Byrka and Aardal [2010] proposed a 1.5-approximation algorithm and a bifactor approximation algorithm by modifying the LP rounding method in [Chudak and Shmoys, 2003]; The current best result is a 1.488-approximation algorithm [Li, 2013].

CLR. Since CLR is more challenging, there are only a few results on approximation algorithms. Harks et al. [2013] proposed a 4.38-approximation algorithm for both unsplittable and splittable CLR, and showed that unsplittable CLR cannot be approximated better than 1.5 unless P = NP. They also extended their algorithm to derive approximation algorithms for three settings of CLR: prize-collecting, grouping, and cross-docking. Recently, Heine et al. [2023] proposed a bifactor approximation algorithm for a variant of CLR, where each depot is also capacitated.

1.2 Our Results

In this paper, we propose two improved approximation algorithms for CLR. The first, denoted as Tree-Alg, is a 4.169approximation algorithm for both unsplittable and splittable CLR, which improves the previous 4.38-approximation algorithm [Harks et al., 2013]. Note that the previous approximation ratio has been kept for a decade. The second, denoted as Path-Alg, achieves a better ratio of 4.092 for splittable CLR. The details of our improvements are as follows.

First, we obtain two stronger lower bounds for CLR, which are essential to our results. Second, by refining the previous 4.38-approximation algorithm, we obtain our Tree-Alg, and the main idea is to obtain tours by splitting trees. At last, motivated by the cycle-splitting method used in vehicle routing problems, we develop our Path-Alg, focusing on splitting paths. Although paths are simpler than trees, the analysis uses more techniques. The main reason is that we may use an approximation algorithm of TSP to compute paths which are more expensive, and then we cannot even obtain a better approximation ratio by a straightforward analysis.

In practice, our algorithms are easy to implement and run very fast. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of the previous algorithm and is also much closer to optimality than the provable approximation factor.

1.3 Paper Organization

The remaining parts of the paper are organized as follows. In Section 2, we introduce some notations and the formal definitions of CLR and UFL. In Section 3, we propose two stronger lower bounds for CLR. In Section 4, we give our Tree-Alg for both unsplittable and splittable CFL, and in Section 5, we give our Path-Alg for splittable CFL. In Section 6, we present the experimental study of our algorithms. At last, we make the concluding remarks in Section 7.

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.

2 Preliminaries

In CLR, we use G = (V ∪U, E, w, ϕ, d, k) to denote the input complete graph. The cost function w is a metric function, i.e., it is symmetric and satisfies the triangle inequality. In UFL, the input graph is the same as CLR, except for the absence of the parameter k, and we use G = (V ∪ U, E, w, ϕ, d) to denote it.

For any function f : X → R≥0, we always define f(Y ) = ∑x∈Y f(x) for any Y ⊆ X. For any subgraph S of G, we use V (S), U(S), and E(S) to denote the customer set, the depot set, and the edge set of S, respectively. Furthermore, we define w(S) = ∑e∈E(S) w(e), ϕ(S) = ∑u∈U(S) ϕ(u), and d(S) = ∑v∈V (S) d(v).

A walk in a graph, denoted by v1v2 . . . vl, is a sequence of vertices v1, v2, . . . , vl, where a vertex may appear more than once and each consecutive pair of vertices is connected by an edge. A path in a graph is a walk where no vertex appears more than once. The first and the last vertices of a path are referred to as its terminals. A closed walk is a walk where the first and the last vertices are the same, and a cycle is a walk where only the first and the last vertices are the same. Given a closed walk, we can skip repeated vertices along the walk to get a cycle, and such an operation is called shortcutting. During shortcutting, if a specific vertex v is consistently skipped, we refer to it as shortcutting v.

A constrained spanning forest in G is a forest that spans (i.e., covers) all vertices in V and each tree in it contains only one depot. A constrained spanning path-packing in G is a set of vertex-disjoint paths that spans all vertices in V , each depot is contained in at most one path in it, and each path in it contains only one depot and the depot is one of its terminals. A constrained spanning cycle-packing in G is a set of vertexdisjoint cycles or paths that spans all vertices in V , each cycle in it contains only one depot, and each path in it contains only two depots and the depots are its terminals.

A tour is a walk that starts and ends at the same depot and does not pass through any other depot. We may only consider simple and minimal tours with each containing only one depot, i.e., each tour is a cycle containing only one depot.

2.1 Formal ProblemDefinition

Definition 1 (CLR). Given an undirected complete graph G = (V ∪ U,E,w, ϕ, d, k), we need to find a set of depots O ⊆ U and a set of tours I with a demand assignment x : V ×I →R≥0 such that

• U(I) ∩O ̸= ∅ for any I ∈ I,
• ∑v∈V (I) xvI ≤ k for any I ∈ I,
• ∑v∈V \V (I) xvI = 0 for any I ∈ I,
• ∑I∈I xvI = d(v) for any v ∈ V ,

In the above definition, if each customer is allowed to be satisfied by using multiple tours, we call it as splittable CLR. For unsplittable CLR, it requires that each customer must be satisfied by using only one tour. Clearly, unsplittable CLR admits a feasible solution only if it holds d(v) ≤ k for any v ∈ V . In any solution (O, I), we will refer to ∑I∈I w(I) as the routing cost and ∑u∈O ϕ(u) as the opening cost.

Definition 2 (UFL). Given an undirected complete graph G = (V ∪ U,E,w, ϕ, d), we need to find a set of depots O ⊆ U such that the cost ∑v∈V d(v) · mino∈O w(o, v) + ∑u∈O ϕ(u) is minimized, i.e., for each v ∈ V we directly assign d(v) of demand to v from its nearest depot o in O with a connection cost of d(v)w(o, v).

In Definition 2, ∑v∈V d(v) · mino∈O w(o, v) is called the connection cost and ∑u∈O ϕ(u) is called the opening cost.

3 Lower Bounds

In this section, we prove two lower bounds of the optimal solution that holds for both unsplittable and splittable CLR. These bounds are crucial for us to prove the approximation ratio.

Given an instance G = (V ∪ U, E, w, ϕ, d, k) of CLR, we construct an UFL instance G = (V ∪ U,E, ˜ w, ˜ ϕ, d) as follows. The sets of depots and customers with their demand remain the same as in CLR, but we set the costs of edges to ˜ w := (2/k)w and the costs of depots to ˜ ϕ := α · ϕ, where α is a fixed constant that will be defined later. Note that α is an important parameter newly proposed by us. In contrast, Harks et al. [2013] only focused on ˜ ϕ := ϕ.

Let OPT (resp., OPT′ ) denote the cost of an optimal solution for CLR (resp., UFL). We let ψ∗ and ϕ∗ to denote the routing cost of vehicles and the opening cost of facilities with respect to the optimal solution of CLR, respectively. Note that we have OPT = ψ∗ + ϕ∗ . We have the following bound.

Our bound in Lemma 3 is more general since the previous paper [Harks et al., 2013] only obtained the bound under α = 1. Next, we consider the second lower bound.

Algorithm 1 An improved approximation algorithm for unsplittable and splittable CLR (Tree-Alg)

Input: An instance of CLR.

Output: A feasible solution to CLR.

• 1: Create an UFL instance with edge costs ˜ w = (2/k)w and depot costs ˜ ϕ = α · ϕ as in Lemma 3.
• 2: Apply Byrka and Aardal's bifactor approximation algorithm [Byrka and Aardal, 2010] with a parameter of γ > 0 on the UFL instance, and let O1 be the set of depots opened in the resulting UFL solution.
• 3: Compute a constrained spanning forest T in G as in Lemma 4, and let O2 = U(T ) be the set of depots contained in some T ∈ T .
• 4: Open all depots in O := O1 ∪O2.
• 5: Obtain a set of feasible tours I by calling the tree-splitting procedure in Algorithm 2.
• 6: Return (O, I).

It was shown in [Harks et al., 2013] that one can use polynomial time to find a constrained spanning forest T in G such that 2w(T ) + ϕ(T ) ≤ 2 · OPT. We propose a better result.

Lemma 4 (♣). There is a polynomial-time algorithm to find a constrained spanning forest T such that

4 General CLR

In this section, we introduce our Tree-Alg, which is a 4.169approximation algorithm for unsplittable and splittable CLR.

4.1 The Algorithm

Our algorithm uses the framework of the 4.38-approximation algorithm in [Harks et al., 2013]. It uses a bifactor approximation algorithm to compute a solution (i.e., a set of depots) for the constructed instance of UFL in Lemma 3. Then, it computes the constrained spanning forest T in Lemma 4. Let O1 be the set of opened depots in the solution of UFL and O2 be the set of depots contained in T . The algorithm will open all depots in O := O1 ∪O2. Based on splitting the trees in T (the tree-splitting procedure in [Harks et al., 2013]), the algorithm will return a feasible solution in polynomial time. The framework of the algorithm is shown in Algorithm 1. Note that the 4.38-approximation algorithm in [Harks et al., 2013] corresponds to our algorithm under α = 1.

Given a set of opened depots O and a constrained spanning forest T , the tree-splitting procedure is to obtain a set of feasible tours using only depots in O, which is also equivalent to solving an instance of MCVRP. Note that it also works for the case of splittable demand. Hence, we may assume w.l.o.g. that a customer can have a demand of more than k. The main idea is to repeatedly find a sub-tree S of trees in T such that k ≥ d(S) > k/2, and then construct a tour for (part of) customers in V (S) by doubling edges in E(S) ∪ {eS} and shortcutting, where eS is a minimum weight edge between one customer in V (S) and one depot in O.

The details are as follows. First, for each customer v ∈ V with d(v) > k, we construct ⌈ d(v) k ⌉ tours for v by connecting v with its nearest opened depot in O and regard v as a zero-demand customer in the following. Then, we consider a tree Tu ∈ T rooted at u ∈ O, and satisfy all non-zerodemand customers in V (Tu) by splitting Tu. Denote the subtree rooted at v and the set of v's children by Tv and Qv, respectively.

• If d(Tu) ≤ k, we construct a tour for all non-zerodemand customers in V (Tu) by doubling all edges in E(Tu) and then shortcutting. Note that d(Tu) may have a demand of less than k/2, but Tu is special since it contains an opened depot.
• Else, we find a minimal sub-tree Tv such that d(Tv) > k and d(Tv′) ≤ k for every v′ ∈ Qv. Consider sub-trees in Tv := {v} ∪ {Tv′ | v′ ∈ Qv}. We greedily partition them into sets T0, . . . , Tl such that d(Ti) ≤ k for each i and d(Ti) > k/2 for each i > 0. For each Ti with i > 0, we combine trees in Ti into a sub-tree S by adding the edges joining v and each tree in Ti and v (if {v} /∈ Ti). Then, we find a minimized cost edge eS connecting one depot in O with one vertex in V (S)∪U(S). By doubling edges in E(S) ∪ {eS} and shortcutting, we construct a tour for all non-zero-demand customers in V (Ti). At last, we update Tu by removing V (S) \ {v} and E(S) from Tu, and regard v as a zero-demand customer in the following if {v} ∈ Ti.

The tree-splitting procedure used in Algorithm 1 is shown in Algorithm 2. The tours have the following properties.

Lemma 5. [Harks et al., 2013]. Given a set of opened depots O and a constrained spanning forest T , the set of tours I returned by the tree-splitting procedure holds that (O, I) is a feasible solution for unsplittable and splittable UFL, and w(I) ≤ 2w(T ) + ∑v∈V (4/k)d(v) · minu∈O w(v, u).

4.2 The Analysis

In this subsection, we show that by carefully setting the values of α and γ we can obtain a 4.169-approximation ratio.

For UFL with any constant γ ≥ 1.678, Byrka and Aardal [2010] proposed a (bifactor) (1 + 2e-γ , γ)- approximation algorithm. It returns a solution whose connection cost is at most (1 + 2e-γ ) · ψLP and whose opening cost is at most γ · ϕLP , where ψLP and ϕLP are the values of the connection cost and the opening cost of an initially computed optimal fractional LP solution, respectively. In Step 2 of Algorithm 1, we apply Byrka and Aardal's algorithm on the UFL instance to open a set of depots O1. Hence, the connection cost and the opening cost in the solution satisfies ∑v∈V d(v) · minu∈O1 ˜ w(v, u) and ˜ ϕ(O1), respectively. Therefore, we have the following bounds.

Recall that OPT′ is the cost of an optimal solution on the UFL instance in Lemma 3. The cost of the optimal fractional LP solution is at most the cost of an optimal solution. Hence, we have ψLP + ϕLP ≤ OPT′ . By Lemma 3, we have

Lemma 7. It holds that ψLP +ϕLP ≤ OPT′ ≤ ψ∗ +α · ϕ∗ .

Theorem 8. For unsplittable and splittable CLR, Tree-Alg is a polynomial-time 4.169-approximation algorithm.

Algorithm 2 The tree-splitting procedure for CLR

Input: An instance of CLR, a set of opened depots O, and a constrained spanning forest T .

Output: A set of feasible tours I to CLR.

• 1: Initialize I = ∅.
• 2: for all v ∈ V with d(v) > k do
• 3: Construct ⌈ d(v) k ⌉ tours for v by connecting v with its nearest opened depot in O.
• 4: Add the tours to I and regard v as a zero-demand customer in the following.
• 5: end for
• 6: for all Tu ∈ T do
• 7: while d(Tu) > k do
• 8: Find v ∈ V (Tu) with d(Tv) > k and d(Tv′ ) ≤ k for each v′ ∈ Qv.
• 9: Greedily partition trees in Tv := {v}∪{Tv′ | v′ ∈ Qv} into sets T0, . . . , Tl such that d(Ti) ≤ k for each i and d(Ti) > k/2 for each i > 0.
• 10: for i ∈ {1, . . . , l} do
• 11: Combine trees in Ti into a sub-tree S by adding the edges joining v and each tree in Ti, and v (if {v} /∈ Ti).
• 12: Find an edge eS with minimized cost connecting one depot in O with one vertex in V (S) ∪ U(S).
• 13: Construct a tour for all non-zero-demand customers in V (Ti) by doubling edges in E(S) ∪ {eS} and shortcutting.
• 14: Add the tour to I, update Tu by removing V (S) \
• {v} and E(S) from Tu, and regard v as a zero-demand customer in the following if {v} ∈ Ti.
• 15: end for
• 16: end while
• 17: Construct a tour for all non-zero-demand customers in V (Tu) by doubling edges in E(Tu) and shortcutting.
• 18: Add the tour to I.
• 19: end for
• 20: Return I.

Proof. By Algorithm 1, it returns a solution (O, I) such that w(I) + ϕ(O)

where the first inequality follows from w(I) ≤ 2w(T ) + ∑v∈V (4/k)d(v) · minu∈O w(v, u) by Lemma 5 and ϕ(O) ≤ ϕ(O1) + ϕ(O2), the second inequality follows from minu∈O w(v, u) ≤ minu∈O1 w(v, u), ˜ w = (2/k)w, ˜ ϕ = α · ϕ, and ϕ(O2) = ϕ(T ), and the last inequality follows from OPT = ψ∗ + ϕ∗ and Lemmas 4 and 6.

Let fγ(α) := max{2(1+2e-γ ), (1/α) · γ}. Since OPT = ψ∗ + ϕ∗ , the approximation ratio is bounded by

where the first inequality follows from Lemma 7.

Setting α = 1.461 and γ = 3.168, we get fγ(α) ≤ 2.169 and max{2 + fγ(α), 1 + α · fγ(α)} ≤ 4.169. Hence, the approximation ratio of Algorithm 1 is at most 4.169.

Since the bifactor approximation algorithm [Byrka and Aardal, 2010] and the tree-splitting procedure [Harks et al., 2013] run in polynomial time, it is easy to see that Tree-Alg also runs in polynomial time.

5 Splittable CLR

In this section, we introduce our Path-Alg. As asked in [Harks et al., 2013], an open problem is whether a more tour-specific approach could lead to better approximation ratios. We answer this question partially by showing that for splittable CLR our Path-Alg is a 4.092-approximation algorithm. The approach is inspired by the cycle-splitting method used for MCVRP in [Li and Simchi-Levi, 1990].

The main idea of the cycle-splitting method proposed in [Li and Simchi-Levi, 1990] is to obtain a Hamiltonian cycle by using a δ-approximation algorithm for metric TSP (recall that δ ≈ 1.5), and then obtain tours based on splitting the cycle. Since we can transform a cycle into a path by deleting an edge from it, instead of splitting a cycle, we focus on splitting a path. Although it seems that there is no big difference between cycles and paths, they may lead to different approximation ratios. This is because the edges incident to depots may have additional costs, and we need to carefully control the number of edges incident to depots.

A path, as a special case of tree, has a simpler structure: for the case of splittable demand, one can greedily divide it into several segments of demand k and possibly leave the last segment (containing the depot) with a demand of less than k. Recall that the tree-splitting procedure is mainly to obtain a sub-tree S such that k ≥ d(S) > k/2 repeatedly. Therefore, based on a path-splitting procedure, we may reduce the connection part of the routing cost from ∑v∈V (4/k)d(v) · minu∈O w(v, u) to ∑v∈V (2/k)d(v)·minu∈O w(v, u). However, it is not straightforward to obtain better approximation ratios for splittable CLR since we need to use twice cost of the paths obtained from a δ-approximation algorithm for metric TSP that is more expensive than the constrained spanning forest computed in Lemma 4. We will obtain a good approximation ratio based on this idea with novel analysis.

5.1 The Algorithm

Compared to Tree-Alg, Path-Alg has two main modifications: firstly, it computes a constrained spanning path-packing rather than a constrained spanning forest, and secondly, it constructs a set of tours through a path-splitting procedure instead of the tree-splitting procedure.

To compute a constrained spanning path-packing, we construct two new graphs G′ and H. Given G = (V ∪ U, E, w, ϕ), we obtain a new graph G′ = (V ∪ U, E, w′ , ϕ) such that w′ (v, v′ ) = w(v, v′ ) for any v, v′ ∈ V and w′ (u, v) = w(u, v)+θ·ϕ(u) for any v ∈ V and u ∈ U, where θ is a constant defined later. Then, we obtain another graph H = (V ∪ {r}, F, c) such that c(r, v) = minu∈U w′ (u, v) and c(v, v′ ) = min{w′ (v, v′ ), c(r, v) + c(r, v′ )}. One can Algorithm 3 An improved approximation algorithm for splittable CLR (Path-Alg)

Input: An instance of CLR.

Output: A feasible solution to CLR.

• 1: Create an UFL instance with edge costs ˜ w = (2/k)w and depot costs ˜ ϕ = α · ϕ as in Lemma 3.
• 2: Apply Byrka and Aardal's bifactor approximation algorithm [Byrka and Aardal, 2010] with a parameter of γ > 0 on the UFL instance and let O1 be the set of depots opened in the resulting UFL solution.
• 3: Compute a constrained spanning path-packing P in G as in Lemma 9 and let O2 = U(P) be the set of depots contained in some P ∈ P.
• 4: Open all depots in O := O1 ∪O2.
• 5: Obtain a set of feasible tours I by calling the path-splitting procedure in Algorithm 4.
• 6: Return (O, I).

also think that H is obtained by contracting all depots in U as a super-depot r and then taking a metric closure of G′ . Note that the edge weight functions in new graphs G′ and H are still metric functions.

Lemma 9. Given a δ-approximation algorithm for metric TSP, there is a polynomial-time algorithm to compute a constrained spanning path-packing P in G.

Proof. By applying a δ-approximation algorithm for metric TSP in H, we can obtain a Hamiltonian cycle C in H. Note that C corresponds to a subgraph of G′ where each vertex in V has an even degree. Therefore, we can obtain a constrained spanning cycle-packing C in G′ by shortcutting. Note that the shortcutting can ensure that each depot is contained in at most one cycle or path in C.

Then, we can transform C into a constrained spanning pathpacking P by doing: (1) for each cycle uv1 . . . viu ∈ C we delete the edge with a smaller cost from uv1 and uvi, and (2) for each path uv1 . . . viu′ ∈ C we delete the edge incident to the depot with a smaller opening cost from uv1 and u′ vi. We can see each depot is contained in at most one path in P.

The framework of our Path-Alg for splittable CLR can be seen in Algorithm 3.

The path-splitting procedure works as follows. First, for each customer v ∈ V with d(v) > k, we construct ⌈ d(v) k ⌉-1 tours for v (with each delivering k of demand) by connecting v with its nearest opened depot in O and update d(v) := d(v) - k · (⌈ d(v) k ⌉-1). In the following, the demand of each customer v holds that 0 < d(v) ≤ k. Then, we consider a path Pu ∈ P rooted at u ∈ O, and satisfy all customers in V (Pu) by splitting Pu. Denote the sub-path rooted at v and v's the only children by Pv and q(v), respectively. We consider the following two cases.

• If d(Pu) ≤ k, we get a tour for all customers in V (Pu) by doubling all edges in E(Pu) and then shortcutting.
• Otherwise, we can do the following repeatedly until it satisfies that d(Pu) ≤ k. First, we can find a customer v ∈ V (Pu) such that d(Pv) > k and d(Pq(v)) ≤ k.

Algorithm 4 The path-splitting procedure for splittable CLR

Input: An instance of CLR, a set of opened depots O, and a constrained spanning path-packing P.

Output: A set of feasible tours I to CLR.

• 1: Initialize I = ∅.
• 2: for all v ∈ V with d(v) > k do
• 3: Construct ⌈ d(v) k ⌉ - 1 tours for v by connecting v with its nearest opened depot in O (each delivers k of demand).
• 4: Add the tours to I and update d(v) := d(v)-k·(⌈ d(v) k ⌉-1).
• 5: end for
• 6: for all Pu ∈ P do ▷ Pu is rooted at the depot u ∈ O
• 7: while d(Pu) > k do
• 8: Find v ∈ V (Pu) with d(Pv) > k and d(Pq(v)) ≤ k. ▷ q(v) is v's the only children
• 9: Find an edge ePv with minimized cost connecting one depot in O with one vertex in V (Pv).
• 10: Construct a tour I for all customers in V (Pv) by doubling edges in E(Pv) ∪ {ePv } and shortcutting with demand assignments: xvI = k - d(Pq(v)) and xv′I = d(v′ ) for each v′ ∈ V (Pq(v)).
• 11: Add the tour to I, update Pu by removing V (Pq(v)) and E(Pv) from Pu, and update d(v) := d(v) - xvI .
• 12: end while
• 13: Construct a tour for all customers in V (Pu) by doubling edges in E(Pu) and shortcutting.
• 14: Add the tour to I.
• 15: end for
• 16: Return I.

Consider the sub-path Pv. Then, we find an edge ePv with minimized cost connecting one depot in O with one vertex in V (Pv). By doubling edges in E(Pv) ∪ {eS} and shortcutting, we construct a tour I for all customers in V (Pv) with demand assignments: xvI = k-d(Pq(v)) and xv′ I = d(v′ ) for each v′ ∈ V (Pq(v)). At last, we update Pu by removing V (Pq(v)) and E(Pv) and setting d(v) := d(v) - xvI .

The path-splitting procedure used in Algorithm 3 is formally shown in Algorithm 4.

Lemma 10 (♣). Given a set of opened depots O and a constrained spanning path-packing P, the path-splitting procedure can use polynomial time to obtain a set of tours I such that (O, I) is a feasible solution for splittable UFL and w(I) ≤ 2w(P) + ∑v∈V (2/k)d(v) · minu∈O w(v, u).

5.2 The Analysis

Based on a straightforward analysis, we may obtain 2w(P)+ ϕ(P) ≤ 2δ ·ψ∗ +2δ ·ϕ∗ , where δ is the approximation ratio of the algorithm used for metric TSP. However, it cannot lead to a better-than-4.169-approximation ratio. In this subsection, we will prove a better bound based on a tighter analysis, and obtain a 4.092-approximation ratio.

Let C ∗ be a minimum cost Hamiltonian cycle in graph H.

Proof. Consider an optimal solution (O, I) of CLR. For each depot o ∈ O, there is a set of tours Io ⊆ I with each in it containing o. By shortcutting all tours in Io, we obtain a cycle Co = ov1 . . . vio such that w′ (Co) ≤ w(Io) + 2θ · ϕ(o). Note that H is obtained by contracting all depots in U as a super-depot r and then taking a metric closure of G′ , and {Co}o∈O corresponds to an Eulerian graph in H. Therefore, by shortcutting {Co}o∈O, we obtain a Hamiltonian cycle in H with a cost of at most ∑o∈O w′ (Co). Since C ∗ is the minimum cost Hamiltonian cycle in H, we can get that

which finishes the proof.

Lemma 12. Given a δ-approximation algorithm for metric TSP, the computed constrained spanning path-packing P satisfies that 2w(P) + ϕ(P) ≤ 2δ · ψ∗ + δ · ϕ∗ under θ = 1 4 .

Proof. Given a δ-approximate Hamiltonian cycle in H, the algorithm in Lemma 9 simply computes a constrained spanning cycle-packing C in G′ by shortcutting the corresponding subgraph in G′ . Hence, we have w′ (C) ≤ δ · c(C ∗ ). Let C = C1 ∪ C2, where C1 and C2 denote the set of cycles and paths in C, respectively.

For each cycle uv1 . . . viu ∈ C1 (resp., path uv1 . . . viu′ ∈ C2), the algorithm deletes the edge with a smaller cost from uv1 and uvi (resp., incident to the depot with a smaller opening cost from uv1 and u′ vi). Therefore, the constrained spanning path-packing P satisfies that w′ (P) ≤ w′ (C) - θ · ϕ(C1) - 12 θ · ϕ(C2) and ϕ(P) ≤ ϕ(C1) + 1 2 ϕ(C2). Note that w′ (P) = w(P)+θ · ϕ(P) since each path in P contains only one edge incident to the depot. Moreover, under θ = 14 , we also have 1 - 2θ = 2θ > 0. Hence, we have

So, we get 2w(P)+ϕ(P) ≤ 2δ·ψ∗ +δ·ϕ∗ by Lemma 11.

Using the well-known Christofides-Serdyukov algorithm [1976; 1978] for metric TSP, we have δ = 32 , and then we have 2w(P)+ϕ(P) ≤ 3ψ∗+ 3 2 ϕ∗ by Lemma 12. Note that this result may only lead to a 4.143-approximation algorithm for splittable CLR. We can obtain a further improvement if using the property of their algorithm. Let T ∗ be a minimum spanning tree in H. We have the following lemma.

Lemma 14 (♣). Given the Christofides-Serdyukov algorithm for metric TSP, the computed constrained spanning pathpacking P satisfies that 2w(P)+ϕ(P) ≤ 3ψ∗ +ϕ∗ if θ = 1 4 .

Theorem 15 (♣). For splittable CLR, Path-Alg is a polynomial-time 4.092-approximation algorithm.

6 Experimental Results

We conduct experiments to compare our two algorithms, Tree-Alg and Path-Alg, with the previous approximation algorithm in [Harks et al., 2013]. Next, we introduce the benchmark instances of CLR, the implementations of our algorithms, and the results, respectively.

Instances. Harks et al. [2013] tested their approximation algorithm on 45 CLR benchmark instances in total, including 36 instances from [Tuzun and Burke, 1999] and 9 instances from [Barreto et al., 2007]. They compared their results with the previous best known solutions (pbks) obtained by heuristic approaches [Prins et al., 2007; Baldacci et al., 2009; Barreto et al., 2007; Tuzun and Burke, 1999] by computing the gaps between their results and the pbks. Although some results of these benchmark instances have been further slightly improved [Baldacci et al., 2011; Contardo et al., 2014], for the sake of comparison, we test our algorithms on these instances and still compute the gaps between our results and the pbks.

Implementations. We present the detailed implementations of our algorithms.

On one hand, given a sub-tree, instead of finding tours by the method of doubling and shortcutting, we obtained a tour by finding a minimum cost matching on the odd-degree vertices contained in the sub-tree and then shortcutting. This was motivated by its ability to guarantee a 1.5-approximation for metric TSP [Christofides, 1976; Serdyukov, 1978], whereas the doubling-and-shortcutting method may only achieve a 2approximation [Williamson and Shmoys, 2011]. Note that in our Path-Alg we used this method to implement the 1.5approximation algorithm of metric TSP as well.

On the other hand, as in [Harks et al., 2013], we used the practical 1.861-approximation algorithm [Jain et al., 2003] of UFL to open a set of depots O1 instead of using the bifactor approximation algorithm [Byrka and Aardal, 2010] since the latter algorithm involves solving an LP, which is not practical. So, there was no need to consider the setting of γ. Moreover, after opening a set of depots using the greedy algorithm, suggested in [Harks et al., 2013], we regarded their opening cost as zero in the following. This does not impact the approximation ratio. For α, we tested different values. This choice was made because for a range of values of α the implementations can always guarantee an approximation ratio. See the following lemma. Harks et al. [2013] only considered α = 1 and showed the implementation had a ratio of 5.722.

Lemma 16 (♣). For any 0.5 ≤ α ≤ 1.26, our implementation of Tree-Alg has an approximation ratio of 5.722; For any 1 ≤ α ≤ 2.07, our implementation of Path-Alg has an approximation ratio of 4.861; Moreover, both implementations have a running time of O(n3 + nm log nm).

Our algorithms are implemented in C++ on a desktop computer with an AMD Ryzen 5 PRO 4650G with Radeon Graphics (3.70 GHz, 32.0 GB RAM) using Windows Subsystem for Linux (WSL). The detailed information of our algorithms, the 45 tested instances and the pbks can be found in https://github.com/JingyangZhao/CLR.

Results. A summary of our results can be found in Table 1, where we list the average gaps between our results of TreeAlg (resp., our results of Path-Alg) and the pbks under different settings of α. Note that our algorithms run very fast. The running time of each instance on average is about 0.08s for both Tree-Alg and Path-Alg, which is almost unchanged under different values of α.

The previous algorithm in [Harks et al., 2013] achieves an average gap of 18.8%. Under α = 0.1, our algorithms get a bigger average gap, which means our results are worse. The reason may be that under α = 0.1 the greedy algorithm opens almost all depots for each instance which is too expensive. For other values of α in Table 1, we can achieve a better ratio. Notably, as we increase the value of α, the gaps exhibit a significant decrease potentially because the greedy algorithm opens less depots. Especially, when setting α = 0.4 and α = 0.7, the gaps become 11.64% and 16.76% for Tree-Alg and Path-Alg, respectively, both surpassing the performance of 18.8%. But, when further increasing α, the gaps start to increase: the number of opened depots may be too small.

We conclude that when setting α suitably, our algorithms achieve much better results than the previous approximation algorithm, and the quality of solutions is also much closer to optimality than the provable approximation ratio. Although Path-Alg has a better approximation ratio in theory, TreeAlg is slightly better on the tested instances in practical. The reason may be that in the worst-case, Tree-Alg delivers only about k/2 of demand on each tour but it delivers close to k of demand on each tour in practical.

7 Conclusion

In this paper, we propose two improved approximation algorithms for CFL: one is a 4.169-approximation algorithm for both the unsplittable case and the splittable case, and another is a 4.092-approximation algorithm for the splittable case. Our algorithms may be extended to some variants of CLR in [Harks et al., 2013]. A remained open problem is to design a better-than-4-approximation algorithm for CLR.

Acknowledgements

This work is supported by National Natural Science Foundation of China under grants 62372095 and 62172077, and Natural Science Foundation of Sichuan Province of China under grant 2023NSFSC0059.