Исследование возможности замены матрицы расстояний задачи коммивояжера матрицей предпорядка

Одной из самых известных задач в комбинаторной оптимизации можно считать задачу коммивояжера (TSP), в которой путешественнику необходимо найти такой маршрут, который проходит по всем заданным городам и возвращается в изначальный и является оптимальным по стоимости проезда. Интерес к TSP вызван его практической значимостью в большом количестве возможных сфер использования в настоящее время (например, доставка, построение навигационных маршрутов, оптимизация маршрутов полетов военных самолетов и т. д.) и в будущем. В данной работе рассматривается один из возможных способов представления этой проблемы, называемый Матрицей̆ Предпорядка. Основная идея заключается в замене весовой матрицы, представляющей TSP, на матрицу, состоящую из элементов, представляющих порядковый номер уникальных значений в весовой матрицы, отсортированных в порядке возрастания. Такая замена позволит создавать классы задач одной сложности, представителем которой будет Матрица Предпорядка. Цель исследования показать возможно ли использовать такой подход как критерий сложности для задач TSP. Для получения оценки мы используем библиотеку TSPLIB для симметричной и ассиметричной задачи коммивояжера, в качестве основных алгоритмов для получения решения мы используем Метод ветвей и границ, который дает точное решение для заданной задачи, и LKH-3, который на данный момент является лучшим по точности алгоритмом для получения точного или приближенного решения. Для задач из TSPLIB мы получаем Матрицу Предпорядка, используя алгоритмы выше получаем маршрут и вычисляем итоговую стоимость маршрута, применяя полученное решение для Матриц Предпорядка к матрице весов. Сравнивая полученную стоимость маршрута с известным оптимальным решением, который есть в TSPLIB, а также сравнения числа узлов в деревьях решений для Матриц Предпорядка и реальных задач, мы делаем выводы о адекватности использовании Матриц Предпорядка.