Минимаксная задача маршрутизации с системой первоочередных заданий

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

doi:10.35634/2226-3594-2023-62-08

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

DOI: https://doi.org/10.35634/2226-3594-2023-62-08

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

Аннотация

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

Литература

1. Ченцов А.Г., Ченцов А.А. Динамическое программирование и вопросы разрешимости задачи маршрутизации «на узкие места» с ресурсными ограничениями // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2022. Т. 32. Вып. 4. C. 569–592. https://doi.org/10.35634/vm220406
2. Ченцов А.Г. Задача маршрутизации «на узкие места» с системой первоочередных заданий // Известия Института математики и информатики Удмуртского государственного университета. 2023. Т. 61. С. 156–186. https://doi.org/10.35634/2226-3594-2023-61-09
3. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Динамическое программирование в задаче курьера на узкие места с применением в авиационной логистике // Управление и обработка информации в технических системах: Материалы XVIII Всероссийской научно-практической конференциии; XIV молодёжной школы-семинара, 3--7 апреля 2023, Домбай, Карачаево-Черкесская Республика. Таганрог, 2023. С. 34-44.
4. Ченцов А.Г., Ченцов П.А. Динамическое программирование в задаче маршрутизации: декомпозиционный вариант // Вестник российских университетов. Математика. 2022. Т. 27. № 137. С. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
5. Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Труды Института математики и механики УрО РАН. 2022. Т. 28. № 2. С. 215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248
6. Ченцов А.Г., Ченцов П.А. Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции // Автоматика и телемеханика. 2023. Вып. 5. С. 133–164. https://www.mathnet.ru/rus/at16064
7. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат. М.: URSS, 2020.
8. Сергеев С.И. Алгоритмы решения минимаксной задачи коммивояжера. I. Подход на основе динамического программирования // Автоматика и телемеханика. 1995. Вып. 7. С. 144–150. https://www.mathnet.ru/rus/at3684
9. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. Вып. 9. С. 3–34. https://www.mathnet.ru/rus/at6414
10. Gutin G., Punnen A.P. The traveling salesman problem and its variations. New York: Springer, 2007. https://doi.org/10.1007/b101971
11. Cook W.J. In pursuit of the traveling salesman: Mathematics at the limits of computation. Princeton: Princeton University Press, 2012.
12. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
13. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. Вып. 1. С. 94–107.
14. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219–228.
15. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 202–218.
16. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.
17. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964.
18. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977.
19. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.
20. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.–Ижевск: Ижевский институт компьютерных исследований, 2008.
21. Ченцов А.Г., Ченцов А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41–54.