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.

Bibliographie

[1] Andrews G. E., Eriksson K., Integer partitions, 2nd edn., Cambridge University Press, Cambridge, 2004, 152 pp.

[2] Arora S., “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, J. ACM, 45:5 (1998), 753–782 | DOI

[3] T. Asano, N. Katoh, H. Tamaki, T. Tokuyama, “Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k”, Proc. of the twenty-ninth annual ACM symposium on theory of computing (STOC '97), ACM, N Y, 1997, 275–283 | DOI

[4] Chrisofides N., “Worst-case analysis of a new heuristic for the Traveling Salesman Problem”, Management Sciences Research Report 388, Carnegie-Mellon University, US, Pennsylvania, 1976, 11 pp.

[5] Dantzig G., Ramser J., “The truck dispatching problem”, Management science, 6:1 (1959), 80–91

[6] Das A., Mathieu C., “A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing”, Algorithmica, 73:1 (2015), 115–142 | DOI

[7] Haimovich M., Rinnooy Kan A.H.G., “Bounds and heuristics for capacitated routing problems”, Math. Operations Research, 10:4 (1985), 527–542 | DOI

[8] Khachay M., Ogorodnikov Y., “Efficient PTAS for the Euclidean CVRP with time windows”, Analysis of Images, Social Networks and Texts, Revised Selected Papers 7th International Conf. (AIST-2018), Lecture Notes in Computer Science, 11179, Springer International Publishing, Cham, 2018, 1–11

[9] Khachay M., Dubinin R., “PTAS for the Euclidean Capacitated Vehicle Routing Problem in Rd”, Proc. DOOR 2016, Lecture Notes in Computer Science, 9869, Springer International Publishing, Cham, 2016, 193–205 | DOI

[10] Khachay M., Zaytseva H., “Polynomial time approximation scheme for single-depot Euclidean Capacitated Vehicle Routing Problem”, Proc. COCOA 2015, Lecture Notes in Computer Science, 9486, Springer International Publishing, Cham, 2015, 178–190 | DOI

[11] Kumar S., Panneerselvam R., “A survey on the vehicle routing problem and its variants”, Intelligent Information Management, 4:3 (2012), 66–74 | DOI

[12] Serdyukov A.I., “O nekotorykh optimalnykh obkhodakh v grafakh”, Upravlyaemye sistemy, 1978, no. 17, 76–79

[13] Song L., Huang H., “The Euclidean Vehicle Routing Problem with multiple depots and time windows”, Proc. COCOA 2017, Part II, Lecture Notes in Computer Science, 10627, Springer International Publishing, Cham, 2017, 449–456 | DOI

[14] Song L., Huang H., Du H., “Approximation schemes for euclidean vehicle routing problems with time windows”, J. Combinatorial Optim., 32:4 (2016), 1217–1231 | DOI

[15] Toth P., Vigo D., Vehicle Routing: problems, methods and applications, MOS-Siam Series on Optimization, SIAM, 2 edn, eds. eds. P. Toth, D. Vigo, 2014, 480 pp.