Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows

M. Yu. Khachay ; Yu. Yu. Ogorodnikov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 233-246

Résumé

The capacitated vehicle routing problem with time windows (CVRPTW) is a well-known NP-hard combinatorial optimization problem. We present a further development of the approach first proposed by M. Haimovich and A.H.G. Rinnooy Kan and propose an algorithm that finds for arbitrary $\varepsilon>0$ a $(1+\varepsilon)$-approximate solution for Eucidean CVRPTW in $\mathrm {TIME}(\mathrm {TSP},\rho,n)+O(n^2)+O\bigl( e^{O(q\,(\frac{q}{\varepsilon})^3(p\rho)^2\log (p\rho))}\bigr)$, where $q$ is an upper bound for the capacities of the vehicles, $p$ is the number of time windows, and $\mathrm {TIME}(\mathrm {TSP},\rho,n)$ is the complexity of finding a $\rho$-approximation solution of an auxiliary instance of Euclidean TSP. Thus, the algorithm is a polynomial time approximation scheme for CVRPTW with $p^3q^4=O(\log n)$ and an efficient polynomial time approximation scheme (EPTAS) for arbitrary fixed values of $p$ and $q$.

Détail

Keywords: capacitated vehicle routing problem, time windows
Mots-clés : efficient polynomial time approximation scheme.