APPROXIMATION ALGORITHMS WITH CONSTANT FACTORS FOR A SERIES OF ASYMMETRIC ROUTING PROBLEMS

E. D. Neznakhina; Незнахина Е. Д.; Yu. Yu. Ogorodnikov; Огородников Ю. Ю.; K. V. Rizhenko; Рыженко К. В.; M. Yu. Khachay; Хачай М. Ю.

doi:10.31857/S268695432360218X

Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации

Авторы: Незнахина Е.Д.¹^,2, Огородников Ю.Ю.¹^,2, Рыженко К.В.¹, Хачай М.Ю.¹
Учреждения:
1. Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
2. Уральский федеральный университет им. Б.Н. Ельцина
Выпуск: Том 514, № 1 (2023)
Страницы: 89-97
Раздел: МАТЕМАТИКА
URL: https://journals.rcsi.science/2686-9543/article/view/247096
DOI: https://doi.org/10.31857/S268695432360218X
EDN: https://elibrary.ru/CYSMDZ
ID: 247096

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона-Трауб.

Ключевые слова

асимметричная задача коммивояжера, приближенные алгоритмы, константная оценка точности, задача о штейнеровском цикле минимального веса, задача маршрутизации транспорта, задача о покрытии графа ограниченным числом циклов

Список литературы

Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Springer US, Boston, MA, 2007.
Toth P., Vigo D. Vehicle Routing. Problems, Methods, and Applications. SIAM, Philadelphia, 2014.
Desrosiers J. and Lübbecke M.E. Branch-Price-and-Cut Algorithms. In Wiley Encyclopedia of Operations Research and Management Science (eds. J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh and J.C. Smith). Wiley and Sons, NJ. 2015.
Gendreau M., Potvin J.-Y. Handbook of Metaheuristics. Springer. 2019.
Vazirani V. Approximation algorithms. Springer. Berlin. 2003.
Williamson D.P., Shmoys D.B. The Design of Approximation Algorithms. New York, USA, 2011.
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.
Сердюков А.И. О некоторых экстремальных обходах в графах // Управляемые системы. 1978. Т. 17. С. 76–79.
Haimovich M., Rinnooy Kan A.H.G. Bounds and Heuristics for Capacitated Routing Problems // Mathematics of Operations Research. 1985. V. 10. № 4. P. 527–542.
Asadpour A., Goemans M.X., Mądry A., Gharan S.O., Saberi A. An -approximation algorithm for the asymmetric traveling salesman problem // Operations Research. 2017. V. 65. № 4. P. 1043–1061.
Svensson O., Tarnawski J., Vegh L.A. A constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem // J. ACM. 2020. V. 67. № 6. P. 1–53.
Traub V., Vygen J. An improved approximation algorithm for the Asymmetric Traveling Salesman Problem // SIAM Journal on Computing. 2022. V. 51. № 1. P. 139–173.
Khachay M., Neznakhina E., Ryzhenko K. Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the Asymmetric Traveling Salesman Problem // Proc. Steklov Inst. Math. 2022. V. 319. № 1. P. S140–S155.
Rizhenko K., Neznakhina K., Khachay M. Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem // Ural Math. Journal. 2023. V. 9. № 1. P. 135–146.
Хачай М.Ю., Незнахина Е.Д., Рыженко К.В. Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов // Труды Института математики и механики УрО РАН. 2023. Т. 29. № 3. С. 261–273.
van Bevern R., Hartung S., Nichterlein A., Sorge M. Constant-factor approximations for capacitated arc routing without triangle inequality // Operations Research Letters. 2014. V. 42. № 4. P. 290–292.
Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. V. 4. P. 237–244.
Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D. A note on the Prize-Collecting Traveling Salesman Problem // Math. Program. 1993. V. 59. P. 413–420.
Khachay M., Neznakhina K. Approximability of the Minimum-Weight -Size Cycle Cover Problem // J. of Global Optimization. 2016. V. 66. № 1. P. 65–82.
VRP-REP: the vehicle routing problem repository. http://www.vrp-rep.org/ Дата обращения 12.09.23.