计算机工程与应用2024，Vol.60Issue(1)：135-144,10.DOI:10.3778/j.issn.1002-8331.2302-0306
带冲突图的着色旅行商问题模型与算法
Colored Traveling Salesman Problem with Conflict Graph:Model and Algorithms
摘要
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 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.关键词
旅行商问题/冲突图/组合优化/进化计算/模因算法Key words
traveling salesman problem/conflict graph/combinatorial optimization/evolutionary computation/memetic algorithm分类
信息技术与安全科学引用本文复制引用
徐文强,周扬名,王喆..带冲突图的着色旅行商问题模型与算法[J].计算机工程与应用,2024,60(1):135-144,10.基金项目
国家自然科学基金(61903144) （61903144）
深圳市人工智能与机器人研究院开放项目(AC01202005002) （AC01202005002）
上海市科技计划项目(21511100800). （21511100800）
