Traveling salesman problems (TSP) and generalized traveling salesman problems (GTSP) are two kinds of well known and challenging combinatorial optimization problems with much diversified application fields. Between the two application problems the GTSP is more complex than TSP. Many researchers have studied TSP extensively, but relatively fewer studies pay attention to GTSP, and also its solution using genetic algorithm (GA). In this paper, the structure of conventional chromosome is generalized to be a chromosome termed as a generalized chromosome (GC). A genetic scheme named as generalized-chromosome-based genetic algorithm (GCGA) is also presented. The proposed GCGA enables GTSP and TSP to be solved under a uniform algorithm mode. Forty one benchmark test problems have been solved with the known optimal solutions using the proposed algorithm to verify its validity. The test results show that GCGA can directly solve GTSP without the need of intermediate transformation to TSP.

• Received 28 November 2003

DOI:https://doi.org/10.1103/PhysRevE.70.016701