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

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