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

作者：刘昌军; 苏琴; 卫军胡; 陶维丽

来源：系统仿真学报, 2008, (24): 6858-6861+6870.

• 嵌套分割算法
• 旅行商问题
• 2-opt算法
• 并行算法 nested partitions method
• traveling salesman problem
• 2-opt
• parallel algorithm

嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可能域加以改良,最后提出算法的并行化实现方法。实验证明嵌套分割算法在解决TSP问题时可以获得高质量的解,并且具有良好的时间性能。

• 单位
  西安交通大学机械制造系统工程国家重点实验室