Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок)

Александр Георгиевич Ченцов; Алексей Александрович Ченцов

doi:10.20537/2226-3594-2017-50-08

Александр Георгиевич Ченцов
- Институт математики и механики им. Н.Н. Красовского УрО РАН
- Уральский федеральный университет
Алексей Александрович Ченцов
- Институт математики и механики им. Н.Н. Красовского УрО РАН

DOI: https://doi.org/10.20537/2226-3594-2017-50-08

Ключевые слова: маршрут, трасса, условия предшестования, динамическое программирование

Аннотация

Рассматривается маршрутная задача о последовательном демонтаже системы излучающих элементов. Предполагается, что данная задача имеет достаточно большую размерность, что затрудняет поиск точных решений и заставляет использовать эвристики. Для улучшения качества последних предлагается использовать оптимизирующие вставки умеренной размерности, в пределах которых используется аппарат широко понимаемого динамического программирования. Локализация вставки определяется из соображений, связанных с использованием условий предшествования. Функции стоимости перемещений и (внутренних по смыслу) работ, связанных с утилизацией (демонтажем) источников, допускают зависимость от списка заданий, которые еще не выполнены: «светят» те и только те источники, которые не демонтированы на момент перемещения и/или исполнения работы. Воздействие каждого такого источника на исполнителя обратно пропорционально квадрату расстояния; для оценивания радиационного воздействия при перемещении на конечном промежутке времени упомянутую нелинейную зависимость следует интегрировать. Воздействия различных источников суммируются.

Литература

1. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. № 9. С. 3-33.
2. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. 1989. № 10. С. 3-29.
3. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. 1989. № 11. С. 3-26.
4. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Springer US, 2007. DOI: 10.1007/b101971
5. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton University Press, 2012. 248 p. DOI: 10.1515/9781400839599
6. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219-228.
7. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 202-218.
8. Литтл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. Вып. 1. С. 90-107.
9. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2008. 240 с.
10. Сесекин А.Н., Ченцов А.А., Ченцов А.Г. Обобщенная задача курьера с функцией затрат, зависящей от списка заданий // Известия РАН. Теория и системы управления. 2010. № 2. С. 68-77.
11. Ченцов А.Г., Ченцов А.А. Задача маршрутизации с ограничениями, зависящими от списка заданий // Доклады Академии наук. 2015. Т. 465. № 2. С. 154-158. DOI: 10.7868/S0869565215320043
12. Ченцов А.Г. Задача последовательного обхода мегаполисов с условиями предшествования // Автоматика и телемеханика. 2014. № 4. С. 170-190.
13. Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016. № 11. С. 96-117.
14. Ченцов А.Г. Беллмановские вставки в задаче маршрутизации с ограничениями и усложненными функциями стоимости // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2014. Вып. 4. С. 122-141. DOI: 10.20537/vm140410
15. Коробкин В.В., Сесекин А.Н., Ташлыков О.Л., Ченцов А.Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. М.: Новые технологии, 2012. 234 c.
16. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник УГАТУ. Сер. Управление, вычислительная техника и информатика. 2009. Т. 13. № 2 (35). C. 280-286.
17. Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2013. Вып. 2 (169). С. 103-111.
18. Александров П.С., Маркушевич А.И., Хинчин А.Я. (Ред.) Энциклопедия элементарной математики. Книга 3. Функции и пределы. М.-Л.: ГИТТЛ, 1952. 559 с.
19. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.
20. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.
21. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.
22. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016. 216 с.
23. Ченцов А.Г. Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2016. Т. 26. Вып. 4. С. 565-578. DOI: 10.20537/vm160410
24. Петунин А.А., Ченцов А.А., Ченцов А.Г., Ченцов П.А. Элементы динамического программирования в конструкциях локального улучшения эвристических решений задач маршрутизации с ограничениями // Автоматика и телемеханика. 2017. № 4. С. 106-125.