Selection of solution strategies for colored traveling salesman problems with different city distribution

摘要

The colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. In CTSP, each salesman is allocated a particular color and each city carrying one to all salesmen' colors allows any salesman of the same color to visit exactly once. There are two strategies to address CTSP, i.e., the direct and transformed. The former is to solve a CTSP directly while the latter addresses it by decomposing it into simpler sub-problems first. Given a CTSP with different city color distribution, the solutions obtained by them may be different. We consider that there should be a certain regularity for selecting a proper solution strategy for a CTSP according to its city color distribution. This paper focuses on investigating such a regularity and establishes some principles for the solution strategies selection. First, we propose a city coloring scheme and algorithm for allocating proportionally different colors to the cities in each cluster. Then, we define a color dispersion degree as the percentage of color-changed cities in each city cluster. Finally, some experiments are conducted to track the regularity for selecting a proper strategy for solving a CTSP according to its city color distribution. The results show that the more scattered the city color distribution, the better the solution achieved by the direct strategy, using the same genetic algorithm. Also, it suggests that the solution algorithm combined with proximity operations, e.g., greedy operation, can efficiently accommodate the fluctuating city color distribution in CTSP.