Задача коммивояжёра – это задача дискретной оптимизации, в которой необходимо определить кратчайший путь обхода всех вершин(городов), посещая каждый только один раз. В общем случае, эта задача является NP-трудной и не имеет полиномиального алгоритма. Однако существуют специальные случаи, для которых можно найти оптимальное решение за полиномиальное время. Для расширения применимости таких алгоритмов и изучения структуры NP-трудных задач существует метод попарного сравнения. Данный подход предлагает сравнивать два примера задачи A и B по некоторому критерию и задавать функцию различия, значение которой равна целевой функции A при использовании в качестве решения полиномиального (псевдополиномиального) точного решения задачи B. Таким образом можно оценить насколько эвристика, дающая точное решения для подкласса примеров задачи, может быть применима для более широкого класса примеров задачи. В нашей работе описано применение метода попарного сравнения для задачи коммивояжера. В работе рассматривается специальный случай, когда все вершины расположены на евклидовой плоскости и образуют границу выпуклого многоугольника, то есть лежат на выпуклой оболочке множества вершин. В таком случае оптимальный маршрут будет проходить по границе многоугольника и решение можно найти за полиномиальное время O(n), где n -- количество заданных вершин. Для перехода от исходной задачи к специальному случаю были изучены два подхода: рассмотрение исходной задачи как набор вложенных выпуклых оболочек и как набор непересекающихся выпуклых оболочек, что является кластеризацией вершин на выпуклые оболочки. Для каждого варианта перехода предложена функция попарных сравнений и описаны алгоритмы получения допустимого решения. Проведено сравнение этих подходов, а также сравнение кластеризации на выпуклые оболочки с классической k-means кластеризацией.