Speeding up Travelling Salesman Problem Using Hybrid Algorithm

Abstract

Traveling salesman problem (TSP) is one of the most popular optimization problems and attracts great attention from many researchers. Several studies have suggested different approaches to solving two-dimensional TSP. This research will present an enhancement for genetic algorithm by using a 2-opt method to solve TSP, such that we will use a 2-opt method to generate the initial population for genetic algorithm, and the roulette wheel choice strategy, the order crossover operator and 2-opt method for mutation operator will be highlighted.

The experiments of  TSP using five real TSP problems taken from the Traveling Salesman Problem Library (TSPLIB), including eil51, st70, pr76,eil76, rd100  (the numbers attached to the problem names represent the number of cities). The error rate of proposed algorithm is (2.233818, 0.030299, 0.057161, 0.084524, 0.123523) . While the error rate of  the traditional GA is (2.300088, 0.052921, 0.064016, 0.091775, 0.14666). The results showed the proposed algorithm is acquired higher quality solutions within a reasonable computational time compared to the traditional genetic algorithm. The programming language Pythom3 was used in programming the proposed method.