УДК 519.16 + 519.85
MSC: 68W25
DOI: 10.21538/0134-4889-2022-28-3-241-258
Исследование выполнено за счет гранта Российского научного фонда № 22-21-00672, https://rscf.ru/project/22-21-00672/ .
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2022, Vol. 319, Suppl. 1, pp. S140–S155. (Abstract)
Посвящается славному 75-летнему юбилею выдающегося российского ученого, чл.-корр. РАН А.Г.Ченцова с искренними поздравлениями и благодарностью.
В статье впервые обосновываются алгоритмы с постоянными гарантированными оценками точности для серии асимметричных маршрутных задач комбинаторной оптимизации: задачи о штейнеровском цикле (SCP), обобщенной задачи коммивояжера (GTSP), задачи маршрутизации транспорта с неделимым потребительским спросом (CVRP-UCD) и задачи коммивояжера с призами (PCTSP). Объединяет представленные результаты то, что все они опираются на полиномиальную сводимость, сохраняющую стоимость (cost-preserving reduction), исследуемых задач к подходящим постановкам асимметричной задачи коммивояжера (ATSP) и (22 + ε)-приближенный алгоритм для этой классической задачи, предложенный О. Свенссоном и В. Трауб в 2019 г.
Ключевые слова: асимметричная задача коммивояжера, алгоритм с постоянной оценкой точности, полиномиальная сводимость, задача о штейнеровском цикле минимального веса, обобщенная задача коммивояжера, задача коммивояжера с призами, задача маршрутизации транспорта
СПИСОК ЛИТЕРАТУРЫ
1. Gutin G., Punnen A. P. The Traveling Salesman Problem and its variations. Boston; 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.
3. Mor A., Speranza M. G. Vehicle routing problems over time: a survey // J. Oper. Res., 4OR-Q. 2020. Vol. 18, no. 2. P. 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. P. 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. B., Fulkerson D. R., Johnson S. M. 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. B., Ramser J. H. The truck dispatching problem // Manag. Sci. 1959. Vol. 6, no. 1. P. 80–91. doi: 10.1287/MNSC.6.1.80
8. Chentsov A. G., Korotaeva L. N. The dynamic programming method in the generalized traveling salesman problem // Math. Comp. Modelling. 1997. Vol. 25, no. 1. P. 93–105. doi: 10.1016/S0895-7177(96)00187-2
9. Chentsov A. G., Khachay M. Yu., Khachay D. M. An exact algorithm with linear complexity for a problem of visiting megalopolises // Proc. Steklov Inst. Math. 2016. Vol. 295, no. 1. P. 38–46. doi: 10.1134/S0081543816090054
10. Archetti C., Bianchessi N., Speranza M. Optimal solutions for routing problems with profits // Discrete Appl. Math. 2013. Vol. 161, no. 4-5. P. 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. P. 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. 2020. Vol. 183. P. 483–523. doi: 10.1007/978-3-030-17953-3_27
13. Avdoshin S., Beresneva E. Local search metaheuristics for capacitated vehicle routing problem: a comparative study // Proc. ISP RAS. 2019. Vol. 31, no. 4. P. 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. P. 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 // International Transactions in Operational Research. 2020. Vol. 27, no. 1. P. 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. P. 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 // Proc. of the 32nd International Conf. on Neural Information Processing Systems (NIPS’18). 2018. P. 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. Res. 2017. Vol. 254. P. 481–505. doi: 10.1007/s10479-017-2409-3
19. Zhukova G. N., Ulyanov M. V., Fomichev M. I. A hybrid exact algorithm for the asymmetric Traveling Salesman Problem: Construction and a statistical study of computational efficiency // Automat. Remote Control. 2019. Vol. 80, no. 11. P. 2054–2067. doi: 10.1134/S0005117919110092
20. Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. Vol. 4, no. 3. P. 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 // Optimization Problems and Their Applications. 2018. Communications in Computer and Information Science. Vol. 871. P. 68–77. doi: 10.1007/978-3-319-93800-4_6
22. Sahni S., Gonzales T. P-complete approximation problems // JACM. 1976. Vol. 23, no. 3. P. 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 //Proc. of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC’97). NY: ACM, 1997. P. 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. 2016. Vol. 45. P. 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. P. 679–710. doi: 10.1007/s10898-020-00990-0
26. Christofides N. Worst-case analysis of a new heuristic for the Travelling Salesman Problem: Technical Report 388 / Graduate School of Industrial Administration, Carnegie-Mellon University. 1976. 5~p.
27. Сердюков А. И. О некоторых экстремальных обходах в графах // Управляемые системы. 1978. № 17. С. 76–79.
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. P. 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 // Proc. of the 50th Annual ACM Symposium on Theory of Computing (STOC). 2018. P. 204–213. doi: 10.1145/3188745.3188824
30. Traub V., Vygen J. An improved approximation algorithm for ATSP // Proc. of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). 2020. P. 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. P. 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 // STACS. 2013. P. 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+. P. 1349–1357.
34. Das A., Mathieu C. A quasipolynomial time approximation scheme for Euclidean Capacitated Vehicle Routing // Algorithmica. 2015. Vol. 73, no. 1. P. 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 // Internat. J. Foundations Comp. Sci. 2010. Vol. 21, no. 6. P. 893–904. doi: 10.1142/S0129054110007623
36. М. Ю. Хачай, Ю. Ю. Огородников. Аппроксимационная схема Хаймовича — Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 235–248. 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. P. 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. P. 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. P. 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. Progr. 1993. Vol. 59, no. 1. P. 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 // Optimization and Applications – 12th International Conference (OPTIMA 2021): Proc. 2021. P. 136–148. P. 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 // Combinatorial Optimization and Applications. 2015. Lecture Notes in Computer Science. Vol. 9486. P. 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. P. 53–69. doi: 10.1007/s10472-019-09626-w
Поступила 12.05.2022
После доработки 14.06.2022
Принята к публикации 20.06.2022
Хачай Михаил Юрьевич
чл.-корр. РАН
д-р физ.-мат. наук
зав. отделом
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: mkhachay@imm.uran.ru
Незнахина Екатерина Дмитриевна
канд. физ.-мат. наук
старший науч. сотрудник
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет им. Б.Н. Ельцина
г. Екатеринбург
e-mail: eneznakhina@yandex.ru
Рыженко Ксения Валерьевна
аспирант, математик
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: kseniarizhenko@gmail.com
Ссылка на статью: М.Ю. Хачай, Е.Д. Незнахина, К.В. Рыженко. Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 3. С. 241-258
English
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
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
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.
[References -> on the "English" button bottom right]
