A Performance Comparison of Genetic Algorithm’s Mutation Operators in n-Cities Open Loop Travelling Salesman Problem

Travelling Salesman Problem (TSP) is one of the most commonly studied optimization problem. In Open Loop Travelling Salesman Problem (OTSP), the salesman travels to all the given

m

cities but does not return to the city he started and each city is visited by salesman exactly once. However, a new problem of OTSP occur when the salesman does not visit all the given

m

cities, but only to visit

n

cities from the given

m

cities. This problem called

n

-Cities Open Loop Travelling Salesman Problem (

n

OTSP), which seems to be more close to the real-life transportation problem. In this paper, Genetic Algorithm (GA) with different mutation operators is implemented to the

n

OTSP in order to investigate which mutation operators give the optimal solution in minimizing the distance and computational time of the

n

visited cities. The mutation operators are inversion, displacement, pairwise swap and the combination of the above three operators. The results of these comparisons show that the GA-inversion mutation operator can achieve better solution in minimizing the total distance of the tour. In addition, the GA with combination of three mutation operators has great potential in reducing the computation time.