TY - GEN
T1 - Fixed set search applied to the traveling salesman problem
AU - Jovanovic, Raka
AU - Tuba, Milan
AU - Voß, Stefan
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - In this paper we present a new population based metaheuristic called the fixed set search (FSS). The proposed approach represents a method of adding a learning mechanism to the greedy randomized adaptive search procedure (GRASP). The basic concept of FSS is to avoid focusing on specific high quality solutions but on parts or elements that such solutions have. This is done through fixing a set of elements that exist in such solutions and dedicating computational effort to finding near optimal solutions for the underlying subproblem. The simplicity of implementing the proposed method is illustrated on the traveling salesman problem. Our computational experiments show that the FSS manages to find significantly better solutions than the GRASP it is based on, the dynamic convexized method and the ant colony optimization combined with a local search.
AB - In this paper we present a new population based metaheuristic called the fixed set search (FSS). The proposed approach represents a method of adding a learning mechanism to the greedy randomized adaptive search procedure (GRASP). The basic concept of FSS is to avoid focusing on specific high quality solutions but on parts or elements that such solutions have. This is done through fixing a set of elements that exist in such solutions and dedicating computational effort to finding near optimal solutions for the underlying subproblem. The simplicity of implementing the proposed method is illustrated on the traveling salesman problem. Our computational experiments show that the FSS manages to find significantly better solutions than the GRASP it is based on, the dynamic convexized method and the ant colony optimization combined with a local search.
KW - GRASP
KW - Metaheuristic
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=85059945573&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-05983-5_5
DO - 10.1007/978-3-030-05983-5_5
M3 - Conference contribution
AN - SCOPUS:85059945573
SN - 9783030059828
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 63
EP - 77
BT - Hybrid Metaheuristics - 11th International Workshop, HM 2019, Proceedings
A2 - Blesa Aguilera, Maria J.
A2 - Blum, Christian
A2 - Pinacho-Davidson, Pedro
A2 - Godoy del Campo, Julio
A2 - Gambini Santos, Haroldo
PB - Springer Verlag
T2 - 11th International Workshop on Hybrid Metaheuristics, HM 2019
Y2 - 16 January 2019 through 18 January 2019
ER -