A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is a challenging computational problem in combinatorial optimization that aims to visit all cities exactly once and return to the first city. Despite that numerous theoretical solutions have been proposed in the literature, finding the exact optimal solution rema...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
An-Najah National University
2024-09-01
|
| Series: | مجلة جامعة النجاح للأبحاث العلوم الطبيعية |
| Subjects: | |
| Online Access: | https://journals.najah.edu/media/journals/full_texts/9_0HnMChH.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849684014495956992 |
|---|---|
| author | Younes Khdeir Ahmed Awad |
| author_facet | Younes Khdeir Ahmed Awad |
| author_sort | Younes Khdeir |
| collection | DOAJ |
| description | The Traveling Salesman Problem (TSP) is a challenging computational problem in combinatorial optimization that aims to visit all cities exactly once and return to the first city. Despite that numerous theoretical solutions have been proposed in the literature, finding the exact optimal solution remains computationally infeasible due to the NP-hard nature of the problem. To address this, many heuristic and optimization approaches have been developed to generate probabilistic results that are often approximations. This paper presents a comparison between four popular algorithms: steepest ascent hill climbing, simulated annealing, genetic algorithm with partially matched crossover, and Particle Swarm Optimization (PSO). The study examines how these algorithms can solve the TSP and avoid local minimum values while achieving a balance between research exploration and exploitation for an optimal solution. For a relatively large number of cities, the simulated annealing algorithm and genetic algorithm produce promising results whilst the genetic algorithm takes longer time to execute due to the iterative application of its variation operators. |
| format | Article |
| id | doaj-art-c1ae84913f974878ac70a04d8908d9da |
| institution | DOAJ |
| issn | 1727-2114 2311-8865 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | An-Najah National University |
| record_format | Article |
| series | مجلة جامعة النجاح للأبحاث العلوم الطبيعية |
| spelling | doaj-art-c1ae84913f974878ac70a04d8908d9da2025-08-20T03:23:35ZengAn-Najah National Universityمجلة جامعة النجاح للأبحاث العلوم الطبيعية1727-21142311-88652024-09-01391738010.35552/anujr.a.39.1.2301A Comparison of Heuristic Algorithms for Solving the Traveling Salesman ProblemYounes Khdeir0Ahmed Awad1Department of Information Technology, Faculty of Engineering and Information Technology, An-Najah National University, Nablus, PalestineDepartment of Information Technology, Faculty of Engineering and Information Technology, An-Najah National University, Nablus, PalestineThe Traveling Salesman Problem (TSP) is a challenging computational problem in combinatorial optimization that aims to visit all cities exactly once and return to the first city. Despite that numerous theoretical solutions have been proposed in the literature, finding the exact optimal solution remains computationally infeasible due to the NP-hard nature of the problem. To address this, many heuristic and optimization approaches have been developed to generate probabilistic results that are often approximations. This paper presents a comparison between four popular algorithms: steepest ascent hill climbing, simulated annealing, genetic algorithm with partially matched crossover, and Particle Swarm Optimization (PSO). The study examines how these algorithms can solve the TSP and avoid local minimum values while achieving a balance between research exploration and exploitation for an optimal solution. For a relatively large number of cities, the simulated annealing algorithm and genetic algorithm produce promising results whilst the genetic algorithm takes longer time to execute due to the iterative application of its variation operators.https://journals.najah.edu/media/journals/full_texts/9_0HnMChH.pdfparticle swarm optimization (pso)genetic algorithm (ga)simulated annealing (sa)traveling salesman problem (tsp) |
| spellingShingle | Younes Khdeir Ahmed Awad A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem مجلة جامعة النجاح للأبحاث العلوم الطبيعية particle swarm optimization (pso) genetic algorithm (ga) simulated annealing (sa) traveling salesman problem (tsp) |
| title | A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem |
| title_full | A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem |
| title_fullStr | A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem |
| title_full_unstemmed | A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem |
| title_short | A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem |
| title_sort | comparison of heuristic algorithms for solving the traveling salesman problem |
| topic | particle swarm optimization (pso) genetic algorithm (ga) simulated annealing (sa) traveling salesman problem (tsp) |
| url | https://journals.najah.edu/media/journals/full_texts/9_0HnMChH.pdf |
| work_keys_str_mv | AT youneskhdeir acomparisonofheuristicalgorithmsforsolvingthetravelingsalesmanproblem AT ahmedawad acomparisonofheuristicalgorithmsforsolvingthetravelingsalesmanproblem AT youneskhdeir comparisonofheuristicalgorithmsforsolvingthetravelingsalesmanproblem AT ahmedawad comparisonofheuristicalgorithmsforsolvingthetravelingsalesmanproblem |