Impact of Problem Size on Exploration-Exploitation Balance in Metaheuristics for the Travelling Salesman Problem

The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem that remains challenging due to its $\mathcal{N}\mathcal{P}$-hard nature. Metaheuristic Algorithms (MAs) provide effective approximations for solving TSP, but their performance is significantly influenced by problem size, affecting their ability to balance exploration and exploitation. This study evaluates five recent and efficient MAs–Skill Optimization Algorithm (SOA), Harris Hawks Optimization (HHO), Gold Rush Optimizer (GRO), Energy Valley Optimizer (EVO), and Crystal Structure Algorithm (CryStAl)–on multiple TSP instances from the TSPLIB benchmark dataset to assess their scalability, convergence behaviour, and search dynamics. Our experimental analysis, supported by the Friedman test, convergence curves, computation times, and exploration-exploitation curves, reveals that no single MA consistently finds the optimal solution, with most exhibiting high standard deviations across different problem sizes. However, according to the Friedman ranking, EVO, CryStAl, and SOA demonstrated superior performance. Convergence curves indicate that EVO achieves the fastest convergence, particularly in medium-dimensional problems. These findings emphasize the impact of problem size on MAs effectiveness and provide insights for designing more scalable optimization strategies.