Colored Traveling Salesman Problems: Models, Solutions, and Applications
本文首次系统综述彩色旅行商问题（CTSP），统一形式化其模型与变体，比较与经典TSP、MTSP、VRP的异同，介绍精确、启发式、大规模、学习及并行求解方法，并回顾在调度多机任务系统中的应用。
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.