Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for...

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• Traveling Salesman Problem (TSP) and Generalized Traveling Salesman Problem (GTSP) are significant combinatorial optimization challenges.
• GTSP is more complex than TSP, with fewer studies focusing on its solution, especially using genetic algorithms (GA).

Purpose of the Study:

• To present a novel genetic algorithm, the generalized chromosome-based genetic algorithm (GCGA), for solving both TSP and GTSP.
• To enable a uniform algorithmic approach for both problem types, reducing complexity and the need for transformations.

Main Methods:

• Generalizing the conventional chromosome structure to a 'generalized chromosome' (GC).
• Developing a genetic scheme, GCGA, utilizing the generalized chromosome.
• Applying GCGA to solve 41 benchmark GTSP and TSP instances with known optimal solutions.

Main Results:

• The proposed GCGA successfully solved all 41 benchmark test problems.
• GCGA demonstrated the ability to solve GTSP directly, without requiring intermediate transformation to TSP.
• The algorithm validates the effectiveness of the generalized chromosome approach for uniform problem-solving.

Conclusions:

• GCGA provides a unified and effective method for solving both TSP and GTSP.
• The generalized chromosome structure is a viable approach for tackling complex combinatorial optimization problems.
• This research contributes a novel algorithm for GTSP, addressing a gap in existing literature.