求解旅行商问题的一种新方法

摘要：

目前关于旅行商问题的启发式算法主要分为两类:环路构造算法和环路改进算法.通过对两类近似算法的深入研究,提出了一种新的方法――简化模型法来求解旅行商问题.该方法通过排序和选择操作得到原网络图的简化模型,对简化模型中的路径进行重构得到旅行商问题的解.通过测试TSPLIB中的实例,表明用简化模型法求解旅行商问题解的质量高、收敛快,时耗小,该算法是实用的.

关键词：组合优化、旅行商问题、NP-Hard、简化模型

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2012-11-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：29-33