| Serial and Parallel Benchmarking of ACO, PSO, GA, and Hybrid Metaheuristics for the Traveling Salesman Problem |
| کد مقاله : 1540-ISME2026 |
| نویسندگان |
|
نگین سادات حسینی نوید *1، محمد مهدی سلطانی2 1پژوهشگر
دانشجوی دانشگاه علم وصنعت ایران 2پژوهشگر مجیدیه شمالی - خ.برادران محمدی(ریحانی)-خیابان صباح شرقی-بلوار توکل-خیابان افتخار شرقی مجتمع بام سامان- واحد 721 |
| چکیده مقاله |
| 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 48-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 34372.86 at ρ=0.6 with 80 ants. Disabling pheromone memory increases dispersion between best and worst runs. The α study indicates an optimum around α≈1.0–1.2 (Evaporation=0.5, Ants=50). For discrete PSO, small swarms (<100 particles) are unstable, whereas mid-to-large swarms (~300–1500) yield lower mean cost with diminishing returns beyond this range. GA experiments (population 10–500) 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≈0.7–0.85 and pm≈0.1–0.25. The hybrid PSO–GA incorporates swap-based moves and early stopping, and a representative parallel run achieves a better final cost (33523.71 vs. 33784.03) with far fewer iterations (3725 vs. 22700) 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 |
| وضعیت: پذیرفته شده برای ارائه شفاهی |