TY - GEN
T1 - Heuristic Function to Solve the Generalized Covering TSP with Artificial Intelligence Search
AU - Greco, Matias
AU - Hernandez, Carlos
N1 - Publisher Copyright:
© 2020 IEEE.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/11/16
Y1 - 2020/11/16
N2 - Search is a universal problem-solving method in Artificial Intelligence. Specifically, Heuristic Search algorithms, such as A*, use a heuristic function to guide the search process. The heuristic function allows algorithms to explore only a part of the search space, resulting in an efficient search process. This paper presents a new heuristic function to solve the Generalized Covering Traveling Salesman Problem (GCTSP). The heuristic function is precalculated. The method to obtain the function is pre-calculating optimal solutions consecutively to small sub-problems of the GCTSP of increasing difficulty, using an incremental Best First Search algorithm, which reuses heuristics values previously precalculated. The resultating heuristic function can be used with different heuristic search algorithms. To the best of our knowledge, this problem has not been solved with Heuristic Search. This paper is the first to present a solution to the GCTSP using Heuristic Search algorithms, such as A∗ and Anytime search algorithms. We evaluated different Heuristic Search algorithms. The experimental evaluation shows results of the same quality, obtained orders-of-magnitude faster than the exact methods traditionally used in Operations Research.
AB - Search is a universal problem-solving method in Artificial Intelligence. Specifically, Heuristic Search algorithms, such as A*, use a heuristic function to guide the search process. The heuristic function allows algorithms to explore only a part of the search space, resulting in an efficient search process. This paper presents a new heuristic function to solve the Generalized Covering Traveling Salesman Problem (GCTSP). The heuristic function is precalculated. The method to obtain the function is pre-calculating optimal solutions consecutively to small sub-problems of the GCTSP of increasing difficulty, using an incremental Best First Search algorithm, which reuses heuristics values previously precalculated. The resultating heuristic function can be used with different heuristic search algorithms. To the best of our knowledge, this problem has not been solved with Heuristic Search. This paper is the first to present a solution to the GCTSP using Heuristic Search algorithms, such as A∗ and Anytime search algorithms. We evaluated different Heuristic Search algorithms. The experimental evaluation shows results of the same quality, obtained orders-of-magnitude faster than the exact methods traditionally used in Operations Research.
KW - A
KW - Best First Search
KW - Heuristic search
KW - Traveling Salesman Problem
UR - http://www.scopus.com/inward/record.url?scp=85098621807&partnerID=8YFLogxK
U2 - 10.1109/SCCC51225.2020.9281156
DO - 10.1109/SCCC51225.2020.9281156
M3 - Conference contribution
AN - SCOPUS:85098621807
T3 - Proceedings - International Conference of the Chilean Computer Science Society, SCCC
BT - 2020 39th International Conference of the Chilean Computer Science Society, SCCC 2020
PB - IEEE Computer Society
T2 - 39th International Conference of the Chilean Computer Science Society, SCCC 2020
Y2 - 16 November 2020 through 20 November 2020
ER -