An-Najah University Journal for Research - A (Natural Sciences)

A Comparison of Heuristic Algorithms for Solving the Traveling Salesman Problem

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
P.O. Box
7, 707
Fax
(970)(9)2345982
Tel.
(970)(9)2345560
(970)(9)2345113/5/6/7-Ext. 2628
E-mail
[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