Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2308.14131 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909172177567744 |
|---|---|
| author | Zhao, Jingyang Xiao, Mingyu |
| author_facet | Zhao, Jingyang Xiao, Mingyu |
| contents | The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (CVRP), where we need to route capacitated vehicles located in multiple depots to serve customers' demand such that each vehicle must return to the depot it starts, and the total traveling distance is minimized. There are three variants of MCVRP according to the property of the demand: unit-demand, splittable and unsplittable. We study approximation algorithms for $k$-MCVRP in metric graphs, where $k$ is the capacity of each vehicle. The best-known approximation ratios for the three versions are $4-Θ(1/k)$, $4-Θ(1/k)$, and $4$, respectively. We give a $(4-1/1500)$-approximation algorithm for unit-demand and splittable $k$-MCVRP, and a $(4-1/50000)$-approximation algorithm for unsplittable $k$-MCVRP. When $k$ is a fixed integer, we give a $(3+\ln2-\max\{Θ(1/\sqrt{k}),1/9000\})$-approximation algorithm for the splittable and unit-demand cases, and a $(3+\ln2-Θ(1/\sqrt{k}))$-approximation algorithm for the unsplittable case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14131 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees Zhao, Jingyang Xiao, Mingyu Data Structures and Algorithms The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (CVRP), where we need to route capacitated vehicles located in multiple depots to serve customers' demand such that each vehicle must return to the depot it starts, and the total traveling distance is minimized. There are three variants of MCVRP according to the property of the demand: unit-demand, splittable and unsplittable. We study approximation algorithms for $k$-MCVRP in metric graphs, where $k$ is the capacity of each vehicle. The best-known approximation ratios for the three versions are $4-Θ(1/k)$, $4-Θ(1/k)$, and $4$, respectively. We give a $(4-1/1500)$-approximation algorithm for unit-demand and splittable $k$-MCVRP, and a $(4-1/50000)$-approximation algorithm for unsplittable $k$-MCVRP. When $k$ is a fixed integer, we give a $(3+\ln2-\max\{Θ(1/\sqrt{k}),1/9000\})$-approximation algorithm for the splittable and unit-demand cases, and a $(3+\ln2-Θ(1/\sqrt{k}))$-approximation algorithm for the unsplittable case. |
| title | Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.14131 |