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

Simple item page
dc.contributor.authorGreco Chandía, Matías José Andrés
dc.contributor.authorHernández, Carlos
dc.date.accessioned2022-05-16T13:00:34Z
dc.date.available2022-05-16T13:00:34Z
dc.date.issued2020
dc.description.abstractSearch 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.
dc.fuente.origenIEEE
dc.identifier.doi10.1109/SCCC51225.2020.9281156
dc.identifier.eisbn9781728183282
dc.identifier.isbn9781728183299
dc.identifier.issn1522-4902
dc.identifier.urihttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9281156
dc.identifier.urihttps://doi.org/10.1109/SCCC51225.2020.9281156
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/63952
dc.information.autorucEscuela de ingeniería ; Greco Chandía, Matías José Andrés ; S/I ; 1071065
dc.language.isoes
dc.nota.accesoContenido parcial
dc.pagina.final8
dc.pagina.inicio1
dc.publisherIEEE
dc.relation.ispartofInternational Conference of the Chilean Computer Science Society (SCCC) (39° : 2020 : Coquimbo, Chile)
dc.rightsacceso restringido
dc.subjectOperations research
dc.subjectHeuristic algorithms
dc.subjectTraveling salesman problems
dc.subjectSearch problems
dc.subjectSpace exploration
dc.subjectProblem-solving
dc.subjectArtificial intelligence
dc.titleHeuristic Function to Solve The Generalized Covering TSP with Artificial Intelligence Searches_ES
dc.typecomunicación de congreso
sipa.codpersvinculados1071065
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Heuristic Function to Solve The Generalized Covering TSP with Artificial Intelligence Search.pdf
Size:
2.82 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de conferencia