Об одной задаче маршрутизации, ориентированной на проблему демонтажа радиационно опасных объектов

Рассматривается задача последовательного обхода мегаполисов при наличии условий предшествования и функций стоимости с зависимостью от списка заданий, не выполненных на текущий момент времени. Оптимизируется выбор маршрутного процесса, включающего перестановку индексов, траекторию и точку старта; оптимизируется также точка финиша. Используется аддитивный критерий, получаемый суммированием затрат на внешние (по отношению к мегаполисам) перемещения, затраты на проведение работ, связанных с посещением мегаполисов, а также оценки терминального состояния. Исследуется процедура построения оптимального решения на основе широко понимаемого динамического программирования. Постановка ориентирована на задачу демонтажа системы радиационно опасных источников; при этом допускается, что демонтированы будут не все источники (это возможно при получении работниками предельных доз радиации), что потребует эвакуации в условиях радиационного воздействия источников, оставшихся недемонтированными. Конкретный вариант критерия сводится к суммарной дозе радиации, получаемой работником как на этапе демонтажа, так и на этапе эвакуации. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.

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

маршрут; трасса; условия предшествования; динамическое программирование.

Литература

1. Ченцов, А.Г. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) / А.А. Ченцов, А.Г. Ченцов // Известия Института математики и информатики Удмуртского государственного университета. - 2017. - Т. 50. - С. 83-109.
2. Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2012.
3. Chentsov, A.G. Optimization "In Windows" for Routing Problems with Constraints A.A. Chentsov, A.G. Chentsov, A.M. Grigor'ev // Communications in Computer and Information Science. - 2019. - V. 1090. - P. 470-485.
4. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - Berlin: Springer, 2002.
5. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. - Princeton, New Jersey: Princeton University Press, 2012.
6. Гимади, Э.Х. Экстремальные задачи на множествах перестановок / Э.Х. Гимади, М.Ю. Хачай. - Екатеринбург: УМЦ УПИ, 2016.
7. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, № 1. - С. 94-107.
8. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - № 9. - С. 219-228.
9. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - № 9. - С. 202-218.
10. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008.
11. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
12. Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
13. Кормен, Т. Алгоритмы: Построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - МЦНМО, 2002.
14. Варга, Дж. Оптимальное управление дифференциальными и функциональными уравнениями / Дж. Варга. - М.: Наука, 1977.
15. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - № 1. - C. 59-82.
16. Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - С. 96-117.
17. Ченцов, А.Г. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Труды Института математики и механики УрО РАН. - 2020. - Т. 26, № 3. - С. 219-234.
18. Петунин, А. А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов. - Екатеринбург: Изд-во Уральского ун-та, 2020.
19. Ченцов, А.Г. Одна задача маршрутизации работ в условиях повышенной радиации / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Известия Института математики и информатики Удмуртского государственного университета. - 2021. - Т. 58. - С. 94-126.
20. Chentsov, A.G. The Routing Problems with Optimization of the Starting Point: Dynamic Programming / A.G. Chentsov, P.A. Chentsov // Известия Института математики и информатики Удмуртского государственного университета. - 2019. - Т. 54. - С. 102-121.