Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912801904132096 |
|---|---|
| author | Zhao, Jingyang Su, Yonghang Xiao, Mingyu |
| author_facet | Zhao, Jingyang Su, Yonghang Xiao, Mingyu |
| contents | 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\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01841 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem Zhao, Jingyang Su, Yonghang Xiao, Mingyu Data Structures and Algorithms 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\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. |
| title | Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.01841 |