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

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