TY - JOUR
T1 - Reducing the size of traveling salesman problems using vaccination by fuzzy selector
AU - Delgadillo, Francisco J.Díaz
AU - Montiel, Oscar
AU - Sepúlveda, Roberto
N1 - Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.
PY - 2016/5/1
Y1 - 2016/5/1
N2 - 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.
AB - 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.
KW - AIS
KW - Fuzzy logic
KW - Metadata
KW - Problem reduction
KW - ROE
KW - TSP
KW - Vaccination
UR - http://www.scopus.com/inward/record.url?scp=84952334001&partnerID=8YFLogxK
U2 - 10.1016/j.eswa.2015.11.026
DO - 10.1016/j.eswa.2015.11.026
M3 - Artículo
SN - 0957-4174
VL - 49
SP - 20
EP - 30
JO - Expert Systems with Applications
JF - Expert Systems with Applications
ER -