Heuristic Function to Solve the Generalized Covering TSP with Artificial Intelligence Search

Matias Greco, Carlos Hernandez

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

Resumen

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.

Idioma originalInglés
Título de la publicación alojada2020 39th International Conference of the Chilean Computer Science Society, SCCC 2020
EditorialIEEE Computer Society
ISBN (versión digital)9781728183282
DOI
EstadoPublicada - 16 nov 2020
Evento39th International Conference of the Chilean Computer Science Society, SCCC 2020 - Coquimbo, Chile
Duración: 16 nov 202020 nov 2020

Serie de la publicación

NombreProceedings - International Conference of the Chilean Computer Science Society, SCCC
Volumen2020-November
ISSN (versión impresa)1522-4902

Conferencia

Conferencia39th International Conference of the Chilean Computer Science Society, SCCC 2020
PaísChile
CiudadCoquimbo
Período16/11/2020/11/20

Áreas temáticas de ASJC Scopus

  • Ingeniería (todo)
  • Informática (todo)

Huella Profundice en los temas de investigación de 'Heuristic Function to Solve the Generalized Covering TSP with Artificial Intelligence Search'. En conjunto forman una huella única.

Citar esto