Enhanced Approximation Algorithms for the Capacitated Location Routing Problem

Jingyang Zhao, Mingyu Xiao, Shunwang Wang · 2025

Read Enhanced Approximation Algorithms for the Capacitated Location Routing Problem by Jingyang Zhao, Mingyu Xiao, Shunwang Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12502.txt.

Introduction

Jingyang Zhao, Mingyu Xiao, and Shunwang Wang present a 2025 algorithms paper on a logistics puzzle that fuses two classics. One half asks where to open depots. The other asks how to route loaded vehicles from them. Each depot costs money to open, each customer demands goods, and trucks have limited capacity. The goal is the cheapest full plan.

The authors give an algorithm guaranteed to land within about 4.17 times the best possible cost, beating the previous record of 4.38. If a customer's demand may arrive across several trips, the guarantee tightens to about 4.09. Benchmark tests also show their plans beating earlier methods in practice, not just on paper.

Catalog record

CREATORJingyang Zhao, Mingyu Xiao, Shunwang Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-12502

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem Jingyang Zhao, Mingyu Xiao, Shunwang Wang Abstract The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated facility location problem. In this problem, we are given a set of depots and a set of customers where each depot has an opening cost and each customer has a demand. The goal is to open some depots and route capacitated vehicles from the opened depots to satisfy all customers’ demand, while minimizing the total cost. In this paper, we propose a 4.169 4.169 -approximation algorithm for this problem, improving the best-known 4.38 4.38 -approximation ratio. Moreover, if the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined 4.091 4.091 -approximation algorithm. 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 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 [ 1 , 2 , 3 ] . Recent surveys of location routing problems can be found in [ 4 , 5 ] . In Capacitated Location Routing (CLR), we are given an undirected complete graph G=(V\cup U,E,w,\phi,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\rightarrow\mathbb{R}_{\geq 0} on edges, an opening cost function \phi:U\rightarrow\mathbb{R}_{\geq 0} on depots, and a demand function d:V\rightarrow\mathbb{R}_{\geq 0} on customers. Each depot u\in U has an opening cost \phi(u) and contains an unbounded fleet of vehicles with the same capacity k\in\mathbb{R}_{>0} (one can image that each vehicle in the depot can be used for many times), each customer v\in V has a demand d(v)>0 , and we need to determine a set of depots O\subseteq U to open and a set of tours \mathcal{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 \mathcal{I} satisfies all customers’ demand. The total cost is defined as \sum_{I\in\mathcal{I}}w(I)+\sum_{u\in O}\phi(u) , where w(I) , the cost of tour I , is defined to be the total cost of edges in I , i.e., w(I)=\sum_{e\in 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 [ 6 , 7 ] , i.e., each vehicle departing from depot u\in U incurs an additional cost of F_{u}\in\mathbb{R}_{\geq 0} . This can be represented by adding F_{u}/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 \phi\equiv 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 \phi\equiv 0 and k=\infty , 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 [ 8 , 9 , 10 , 11 , 12 , 13 , 14 ] . 1.1 Related Work 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 [ 15 , 16 ] is a well-known 1.5 -approximation algorithm, and the ratio has been recently improved to 1.5-10^{-36} by [ 17 , 18 ] . For metric m -depot TSP, Rathinam et al. [ 19 ] proposed a simple 2-approximation algorithm, and Xu et al. [ 20 ] improved the ratio to 2-1/m . There are also some works for the case that m is fixed [ 21 , 22 , 23 ] . Vehicle Routing. For the case of single depot, Haimovich and Kan [ 24 ] proposed a 2.5-approximation algorithm for splittable CVRP, and Altinkemer and Gavish [ 25 ] proposed a 3.5-approximation algorithm for unsplittable CVRP. For the case of multidepot, Li and Simchi-Levi [ 26 ] proposed a 4-approximation algorithm for splittable MCVRP, and Harks et al. [ 27 ] proposed a 4-approximation algorithm for unsplittable MCVRP. These results got improved only very recently. For CVRP, Blauth et al. [ 28 ] improved the ratio to 2.5-\frac{1}{3000} for the splittable case, and Friggstad et al. [ 29 ] improved the ratio to about 3.164 for the unsplittable case. For MCVRP, Zhao and Xiao [ 30 ] obtained a ratio of 4-\frac{1}{1500} for the splittable case and a ratio of 4-\frac{1}{50000} for the unsplittable case. Recently, Lai et al. [ 31 ] proposed a (6-4/m) -approximation algorithm for MCVRP with fixed m , considering constraints where the number of vehicles at each depot is limited and each vehicle can be used for only one tour. UFL. UFL has a rather rich history on approximation algorithms (see the book [ 32 ] ), where many new techniques were developed. We mention the following results: Jain et al. [ 33 ] proposed a practical 1.861-approximation algorithm based on the greedy method with a running time of O(nm\log nm) ; Byrka and Aardal [ 34 ] proposed a 1.5-approximation algorithm and a bifactor approximation algorithm by modifying the LP rounding method in [ 35 ] ; The current best result is a 1.488-approximation algorithm [ 36 ] . CLR. Since CLR is more challenging, there are only a few results on approximation algorithms. Harks et al. [ 27 ] 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. [

Read the complete text