A Hybrid Heuristic Algorithm for the Traveling Salesman Problem with Structured Initialization in Global–Local Search

This work proposes solving the Traveling Salesman Problem by applying combined heuristic global and local search methods. The proposed method is divided into three phases: first, it evaluates an initial route and chooses the minimum value of rows in a distance matrix. The next phase seeks to improve the route’s cost globally and with a 2-opt local search method, remove the crossings, and further minimize the cost of departure. Finally, the last phase evaluates and conserves each cost using tabu search, proposing a parameter β that describes the algorithm convergence factor. This paper assessed 29 TSPLIB instances and compared them with other algorithms: the ant colony optimization algorithm (ACO), artificial neural network (ANN), particle swarm optimization (PSO), and genetic algorithm (GA). With the proposed algorithm, results close to the optimal ones are obtained, and the proposed algorithm is assessed on 29 TSPLIB instances. Based on 30 independent runs per instance, the method achieves a mean absolute percentage error (MAPE) of 1.4484% relative to the known optima, demonstrating its accuracy. Furthermore, statistical comparisons using the coefficient of variation (CV) for runtime and the Wilcoxon signed-rank test confirm that the proposed hybrid algorithm is significantly faster than traditional ant colony optimization (T-ACO) and a new ant colony optimization algorithm (N-ACO) while maintaining competitive solution quality.