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

Abstract

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

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.