A swarm intelligence approach for the colored traveling salesman problem

摘要

This paper addresses the recently introduced colored traveling salesman problem (CTSP), which is a variant of the multiple traveling salesman problem (MTSP). In the MTSP, given a set of cities, there are multiple salesman to visit these cities though each city must be visited exactly once by one salesman only. On the other hand in case of the CTSP, every salesman have their exclusive cities to visit and a group of shared cities that are shared among different salesmen but should be visited exactly once by one salesman only. In this paper, an artificial bee colony (ABC) algorithm based approach is proposed for the CTSP and its superiority over other state-of-the-art approaches is demonstrated experimentally in terms of both quality of solution and computational time on the benchmark instances available in the literature. In addition, the encoding scheme that we have used to represent a CTSP solution within the ABC algorithm is theoretically analyzed and it is shown that our encoding scheme yields a solution space that is considerably smaller than the scheme used by the state-of-the-art approaches for the CTSP.