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.

Title

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

Publisher

An-Najah University

Publisher Country

Palestine

Indexing

Scopus

Impact Factor

None

Publication Type

Both (Printed and Online)

Volume

--

Year

2024

Pages

--