| 嵌套分割算法在旅行商问题上的应用 |
| |
| 引用本文： | 刘昌军,苏琴,卫军胡,陶维丽.嵌套分割算法在旅行商问题上的应用[J].系统仿真学报,2008,20(24). |
| |
| 作者姓名： | 刘昌军 苏琴 卫军胡 陶维丽 |
| |
| 作者单位： | 西安交通大学系统工程研究所机械制造系统工程国家重点实验室 |
| |
| 基金项目： | 国家自然科学基金
，
863高科技计划
，
陕西省自然科学基础研究计划
|
| |
| 摘 要： | 嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可能域加以改良,最后提出算法的并行化实现方法。实验证明嵌套分割算法在解决TSP问题时可以获得高质量的解,并且具有良好的时间性能。
|
| 关 键 词： | 嵌套分割算法 旅行商问题 2-opt算法 并行算法 |
Application of Nested Partitions Method in Traveling Salesman Problem |
| |
| LIU Chang-jun,SU Qin,WEI Jun-hu,TAO Wei-li.Application of Nested Partitions Method in Traveling Salesman Problem[J].Journal of System Simulation,2008,20(24). |
| |
| Authors: | LIU Chang-jun SU Qin WEI Jun-hu TAO Wei-li |
| |
| Abstract: | 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. |
| |
| Keywords: | nested partitions method traveling salesman problem 2-opt parallel algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
