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

Two-level degradation hybrid algorithm for multiple traveling salesman problem

作　　者：林冬梅[1] 王东[2] 李娅[2] 

机构地区：[1]佛山科学技术学院信息与教育技术中心,广东佛山528000 [2]佛山科学技术学院计算机科学与技术系,广东佛山528000

出　　处：《计算机应用研究》2011年第8期2876-2879,共4页Application Research of Computers

基　　金：广东省自然科学基金资助项目(10152800001000029;10252800001000001)

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

关 键 词：多旅行商问题 双层降解 混合算法 聚类 化简 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]