Discrete Evolutionary Algorithm with Distance-Based Crossover and Multiple Mutation Strategy for Traveling Salesman Problems

Abstract

The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem for which traditional evolutionary algorithms often converge prematurely and yield suboptimal solutions as problem complexity increases. This study aims to overcome these limitations by developing an optimization approach that maintains population diversity while accelerating convergence toward optimal routes. To address these challenges, we introduce Evolutionary Algorithm with Distance-based Crossover and Multiple Mutation Strategy (EADXMM), a novel evolutionary algorithm characterized by its unique hybrid mechanism. Unlike standard approaches, EADXMM employs a distance-based crossover operator to produce better-guided offspring and a multi-strategy mutation framework that actively preserves and enhances population diversity. Following the mutation phase, a complete 2-opt local search is executed to refine candidate solutions and ensure rapid convergence. The performance of EADXMM was rigorously evaluated on 22 benchmark TSP instances of varying scale from the TSPLIB repository and compared against four established metaheuristics: ACO, VTPSO, ABCSS, and DSMO. Experimental results demonstrate that EADXMM exhibits superior robustness and solution quality, consistently outperforming the competing algorithms on 15 of the 22 benchmark instances. These findings confirm that the strategic integration of distance-based crossover, diversified mutation methods, and complete 2-opt local search effectively navigates the complex search space, enabling highly efficient route determination for large-scale TSPs.