Performance Analysis of Classical Algorithms for the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is a fundamental optimization problem with wide-ranging applications in logistics, routing, and network design. This paper presents a comprehensive performance analysis of classical algorithms applied to solve the TSP, including exact methods like Brute Force and Dynamic Programming, and heuristic approaches such as Particle Swarm Optimization (PSO), Simulated Annealing (SA), Genetic Algorithms (GA), and k-Nearest Neighbors (KNN). The study evaluates these algorithms across multiple problem instances, varying in scale and complexity, to compare their solution quality, computational efficiency, and scalability.