Эвристика Лина-Кернигана: локальный поиск с переменной глубиной для задачи коммивояжера

Математический фундамент метода вырастает из простых процедур $k$-opt обменов. Алгоритм 2-opt удаляет два пересекающихся ребра текущего маршрута и заменяет их двумя новыми, устраняя "кресты" и улучшая длину пути. Алгоритм 3-opt делает то же самое с тремя ребрами. Однако с ростом $k$ вычислительная сложность проверки всех комбинаций растет как $O(n^k)$, что делает статический $k$-opt неприменимым для больших $k$. Гениальность эвристики Лина-Кернигана состоит в адаптивном определении числа $k$ на каждом шаге: алгоритм строит последовательность удаляемых и добавляемых ребер шаг за шагом, решая остановиться именно тогда, когда дальнейшее увеличение цепочки перестает обещать улучшение маршрута.

Алгоритмически процесс описывается как поиск улучшающего чередующегося пути на графе. Начиная с некоторого узла, алгоритм удаляет ребро (увеличивая временный "дефицит" длины), затем добавляет новое короткое ребро, затем снова удаляет и так далее. Условием продолжения цепочки является строгий математический критерий: суммарный выигрыш (gain) на текущем шаге должен оставаться положительным. Это означает, что если мы замкнем маршрут прямо сейчас, он будет короче исходного. Алгоритм строит дерево таких чередующихся путей с помощью поиска в глубину, эффективно отсекая ветви, не удовлетворяющие критерию положительного выигрыша, что позволяет исследовать эквиваленты 10-opt или даже 50-opt обменов за доли секунды.

Наибольший прорыв в эффективности LK-алгоритма произошел с появлением реализации LKH, созданной датским математиком Кьелдом Хельсгауном (Kjeld Helsgaun) в 2000 году. Хельсгаун модифицировал математическую структуру поиска, внедрив 1-деревья минимального веса (minimum 1-trees) и $\alpha$-оценки для предварительной фильтрации ребер-кандидатов. Идея состоит в том, что ребро, не принадлежащее минимальному 1-дереву и имеющее большой штраф (большую $\alpha$-оценку), с ничтожной вероятностью войдет в оптимальный маршрут коммивояжера. Отсечение таких ребер на старте сужает пространство поиска до крошечной окрестности, превращая экспоненциальный взрыв в линейное время работы.

Сегодня реализация LKH успешно решает инстансы задачи коммивояжера (такие как World TSP) из 1.9 миллиона городов, что долгое время казалось невозможным для вычислительной техники. Математика эвристики Лина-Кернигана учит нас важному принципу дискретной оптимизации: вместо жестко заданных структур локального поиска (статичный $k$-opt) необходимо применять адаптивные механизмы, способные интеллектуально исследовать глубокие окрестности решения, опираясь на сильные математические границы и графовые оценки.

Список литературы:
1. Lin S., Kernighan B.W. An effective heuristic algorithm for the traveling-salesman problem. — Operations Research, 1973.
2. Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. — European Journal of Operational Research, 2000.
3. Applegate D.L., Bixby R.E., Chvatal V., Cook W.J. The Traveling Salesman Problem: A Computational Study. — Princeton University Press, 2006.