Open AccessExact and Local Search Methods for Solving Travelling Salesman Problem with Practical Application
Author(s) -
Sajjad Majeed Jasim,
Faez Hassan Ali
Publication year - 2019
Publication title -
iraqi journal of science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.152
H-Index - 4
eISSN - 2312-1637
pISSN - 0067-2904
DOI - 10.24996/ijs.2019.60.5.22
Subject(s) - travelling salesman problem , simulated annealing , mathematical optimization , local search (optimization) , local optimum , genetic algorithm , mathematics , hill climbing , computer science , 2 opt , matrix (chemical analysis) , algorithm , materials science , composite material
This paper investigates some exact and local search methods to solve the traveling salesman problem. The Branch and Bound technique (BABT) is proposed, as an exact method, with two models. In addition, the classical Genetic Algorithm (GA) and Simulated Annealing (SA) are discussed and applied as local search methods. To improve the performance of GA we propose two kinds of improvements for GA; the first is called improved GA (IGA) and the second is Hybrid GA (HGA).
The IGA gives best results than GA and SA, while the HGA is the best local search method for all within a reasonable time for 5 ≤ n ≤ 2000, where n is the number of visited cities. An effective method of reducing the size of the TSP matrix was proposed with the existence of successive rules. The problem of the total cost of Iraqi cities was also discussed and solved by some methods in addition to local search methods to obtain the optimal solution.