Tesis:
Algoritmos de búsqueda en entorno variable para resolver el Generalized Orienteering Problem
- Autor: URRUTIA ZAMBRANA, Adolfo
- Título: Algoritmos de búsqueda en entorno variable para resolver el Generalized Orienteering Problem
- Fecha: 2024
- Materia:
- Escuela: E.T.S. DE INGENIEROS DE TELECOMUNICACION
- Departamentos: INTELIGENCIA ARTIFICIAL
- Acceso electrónico: https://oa.upm.es/81315/
- Director/a 1º: TIRADO DOMÍNGUEZ, Gregorio
- Director/a 2º: MATEOS CABALLERO, Alfonso
- Resumen: El Orienteering Problem (OP) es un problema de optimización NP-Duro que está presente en muchísimas aplicaciones de la vida diaria, desde la entrega de paquetería hasta la creación de itinerarios turísticos. Desde su introducción hace casi 40 años, el OP ha sido un campo muy activo de investigación y en la literatura se encuentran numerosas extensiones. Entre ellas está el Generalized Orienteering Problem (GOP), que es una extensión no lineal que asocia un vector de puntuaciones a los vértices del grafo, lo que permite un mejor modelado de problemas como al que se enfrenta un turista al visitar una nueva ciudad llena de atracciones con características variadas.
A pesar de su potencial, el Generalized Orienteering Problem no ha sido tan estudiado como otras extensiones del OP, y al momento de iniciar este trabajo de investigación, contaba únicamente con un conjunto de instancias. Sumado a lo anterior, los resultados obtenidos por las distintas técnicas aplicadas a su resolución se encontraban dispersos y con algunos errores de cálculo.
Partiendo de lo antes mencionado, en esta tesis se propone una metodología novedosa basada en Búsqueda en Entorno Variable (VNS) para resolver el GOP. Los algoritmos propuestos extienden el estado del arte agregando modificaciones que alteran de forma relevante el funcionamiento de las metaheurísticas existentes. Estos aportes son puestos a prueba a través de una extensa experiencia computacional y los resultados muestran que han sido capaces de superar a todas las otras técnicas de la literatura, no solo en las instancias preexistentes, sino también en 6 nuevos conjuntos de instancias creados para el GOP.
Finalmente, se ha propuesto también una extensión del GOP denominada Team Generalized Orienteering Problem (TGOP). Dicha propuesta permite la creación de múltiples itinerarios cuya puntuación total puede ser obtenida utilizando dos diferentes funciones objetivo. Para resolver este nuevo problema, se ha propuesto también un algoritmo novedoso basado en VNS que extiende el anterior, incorporando el concepto de cooperación, que ha demostrado ser clave en su eficiencia. De la misma manera que se hizo para la metodología propuesta para el GOP, los algoritmos propuestos para el TGOP, en sus distintos niveles de cooperación y configuraciones, han sido evaluados con detalle sobre instancias nuevas y ya existentes, mostrando un desempeño muy bueno respecto a las metaheurísticas presentes en el estado del arte.
ABSTRACT
The Orienteering Problem (OP) is an NP-Hard optimization problem that is present in many applications in daily life, from package delivery to the creation of tourist itineraries. Since its introduction almost 40 years ago, the OP has been a very active field of research and numerous extensions are found in the literature. Among them is the Generalized Orienteering Problem (GOP), which is a non-linear extension that associates a vector of scores to the vertices of the graph, which allows better modeling of problems such as the one a tourist faces when visiting a new city full of attractions with varied characteristics.
Despite its potential, the Generalized Orienteering Problem has not been studied as much as other extensions of the OP, and at the time of starting this research work, it only had one set of instances. In addition to the above, the results obtained by the different techniques applied to its resolution were dispersed and with some calculation errors.
Based on the aforementioned, this thesis proposes a novel methodology based on Variable Neighborhood Search (VNS) to solve the GOP. The proposed algorithms extend the state of the art by adding modifications that significantly alter the operation of existing metaheuristics. These contributions are tested through extensive computational experience and the results show that they have been able to outperform all other techniques in the literature, not only on pre-existing instances, but also on 6 new sets of instances created for the GOP.
Finally, an extension of the GOP called Team Generalized Orienteering Problem (TGOP) has also been proposed. This proposal allows the creation of multiple itineraries whose total score can be obtained using two different objective functions. To solve this new problem, a novel algorithm based on VNS has also been proposed that extends the previous one, incorporating the concept of cooperation, which has proven to be key in its efficiency. In the same way it was done for the GOP, the algorithms proposed for the TGOP, in their different levels of cooperation and configurations, have been evaluated in detail on new and existing instances, showing a very good performance with respect the metaheuristics of the state of the art.