A Study on Solution Approaches to Travelling Salesperson Problem

Abstract

The study compares Ant Colony Optimization (ACO), Genetic Algorithm (GA), and Particle Swarm Optimization (PSO) for solving the symmetric Travelling Salesperson Problem (TSP) using real-world geographic data from heritage sites in the Kathmandu Valley. Using latitude–longitude data and distance matrices obtained from Google Maps, experiments were conducted on small (Ten), medium (Thirty), and large (Forty-Nine) size problem instances in Python. Performance is evaluated in terms of solution quality, convergence behavior, computational time, and scalability. The results indicate that all three algorithms perform comparably for small problem instances. As the problem size increases, Ant Colony Optimization consistently produces shorter tours and demonstrates more robust convergence and superior scalability. Ant Colony Optimization is identified as the most suitable approach for large, real-world symmetric TSP problems involving geographic data.