| 基于求解TSP问题的双向扩展差额算法 |
| |
| 引用本文： | 饶卫振,金淳,黄英艺.基于求解TSP问题的双向扩展差额算法[J].管理工程学报,2011,25(2). |
| |
| 作者姓名： | 饶卫振 金淳 黄英艺 |
| |
| 作者单位： | 大连理工大学系统工程研究所,辽宁,大连,116024 |
| |
| 基金项目： | 国家自然科学基金资助项目，辽宁省自然科学基金资助项目 |
| |
| 摘 要： | 旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.
|
| 关 键 词： | 双向扩展差额算法 两端延伸最近城市搜索法 启发式算法 TSP问题 |
Two Directions Moving With Difference Algorithms to Solve Traveling Salesman Problems |
| |
| RAO Wei-zhen,JIN Chun,HUANG Ying-yi.Two Directions Moving With Difference Algorithms to Solve Traveling Salesman Problems[J].Journal of Industrial Engineering and Engineering Management,2011,25(2). |
| |
| Authors: | RAO Wei-zhen JIN Chun HUANG Ying-yi |
| |
| Affiliation: | RAO Wei-zhen,JIN Chun,HUANG Ying-yi(Institute of Systems Engineering,Dalian University of Technology,Dalian 116024,China) |
| |
| Abstract: | Traveling salesman problems(TSP) are an optimization problem that has been studied extensively.The primary objective of TSP is to locate the shortest route for each customer visit by salespersons.The approximate algorithm is a better choice than the exact algorithms in order to solve TSP.Approximate algorithms can be divided into two classes:construction algorithms and improvement algorithms.A construction algorithm builds a tour with no attempts to improve tour logistics after it is constructed.Algorithms ... |
| |
| Keywords: | two directions moving with difference algorithm the both ends extending nearest city searching algorithm heuristics algorithms traveling salesman problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
