Enhanced Partially Matched Crossover for Solving the Traveling Salesman Problem

This paper proposes an Enhanced Partially Matched Crossover (PMXP) operator for solving the Traveling Salesman Problem (TSP) using Genetic Algorithms (GAs). Traditional crossover operators such as PMX, CX, and OX often suffer from redundancy, poor diversity maintenance, and premature convergence. The proposed PMXP addresses these limitations by introducing flexible crossover boundaries, excluding redundant gene mappings, and selectively applying mappings to preserve diversity and structure in offspring. A novel cyclic shift mutation operator is also integrated to enhance exploration. Experimental evaluations were conducted on seven benchmark TSP datasets from TSPLIB, including BERLIN52, GR202, GR137, and D657. Results show that PMXP outperforms classical operators in six out of seven datasets, achieving up to 24% improvement in best fitness compared to PMX and consistently lower standard deviation, indicating stable convergence. Route visualizations and statistical analysis confirm that PMXP provides a better balance between exploration and exploitation. These findings suggest that PMXP is a competitive and effective crossover strategy for combinatorial optimization problems such as the TSP.