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

• Дата: 2024
• Автори: Stetsyuk, Petro, Korablov, Mykola, Stoian, Oleksandr, Hubernator, Oleh, Mykhailenko, Oleksandra
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2024
• Теми: задача комівояжера; гамільтонів цикл; змішане цілочислове лінійне програмування; AMPL; Gurobi; CPLEX; NEOS server; пішохідний туризм
• Онлайн доступ: https://jais.net.ua/index.php/files/article/view/238
• Назва журналу: Problems of Control and Informatics

Задача комівояжера є однією з найстаріших та найбільш досліджених задач математичного програмування та дослідження операцій. Навіть у своїй найпростішій постановці вона має безліч застосувань у різноманітних сферах, а потреба враховувати складні додаткові обмеження при побудові маршрутів чи визначені послідовності дій спонукає дослідників до створення нових узагальнених моделей. У роботі сформульовано нове узагальнення задачі комівояжера — задача пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Для розв’язання даної задачі розглянуто дві математичні моделі змішаного цілочислового лінійного програмування: на основі узагальнених обмежень Міллера, Такера і Земліна (перша); та Гевіша і Грейвса (друга). На тестових прикладах продемонстровано переваги та недоліки обох моделей та запропоновано комбіновану модель, що поєднує їхні ідеї при використанні узагальнених обмежень Міллера, Такера і Земліна разом з узагальненими обмеженнями Гевіша та Грейвса для забезпечення зв’язності отриманого циклу та відсутності підциклів у ньому. Така комбінована модель також дозволяє доповнювати задачу спеціальними додатковими обмеженнями (деякі з них описано в цій роботі), що дає змогу ще більше розширити постановку задачі, яка розв’язується. Наведено обчислювальні експерименти, які підтверджують можливість використання комбінованої моделі для розв’язання задач такого типу з додатковими обмеженнями різного виду та без них. Представлено приклад застосування запропонованої комбінованої моделі для побудови персоналізованих пішохідних туристичних маршрутів центром Києва, описано архітектуру розробленого прототипу веб-застосунку для розв’язання даної задачі. Розглянуто перспективи застосування запропонованої моделі в різних сферах та описано переваги, які можуть отримати кінцеві користувачі від використання застосунків, розроблених на її основі.