Tesis doctorales de la Escuela Internacional de Doctorado de la URJC desde el curso 2024/25
El problema multiobjetivo del comerciante reparador con beneficios
Autor
MORANTE GONZÁLEZ, RUBÉN
Director
SÁNCHEZ-ORO CALVO, JESÚS
Codirector
LÓPEZ SÁNCHEZ, ANA DOLORES
Fecha de defensa
27-11-2025
Calificación
Sobresaliente cum laude
Programa
Tecnologías de la información y las Comunicaciones (TICs)
Mención internacional
No
Resumen
En esta Tesis Doctoral se presenta un problema de optimización combinatoria que puede considerarse una fusión de dos problemas clásicos de la literatura: el problema del vendedor ambulante con beneficios (TSPP) y el problema del reparador ambulante con beneficios (TRPP). La combinación de estos problemas da lugar a una nueva variante denominada problema multiobjetivo del comerciante reparador con beneficios (Mo-TSRPP). El Mo-TSRPP aparece para modelar una situación real en la que un técnico autónomo, especializado en la reparación de electrodomésticos, debe planificar su ruta diaria con el fin de maximizar su rentabilidad y eficiencia operativa. Esta resolución encaja en muchas otras situaciones reales.
El Mo-TSRPP tiene como objetivo optimizar simultáneamente tres criterios fundamentales: el coste total de desplazamiento, la latencia total de servicio y el beneficio total obtenido. La latencia hace referencia al tiempo transcurrido desde el inicio de la ruta hasta la prestación del servicio en cada cliente, lo que tiene un impacto directo en la satisfacción del usuario. Indirectamente, el número de clientes atendidos también se considera en la optimización, aunque no como un objetivo explícito, sino como un efecto emergente del proceso de selección de rutas en el Frente de Pareto. Este frente representa el conjunto de soluciones no dominadas en las que no es posible mejorar un criterio sin empeorar otro.
El problema surge en un contexto donde muchos profesionales independientes deben gestionar de manera eficiente su tiempo y recursos, eligiendo estratégicamente qué clientes visitar y en qué orden. A diferencia de otros problemas de ruteo, en el Mo-TSRPP no es obligatorio atender a todos los clientes disponibles, ya que cada uno ofrece un beneficio frente al coste de desplazamiento y la latencia acumulada. Esto introduce una dimensión de toma de decisiones clave en la que se deben evaluar múltiples alternativas con diferentes compromisos entre los objetivos.
Para abordar la resolución del Mo-TSRPP, se propone un enfoque basado principalmente en la metaheurística Variable Neighborhood Descent (VND), la cual se encarga de explorar sistemáticamente distintas estructuras de vecindad con el objetivo de mejorar iterativamente las soluciones. Como paso inicial, VND se apoya en un procedimiento constructivo basado en Greedy Randomized Adaptive Search Procedure (GRASP), utilizado exclusivamente para generar soluciones iniciales de alta calidad mediante una selección aleatoria guiada. Esta integración permite al algoritmo VND partir de buenos puntos de inicio y potenciar su capacidad de intensificación, logrando así una aproximación eficiente y diversa al Frente de Pareto.
Para evaluar el rendimiento del método propuesto, se realiza una comparación con tres algoritmos evolutivos ampliamente utilizados en la optimización multiobjetivo: NSGA-II, SPEA-2 y MOEA/D. Se analizan diversos conjuntos de instancias experimentales, considerando variaciones en la cantidad de clientes, la distribución geográfica y los parámetros de beneficio y coste. Los resultados muestran que la estrategia híbrida GRASP-VND es capaz de generar soluciones competitivas, superando en varios casos a los algoritmos evolutivos en términos de calidad del Frente de Pareto y eficiencia computacional.
Finalmente, para ilustrar la aplicabilidad del enfoque desarrollado, se presenta un caso de estudio realista basado en datos obtenidos de un servicio técnico de reparaciones. Se analiza cómo la metodología propuesta permite mejorar la planificación de rutas en escenarios reales, proporcionando herramientas útiles para la toma de decisiones en entornos dinámicos y altamente competitivos. Esta validación práctica destaca la relevancia del Mo-TSRPP como un problema de optimización aplicable a múltiples contextos empresariales donde la gestión eficiente de recursos móviles es un factor clave para la rentabilidad y sostenibilidad del negocio.
