Abstract: The colored traveling salesman problem is an important variant of the multiple traveling salesman problem, which is widely used to model optimization problems in multi-machine engineering systems with overlapping areas. The colored traveling salesman problem is difficult to effectively address in scenarios with conflict, which often arises when two cities cannot be visited by the same salesman. Inspired by existing combinatorial optimization problems with conflict graph, a colored traveling salesman problem with conflict graph is proposed and formally defined in this paper. The colored traveling salesman problem with conflict graph is NP-hard, and the CPLEX exact solver can only optimally solve small-scale problem instances. To solve larger instances, an effective memetic algorithm is proposed in this paper, which integrates an adaptive large neighborhood search (ALNS) to perform local optimization. Compared with the exact algorithms, the proposed memetic algorithm finds better results for 9 out of 20 small-scale instances, and uses less computational time for 18?instances. Compared with heuristic algorithms, the proposed memetic algorithm achieves better results for all 14?medium-scale instances. Finally, an ablation experiment is performed to verify the effectiveness of ALNS used in the proposed memetic algorithm.

Key words: traveling salesman problem, conflict graph, combinatorial optimization, evolutionary computation, memetic algorithm

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

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