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

doi:10.3778/j.issn.1002-8331.2302-0306

摘要/Abstract

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

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

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

徐文强, 周扬名, 王喆. 带冲突图的着色旅行商问题模型与算法[J]. 计算机工程与应用, 2024, 60(1): 135-144.

XU Wenqiang, ZHOU Yangming, WANG Zhe. Colored Traveling Salesman Problem with Conflict Graph: Model and Algorithms[J]. Computer Engineering and Applications, 2024, 60(1): 135-144.

参考文献

[1] LI J, ZHOU M C, SUN Q, et al. Colored traveling salesman problem[J]. IEEE Transactions on Cybernetics, 2014, 45(11): 2390-2401.
[2] 孟祥虎. 着色旅行商问题及其动态化研究[D]. 南京: 东南大学, 2017.
MENG X H. A colored traveling salesman problem and its dynamics problem[D]. Nanjing: Southeast University, 2017.
[3] MENG X H, LI J, ZHOU M C, et al. Population-based incremental learning algorithm for a serial colored traveling salesman problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 48(2): 277-288.
[4] MENG X H, LI J, ZHOU M C, et al. A dynamic colored traveling salesman problem with varying edge weights[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(8): 13549-13558.
[5] 徐向平. 广义着色旅行商问题及其算法研究[D]. 南京: 东南大学, 2021.
XU X P. Research on general colored traveling salesman problem and its algorithm[D]. Nanjing: Southeast University, 2021.
[6] XU X P, LI J, ZHOU M C. Bi-objective colored traveling salesman problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(7): 6326-6336.
[7] XU X P, LI J, ZHOU M, et al. Precedence-constrained colored traveling salesman problem: an augmented variable neighborhood search approach[J]. IEEE Transactions on Cybernetics, 2021, 52(9): 9797-9808.
[8] 董学士, 董文永, 蔡永乐. 混合算法求解着色瓶颈旅行商问题[J]. 计算机研究与发展, 2018, 55(11): 2372-2385.
DONG X S, DONG W Y, CAI Y L. Hybrid algorithm for colored bottleneck traveling salesman problem[J]. Journal of Computer Research and Development, 2018, 55(11): 2372-2385.
[9] 董文永, 董学士, 王豫峰. 改进蜂群算法求解大规模着色瓶颈旅行商问题[J]. 通信学报, 2018, 39(12): 18-29.
DONG W Y, DONG X S, WANG Y F. Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem[J]. Journal on Communications, 2018, 39(12): 18-29.
[10] DONG X, CAI Y. A novel genetic algorithm for large scale colored balanced traveling salesman problem[J]. Future Generation Computer Systems, 2019, 95: 727-742.
[11] DONG X, XU M, LIN Q, et al. IT? algorithm with local search for large scale multiple balanced traveling salesmen problem[J]. Knowledge-Based Systems, 2021, 229: 107330.
[12] 代星. 最大值最小化着色旅行商问题的研究及应用[D]. 南京: 东南大学, 2017.
DAI X. Research on a min-max colored traveling problem and its application[D]. Nanjing: Southeast University, 2017.
[13] 王东明, 代星, 孟祥虎, 等. 基于萤火虫算法的最大值最小化着色旅行商问题的求解[J]. 扬州大学学报 (自然科学版), 2019, 22(2): 56-60.
WANG D M, DAI X, MENG X H, et al. Firefly algorithm for min-max colored traveling salesman problem[J]. Journal of Yangzhou University (Natural Science Edition), 2019, 22(2): 56-60.
[14] MENG X H, LI J, DAI X, et al. Variable neighborhood search for a colored traveling salesman problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(4): 1018-1026.
[15] XU X P, LI J, ZHOU M C. Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(3): 1583-1593.
[16] HE P, HAO J K. Iterated two-phase local search for the colored traveling salesmen problem[J]. Engineering Applications of Artificial Intelligence, 2021, 97: 104018.
[17] HE P, HAO J K, WU Q. Grouping memetic search for the colored traveling salesmen problem[J]. Information Sciences, 2021, 570: 689-707.
[18] 韩舒宁, 徐敏, 董学士, 等. 混合伊藤算法求解多尺度着色旅行商问题[J]. 计算机应用, 2022, 42(3): 695-700.
HAN S N, XU M, DONG X S, et al. Hybrid IT? algorithm for multi?scale colored traveling salesman problem[J]. Journal of Computer Applications, 2022, 42(3): 695-700.
[19] PANDIRI V, SINGH A. A swarm intelligence approach for the colored traveling salesman problem[J]. Applied Intelligence, 2018, 48(11): 4412-4428.
[20] DONG X, LIN Q, XU M, et al. Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem[J]. IET Intelligent Transport Systems, 2019, 13(10): 1483-1491.
[21] ZHOU Y, XU W, FU Z H, et al. Solving colored traveling salesman problem via multi-neighborhood simulated annealing search[C]//2021 IEEE International Conference on Networking, Sensing and Control (ICNSC), 2021: 1-6.
[22] ZHOU Y, XU W, FU Z H, et al. Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 16072-16082.
[23] PFERSCHY U, SCHAUER J. The knapsack problem with conflict graphs[J]. Journal of Graph Algorithms and Applications, 2009, 13(2): 233-249.
[24] BETTINELLI A, CACCHIANI V, MALAGUTI E. A branch-and-bound algorithm for the knapsack problem with conflict graph[J]. INFORMS Journal on Computing, 2017, 29(3): 457-473.
[25] Lü Z, HAO J K. A memetic algorithm for graph coloring[J]. European Journal of Operational Research, 2010, 203(1): 241-250.
[26] KRASNOGOR N, SMITH J. A tutorial for competent memetic algorithms: model, taxonomy, and design issues[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(5): 474-488.
[27] WOOLSON R F. Wilcoxon signed‐rank test[J]. Wiley Encyclopedia of Clinical Trials, 2007: 1-3.