Аннотация:
Рассматриваются задачи маршрутизации перемещений с условиями предшествования и динамическими ограничениями, включающими зависимость от списка заданий (выполненных на момент перемещения или, напротив, еще не выполненных). Стоимости перемещений также могут зависеть от списка заданий. Объектами посещения являются мегаполисы (непустые конечные множества), что отвечает возможной многовариантности перемещений. В качестве основного метода исследования используется широко понимаемое динамическое программирование в реализации, не предусматривающей (при наличии условий предшествования) построения всего массива значений функции Беллмана.
Отдельно рассматриваются процедура построения “полного” решения, включая определение оптимальных маршрута и трассы (траектории), и процедура, обеспечивающая нахождение значения задачи (глобального экстремума), которое может использоваться при тестировании эвристических алгоритмов.
Для решения маршрутных задач большой размерности, осложненных ограничениями, типичными для листовой резки на станках с числовым программным управлением, построен эффективный эвристический алгоритм. Для задач умеренной размерности проведено сравнение достигаемых результатов с оптимальным, доставляемым динамическим программированием.
Работа выполнена при финансовой поддержке постановления № 211 Правительства Российской федерации (контракт № 02.A03.21.0006) и РФФИ (проект 16-01-00649).
Статья представлена к публикации членом редколлегии:А. А. Лазарев
Образец цитирования:
А. Г. Ченцов, П. А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автомат. и телемех., 2016, № 11, 96–117; Autom. Remote Control, 77:11 (2016), 1957–1974
А. Г. Ченцов, П. А. Ченцов, “Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции”, Автомат. и телемех., 2023, № 5, 133–164; A. G. Chentsov, P. A. Chentsov, “Two-stage dynamic programming in the routing problem with decomposition”, Autom. Remote Control, 84:5 (2023), 609–632
A. G. Chentsov, P. A. Chentsov, “Two-Stage Dynamic Programming in the Routing Problem with Decomposition”, Autom Remote Control, 84:5 (2023), 543
Alexandr G. Chentsov, Pavel A. Chentsov, Communications in Computer and Information Science, 1881, Mathematical Optimization Theory and Operations Research: Recent Trends, 2023, 218
А. Г. Ченцов, П. А. Ченцов, “Динамическое программирование в задаче маршрутизации: декомпозиционный вариант”, Вестник российских университетов. Математика, 27:137 (2022), 95–124
А. Г. Ченцов, П. А. Ченцов, “Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования”, Тр. ИММ УрО РАН, 28, № 2, 2022, 215–248
А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений”, Челяб. физ.-матем. журн., 7:2 (2022), 209–233
A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Some applications of optimization routing problems with additional constraints”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 32:2 (2022), 187–210
А. Г. Ченцов, А. А. Ченцов, “Об одной задаче маршрутизации, ориентированной на проблему демонтажа радиационно опасных объектов”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 15:3 (2022), 83–95
A.G. Chentsov, P.A. Chentsov, “To the application of two-stage dynamic programming in the problem of sequential visiting of megalopolises”, Procedia Structural Integrity, 40 (2022), 105
А. Г. Ченцов, П. А. Ченцов, “Об одной задаче последовательного обхода множеств”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 31:3 (2021), 487–504
Д. А. Новиков, “Задача об оптимальной последовательности проверки независимых гипотез”, УБС, 94 (2021), 5–32
Tatiana A. Makarovskikh, IFIP Advances in Information and Communication Technology, 634, Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems, 2021, 51
A. A. Chentsov, A. G. Chentsov, A. N. Sesekin, “Optimal routing in a problem with constraints and cost functions depending on the task list”, J. Phys.: Conf. Ser., 1864:1 (2021), 012050
А. Г. Ченцов, П. А. Ченцов, “К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями”, Изв. ИМИ УдГУ, 55 (2020), 135–154
Alexander G. Chentsov, Pavel A. Chentsov, “On routing problem with starting point optimization”, Ural Math. J., 6:2 (2020), 44–62
A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Optimizing insertions in a constraint routing problem with complicated cost functions”, J. Comput. Syst. Sci. Int., 58:1 (2019), 113–125
A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Изв. ИМИ УдГУ, 54 (2019), 102–121
А. Г. Ченцов, А. А. Ченцов, “К вопросу о маршрутизации перемещений в задаче с динамическими ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 29:3 (2019), 363–381
A. G. Chentsov, “Methods of extremal routing and their application to the control of sheet cutting on cnc machines”, Mechanics, Resource and Diagnostics of Materials and Structures (Mrdms-2019), AIP Conf. Proc., 2176, eds. E. Gorkunov, V. Panin, S. Ramasubbu, Amer. Inst. Phys., 2019, 020001
Цитирование в формате AMSBIB
Обратная связь: