Resolviendo el problema de cobertura del vendedor viajero generalizado con búsqueda heurística
Cargando...
Archivos
Fecha
2020
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
La búsqueda de primero el mejor es una estrategia de búsqueda heurística de Inteligencia Artificial,
y su funcionamiento se basa seleccionar para expansión, entre todos los estados generados, el
estado más prometedor. Muchos de estos algoritmos, incluyendo A*, utilizan una función de
evaluación heurística que depende del dominio del problema para tomar una decisión informada y
hacer la búsqueda más eficiente. En este trabajo se propone un método para obtener una función
heurística en problemas de planificación de rutas con coberturas, específicamente para el problema
de cobertura del vendedor viajero generalizado (GCTSP) el cual permite resolver el problema
utilizando Inteligencia Artificial. Este problema tiene aplicaciones en el transporte de ayuda
humanitaria en situaciones de emergencia, la ubicación de nodos en el desarrollo de redes eléctricas
y de telecomunicaciones, entre otras. La forma de obtener esta función heurística es pre-calculando
soluciones con valores óptimos a sub-problemas del GCTSP original mediante un algoritmo BFS. Esto
permite generar una tabla de valores heurísticos o Pattern Database, que se puede utilizar para
luego resolver el problema con diferentes algoritmos. La heurística propuesta permite ejecutar
búsquedas con distintos algoritmos subóptimos que si no se cuenta con una evaluación heurística
no sería posible evaluarlos.
También, se propone un nuevo algoritmo de búsqueda primero el mejor de tipo Anytime, el cual
entrega soluciones con una calidad acorde al tiempo de ejecución, basado en Focal Search.
Se despliegan resultados de la utilización de la heurística propuesta sobre diferentes algoritmos
anytime BFS, y se obtienen soluciones de calidad similar en menos tiempo que los métodos exactos,
tradicionalmente usados en Investigación de Operaciones.
Notas
Tesis (Magíster en Ciencias de la Computación)
Palabras clave
Programación Heurística, Vendedores Viajeros