Об одной задаче маршрутизации с неаддитивным агрегированием затрат

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

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

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

Литература

1. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
2. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982.
3. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - Berlin: Springer, 2002.
4. Гимади, Э.Х. Экстремальные задачи на множествах перестановок / Э.Х. Гимади, М.Ю. Хачай. - Екатеринбург: УМЦ УПИ, 2016.
5. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - М.: Мир, 1964.
6. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - М.: Мир. 1964.
7. Сергеев, С.И. Алгоритмы решения минимаксной задачи коммивояжера. I. Подход на основе динамического программирования / С.И. Сергеев // Автоматика и телемеханика. - 1995. - № 7. - C. 144-150.
8. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1. - С. 94-107.
9. Ченцов, А.Г. Маршрутизация перемещений при динамических ограничениях: задача 'на узкие места' / А.Г. Ченцов, А.А. Ченцов // Вестник Удмуртского университета. Серия: Математика. Механика. Компьютер. науки. - 2016. - Т. 26, № 1. - С. 121-140.
10. Сесекин, А.Н. Маршрутизация с абстрактной функцией агрегирования стоимостей перемещений / А.Н. Сесекин, А.А. Ченцов, А.Г. Ченцов // Труды Института математики и механики УрО РАН. - 2010. - Т. 16, № 3. - С. 240-264.
11. Ченцов, А.Г. Об одной задаче на узкие места / А.Г. Ченцов, Я.В. Салий // Тезисы Всероссийской научно-практической конференции 'Статистика. Моделирование. Оптимизация - 2011'. - Челябинск: Издат. центр ЮУрГУ. - С. 85-91.
12. Ченцов, А.Г. Динамическое программирование в 'обобщенной задаче на узкие места' и оптимизация точки старта / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2018. - Т. 28, № 3. - С. 348-363.
13. Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2002.
14. Ченцов, А.Г. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) / А.Г. Ченцов, А.А. Ченцов // Известия Института математики и информатики УдГУ. - 2017. - Т. 50. - C. 83-109.
15. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: Регулярная и хаотическая динамика, 2008.
16. Дьедонне Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
17. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
18. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2000.
19. Ченцов, А.Г. Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования / А.Г. Ченцов, П.А. Ченцов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2018. - Т. 11, № 2. - С. 83-95.
20. Ченцов, А.А. Экстремальная задача маршрутизации 'на узкие места' с ограничениями в виде условий предшествования / А.А. Ченцов, А.Г. Ченцов // Труды Института математики и механики УрО РАН. - 2008. - Т. 14, № 2. - С. 129-142.
21. Ченцов, А.Г. Об одной задаче маршрутизации с внутренними работами / А.Г. Ченцов, И.Б. Чеблоков // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2012. - Вып. 1. - С. 96-119.
22. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. - Вып. 1. - С. 59-82.
23. Lawler, E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems / E.L. Lawler // Stichting Mathematisch Centrum. - 1979 . - P. 1-16.
24. Ченцов, А.Г. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. - 2016. - № 1. - С. 41-54.