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