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

  • 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

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.

Published
May 26, 2019
How to Cite
JASIM, Sajjad Majeed; ALI, Faez Hassan. Exact and Local Search Methods for Solving Travelling Salesman Problem with Practical Application. Iraqi Journal of Science, [S.l.], v. 60, n. 5, p. 1138-1153, may 2019. ISSN 2312-1637. Available at: <http://scbaghdad.edu.iq/eijs/index.php/eijs/article/view/776>. Date accessed: 26 june 2019.
Section
Mathematics