A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem
Authors:
Article info
2023-09-25
2024-09-01
2024-09-29
None - None
Keywords
- Particle Swarm Optimization (PSO)
- Genetic algorithm (GA)
- Simulated Annealing (SA)
- Traveling Salesman Problem (TSP)
Abstract
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.
A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem
المؤلفون:
معلومات المقال
2023-09-25
2024-09-01
2024-09-29
None - None
الكلمات الإفتتاحية
- Particle Swarm Optimization (PSO)
- Genetic algorithm (GA)
- Simulated Annealing (SA)
- Traveling Salesman Problem (TSP)
الملخص
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.
An-Najah National University
Nablus, Palestine
Nablus, Palestine
- P.O. Box
- 7, 707
- Fax
- (970)(9)2345982
- Tel.
- (970)(9)2345560
- (970)(9)2345113/5/6/7-Ext. 2628
- [email protected]
- EIC
- Prof. Waleed Sweileh
An-Najah University Journal for Research - A (Natural Sciences) by An-Najah University, Nablus, Palestine is licensed under CC BY-NC 4.0