Optimization under Uncertainty in the Prize-Collecting Traveling Salesman Problem: An Artificial Intelligence and Simheuristics Approach

Abstract

This research addresses the Prize-Collecting Traveling Salesman Problem (PCTSP) under demand uncertainty, a challenge in route optimization where unmet demands incur penalties. Traditional deterministic models fail to capture real-world vari- ability. In this context, a new methodology is proposed that integratess Artificial Intelligence (AI) and simheuristic techniques, which arise from the combination of simulations with heuristics, to improve decision making in uncertain environments. Specifically, Machine Learning models are used to predict demand by obtain- ing an approximation to the most affine deterministic world assumption, while clustering methods generate realistic demand scenarios. All this giving a more realistic approach replacing the classical ones with Monte Carlo simulations. A simheuristic approach combining GRASP with simulations will be used, aided by Machine Learning methods to improve the evaluation of solutions under stochastic conditions.

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.