Об одной задаче маршрутизации, ориентированной на проблему демонтажа радиационно опасных объектов
Автор: Ченцов Александр Георгиевич, Ченцов Алексей Александрович
Рубрика: Математическое моделирование
Статья в выпуске: 3 т.15, 2022 года.
Бесплатный доступ
Рассматривается задача последовательного обхода мегаполисов при наличии условий предшествования и функций стоимости с зависимостью от списка заданий, не выполненных на текущий момент времени. Оптимизируется выбор маршрутного процесса, включающего перестановку индексов, траекторию и точку старта; оптимизируется также точка финиша. Используется аддитивный критерий, получаемый суммированием затрат на внешние (по отношению к мегаполисам) перемещения, затраты на проведение работ, связанных с посещением мегаполисов, а также оценки терминального состояния. Исследуется процедура построения оптимального решения на основе широко понимаемого динамического программирования. Постановка ориентирована на задачу демонтажа системы радиационно опасных источников; при этом допускается, что демонтированы будут не все источники (это возможно при получении работниками предельных доз радиации), что потребует эвакуации в условиях радиационного воздействия источников, оставшихся недемонтированными. Конкретный вариант критерия сводится к суммарной дозе радиации, получаемой работником как на этапе демонтажа, так и на этапе эвакуации. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.
Маршрут, трасса, условия предшествования, динамическое программирование
Короткий адрес: https://sciup.org/147238551
IDR: 147238551 | УДК: 519.6 | DOI: 10.14529/mmp220306
On one routing problem oriented on the problem of dismantling radiation-hazardous objects
We consider a problem of sequential visiting of megalopolises under the preceding conditions and costs functions depending on the list of tasks currently unfulfilled. Selection of a routing process involving index permutation, trajectory and starting point is optimized; point of finish is optimized also. We use additive criterion consisting in summary costs of external (as for megalopolises) movings, costs of works related to visiting of megalopolises and assessments of the terminal state. Procedure of construction of optimal solution based on widely understood dynamic programming is investigated. The statement is focused on the problem of dismantling the system of radiation-hazardous sources; at the same time, it is assumed that not all sources are dismantled (it is possible when workers receive maximum doses of radiation), which requires evacuation in conditions of radiation exposure of sources that remain undismantled. A specific variant of the criterion is reduced to the summary dose of radiation received by an employee both at the stage of dismantling and at the stage of evacuation. An algorithm based on the theoretical constructions is proposed and realized on personal computer; a computational experiment is completed.
Список литературы Об одной задаче маршрутизации, ориентированной на проблему демонтажа радиационно опасных объектов
- Ченцов, А.Г. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) / А.А. Ченцов, А.Г. Ченцов // Известия Института математики и информатики Удмуртского государственного университета. - 2017. - Т. 50. - С. 83-109.
- Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2012.
- 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.
- Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. -Berlin: Springer, 2002.
- 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.
- Гимади, Э.Х. Экстремальные задачи на множествах перестановок / Э.Х. Гимади, М.Ю. Хачай. - Екатеринбург: УМЦ УПИ, 2016.
- Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, № 1. -С. 94-107.
- Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - № 9. - С. 219-228.
- Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - № 9. - С. 202-218.
- Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ «Регулярная и хаотическая динамика:», Ижевский институт компьютерных исследований, 2008.
- Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
- Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
- Кормен, Т. Алгоритмы: Построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. -МЦНМО, 2002.
- Варга, Дж. Оптимальное управление дифференциальными и функциональными уравнениями / Дж. Варга. - М.: Наука, 1977.
- Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. -№ 1. - C. 59-82.
- Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - С. 96-117.
- Ченцов, А.Г. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Труды Института математики и механики УрО РАН. -2020. - Т. 26, № 3. - С. 219-234.
- Петунин, А. А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов. - Екатеринбург: Изд-во Уральского ун-та, 2020.
- Ченцов, А.Г. Одна задача маршрутизации работ в условиях повышенной радиации / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Известия Института математики и информатики Удмуртского государственного университета. - 2021. - Т. 58. - С. 94-126.
- Chentsov, A.G. The Routing Problems with Optimization of the Starting Point: Dynamic Programming / A.G. Chentsov, P.A. Chentsov // Известия Института математики и информатики Удмуртского государственного университета. - 2019. - Т. 54. - С. 102-121.
