A Decomposition Approach to Colored Traveling Salesman Problems

As a well-known combinatorial optimization problem, multiple traveling salesman problem (MTSP) fails to characterize some application problems where cities may have different accessibility for some but not necessarily all salesmen. This work proposes a colored traveling salesman problem (CTSP) in which a city has one to multiple colors allowing any salesman with the same color to visit. It presents a decomposition approach that converts CTSP into a combination of several individual traveling salesman problems (TSPs) and one MTSP for an important class of CTSP. To solve the transformed one, this work proposes a modified greedy algorithm allowing multi-colored city assignment during city search and adopts the formerly presented simulated annealing genetic algorithm. A dual-bridge waterjet cutting example is utilized to compare the presented decomposition approach and direct one. The results show that the former can achieve a better solution than the latter if the cities of same color(s) are clumped.