嵌套分割算法在旅行商问题上的应用  

Application of Nested Partitions Method in Traveling Salesman Problem

作　　者：刘昌军[1] 苏琴[1] 卫军胡[1] 陶维丽[1] 

机构地区：[1]西安交通大学系统工程研究所,机械制造系统工程国家重点实验室,西安710049

出　　处：《系统仿真学报》2008年第24期6858-6861,6870,共5页Journal of System Simulation

基　　金：国家自然科学基金(60736027,60704033);863高科技计划(2007AA04Z154);陕西省自然科学基础研究计划(2007F41)

摘　　要：嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可能域加以改良,最后提出算法的并行化实现方法。实验证明嵌套分割算法在解决TSP问题时可以获得高质量的解,并且具有良好的时间性能。The Nested Partitions Method （NPM） is a new global optimization method recently proposed, which can be applied to solve many large-scale discrete optimization problems. The main idea of this method was introduced and its application to the Traveling Salesman Problem was proposed. Based on the analysis of the four arithmetic operators of the NPM for the TSP, the 2-opt algorithm was combined in the local search and the initial most promising region was improved. Numerical results show the high accuracy and efficiency of the algorithm. Finally, the parallel version of the NPM was proposed.

关 键 词：嵌套分割算法 旅行商问题 2-opt算法 并行算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]