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

来源：计算机工程与应用杂志2024年第1期北京时间：

作者：徐文强, 周扬名, 王喆

单位：1.华东理工大学 信息科学与工程学院，上海 200237；2.上海交通大学 中美物流研究院，上海 200030

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

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