М.Ю. Хачай, Е.Д. Незнахина, К.В. Рыженко. Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера ... С. 241-258

УДК 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]