Algoritmos de búsqueda en entorno variable para resolver el Generalized Orienteering Problem

• Autores: Adolfo Javier Urrutia Zambrana
• Directores de la Tesis: Gregorio Tirado Domínguez (codir. tes.) , Alfonso Mateos Caballero (codir. tes.)
• Lectura: En la Universidad Politécnica de Madrid ( España ) en 2024
• Idioma: español
• Tribunal Calificador de la Tesis: Carlos Javier Pérez Sánchez (presid.) , Antonio Jiménez Martín (secret.) , Alba María Agustín Martín (voc.) , Jose Maria Ferrer Caja (voc.) , Clara Simón de Blas (voc.)
• Programa de doctorado: Programa de Doctorado en Ingeniería Matemática, Estadística e Investigación Operativa por la Universidad Complutense de Madrid y la Universidad Politécnica de Madrid
• Calificación: Sobresaliente Cum Laude
• Enlaces
  • Tesis en acceso abierto en: Archivo Digital UPM
• 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.