Задача коммивояжёра (Traveling Salesman Problem, TSP) представляет собой одну из ключевых задач дискретной оптимизации, требующую нахождения кратчайшего маршрута, проходящего через каждую вершину заданного множества ровно один раз и возвращающегося в начальную точку. В данной работе рассматривается Евклидова версия задачи (ETSP), где расстояния между вершинами заданы координатами на плоскости. TSP находит широкое применение в таких областях, как логистика, транспортное планирование, маршрутизация сетей и управление дронами. Несмотря на NP-трудность задачи в общем случае, для ряда специальных случаев существуют полиномиальные алгоритмы. В данной статье предложен метод попарного сравнения, позволяющий оценить эффективность эвристик, точных для подклассов задач, на более широких классах примеров. Метод заключается в сравнении двух экземпляров задачи A и B по определённому критерию и вычислении функции различия, отражающей целевую функцию A при использовании решения задачи B. Применение данного подхода для ETSP может способствовать расширению возможностей полиномиальных алгоритмов на примеры, включающие выпуклые оболочки. Результаты исследования демонстрируют потенциал метода попарного сравнения для анализа структуры NP-трудных задач и совершенствования алгоритмов их решения.
