Dynamic programming in the routing problem: decomposition variant
- Authors: Chentsov A.G.1,2, Chentsov P.A.1,2
-
Affiliations:
- N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences
- Ural Federal University named after the first President of Russia B. N. Yeltsin
- Issue: Vol 27, No 137 (2022)
- Pages: 95-124
- Section: Articles
- URL: https://journal-vniispk.ru/2686-9667/article/view/295006
- DOI: https://doi.org/10.20310/2686-9667-2022-27-137-95-124
- ID: 295006
Cite item
Full Text
Abstract
Keywords
About the authors
Aleksandr G. Chentsov
N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences; Ural Federal University named after the first President of Russia B. N. Yeltsin
Email: chentsov@imm.uran.ru
Doctor of Physics and Mathematics, Corresponding Member of the Russian Academy of Sciences, Chief Researcher; Professor 16 S. Kovalevskaya St., Yekaterinburg 620108, Russian Federation; 19 Mira St., Yekaterinburg 620002, Russian Federation
Pavel A. Chentsov
N. N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences; Ural Federal University named after the first President of Russia B. N. Yeltsin
Email: chentsov.p@mail.ru
Candidate of Physics and Mathematics, Senior Researcher; Senior Researcher 16 S. Kovalevskaya St., Yekaterinburg 620108, Russian Federation; 19 Mira St., Yekaterinburg 620002, Russian Federation
References
- G. Gutin, A.P. Punnen, The Traveling Salesman Problem and its Variations, Springer, Berlin, 2002, 850 pp.
- W.J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University, United States, 2012, 228 pp.
- Э.Х. Гимади, М.Ю. Хачай, Экстремальные задачи на множествах перестановок, УМЦ УПИ, Екатеринбург, 2016, 216 с.
- M. Kubo, H. Kasugai, “The precedence constrained traveling salesman problem”, Journal of the Operations Research Society of Japan, 34:2 (1991), 152-172.
- Y. Salii, “Revisisting dynamic programming for precedence-constrained Traveling Salesman Problem and its time-dependent generalization”, European Journal of Operational Research, 272:1 (2019), 32-42.
- E. Balas, “New classes of efficiently solvable generalized Taveling Salesman Problems”, Annals of Operations Research, 86 (1999), 529-558.
- J.A. Chisman, “The clustered traveling salesman problem”, Computers and Operation Research, 2:2 (1975), 115-119.
- М.Ю. Хачай, Е.Д. Незнахина, “Приближенные схемы для обобщенной задачи коммивояжера”, Тр. ИММ УрО РАН, 22, 2016, 283-292.
- F.C.J. Lokin, “Procedures for traveling salesman problems with additional constraints”, European of Journal Operation al. Research, 3:2 (1979), 135-141.
- С.С. Лебедев, “О декомпозиции некоторых прикладных задач дискретной оптимизации”, Экономика и математические методы, 44:2 (2008), 121-125.
- В.И. Цурков, Декомпозиция в задачах большой размерности, Наука, М., 1981, 350 с.
- А.А. Первозванский, В.Г. Гайцгори, Декомпозиция, агрегирование и приближенная оптимизация, Наука, М., 1975, 344 с.
- А.Г. Ченцов, Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, Ижевский институт компьютерных исследований, Ижевск, 2008, 238 с.
- Р. Беллман, “Применение динамического программирования к задаче о коммивояжере”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 219-222.
- М. Хелд, Р.М. Карп, “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 202-218.
- А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов, “Экстремальная задача маршрутизации с внутренними потерями”, Тр. ИММ УрО РАН, 14, 2008, 183-201.
- A.G. Chentsov, P.A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 54 (2019), 102-121.
- А.Г. Ченцов, П.А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автоматика и телемеханика, 2016, №11, 96-117.
- А.Г. Ченцов, “К вопросу о маршрутизации комплексов работ”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, №1, 59-82.
- К. Куратовский, А. Мостовский, Теория множеств, Мир, М., 1970, 416 с.
- Ж. Дьедонне, Основы современного анализа, Мир, М., 1964, 430 с.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, Алгоритмы: построение и анализ, МЦНМО, М., 2000, 955 с.
- Дж. Варга, Оптимальное управление дифференциальными и функциональными уравнениями, Наука, М., 1977, 624 с.
- А.А. Петунин, А.Г. Ченцов, П.А. Ченцов, Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы, Издательство Уральского университета, Екатеринбург, 2020, 247 с.
Supplementary files
