1)метод ветвей и границ (алг. Литтла): В начале определяется некоторое допустимое решение, после чего множество всех оставшихся вариантов разбиваются на мелкие подмножества. На каждом шаге разбиения вычисляется нижняя граница текущего разбиения. С помощью найденных границ происходит дальнейшее разбиение подмножеств допустимых маршрутов и в конечном итоге определяется конечный маршрут. Если находится маршрут, длина которого не превосходит наименьших нижних границ других маршрутов, то данное промежуточное решение становится наилучшим допустимым решением. 2) «иди в ближайший»: Что построить кольцевую структуру, необходимо последовательно к существующей части добавлять ближайший, не вошедший еще в маршрут, пункт. Данный алгоритм оперирует разомкнутым маршрутом с исходным пунктом. Другой подход заключается в том, чтобы иметь изначально замкнутую подструктуру и вставлять в нее очередной пункт на пустое место. Различные модификации алгоритма связаны с выбором пункта и места вставки. 3) алг. минимальной вставки: сформировать начальный маршрут; для каждой вершины v найти такие i и j, чтобы Сiv+Сvj–Сij->min; для данной вершины найти такую другу вершину, при добавлении которой в маршрут, минимально увеличивается маршрут относительно удаленного ребра; вставить вершину; повторить сначала, если есть еще вершины n^2*lg(n)-кол-во вычислений. Есть методы ближайшей вставки и дальней вставки.
