Serial and Parallel Benchmarking of ACO, PSO, GA, and Hybrid Metaheuristics for the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a canonical NP-hard routing problem encountered in engineering logistics, inspection planning, and sequencing tasks. This paper reports an implementation-based benchmark of Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and a Genetic Algorithm (GA), together with two hybrids (PSO–GA and PSO–ACO), under serial and parallel execution on a ۴۸-city instance. For ACO, parameter sweeps over ant count, pheromone evaporation rate (ρ), the heuristic–pheromone balance (α), and pheromone-memory usage show that moderate evaporation improves robustness; the best reported mean tour length is ۳۴۳۷۲.۸۶ at ρ=۰.۶ with ۸۰ ants. Disabling pheromone memory increases dispersion between best and worst runs. The α study indicates an optimum around α≈۱.۰–۱.۲ (Evaporation=۰.۵, Ants=۵۰). For discrete PSO, small swarms (<۱۰۰ particles) are unstable, whereas mid-to-large swarms (~۳۰۰–۱۵۰۰) yield lower mean cost with diminishing returns beyond this range. GA experiments (population ۱۰–۵۰۰) using order crossover and swap mutation confirm improved best/mean cost at larger populations at the expense of roughly linear runtime growth; favorable operator settings occur near pc≈۰.۷–۰.۸۵ and pm≈۰.۱–۰.۲۵. The hybrid PSO–GA incorporates swap-based moves and early stopping, and a representative parallel run achieves a better final cost (۳۳۵۲۳.۷۱ vs. ۳۳۷۸۴.۰۳) with far fewer iterations (۳۷۲۵ vs. ۲۲۷۰۰) than the serial counterpart. Overall, results show that careful tuning, hybridization, and implementation-aware parallelization jointly determine practical TSP performance.

کلیدواژه ها:

Traveling Salesman Problem (TSP) ، Ant Colony Optimization (ACO) ، Particle Swarm Optimization (PSO) ، Genetic Algorithm (GA) ، Hybrid Metaheuristics