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

Resumen

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

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.

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.