Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912632469979136 |
|---|---|
| author | Friggstad, Zachary Mömke, Tobias |
| author_facet | Friggstad, Zachary Mömke, Tobias |
| contents | In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations $C$ and a set of depots $R$ located in a metric space with costs $c(i,j)$ between $u,v \in C \cup R$. Additionally, we are given a capacity bound $k$. The goal is to find a collection of tours of minimum total cost such that each tour starts and ends at some depot $r \in R$ and includes at most $k$ clients and such that each client lies on at least one tour. Our main result is a $3.9365$-approximation based on rounding a new LP relaxation for CVRP-MD. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05321 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding Friggstad, Zachary Mömke, Tobias Data Structures and Algorithms In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations $C$ and a set of depots $R$ located in a metric space with costs $c(i,j)$ between $u,v \in C \cup R$. Additionally, we are given a capacity bound $k$. The goal is to find a collection of tours of minimum total cost such that each tour starts and ends at some depot $r \in R$ and includes at most $k$ clients and such that each client lies on at least one tour. Our main result is a $3.9365$-approximation based on rounding a new LP relaxation for CVRP-MD. |
| title | Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.05321 |