Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem

Jingyang Zhao, Yonghang Su, Mingyu Xiao · 2026

Read Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem by Jingyang Zhao, Yonghang Su, Mingyu Xiao (2026) 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-2601-01841.txt.

Introduction

Delivery fleets based at several depots may split one customer's order among multiple vehicles, and planning the cheapest routes is a notoriously hard optimization problem. Jingyang Zhao, Yonghang Su, and Mingyu Xiao improve the guaranteed approximation for this multiple-depot split delivery problem, parameterized by the number of depots.

The previous best algorithm promised routes within six times optimal. The new one lowers the factor. It uses the best traveling salesman ratio. It enumerates partitions of low-cost components. It builds a cheap cycle cover. Paths are then assigned to vehicles through minimum-cost flow. The techniques also improve the multiple-depot traveling salesman problem. A simpler five-approximation is offered too. A bi-factor variant trades small capacity violations for speed or cost. Experiments confirm complementary strengths across instance types.

Catalog record

CREATORJingyang Zhao, Yonghang Su, Mingyu Xiao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-01841

Browse the full library · About the Tower of Babel

Full text

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

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem Jingyang Zhao, Yonghang Su, Mingyu Xiao Abstract The Multiple-Depot Split Delivery Vehicle Routing Problem (MD-SDVRP) is a challenging problem with broad applications in logistics. The goal is to serve customers’ demand using a fleet of capacitated vehicles located in multiple depots, where each customer’s demand can be served by more than one vehicle, while minimizing the total travel cost of all vehicles. We study approximation algorithms for this problem. Previously, the only known result was a 6-approximation algorithm for a constant number of depots (INFORMS J. Comput. 2023), and whether this ratio could be improved was left as an open question. In this paper, we resolve it by proposing a ( 6 − 2 ⋅ 10 − 36 ) (6-2\cdot 10^{-36}) -approximation algorithm for this setting. Moreover, we develop constant-factor approximation algorithms that work beyond a constant number of depots, improved parameterized approximation algorithms related to the vehicle capacity and the number of depots, as well as bi-factor approximation algorithms. 1 Introduction The (Capacitated) Vehicle Routing Problem (VRP) is a classical and extensively studied routing problem Toth and Vigo 2014 . In this problem, we are given a set of customers with integer demand and a depot that provides an unlimited number of vehicles with the same integer capacity. The objective is to design vehicle routes for to satisfy all customers such that the total traveling cost is minimized. Each vehicle route must begin and end at the depot, and in which the vehicle delivers at most its capacity of demand to customers. There are two famous variants of the CVRP: splittable and unsplittable . In the splittable CVRP, each customer’s demand can be served by multiple vehicles, whereas in the unsplittable CVRP, each customer’s demand must be served entirely by a single vehicle. When the model is extended to allow multiple depots, it becomes the Multiple-Depot VRP (MD-VRP), which has also received substantial attention in the literature Montoya-Torres et al. 2015 . However, in real-world scenarios, the number of vehicles available at each depot may be limited. To address this situation, the Split Delivery VRP (SDVRP), a variant of the splittable VRP, was introduced Dror and Trudeau 1989 ; Dror and Trudeau 1990 . The SDVRP has since been studied extensively Belenguer et al. 2000 ; Zhang et al. 2015 ; Gamst et al. 2024 ; Lin et al. 2025 ; Konstantakopoulos et al. 2022 , and a comprehensive survey can be found in Archetti et al. 2014 . Analogously, when multiple depots are involved, the corresponding problem is known as the Multiple-Depot SDVRP (MD-SDVRP) Lai et al. 2023 . Formally, in the MD-SDVRP, we are given an undirected complete graph G=(V,E) with vertex set V=J\cup D and edge set E=V\times V . The set J represents n customers, and D represents k depots. Each customer v\in J has a demand q_{v}\in\mathbb{N}^{+} , and each depot u\in D owns r_{u}\in\mathbb{N}^{+} vehicles with the same capacity Q\in\mathbb{N}^{+} . Let L denote the set of all vehicles and m=|L| . Each edge e\in E has a non-negative cost c(e)\geq 0 , and the edge cost function c satisfies the triangle inequality. The objective is to design vehicle routes to satisfy all customers while minimizing the total traveling cost. When k=1 , the MD-SDVRP reduces to the SDVRP. We study (parameterized) approximation algorithms and bi-factor approximation algorithms for the MD-SDVRP. For a minimization problem, an algorithm is called a \rho -approximation algorithm if, for any instance I , it computes a solution of cost at most \rho times the optimal value in polynomial time \text{poly}(|I|) , where |I| denotes the input size. The quantity \rho is referred to as the approximation ratio . With respect to some parameter k\in\mathbb{N}^{+} , an algorithm is called a slice-wise polynomial-time (XP) \rho -approximation algorithm if it runs in \text{poly}(|I|) time for every fixed k=\mathcal{O}(1) and achieves an approximation ratio of \rho ; an algorithm is called a fixed-parameter tractable (FPT) \rho -approximation algorithm if it runs in \mathcal{O}(f(k))\cdot\text{poly}(|I|) time for some computable function f(k) and achieves an approximation ratio of \rho . The notion of a bi-factor approximation algorithm may vary across problems. For the MD-SDVRP, we define a bi-factor (\rho,\gamma) -approximation algorithm as a polynomial-time algorithm that computes a solution whose cost is at most \rho times the optimal value (under the original capacity constraint), while allowing each vehicle to exceed its capacity Q , but with the total load on each vehicle bounded by \gamma\cdot Q , where \gamma\geq 1 . In the same manner, with respect to some parameter k , one can define XP/FPT bi-factor approximation algorithms. 1.1 Related Work In this subsection, we review the existing approximation algorithms for the MD-SDVRP and its related problems. 1.1.1 The VRP and the SDVRP First, we consider the VRP and the SDVRP, where the VRP can be viewed as a special case of the SDVRP in which the depot has an unlimited number of vehicles. For the case Q=\infty , by the triangle inequality, the VRP is equivalent to the Traveling Salesman Problem (TSP). For the TSP, Christofides Christofides 2022 proposed a 1.5 -approximation algorithm, and the ratio has been improved to less than 1.5-10^{-36} in Karlin et al. 2023 . In the following, we use \alpha to denote the current best approximation ratio for the TSP. For the case Q\neq\infty , Haimovich and Kan Haimovich and Kan 1985 proposed an (\alpha+1) -approximation algorithm for the splittable VRP, and Altinkemer and Gavish Altinkemer and Gavish 1987 proposed an (\alpha+2) -approximation algorithm for the unsplittable VRP. Recently, Blauth et al. Blauth et al. 2023 improved the ratio to \alpha+1-\varepsilon_{\alpha} for the splittable VRP, and Friggstad et al. Friggstad et al. 2022 improved the ratio to \alpha+1+\ln 2-\varepsilon_{\alpha} for the unsplittable VRP, where \varepsilon_{\alpha} is slightly greater than \frac{1}{3000} if \alpha=1.5 . For the SDVRP, to our knowledge, the only existing result is a 4-approximation algorithm, which can be trivially derived from the algorithm for the MD-SDVRP Lai et al. 2023 . 1.1.2 The MD-VRP and the MD-SDVRP For the case Q=\infty , by the triangle inequality, the MD-VRP is equivalent to the Multiple-Depot TSP (MD-TSP). For the MD-TSP, Rathinam et al. Rathinam et al. 2007 proposed a 2-approximation algorithm, and Xu et al. Xu et al. 2011 improved the ratio to 2-1/k . Moreover, with respect to the parameter k , Xu and Rodrigues Xu and Rodrigues 2015 obtained an XP 1.5 -approximation algorithm with running time \mathcal{O}(|V|^{k+2}|E|^{k-1}) . Traub et al. Traub et al. 2022 obtained an XP (\alpha+\varepsilon) -approximation algorithm with running time |V|^{\mathcal{O}(k/\varepsilon)} for any constant \varepsilon>0 . Deppert et al. Deppert et al. 2023 obtained a randomized FPT (1.5+\varepsilon) -approximation algorithm with running time (1/\varepsilon)^{\mathcal{O}(k\log k)}\cdot\mathcal{O}(|V|^{3}) . For the case Q\neq\infty , Li and Simchi-Levi Li and Simchi-Levi 1990 proposed a (2\alpha+1) -approximation algorithm for the splittable MD-VRP, and Harks et al. Harks et al. 2013 proposed a 4-approximation algorithm for the unsplittable MD-VRP. Zhao and Xiao Zhao and Xiao 2025b improved the ratio to 4-\frac{1}{1500} for the splittable MD-VRP and to 4-\frac{1}{50000} for the unsplittable MD-VRP. Very recently, Friggstad and Mömke Friggstad and Mömke 2025 further improved the

Read the complete text