Título: «Variante heurística para el problema del viajante. Caso de aplicación: Circuito de pesca deportiva«
Tesista: Priscila Martínez
Directora: Mg. Lidia López
Carrera: Licenciatura en Ciencias de la Computación
Fecha de defensa: 8 de septiembre de 2017
Resumen
El presente trabajo se enmarca en la construcción de un circuito turístico abocado a la pesca deportiva, aplicando algoritmos de optimización combinatoria con el objetivo de generar la mejor solución al problema del recorrido para la pesca de salmónidos en la Provincia de Neuquén.
La optimización combinatoria es una rama de la optimización. Su dominio se compone de problemas de optimización donde el conjunto de posibles soluciones es discreto o se puede reducir a un conjunto discreto.
A la hora de tratar con problemas de optimización combinatoria, el objetivo consiste en encontrar la mejor solución posible existente o solución óptima, aquella que minimiza una función de costo dada.
A medida que la complejidad del espacio de búsqueda aumenta, el costo de ejecución de dichos algoritmos puede aumentar de forma exponencial, convirtiendo la resolución en prácticamente inviable. Otra posibilidad para afrontar este tipo de problemas, consiste en buscar una solución sub-óptima, pero en un tiempo razonable. En algunos casos es posible encontrar incluso la solución óptima al problema.
La planificación y gestión de caminos para recorridos con preferencias exige disponer de sistemas eficientes de optimización de rutas. Su complejidad es exponencial y, por lo tanto, entra en la categoría de los problemas que no se pueden resolver en tiempo polinómico, lo que en otras palabras, quiere decir, que una computadora actual puede tardar milenios en hallar la solución al problema.
Por lo tanto, este tipo de problemas no es abordable con técnicas de resolución exactas, salvo para problemas muy pequeños, debiéndose emplear heurísticas para encontrar soluciones factibles.
En esta tesis se pretende modelar un circuito turístico asociado a la pesca deportiva que se presenta como un grafo con restricciones relacionadas con accidentes geográficos y otras limitantes. El mismo se encuadra dentro del Problema del Viajante. [5] Se estudiará este problema en profundidad y se diseñará un modelo basado en grafos representados por matrices de adyacencia, y una heurística para la obtención del grafo resultado con la meta de resolver el planteo combinando alguna de las técnicas existentes y el conocimiento del dominio de la aplicación de pesca deportiva. Se utilizarán técnicas y/o herramientas de visualización de la información para la representación gráfica.
Se implementa un algoritmo meta heurístico de búsqueda tabú, el cual está basado en una búsqueda local, para encontrar una solución al problema. Debido a que el número de vértices es medianamente pequeño, implica que sea soluble computacionalmente, en un tiempo y con una eficiencia razonable.
Sobre el final del trabajo, se ejemplifica la aplicación de un algoritmo heurístico constructivo para resolver el Problema del Viajante, aplicado al circuito de pesca de salmónidos de la Provincia de Neuquén.
