Об одной задаче маршрутизации с неаддитивным агрегированием затрат
Автор: Ченцов Александр Георгиевич, Ченцов Алексей Александрович, Сесекин Александр Николаевич
Рубрика: Математическое моделирование
Статья в выпуске: 1 т.13, 2020 года.
Бесплатный доступ
Исследуется задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и неаддитивным агрегированием затрат. Предполагается, что на уровне (при оценивании системы циклов, определяемых всякий раз этапами внешнего перемещения и внутренних работ) вариант агрегирования отвечает задаче узкие места с корректирующим параметром. На уровне (в пределах цикла) агрегирование затрат на внешнее перемещение и проведение работ может быть произвольным. Построен вариант процедуры динамического программирования, включая экономичный вариант, использующий условия предшествования. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ в случае постановки, ориентированной на задачу об управлении автономной системой, функционирующей в агрессивной среде и осуществляющей последовательно процесс демонтажа источников воздействий (данной среды) на систему. Эта постановка может отвечать инженерной задаче о демонтаже источников радиационного излучения при аварийных ситуациях на АЭС в случае применения роботизированной системы с электронным оборудованием, функционирование которого возможно лишь при соблюдении допусков на интенсивность радиационного воздействия в течении всего временного промежутка. Для данного варианта общей постановки проведен вычислительный эксперимент с применением ПЭВМ.
Динамическое программирование, маршрут, условия предшествования
Короткий адрес: https://sciup.org/147232985
IDR: 147232985 | УДК: 519.6 | DOI: 10.14529/mmp200105
On one routing problem with non-additive cost aggregation
We investigate the problem on sequential round of megalopolises (nonempty finite sets) with preceding conditions and nonadditive aggregation of costs. We suppose that a variant of aggregation with respect to "external'' phase (by the estimation of the system of cycles, which are determined every time by the "external'' movement and internal jobs) corresponds to the "bottleneck'' problem with the correction parameter. At the "internal'' phase (within the cycle), an aggregation of costs with respect to external movement and carrying out works can be arbitrary. We construct nonadditive variant of the procedure of dynamic programming (DP) including economical variant, which uses preceding conditions. In the form of a program for a personal computer, we realize the optimal algorithm based on DP for the statement oriented to the problem on control of an autonomous system, which works in aggressive environment and implements a sequential process of dismantling of the sources of exposures (of this environment) to the system. Such a statement can correspond to the engineering problem on sequential dismantling of the sources of radiation under emergency situations on the nuclear power plants in the case of application of the robotic system with electronic equipment, which can work only if tolerances are complied with respect to influence of radiation during entire time interval. For this variant of the general statement, we implement a calculation experiment by means of a personal computer.
Список литературы Об одной задаче маршрутизации с неаддитивным агрегированием затрат
- Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 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.
