权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

路线优化问题的近似算法：利用几何结构及其在大规模问题中的应用

基本信息

批准号：
10205225
负责人：
TAMAKI Hisao
金额：
$ 5.76万
依托单位：
Meiji University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

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.

从平面上旅行商问题的Arora多项式时间近似方案出发，我们旨在将这一理论结果应用到实际的求解方法中，并研究了一些方法。主要成果概括如下。(1)阿罗拉的动态规划的有效实施：根据观察，在他的动态规划制定的每个子问题可以通过一个二进制字符串基于子问题和格式良好的括号之间的一对一的对应关系compatible表示，我们开发了一个快速的计划，映射到其子问题的子问题。使用这个方案，我们实现了两个数量级的速度比一个天真的实现。这使我们能够对Aroras方案的各种用途进行实验。(2)引入Catalan分解的概念，并在此基础上提出一个动态规划方案：用图的拓扑分解代替Arora的矩形分解，并应用（1）的实现方案。(3)交替循环贡献方法的发展：给定一个待改进的旅游（主旅游）和其他图尔斯参考（贡献图尔斯），我们提取主旅游和每个贡献旅游之间的差异，在一组交替循环的形式。然后，我们选择这些交替循环中的一些，将它们与主巡回合并，并在结果图中获得最佳巡回，希望得到对主巡回的改进。交替循环的选择是基于每个循环的翻转增益和当所有选定的循环被添加到主巡回时所得到的图形的易处理性。(4)提升链式Lin-Kernihan启发式算法的开发：我们将（2）和（3）的方法应用于链式Lin-Kernihan启发式算法，并获得了显着的性能改善。