Journal
COMPUTACION Y SISTEMAS
Volume 22, Issue 2, Pages 491-503Publisher
IPN, CENTRO INVESTIGAVION COMPUTACION
DOI: 10.13053/CyS-22-2-2956
Keywords
Genetic algorithm; multiple traveling salesman problem; group theory; crossover operator; 2-opt mutation
Categories
Ask authors/readers for more resources
In this paper, we proposed a new crossover operator and a population initialization method for solving multiple traveling salesmen (MTSP) problem in genetic algorithm (GA) framework. The group theory based technique of intital population generation ensures the uniqueness of members in population, hence no redundancy in the search space and also remove the random initialization effect. The new crossover is based on the intuitive idea that the city in sub optimal / optimal tours occurs at same position. In this crossover the Hamming distance is preserved and there is very less chance to generate child same as members in the population, so diversity of the population is not much affected. For efficient representation of search space, we exploited the multi-chromosome representation technique to encode the search space of MTSP. We evaluate and compare the proposed technique with the methods using crossover TCX, ORX +A, CYX +A and PMX +A reported in [ 35] for two standard objective functions of the MTSP, namely, minimising total travel cost of m tours of the m salesman and minimising the longest tour cast travel by any one salesman. Experimental results show that the GA with proposed population initialization and crossover gives better result compared to all four methods for second objective, however, in very few cases slightly degraded result for first objective.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available