混合伊藤算法求解多尺度着色旅行商问题

作者：韩舒宁; 徐敏; 董学士; 林青; 沈凡凡

来源：计算机应用, 2021, 1-7.

• 混合伊藤算法
• 着色旅行商问题
• 蚁群算法
• 漂移算子
• 波动算子

着色旅行商问题（CTSP）是多旅行商问题（MTSP）与旅行商问题（TSP）的一种扩展，主要应用于含重复区域的多机调度（MES）等工程问题。CTSP是NP完全问题，尽管一些学者尝试采用遗传算法、模拟退化等方法求解该问题，但相关文献求解的问题尺度有限，且速度和求解质量上不尽如意。基于此，尝试采用一种基于均匀设计（UD）融合蚁群算法（ACO）和伊藤算法（IT?）的混合伊藤算法（UDHIT?）来求解该问题。该算法采用均匀设计来选择混合伊藤算法合适的参数组合，借助于蚁群算法的概率图模型来产生可行解，并利用UDHIT?算法的漂移和波动算子优化。实验的结果表明：UDHIT?求解多尺度CTSP的最优解和平均解比传统遗传算法、蚁群算法和伊藤算法有所改善。

• 单位
  长江航道规划设计研究院; 青岛大学; 南京审计大学