带冲突图的着色旅行商问题模型与算法

摘要：

着色旅行商问题是多旅行商问题的一个重要变种,它被广泛地应用于带有重叠区域的多机工程系统.现有的着色旅行商问题难以有效应对带冲突的场景,这种冲突通常表现为两个城市不允许被同一旅行商访问.受带冲突图的组合优化问题的启发,提出了带冲突图的着色旅行商问题,且给出了其形式化的表达.带冲突图的着色旅行商问题是一个NP难问题,精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解.为了求解更大规模的实例,提出了一个有效的模因算法.该模因算法采用了自适应大规模邻域搜索算子.对比模因算法和精确算法,模因算法在20个小规模实例中的9个结果更好,在18个实例上展现了其远超精确算法的求解速度.而比较模因算法和其他启发式算法,模因算法在全部14个中等规模实例上均取得了更好结果.此外,消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性.

关键词：旅行商问题、冲突图、组合优化、进化计算、模因算法

所属期刊栏目：60

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;深圳市人工智能与机器人研究院开放项目;上海市科技计划项目

在线出版日期：2024-01-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：135-144