К вопросу о применении минимаксной задачи коммивояжера к проблемам авиационной логистики

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

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

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

Литература

1. Ченцов, А.Г. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин. – М.: URSS, 2020.
2. Ченцов, А.Г. Маршрутизация перемещений при динамических ограничениях: задача "на узкие места" / А.Г. Ченцов, А.А. Ченцов // Вестник Удмуртского университета.
Математика. Механика. Компьютерные науки. – 2016. – Т. 26, № 1. – С. 121–140.
3. Ченцов, А.Г. Динамическое программирование в "обобщенной задаче на узкие места" и оптимизация точки старта / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. – 2018. – Т. 28, № 3. – С. 348–363.
4. Ченцов, А.Г. Динамическое программирование и вопросы разрешимости задачи маршрутизации "на узкие места" с ресурсными ограничениями / А.Г. Ченцов, А.А. Ченцов
// Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. – 2022. – Т. 32, № 4. – С. 569–592.
5. Gutin, G. The Traveling Salesman Problem and its Variations / G. Gutin, A.P. Punnen. – Berlin: Springer, 2002.
6. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. – Princeton, New Jersey: Princeton University Press, 2012.
7. Гимади, Э.Х. Экстремальные задачи на множествах перестановок / Э.Х. Гимади, М.Ю. Хачай. – Екатеринбург: УМЦ УПИ, 2016.
8. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. – 1989. – № 9. – С. 3–34.
9. Меламед, И.И. Задача коммивояжера. Точные методы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. – 1989. – № 10. – С. 3–29.
10. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. – 1989. – № 11. – С. 3–26.
11. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. – 1965. – Т. 1, № 1. – С. 94–107.
12. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. – 1964. – Т. 9. – С. 219–228.
13. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. – 1964. – Т. 9. – С. 202–218.
14. Сергеев, С.И. Алгоритмы решения минимаксной задачи коммивояжера. I. Подход на основе динамического программирования / С.И. Сергеев // Автоматика и телемеханика. – 1995. – № 7. – C. 144–150.
15. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. – М.: Мир, 1970.
16. Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. – М.: Мир, 1964.
17. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2000.
18. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. – Ижевск: НИЦ, 2008.
19. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. – 2013. – № 1. – С. 59–82.
20. Lawler, E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems / E.L. Lawler // CWI Technical Report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW. – 1979. – V. 106, № 79. – P. 1–16.
21. Ченцов, А.Г. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. – 2016. – № 1. – С. 41–54.