Exact and local search methods for solving travelling salesman problem with practical application
Other Title(s)
طرق الحل التام و البحث المحلية لحل مسالة البائع المتجول مع تطبيق عملي
Joint Authors
Jasim, Suad Sajjad
Ali, Faiz Hasan
Source
Issue
Vol. 60, Issue 5 (31 May. 2019), pp.1138-1153, 16 p.
Publisher
University of Baghdad College of Science
Publication Date
2019-05-31
Country of Publication
Iraq
No. of Pages
16
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Jasim, Suad Sajjad& Ali, Faiz Hasan. 2019. Exact and local search methods for solving travelling salesman problem with practical application. Iraqi Journal of Science،Vol. 60, no. 5, pp.1138-1153.
https://search.emarefa.net/detail/BIM-970654
Modern Language Association (MLA)
Jasim, Suad Sajjad& Ali, Faiz Hasan. Exact and local search methods for solving travelling salesman problem with practical application. Iraqi Journal of Science Vol. 60, no. 5 (2019), pp.1138-1153.
https://search.emarefa.net/detail/BIM-970654
American Medical Association (AMA)
Jasim, Suad Sajjad& Ali, Faiz Hasan. Exact and local search methods for solving travelling salesman problem with practical application. Iraqi Journal of Science. 2019. Vol. 60, no. 5, pp.1138-1153.
https://search.emarefa.net/detail/BIM-970654
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 1153
Record ID
BIM-970654