Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму

• Опубліковано в: : Проблеми керування та інформатики
• Дата: 2024
• Автори: Стецюк, П.І., Корабльов, М.М., Стоян, О.О., Губернатор, О.А., Михайленко, О.В.
• Формат: Стаття
• Мова: Українська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2024
• Теми: Методи оптимізації та оптимальне керування
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/211211
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму / П.І. Стецюк, М.М. Корабльов, О.О. Стоян, О.А. Губернатор, О.В. Михайленко // Проблеми керування та інформатики. — 2024. — № 4. — С. 5–27. — Бібліогр.: 14 назв. — укр.

У статті сформульовано нове узагальнення задачі комівояжера — задачі пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Розглянуто дві математичні моделі змішаного цілочислового лінійного програмування (МЦЛП): одна на основі узагальнених обмежень Міллера, Такера і Земліна, інша — Гевіша і Грейвса. Запропоновано комбіновану модель, яка об’єднує ідеї обох підходів. Проведено обчислювальні експерименти, які підтверджують можливість використання цієї моделі для розв’язання задач з додатковими обмеженнями. The article formulates a new generalization of the traveling salesman problem — the task of finding the shortest cycle visiting a specified number of graph cluster vertices. Two mixed integer linear programming (MILP) models are considered: one based on the generalized Miller-Tucker-Zemlin constraints, and the other on the Gavish-Graves constraints. A combined model integrating the ideas of both approaches is proposed. Computational experiments confirm the feasibility of using this model to solve problems with additional constraints.