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

被引：3

作者：

林冬梅 ^{[1
]}

王东 ^{[2
]}

李娅 ^{[2
]}

机构：

[1] 佛山科学技术学院信息与教育技术中心

[2] 佛山科学技术学院计算机科学与技术系

来源：

计算机应用研究 | 2011年 / 28卷 / 08期

基金：

广东省自然科学基金;

关键词：

多旅行商问题; 双层降解; 混合算法; 聚类; 化简;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：2876 / 2879

页数：4