Cumulative Capacitated Colored Traveling Salesman Problem.

Area of Science:

• Operations Research
• Combinatorial Optimization
• Logistics

Background:

• The Colored Traveling Salesman Problem (CTSP) extends the classic TSP by incorporating city accessibility constraints based on colors.
• Real-world routing problems often require fast response times and consider customer capacities, necessitating specialized models.

Purpose of the Study:

• To introduce a novel city/customer-centric model, the Cumulative Capacitated CTSP (C2-CTSP), addressing practical routing challenges.
• To develop the first hypergraph and mathematical programming formulations for the C2-CTSP.
• To design and evaluate a General Variable Neighborhood Search (GVNS) metaheuristic for solving the C2-CTSP.

Main Methods:

• Developed hypergraph and mathematical programming formulations for the C2-CTSP.
• Designed a GVNS metaheuristic incorporating greedy backtracking for initialization, random perturbation operations (2-swap, reinsertion, double-bridge), and variable neighborhood descent for local search (neighborhood-list-2-opt, relocation, generalized partition crossover).
• Conducted extensive experiments comparing GVNS against genetic algorithms, ant colony systems, and other VNS methods on 20 test cases.

Main Results:

• The proposed GVNS demonstrated superior search ability and convergence rate compared to all competing algorithms, including tuned genetic algorithms and ant colony systems.
• Statistical analysis confirmed the significant performance advantage of GVNS.
• Analysis of GVNS variants validated the crucial contribution of each operator to its overall effectiveness.

Conclusions:

• The C2-CTSP model effectively addresses practical routing problems with fast response and capacity constraints.
• The developed GVNS metaheuristic is a highly effective and efficient method for solving the C2-CTSP.
• Each component of the GVNS plays a vital role in achieving its superior performance in complex routing scenarios.