Exact and Local Search Methods for Solving Travelling Salesman Problem with Practical Application

Sajjad Majeed Jasim; Faez Hassan Ali

doi:10.24996/ijs.2019.60.5.22

Authors

Sajjad Majeed Jasim Department of Mathematics, College of Science, Al-Mustansiryah University, Baghdad, Iraq
Faez Hassan Ali Department of Mathematics, College of Science, Al-Mustansiryah University, Baghdad, Iraq

DOI:

https://doi.org/10.24996/ijs.2019.60.5.22

Keywords:

Travelling Salesman Problem, Greedy Method, Improved Minimum Distance Method, Branch and Bound Technique, Genetic Algorithm, Simulated Annealing

Abstract

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.