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$.
Keywords: capacitated vehicle routing problem, time windows, efficient polynomial time approximation scheme
The paper was received by the Editorial Office on May 29, 2018.
Funding Agency: The first author is supported by the Russian Science Foundation (project no. 14-11-00109).
Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia; Omsk State Technical University, Omsk, 644050 Russia, e-mail: mkhachay@imm.uran.ru
Yurii Yur’evich Ogorodnikov, Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia, Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: yogorodnikov@gmail.com
REFERENCES
1. Andrews G. E., Eriksson K. Integer partitions. Cambridge: Cambridge University Press, 2nd edn., 2004, 152 p. ISBN-10: 0521600901 .
2. Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 1998, vol. 45, no. 5, pp. 753–782. doi: 10.1145/290179.290180 .
3. Asano T., Katoh N., Tamaki H., Tokuyama T. 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). N Y: ACM, 1997. P. 275–283. doi: 10.1145/258533.258602 .
4. Chrisofides N. Worst-case analysis of a new heuristic for the Traveling Salesman Problem. Management Sciences Research Report 388, US, Pennsylvania: Carnegie-Mellon University, 1976, 11 p.
5. Dantzig G., Ramser J. The truck dispatching problem. Management science, 1959, vol. 6, no. 1, pp. 80–91.
6. Das A., Mathieu C. A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 2015, vol. 73, no. 1, pp. 115–142. doi: 10.1007/s00453-014-9906-4 .
7. Haimovich M., Rinnooy Kan A.H.G. Bounds and heuristics for capacitated routing problems. Math. Operations Research, 1985, vol. 10, no. 4, pp. 527–542. doi: 10.1287/moor.10.4.527 .
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 Internat. Conf. (AIST-2018), Cham: Springer International Publishing, 2018, Ser. Lecture Notes in Computer Science, vol. 11179, pp. 1–11.
9. Khachay M., Dubinin R. PTAS for the Euclidean Capacitated Vehicle Routing Problem in $R^d$. Proc. DOOR 2016, Cham: Springer International Publishing, 2016, Ser. Lecture Notes in Computer Science; vol. 9869, pp. 193–205. doi: 10.1007/978-3-319-44914-2_16 .
10. Khachay M., Zaytseva H. Polynomial time approximation scheme for single-depot Euclidean Capacitated Vehicle Routing Problem. Proc. COCOA 2015, Cham: Springer International Publishing, 2015, Ser. Lecture Notes in Computer Science; vol. 9486, pp. 178–190. doi: 10.1007/978-3-319-26626-8_14 .
11. Kumar S., Panneerselvam R. A survey on the vehicle routing problem and its variants. Intelligent Information Management, 2012, vol. 4, no. 3, pp. 66–74. doi: 10.4236/iim.2012.43010 .
12. Serdyukov A. On some extremal routes in graphs. Upravliaemye systemy, 1978, iss. 17, pp. 76–79 (in Russian).
13. Song L., Huang H. The Euclidean Vehicle Routing Problem with multiple depots and time windows. Proc. COCOA 2017, Part II, Cham: Springer International Publishing, 2017, Ser. Lecture Notes in Computer Science, vol. 10627, pp. 449–456. doi: 10.1007/978-3-319-71147-8_31 .
14. Song L., Huang H., Du H. Approximation schemes for euclidean vehicle routing problems with time windows. J. Combinatorial Optim., 2016, vol. 32, no. 4, pp. 1217–1231. doi: 10.1007/s10878-015-9931-5 .
15. Toth P., Vigo D. Vehicle Routing: problems, methods and applications, 2 edn., 2014, MOS-Siam Series on Optimization, SIAM, 480 p. ISBN: 978-1-611973-58-7 .
