An $n^{O(\log \log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane

René Sitters

We present a quasi polynomial time approximation scheme (Q-PTAS) for the capacitated vehicle routing problem (CVRP) on $n$ points in the Euclidean plane for arbitrary capacity $c$.…