A sim-learnheuristic algorithm for the stochastic and context-aware team orienteering problem
Resumen
This paper addresses the Team Orienteering Problem (TOP) with stochastic, context-aware travel times. Traditionally, simheuristics have been used to address stochastic variants of TOP and related routing problems. Simheuristics combine metaheuristics and simulation to deal with stochastic inputs, but they often rely on generic, independent random sampling which ignores that travel times in real traffic networks are dynamic and depend on contextual factors, such as congestion or weather conditions. We propose to extend the traditional simheuristic concept by integrating a machine learning component to overcome this limitation. To apply this novel methodology, models are trained on historical data to predict context-aware travel times. In addition, this historical data and clustering models are used to generate context-aware probability distributions. These customized distributions provide the simulation step with more realistic inputs, ensuring that the evaluation of candidate solutions reflects actual dynamic conditions. We compare a deterministic metaheuristic, a standard simheuristic approach, and the proposed sim-learnheuristic approach on extended benchmark instances. Computational experiments show that the sim-learnheuristic consistently outperforms both the traditional simheuristic and the deterministic metaheuristic, achieving average improvements of approximately 18% and 30%, respectively, under stochastic-dynamic evaluation.
Cristina Tobar Fernández
Estudiante de Doctorado en Inteligencia Artificial
Cristina Tobar se graduó como Matemática y como Estadística en la Universidad de Sevilla en 2023. Posteriormente completó el Máster Universitario en Métodos Analíticos para Datos Masivos: Big Data por la Universidad Carlos III en el año 2024. Sus principales intereses de investigación se centran en la hibridación de metaheurísticas y exactos con métodos de simulación y Machine Learning para la mejora de la resolución de problemas de optimización estocásticos. Estos estudios los compagina desde el año 2023 con su puesto como Optimization Scientist en OGA.ai. Además desde el año 2024 cursa un Doctorato sobre Inteligencia Artificial aplicada a la optimización estocástica de procesos críticos de negocio bajo el marco de un Doctorado Industrial.
Sergio Pérez-Peló
Doctor en Inteligencia Artificial
Estudiante de doctorado en la Universidad Rey Juan Carlos
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.