文献类型：期刊文献

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

英文题名：Colored Traveling Salesman Problem with Conflict Graph:Model and Algorithms

作者：徐文强[1];周扬名[2];王喆[1]

机构：[1]华东理工大学信息科学与工程学院,上海200237;[2]上海交通大学中美物流研究院,上海200030

年份：2024

卷号：60

期号：1

起止页码：135

中文期刊名：计算机工程与应用

外文期刊名：Computer Engineering and Applications

收录：CSTPCD;;EI(收录号：20241215760089);北大核心:【北大核心2023】；CSCD:【CSCD_E2023_2024】；

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

语种：中文

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

外文关键词：traveling salesman problem;conflict graph;combinatorial optimization;evolutionary computation;memetic algorithm

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