Creating hard-to-solve instances of travelling salesman problem

Travelling salesman problem is a classical combinatorial optimization problem. Instances of this problem have been used as benchmark for testing the performance of many proposals of discrete optimizer algorithms. However, the hardness or the difficulty degree to solve the instances has not been usually addressed. In the past the evaluation of the difficulty of the instances has required to obtain a high-quality solution, ideally the optimal one. However, this type of strategy burdens the evaluation with large processing times. In this work, diverse indirect measures for evaluating the hardness to solve instances of the travelling salesman problem are proposed. These evaluations are inferred from the spatial attributes of previously evaluated instances, and later correlated with the hardness of the instances. Finally, where a significant correlation is found, a linear model is built and linked to a genetic algorithm. As a consequence of this work, mechanisms for hardening instances of travelling salesman problem are implemented. (C) 2018 Published by Elsevier B.V.