Tesis doctoral en la UPV/EHU inspirada en el "Orienteering Problem"

El pasado 25 de febrero de 2021 Gorka Kobeaga defendió en la UPV/EHU su tesis doctoral titulada "Algorithms for Large Orienteering Problems". Las investigaciones que han desembocado en la tesis y en varios artículos científicos se han desarrollado conjuntamente en la UPV/EHU y en el Instituto BCAM de Bilbao. En la memoria se aborda el diseño de algoritmos para obtener soluciones óptimas al "problema de la orientación", inspirado en el deporte que tanto nos apasiona y que es una variante del clásico "problema del viajante", muy conocido en la literatura de la investigación operativa y la logística.

El planteamiento del problema consiste en diseñar una ruta que, con un límite de tiempo o kilómetros, pase por algunos de los objetivos que han sido distribuidos sobre un mapa, de forma que se obtenga cierta recompensa por cada objetivo visitado. La solución óptima es la que acumule la mayor recompensa posible. Aunque estos modelos matemáticos estén enfocados hacia soluciones comerciales para empresas de transporte y logística, el contexto nos recuerda plenamente a las pruebas de orientación de tipo score (utilizado principalmente en las carreras de rogaining) y de ahí viene su denominación técnica. Debido a su complejidad computacional, la alternativa más práctica para resolver estos problemas son los algoritmos genéticos. Los códigos desarrollados en esta tesis están entre los más eficientes del mundo, ya que son capaces de analizar propuestas con más de 100 localizaciones o balizas.

En las primeras páginas de la memoria se hace mención al origen del problema y se muestra unas gráficas con itinerarios que recuerdan a las estrategias que los equipos de orientación plantean para enfrentarse a una rogaine. Si alguien tiene interés en los detalles técnicos, la memoria se puede descargar del siguiente enlace:

https://bird.bcamath.org/bitstream/handle/20.500.11824/1254/thesis.pdf?sequence=1