For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: Steiner Cycle Problem (SCP), Generalized Traveling Salesman Problem (GTSP), Capacitated Vehicle Routing Problem with Unsplittable Client Demands (CVRP-UCD), and Prize Collecting Traveling Salesman Problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate statements of Asymmetric Traveling Salesman Problem (ATSP) and on the (22 + ε)-approximate algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.
Keywords: Asymmetric Traveling Salesman Problem, constant-factor approximation algorithm, polynomial-time reduction, Steiner Cycle Problem, Generalized Traveling Salesman Problem, Prize Collecting Traveling Salesman Problem, Vehicle Routing Problem
Received May 12, 2022
Revised June 14, 2022
Accepted June 20, 2022
Funding Agency: This work was supported by the Russian Science Foundation (project no. 22-21-00672).
Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: mkhachay@imm.uran.ru
Ekaterina Dmitrievna Neznakhina, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: eneznakhina@yandex.ru
Kseniya Valer’evna Ryzhenko, doctoral student, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: kseniarizhenko@gmail.com
REFERENCES
1. Gutin G., Punnen A.P. The traveling salesman problem and its variations. New York, NY: Springer, 2007, 830 p. doi: 10.1007/b101971
2. Toth P., Vigo D. Vehicle routing: problems, methods, and applications. Philadelphia: SIAM, 2014, 463 p. ISBN: 1611973589 .
3. Mor A., Speranza M.G. Vehicle routing problems over time: a survey. J. Oper. Res., 4OR-Q, 2020, vol. 18, no. 2, pp. 129–149. doi: 10.1007/s10288-020-00433-2
4. Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Internat. J. Product. Res., 2018, vol. 56, no. 14, pp. 4819–4830. doi: 10.1080/00207543.2017.1421784
5. Chung S.H., Sah B., Lee J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Comput. Oper. Res., 2020, vol. 123, art. no. 105004. doi: 10.1016/j.cor.2020.105004
6. Dantzig G., Fulkerson R., Johnson S. Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. America, 1954, vol. 2, no. 4. doi: 10.1287/opre.2.4.393
7. Dantzig G., Ramser J.H. The truck dispatching problem. Manag. Sci., 1959, vol. 6, no. 1, pp. 80–91. doi: 10.1287/MNSC.6.1.80
8. Chentsov A., Korotayeva L.N. The dynamic programming method in the generalized traveling salesman problem. Math. Comp. Modelling, 1997, vol. 25, no. 1, pp. 93–105. doi: 10.1016/S0895-7177(96)00187-2
9. Chentsov A.G., Khachai M.Yu., Khachai D.M. An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Inst. Math., 2016, vol. 295, no. 1, pp. 38–46. doi: 10.1134/S0081543816090054
10. Archetti C., Bianchessi N., Speranza M. Optimal solutions for routing problems with profits. Discr. Appl. Math., 2013, vol. 161, no. 4-5, pp. 547–557. doi: 10.1016/j.dam.2011.12.021
11. Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing. Math. Program. Comp., 2017, vol. 9, no. 1, pp. 61–100. doi: 10.1007/s12532-016-0108-8
12. Pessoa A., Sadykov R., Uchoa E., Vanderbeck F. A generic exact solver for vehicle routing and related problems. Math. Program., 2019, vol. 183, pp. 483–523. doi: 10.1007/978-3-030-17953-3_27
13. Avdoshin S.M., Beresneva E. Local search metaheuristics for capacitated vehicle routing problem: a comparative study. Proc. ISP RAS, 2019, vol. 31, no. 4, pp. 121–138. doi: 10.15514/ISPRAS-2019-31(4)-8
14. Qiu M., Fu Z., Eglese R., Tang Q. A Tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups. Comput. Oper. Res., 2018, vol. 100, pp. 102–116. doi: 10.1016/j.cor.2018.07.021
15. Frifita S., Masmoudi M. VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties. Int. Trans. Oper. Res., 2020, vol. 27, no. 1, pp. 291–313. doi: 10.1111/itor.12604
16. Smith S., Imeson F. GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Comput. Oper. Res., 2017, vol. 87, pp. 1–19. doi: 10.1016/j.cor.2017.05.010
17. Nazari M., Oroojlooy A., Takac M., Snyder L.V. Reinforcement learning for solving the vehicle routing problem. In: Proc. of the 32nd International Conf. on Neural Information Processing Systems (NIPS’18), 2018, pp. 9861–9871. doi: 10.5555/3327546.3327651
18. Verbeeck C., Vansteenwegen P., Aghezzaf E.-H. The time-dependent orienteering problem with time windows: a fast ant colony system. Ann. Oper. Research, 2017, vol. 254, pp. 481–505. doi: 10.1007/s10479-017-2409-3
19. Zhukova G.N., Ul’yanov M.V., Fomichev M.I. A hybrid exact algorithm for the asymmetric traveling salesman problem: construction and a statistical study of computational efficiency. Autom. Remote Control, 2019, vol. 80, no. 11, pp. 2054–2067. doi: 10.1134/S0005117919110092
20. Papadimitriou C. The Euclidean travelling salesman problem is NP-complete. Theor. Comput. Sci., 1977, vol. 4, no. 3, pp. 237–244. doi: 10.1016/0304-3975(77)90012-3
21. Khachay M., Neznakhina K. Towards tractability of the Euclidean generalized traveling salesman problem in grid clusters defined by a grid of bounded height. In: Optimization Problems and Their Applications. Communications in Computer and Information Science, vol. 871. Springer, 2018, pp. 68–77. doi: 10.1007/978-3-319-93800-4_6
22. Sahni S., Gonzales T. P-complete approximation problems. J. ACM, vol. 23, no. 3, pp. 555–565. doi: 10.1145/321958.321975
23. 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. In: STOC ’97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. NY: ACM, 1997, pp. 275–283. doi: 10.1145/258533.258602
24. Bartal Y., Gottlieb L.A., Krauthgamer R. The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 2012, vol. 45, pp. 1563–1581. doi: 10.1145/2213977.2214038
25. Khachay M., Ogorodnikov Yu., Khachay D. Efficient approximation of the metric CVRP in spaces of fixed doubling dimension. J. Glob. Optim, 2021, vol. 80, no. 3, pp. 679–710. doi: 10.1007/s10898-020-00990-0
26. Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum, 2022, vol. 3, no. 1, art. no. 20, 4 p. doi: 10.1007/s43069-021-00101-z
27. Serdyukov A.I. Some extremal bypasses in graphs. Upravliaemie Systemy, 1978, no. 17, pp. 76–79 (in Russian).
28. Asadpour A., Goemans M., Madry A., Gharan S.O., Saberi A. An O(log n∕log log n)-approximation algorithm for the asymmetric traveling salesman problem. Oper. Res., 2017, vol. 65, no. 4, pp. 1043–1061. doi: 10.1287/opre.2017.1603
29. Svensson O., Tarnawski J., Végh L. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In: STOC 2018: Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 204–213. doi: 10.1145/3188745.3188824
30. Traub V., Vygen J. An improved approximation algorithm for ATSP. In: STOC 2020: Proc. of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 1–13. doi: 10.1145/3357713.3384233
31. van Bevern R., Komusiewicz C., Sorge M. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 2017, vol. 70, no. 3, pp. 262–278. doi: 10.1002/net.21742
32. Wahlström M. Abusing the Tutte matrix: An algebraic instance compression for the K-set-cycle problem. In: STACS, 2013, pp. 341–352. doi: 10.4230/LIPIcs.STACS.2013.341
33. Steinová M. Approximability of the minimum Steiner cycle problem. Comput. Inform., 2010, vol. 29, no. 6+, pp. 1349–1357.
34. Das A., Mathieu C. A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 2015, vol. 73, no. 1, pp. 115–142. doi: 10.1007/s00453-014-9906-4
35. Adamaszek A., Czumaj A., Lingas A. PTAS for k-tour cover problem on the plane for moderately large values of k. Int. J. Found. Comput. Sci., 2010, vol. 21, no. 6, pp. 893–904. doi: 10.1142/S0129054110007623
36. Khachay M.Yu., Ogorodnikov Yu.Yu. Haimovich – Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension. Trudy Inst. Mat. i Mekh. UrO RAN, 2019, vol. 25, no. 4, pp. 235–248 (in Russian). doi: 10.21538/0134-4889-2019-25-4-235-248
37. Hall P. On representatives of subsets. J. London Math. Soc., 1935, vol. 10, no. 1, pp. 26–30. doi: 10.1112/jlms/s1-10.37.26
38. Balas E. The prize collecting traveling salesman problem. Networks, 1989, vol. 19, no. 6, pp. 621–636. doi: 10.1002/net.3230190602
39. Paul A., Freund D., Ferber A., Shmoys D., Williamson D. Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res., 2019, vol. 45, no. 2, pp. 576–590. doi: 10.1287/moor.2019.1002
40. Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D. A note on the prize collecting traveling salesman problem. Math. Program., 1993, vol. 59, no. 1, pp. 413–420. doi: 10.1007/BF01581256
41. Khachay M., Ukolov S., Petunin A. Problem-specific branch-and-bound algorithms for the precedence constrained generalized traveling salesman problem. In: Optimization and Applications - 12th International Conference, OPTIMA 2021, Proceedings, 2021, pp. 136–148. doi: 10.1007/978-3-030-91059-4_10
42. Bhattacharya B., Ćustić A., Rafiey A., Rafiey A., Sokol V. Approximation algorithms for generalized MST and TSP in grid clusters. In: Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol. 9486. Springer, 2015, pp. 110–125. doi: 10.1007/978-3-319-26626-8_9
43. Khachay M., Neznakhina K. Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters. Ann. Math. Artif. Intell., 2020, vol. 88, no. 1, pp. 53–69. doi: 10.1007/s10472-019-09626-w
Cite this article as: M.Yu. Khachai, E.D. Neznakhina, K.V. Ryzhenko. Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to Asymmetric Traveling Salesman Problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 3, pp. 241–258; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2022, Vol. 319, Suppl. 1, pp. S140–S155.
