摘要
目前关于旅行商问题的启发式算法主要分为两类:环路构造算法和环路改进算法。通过对两类近似算法的深入研究,提出了一种新的方法——简化模型法来求解旅行商问题。该方法通过排序和选择操作得到原网络图的简化模型,对简化模型中的路径进行重构得到旅行商问题的解。通过测试TSPLIB中的实例,表明用简化模型法求解旅行商问题解的质量高、收敛快,时耗小,该算法是实用的。
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.
出处
《华东交通大学学报》
2012年第5期29-33,共5页
Journal of East China Jiaotong University
基金
国家自然科学基金项目(61165004)
江西省教育厅青年基金项目(GJJ12321)
关键词
组合优化
旅行商问题
NP-HARD
简化模型
combinatorial optimization
traveling salesman problem
NP-Hard
simplified model
