Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
By: Zachary Friggstad, Tobias Mömke
Potential Business Impact:
Finds cheapest delivery routes from many starting points.
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.
Similar Papers
Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
Data Structures and Algorithms
Finds cheapest way to deliver goods.
Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
Data Structures and Algorithms
Makes delivery trucks save money on trips.
Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
Data Structures and Algorithms
Finds best delivery routes when customer needs are unknown.