Abstract: The colored traveling salesman problem(CTSP)is an extension of the classical multiple traveling salesman problem. In CTSP, there are multiple salesmen and multiple city nodes that need to be visited. Each salesman is allocated a particular color and each city carries 1, 2, or all salesmen's colors. Each city allows any salesmen with the same color to visit exactly once. The goal of CTSP is to determine the best travel route for each salesman to visit cities, so that, while meeting the above constraints, the total traveling distance of all the salesmen is the least.
CTSP originates from a class of practical applications in multi-machine scheduling. In this multi-machine system, the entire workspace is divided into multiple sections, and the processing tasks in each section have different accessibility for individual robots. Treating these processing tasks as city node locations and the robots executing tasks as salespersons, by setting the color attributes of salespersons and city nodes to control the differential access of robots to processing tasks, this problem is modeled as a CTSP problem. CTSP is an NP-hard combinatorial optimization problem with wide-ranging real-life applications, capable of solving many practical problems. For example, in modern logistics and distribution, customers may have preferences for delivery personnel; simultaneously, different types of goods may require different types of vehicles for delivery, and allocating different types of vehicles to transport different types of goods presents a challenge. Therefore, researching and developing effective algorithms to solve the CTSP problem is of great importance and contributes significantly to the current TSP literature.
This article proposes an effective adaptive large neighborhood search (ALNS) algorithm for the NP-hard problem CTSP. The algorithm consists of four important components: (1)a random greedy initial solution construction method, (2)four specialized destroyer and repair operations, (3)an efficient local search procedure, and (4)an adaptive mechanism for selecting destroyer and repair operations. The ALNS algorithm first generates an initial solution using a random greedy method and then performs a series of iterations. In each iteration, the algorithm adaptively selects the most suitable destroyer and repair operators, applies them to the current solution, and uses the local search procedure to further update the current solution. In each iteration, the algorithm updates the current search by finding the best solution and adjusting the weights of the destroyer and repair operators. The computational results of the proposed algorithm on three sets of benchmark instances from the literature demonstrate the proposed ALNS algorithm can effectively solve the CTSP problem on three sets of standard test instances from the literature. Especially, the ALNS algorithm can obtain better quality solutions in less runtime than the CTSP algorithm in the literature.
Future research could consider extensions of the CTSP, such as incorporating additional constraints like time windows of customers and vehicle capacities. This would be an interesting research direction with significant contributions to the current TSP literature. Additionally, there is a lack of exact algorithms for solving the CTSP in the literature. Researching exact algorithms for solving the CTSP would be a worthwhile direction. Furthermore, for the CTSP, exploring combinations and hybrid strategies of various algorithms, such as combining evolutionary algorithms with local search algorithms, could enhance the efficiency and quality of problem-solving. Additionally, leveraging machine learning techniques, especially deep learning methods, to tackle the CTSP is also a promising research direction.

Key words: colored traveling salesman, large neighborhood search, routing optimization

摘要： 着色旅行商问题(Colored Traveling Salesman Problem,CTSP)来源于一类多机器人加工实践应用,在现实生活中有着广泛的应用场景。在CTSP中,每个旅行商各自分配一种特定的颜色,每个城市节点携带一个或者多个旅行商的颜色值,这些城市节点只能被带有相同颜色的旅行商访问。针对CTSP这个NP难问题,本文提出了一种高效的自适应大邻域搜索算法来求解CTSP。该算法包括四个重要的组成部分:一个随机贪心的初始解构造方法、四个专门的破坏操作和修复操作、一个高效的局部搜索程序和一个自适应破坏和修复操作选择机制。在文献中三组标准算例集上的实验结果表明,本文提出的自适应大邻域搜索算法能够高效地求解CTSP问题。

关键词: 着色旅行商, 大邻域搜索, 路径优化