К вопросу о применении минимаксной задачи коммивояжера к проблемам авиационной логистики
Автор: Ченцов А.Г., Ченцов А.А., Сесекин А.Н.
Рубрика: Математическое моделирование
Статья в выпуске: 3 т.16, 2023 года.
Бесплатный доступ
Рассматривается задача об организации системы перемещений между заданными пунктами (городами) в условиях ограничений ресурсного характера и при наличии условий предшествования. Условия разрешимости данной задачи извлекаются из решения минимаксной задачи коммивояжера (задача на узкие места) без ресурсных ограничений. Решение данной экстремальной задачи маршрутизации определяется на основе широко понимаемого динамического программирования в его неаддитивной версии. Возможные применения могут быть связаны с вопросами формирования маршрута транспортного средства (самолет или вертолет) с целью организации системы перевозок в условиях дефицита топлива; предполагается, что помимо обязательного посещения всех пунктов имеются требования по попутному перемещению грузов между некоторыми из пунктов, что создает дополнительные ограничения (условия предшествования). Для решения вспомогательной экстремальной задачи построен оптимальный алгоритм, реализованный на ПЭВМ.
Маршрутизация перемещений, система ограничений, динамическое программирование
Короткий адрес: https://sciup.org/147241742
IDR: 147241742 | УДК: 519.8 | DOI: 10.14529/mmp230302
On the application of the minimax traveling salesman problem in aviation logistics
We consider the problem of organizing a system of movement between the given points (cities) under conditions of resource constraints and in the presence of precedence conditions. The solvability conditions for this problem are extracted from the solution to the minimax traveling salesman problem (the bottleneck problem) without resource constraints. The solution to this extreme routing problem is determined on the basis of a broadly understood dynamic programming in its ``non-additive'' version. Possible applications may be related to the formation of the route of a vehicle (airplane or helicopter) in order to organize a transportation system in conditions of fuel shortage; it is assumed that in addition to the mandatory visits to all points, there are requirements for the passing movement of goods between some of the points, which creates additional restrictions (precedence conditions). To solve an auxiliary extremal problem, an optimal algorithm is constructed and implemented on a PC.
Список литературы К вопросу о применении минимаксной задачи коммивояжера к проблемам авиационной логистики
- Ченцов, А.Г. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин. - М.: URSS, 2020.
- Ченцов, А.Г. Маршрутизация перемещений при динамических ограничениях: задача «на узкие места> / А.Г. Ченцов, А.А. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2016. - Т. 26, № 1. - С. 121-140.
- Ченцов, А.Г. Динамическое программирование в «обобщенной задаче на узкие места> и оптимизация точки старта / А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2018. - Т. 28, № 3. - С. 348-363.
- Ченцов, А.Г. Динамическое программирование и вопросы разрешимости задачи маршрутизации «на узкие места> с ресурсными ограничениями / А.Г. Ченцов, А.А. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. -2022. - Т. 32, № 4. - С. 569-592.
- Gutin, G. The Traveling Salesman Problem and its Variations / G. Gutin, A.P. Punnen. -Berlin: Springer, 2002.
- 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.
- Гимади, Э.Х. Экстремальные задачи на множествах перестановок / Э.Х. Гимади, М.Ю. Хачай. - Екатеринбург: УМЦ УПИ, 2016.
- Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
- Меламед, И.И. Задача коммивояжера. Точные методы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
- Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
- Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, № 1. -С. 94-107.
- Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - Т. 9. - С. 219-228.
- Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - Т. 9. - С. 202-218.
- Сергеев, С.И. Алгоритмы решения минимаксной задачи коммивояжера. I. Подход на основе динамического программирования / С.И. Сергеев // Автоматика и телемеханика. -1995. - № 7. - C. 144-150.
- Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
- Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
- Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. -М.: МЦНМО, 2000.
- Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ, 2008.
- Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2013. -№ 1. - С. 59-82.
- 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.
- Ченцов, А.Г. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. - 2016. - № 1. -С. 41-54.
