一、TSP问题的概念

旅行商问题是需要取访问n个城市里面的每个城市一次且只能一次，从一个城市出发最后在回到这个出发的城市，我们的目的是要尽可能是减少旅行的距离。

二、LK算法

LK算法是一种启发式算法，通过一个给定的初始的解路径，通过一次次改进路径以获得更好的解路径，一个简单的例子是2-opt算法

算法提出背景

先引入λ-opt的概念

从概念我们可以很清楚的了解到，如果一个解路径达到n-optimal，那么这个包含n个城市的路径就是最优的。因此，λ的取值越大，最后所得到的解是最优解的可能性越大。但不幸的是，λ-exchange所需要的时间复杂度是O(n^λ)，所以我们经常将λ取值2、3、4或者5。

上述方法存在一个缺点：我们必须提前说明λ的取值，但我们很难在解的质量和时间运行之间找到一个平衡，找到一个合适的λ值，因此LK算法提出来一个有效的解决算法：variable λ-opt 算法

variable λ-opt算法（即LK算法）

该算法在执行过程中改变λ的取值，每次迭代过程中都要确定一次λ的取值。在每次迭代中，算法升序的检查λ个链路的交换是否可以产生一个更短的路径（从λ=2开始）。

下面更详细的介绍算法
假设T是当前路径，每一次迭代中尝试找到两个链路的集合，X = {x₁,…,x_r}和Y = {y₁,…,y_r}，从T里面将X集合里面的链路删除掉并且替换为Y集合里面的链路，以得到一个更好的解。这些边的交换的行为叫做一次λ-opt move，下图展示了一次3-opt move。

图1 A 3-opt move

集合X和Y由一个接一个的元素构造。初始情况下X和Y是空的。在第i步，一对链路 x_i 和y_i被分别加到X和Y中。为了实现一个更有效的算法，只有满足下面4个准则的边才能进去X和Y。
（1）顺序交换准则（The sequential exchange criterion）
x_i和y_i必须共享一个端点，y_i和x_i+1也必须共享一个端点。如果用t₁来表示x₁两个端点中的一个，那么通常我们这样来表示：x_i = （t_2i， t_2i），y_i = （t_2i， t_2i+1），x_i+1 = （t_2i+1， t_2i+2），i≥1，如图2所示。

图二 链路的表示以及限制

如图所示， 序列（x₁，y₁，x₂，y₂，…，x_r，y_r）构成了一条邻近的链路。一个必要不充分条件是X和Y的交换所形成的新路程应该是闭合的。这样的交换被称为sequential。
（2）可行性准则（The feasibility criteria）
当i≥3，选择x_i = （t_2i-1， t_2i）时，如果将t_2i和t₁连接，那么结果应该是一个tour。。
（3）正收益准则（The positive criterion）
假设g_i = c（x_i） - c（y_i），G_i = g₁ + g₂ + … + g_i，每次y_i的选择必须要整G_i是正的。这条准则基于以下事实：如果一个序列的总和是正的，那么一定能使下面两个式子成立

即如果一个序列的总和大于0，总能找到一个序列使得每个Gi大于0，即总能找到一个从g_k开始的序列
（4）不相交准则（The disjunctivity criterion）
X和Y两个集合需要不相交

算法的概要如下图

图3：The basic LK algorithm

三：LK算法的改善

对于集合X,Y里面链路的搜索时上述LK算法的一个瓶颈。因此，为了增加算法的有效性，在找链路进入X，Y时需要有一些限制。只有那些有大概率导致找到一个更短tour的交换链路才被考虑。

上部分所呈现的算法通过下面四个规则限制了链路的搜索：
（1）只有顺序交换才被允许
（2）G_i必须是正的
（3）Tour必须可以闭合（对于i≥3）
（4）原来被打断的链路不能再被添加，同样原来被添加的链路不能再被破环

除此之外，Lin和Kernighan提出了下面的规则来限制搜索：
（5）对于一个进入tour的链路的搜索，y_i = （t_2i， t_2i+1），被限制在离t_2i最近的5个相邻的链路
（6）对于i≥4，如果x_i是几个（2-5）可行解所共有的链路，那么x_i不必被破坏
（7）如果当前tour和原来的tour一模一样，则停止搜索更优的tour

除了限制搜索，Lin和Kernighan还加了几条改善来指导（direct）搜索

（8）当选择y_i（i≥2）时，给每个可能的y_i给出一个优先级c（x_i+1） - c（y_i）
（9）如果有2个备选的x₄，c（x₄）高的将被选择

最后，Lin和Kernighan给出了一个改进来防止只有非顺序交换才可能导致更好的解放方案的情况，如图4所示

图4：非顺序交换

在找到局部最优之后，可以尝试非顺序交换来判断是否可以进一步进行改进。

四：参考

【1】S. Lin & B. W. Kernighan,
“An Effective Heuristic Algorithm for the Traveling-Salesman Problem”,
Oper. Res. 21, 498-516 (1973).
【2】Keld Helsgaun
“An Effective Implementation of the
Lin-Kernighan Traveling Salesman Heuristic”
European Journal of Operational Research.126(1),106-130(2000)