Description:
The Traveling Salesman Problem - TSP is one of the most explored problems not only in the literature but to solve real problems regarding the economy, transportation, and logistics, to cite a few cases. Adapting TSP to solve different problems has originated several variants of the optimization problem with more complex objectives and different restrictions. TSP is a discrete NP-hard problem for which deterministic techniques require exponential time to obtain optimal solutions. Metaheuristics have been used to solve the problem in polynomial time. Several studies have tried hybridizing metaheuristics with specialised heuristics to improve the quality of the solutions. This paper focuses on the solution of the classical TSP using low-level hybridizations, experimenting with eight metaheuristics and heuristics derived from k-OPT, SISR, and segment intersection search, resulting in twenty-four combinations. Some combinations allow more than a set of searching parameters. Problems with 50 to 280 cities are solved. At the end of the optimization process, a segment uncrossing heuristic is applied, resulting in a reduction of the length of the route of more than 70% in some cases. Parameter tuning of the metaheuristics is not carried out, exploiting the different searching patterns of the eight metaheuristics instead.The solutions’ quality is comparable to those presented in the literature