TL;DR
This paper introduces the "Colored Traveling Salesman Problem" (CTSP), a more realistic variant of the classic Traveling Salesman Problem (TSP) where multiple agents (salesmen) have both private and shared sets of locations to visit. They propose two improved genetic algorithms (GAs) – a greedy GA and a hill-climbing GA – to efficiently solve CTSP, demonstrating that the hill-climbing GA significantly outperforms others in both convergence speed and solution quality.
What Problem Does This Paper Address?
The classic Traveling Salesman Problem (TSP) and its multi-agent extension, the Multiple Traveling Salesman Problem (MTSP), assume that all agents operate within a single, shared set of locations (cities). However, many real-world scenarios, such as scheduling in multi-machine engineering systems, involve agents with distinct private workspaces that partially overlap with a common public workspace. Existing MTSP formulations cannot adequately model these situations because they don't account for individual agent constraints and capabilities within their private domains. This paper addresses this gap by formulating the "Colored Traveling Salesman Problem" (CTSP), where each salesman has a unique set of "private" cities and also shares a set of "public" cities, with each set being "colored" differently to represent these distinct ownerships.
Methods
The authors propose a novel formulation for CTSP, which is then modeled as a 0-1 Integer Programming problem. To solve this NP-hard problem, they develop two enhanced Genetic Algorithms (GAs):
- Greedy GA: This approach aims to improve the quality of the initial population generated randomly. It uses a greedy criterion (shortest distance to the next unvisited city) to reorder the city sequences within each salesman's tour, leading to a better starting point for the evolutionary process.
- Hill-Climbing GA: This algorithm builds upon the standard GA by incorporating a local search optimization step. After the standard GA operations (selection, crossover, mutation) produce a new generation, a hill-climbing procedure is applied to the best individual. This local search attempts to further improve the solution by exploring neighboring states, preventing the GA from getting stuck in local optima and accelerating convergence.
The paper also details the dual-chromosome representation used in their GAs, where one chromosome represents the city sequence and another represents the salesman assignment for each city.
Datasets
The paper does not use pre-existing datasets. Instead, it introduces a custom benchmark problem for CTSP. This benchmark involves 51 cities, with one public city set and four private city sets assigned to four salesmen. The city distribution and distances are visually represented in Figure 7.
Key Insights and Ideas
- CTSP as a Realistic Extension: The core insight is that CTSP provides a more flexible and realistic framework for modeling problems where agents have distinct capabilities and constraints within shared environments.
- Greedy Initialization Boosts GA: Improving the initial population with a greedy heuristic significantly accelerates the convergence of the GA, leading to satisfactory solutions much faster than a standard GA.
- Hill-Climbing Escapes Local Optima: The hill-climbing component is crucial for overcoming the tendency of GAs to get trapped in local optima, enabling them to find better overall solutions.
- Hill-Climbing GA's Superiority: The combination of GA with hill-climbing proves to be the most effective, achieving better solution quality and significantly faster convergence compared to the basic GA and the greedy GA.
Key Results
The paper presents a case study comparing the basic GA, greedy GA, and hill-climbing GA on their custom CTSP benchmark.
- Convergence Rate: The greedy GA and hill-climbing GA converged much faster than the basic GA. The greedy and hill-climbing GAs reached their termination conditions in approximately 1300 generations, while the basic GA required around 14000 generations (and was run for 20000 epochs to achieve a comparable, though worse, result). The hill-climbing GA was particularly efficient, achieving a good solution within about 200 epochs.
- Solution Quality: The hill-climbing GA consistently produced the best results. The mean tour length achieved by the hill-climbing GA was 523.695 km, significantly better than the greedy GA (550.986 km) and the basic GA (648.831 km) after 2000 epochs. The best individual tour length found by the hill-climbing GA was 519.256 km.
Limitations and Future Work
- Limitations: The paper acknowledges that while GAs are effective for finding good-quality solutions, they do not guarantee optimality. The performance of the hill-climbing GA is dependent on the neighborhood search strategy (two-point swapping in this case).
- Future Work: The authors intend to research other heuristics for CTSP and explore its related applications. They also suggest investigating different neighborhood selection strategies for the hill-climbing algorithm.
Summary updated