Colored Traveling Salesman Problems: Models, Solutions, and Applications

A colored traveling salesman problem (CTSP) can subtly and thoroughly depict the homogeneity of salesmen and the assignment relationships between them and cities by using colors. It has been proven to be a generalization of existing traveling salesman problems (TSPs) and multiple TSPs (MTSPs). Nevertheless, its solutions and applications to various areas, e.g., logistic, manufacturing, and transporation, remain to be explored. To promote the understanding, research, and applications of CTSPs, we carry out the first survey on CTSPs by: 1) organizing the CTSP development timeline and re-formalizing the existing CTSPs as well as typical variants with different objectives and constraints in a unified way; 2) comparing CTSPs with existing TSPs, MTSPs, and vehicle routing problems (VRPs), and revealing their differences and connections; 3) introducing the main principles and procedures of the exact, heuristic, large-scale, learning-based, and parallel solutions of CTSPs; 4) reviewing the typical applications of CTSPs to scheduling a variety of multimachine mission systems; and 5) discussing the future research directions of CTSPs and their potential applications. This article is not only the first survey of CTSPs but can also serve as a reference for research on related sequencing problems such as TSPs, MTSPs, and VRPs.