A sim-learnheuristic algorithm for the stochastic and context-aware team orienteering problem
Abstract
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
Artificial Intelligence PhD Student
Cristina Tobar graduated in Mathematics and Statistics from the University of Seville in 2023. She subsequently completed the Master’s Degree in Analytical Methods for Big Data at Carlos III University in 2024. Her main research interests focus on the hybridization of metaheuristic and exact methods with simulation and Machine Learning techniques to improve the resolution of stochastic optimization problems. Since 2023, she has combined these studies with her role as an Optimization Scientist at OGA.ai. Additionally, since 2024, she has been pursuing a PhD in Artificial Intelligence applied to the stochastic optimization of critical business processes within the framework of an Industrial PhD program.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.