Finding the Shortest Hamiltonian Path for Iranian Cities,using Tabu Search and Memetic algorithms

The traveling salesman problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-hard problems. This means that no known algorithm is guaranteed to solve all TSP instances to optimality within reasonable execution time. Due to the different nature of metaheuristics algorithms and the importance and application of TSP in different fields, in this paper the shortest Hamiltonian path is achieved between 423 Iranian cities by the two types of algorithms. for the first time Tabu search as a single-solution-based algorithm and memetic algorithm as a population-based algorithm is selected. To evaluate the accuracy and efficiency of the proposed algorithms, standard problems with size from 16 cities to 1060 cities have been used. Results demonstrate the performance and effectiveness of proposed algorithms. Java programming language to code algorithms has been used in this research. Parameters tuning for each algorithm is done separately and ultimately the best value for each parameter has been determined. Finally, the performances of each algorithm determined by quality of solution and CPU time and the results have been compared.