| 求解旅行商问题的一种新方法 |
| |
| 引用本文： | 吕善国,曹义亲,陈红丽.求解旅行商问题的一种新方法[J].华东交通大学学报,2012(5):29-33. |
| |
| 作者姓名： | 吕善国 曹义亲 陈红丽 |
| |
| 作者单位： | 华东交通大学软件学院,江西南昌330013 |
| |
| 基金项目： | 国家自然科学基金项目(61165004);江西省教育厅青年基金项目(GJJ12321) |
| |
| 摘 要： | 目前关于旅行商问题的启发式算法主要分为两类:环路构造算法和环路改进算法.通过对两类近似算法的深入研究,提出了一种新的方法――简化模型法来求解旅行商问题.该方法通过排序和选择操作得到原网络图的简化模型,对简化模型中的路径进行重构得到旅行商问题的解.通过测试TSPLIB中的实例,表明用简化模型法求解旅行商问题解的质量高、收敛快,时耗小,该算法是实用的.
|
| 关 键 词： | 组合优化 旅行商问题 NP-Hard 简化模型 |
A New Algorithm for Traveling Salesman Problem |
| |
| Lv Shanguo,Cao Yiqin,Chen Hongli.A New Algorithm for Traveling Salesman Problem[J].Journal of East China Jiaotong University,2012(5):29-33. |
| |
| Authors: | Lv Shanguo Cao Yiqin Chen Hongli |
| |
| Institution: | (School of Software,East China Jiaotong University,Nanchang 330013,China) |
| |
| Abstract: | The main heuristic algorithm for TSP falls into two classes:tour construction algorithms and tour improvement algorithms.Through research on the two kinds of approximate algorithms of TSP and in order to solve TSP,we propose a new algorithm called simplified model--the new SModel,which is formed by sorting and selecting the initial network.The new algorithm generates a global tour by reconstructing all paths in SModel.By testing the instances of TSPLIB,the paper demonstrates that the proposed algorithm is feasible,time-saving and practical. |
| |
| Keywords: | combinatorial optimization traveling salesman problem NP-Hard simplified model |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
