Preliminary Analysis on the Relative Solution Space Sizes for MTSP with Genetic Algorithm.

It is well known that the chromosome design is pivotal to solve the multiple traveling salesman problems with genetic algorithm. A well-designed chromosome coding can eliminate or reduce the redundant solutions. One chromosome and two chromosome design methods and a recently proposed two-part chromosome design are firstly introduced in this paper. Then the preliminary quantitative comparison analysis of the solution spaces of three different chromosome design methods is presented when the number of cities is linear with the travelers. The concept of relative solution space is proposed in order to compare the relative size of the solution spaces. The solution space of two-part chromosome design is much smaller than those of the traditional chromosome design. The result given in this paper provides a good guideline for the possible algorithmic design and engineering applications. [ABSTRACT FROM AUTHOR]