Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding

Abstract

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.