A quasi-polynomial time approximation scheme for Euclidean CVRPTW

The capacitated vehicle routing problem with time windows (CVRPTW) is a variant of the classical vehicle routing problem. In a category of CVRPTW, each customer has same unit-demand and must be served within a time window from a finite set of consecutive time windows. This paper gives a quasi-polynomial time approximation scheme (Q-PTAS) for this category of CVRPTW under the Euclidean setting. With a reasonable vehicle speed requirement, our algorithm could generate a set of routes of the length of (1 + O(ε))OPT on expectation.