一种求解多旅行商问题双层降解混合算法*

为了能快速近似求解多旅行商问题，提出了双层降解混合算法。首层降解根据问题空间展布特性，利用聚类技术将问题分解为若干子类问题，底层降解将子类问题转换为经典的旅行商问题，通过缩减子类问题初始状态下的边数量，使得子类问题求解难度得到再度降低，最终利用精确算法进行求解能够得到高质量优化解。对比实验表明双层降解混合算法具有计算时间短和求解质量高的优势，说明了新算法的有效性和高效性。

Two-level degradation hybrid algorithm for multiple traveling salesman problem

This paper put forward a new two-level degradation hybrid algorithm for quickly solving the multiple traveling salesman problems. Top-level degradation divided the original problem into some sub-class problems according to the distribution property of the problem space. Low-level degradation converted these sub-class problems to some corresponding classical traveling salesman problems. The difficulty solving these sub-class problems would be cut down while decreasing the initial edge number of these problems. Finally, could solve high-quality solutions by exact algorithm. The contrast experiments with the same type algorithms show that the computation time of the new algorithm is shorter and the solving quality of the new algorithm is higher. This shows that the new algorithm is effective and efficient.