Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem

摘要

We consider the classic setting of Capacitated Vehicle Routing Problem (CVRP): single product, single depot, demands of all customers are identical. It is known that this problem remains strongly NP-hard even being formulated in Euclidean spaces of fixed dimension. Although the problem is intractable, it can be approximated well in such a special case. For instance, in the Euclidean plane, the problem (and it's several modifications) have polynomial time approximation schemes (PTAS). We propose polynomial time approximation scheme for the case of R~3.