Reducing the size of traveling salesman problems using vaccination by fuzzy selector

At present, no algorithm can solve Combinatorial Optimization Problems (COPs) in polynomial time. The Traveling Salesman Problem (TSP) is an NP-hard COP example widely used as a test problem since it is mathematically equivalent to others in diverse fields. State of the art algorithms provide low quality solutions for large instances at high computational cost. Reducing the TSP size is a heuristic that works well finding solutions at a reduced cost. The Reduce-Optimize-Expand (ROE) methodology allows to solve COPs faster by improving the quality of solutions, however, obtaining optimal reductions is still an open problem since there is no way to determine if the removed nodes are part of the optimal solution without knowing it beforehand. This paper presents an intelligent strategy with a fuzzy logic classifier, based on the ROE, to obtain systematic reductions of TSP instances. The method was tested using TSP instances from the TSPLIB, ranging from 131 to 2924 cities. Comparative experimental results obtained higher-quality reductions, thus improving the overall performance of ROE when using the intelligent selection strategies. Intelligent reductions contribute to improve the performance of existing TSP algorithms, even given solution to many unsolved problems with huge amount of nodes by reducing them to a treatable size.