Approximation algoirithms for route optimization problems : exploiting geometric structures and application to large scale problems

从平面上旅行商问题的Arora多项式时间逼近格式出发，我们旨在将这一理论结果应用到实际的求解方法中，并研究了一些方法。主要成果如下：(1)Arora动态规划的有效实现：基于Arora的动态规划公式中的每个子问题都可以由一个二进制字符串紧凑地表示，基于子问题和格式良好的括号之间的一一对应关系，我们提出了一种将子问题映射到其子问题的快速方案。使用该方案，我们实现了两个数量级的速度，而不是简单的实现。(2)引入了加泰罗尼亚分解的概念，并在此基础上提出了一种动态规划方案：我们用图的拓扑分解代替了Arora的矩形分解，并应用了(1)的实现方案。(3)交替圈贡献法的发展：给定一个待改进的路线(主路线)和其他供参考的路线(贡献路线)，我们以交替圈的形式提取主路线和每个贡献路线之间的差异。然后我们选择这些交替循环中的一些，将它们与主圈合并，并在所得到的图中获得最优圈，希望得到比主圈更好的结果。交替循环的选择是基于每个循环的翻转增益和当所有选择的循环被添加到主循环中时所得到的图的可处理性。(4)改进的链式Lin-Kernihan启发式：我们将(2)和(3)的方法应用于链式Lin-Kernighan启发式，获得了显著的性能改进。

Starting from the polynomial time approximation scheme of Arora for the traveling salesman problem in the plane, we aimed at applying this theoretical result to practical solution methods and investigated a number of approaches. Main achievements are summarized as follows.(1) Efficient implementation of Arora's dynamic programming : based on the observation that each subproblem in his dynamic programming formulation can be compactly represented by a binary string based on the one-to-one correspondence between subproblems and well-formed parenthesis, we developed a fast scheme that maps a subproblem to its child subproblems. Using this scheme, we achieved two orders of magnitude speed up over a naive implementation. This enabled us to experiment on various uses of Aroras scheme.(2) Introducing the concept of Catalan decomposition and developing a dynamic programming scheme based on it : We replaced the rectangular decomposition of Arora by a topological decomposition of a graph and applied the implementation scheme of (1).(3) Development of alternating cycles contribution method : Given a tour to be improved (principal tour) and other tours for references (contributing tours), we extract the difference between the principal tour and each contributing tour in the form of a set of alternating cycles. We than select some of these alternating cycles, merge them with the principal tour and obtain the optimal tour in the resulting graph, hoping to get an improvement over the principal tour. The selection of alternating cycles is based on the flip gain of each cycle and the tractability of the resulting graph when all the selected cycles are added to the principal tour.(4) Development of boosted chained Lin-Kernihan heuristic : We applied the methods of (2) and (3) to the chained Lin-Kernighan heuristic and obtained a significant performance improvement.