Colored Traveling Salesman Problems: Models, Solutions, and Applications

Area of Science:

• Operations Research
• Combinatorial Optimization
• Computer Science

Background:

• The colored traveling salesman problem (CTSP) models salesman homogeneity and city assignment relationships using colors.
• CTSP is a generalization of the traveling salesman problem (TSP) and multiple traveling salesman problems (MTSP).
• Despite its potential, CTSP solutions and applications in logistics, manufacturing, and transportation require further exploration.

Purpose of the Study:

• To conduct the first comprehensive survey on CTSPs, fostering understanding, research, and applications.
• To organize the CTSP development timeline and re-formalize existing CTSPs and variants.
• To provide a unified perspective on CTSPs, their solutions, and applications.

Main Methods:

• Systematic review and synthesis of existing CTSP literature.
• Comparative analysis of CTSPs with TSP, MTSP, and vehicle routing problems (VRPs).
• Categorization and explanation of exact, heuristic, large-scale, learning-based, and parallel solution approaches for CTSPs.

Main Results:

• A unified formalization of CTSPs and their variants with diverse objectives and constraints.
• A clear distinction and connection between CTSPs, TSPs, MTSPs, and VRPs.
• An overview of solution methodologies and a review of CTSP applications in multimachine mission systems scheduling.

Conclusions:

• This survey serves as a foundational reference for CTSP research and related sequencing problems.
• It highlights the need for further exploration of CTSP solutions and applications.
• It identifies future research directions and potential applications for CTSPs.