A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems

Resumen Técnico: Un Marco Unificado de Aprendizaje por Refuerzo con Conocimiento Incrustado para Problemas Generalizados de Ruteo de Vehículos con Capacidad

Definición del Problema
El Problema de Ruteo de Vehículos con Capacidad (CVRP) es un problema fundamental de optimización combinatoria NP-duro, central en logística y transporte. Las aplicaciones del mundo real a menudo requieren resolver variantes generalizadas que incorporan restricciones complejas, como ventanas de tiempo (VRPTW), requisitos de carga de retorno/carga (VRPB), rutas abiertas (OVRP) y límites de distancia (VRPL). Aunque los métodos basados en aprendizaje recientes han mostrado promesa, a menudo dependen de un entrenamiento de extremo a extremo que carece de conocimiento algorítmico explícito, lo que podría limitar la calidad de la solución. Además, los enfoques existentes luchan por unificar diversos tipos de restricciones dentro de un único marco sin modificaciones arquitectónicas extensas.

Metodología
Los autores proponen un Marco Unificado de Aprendizaje por Refuerzo (RL) con Conocimiento Incrustado inspirado en la heurística clásica Primero Ruta, Segundo Agrupar (RFCS). A diferencia de los solucionadores tradicionales de extremo a extremo, este marco descompone el problema en dos etapas distintas, integrando principios de diseño algorítmico con aprendizaje neuronal:

1. Primero Ruta (Componente RL): Una política de red neuronal (basada en una arquitectura codificador-descodificador Transformer) aprende a generar una permutación global de los nodos de clientes. Esta etapa se centra en construir una secuencia que visite a todos los clientes exactamente una vez.
2. Segundo Agrupar (Componente de Conocimiento): Un solucionador de programación dinámica (DP) toma la permutación de clientes generada por el agente RL y la divide óptimamente en rutas de vehículos factibles. Este módulo maneja explícitamente todas las restricciones (capacidad, ventanas de tiempo, carga de retorno, límites de distancia) y calcula el costo óptimo para la secuencia dada.
3. Mecanismo de Recompensa: El agente RL se entrena utilizando el costo total negativo calculado por el solucionador DP como señal de recompensa. Esto alinea el objetivo de optimización del RL directamente con la formulación original del problema, eliminando la necesidad de solucionadores heurísticos del Problema del Viajante de Comercio (TSP) para generar la ruta inicial.
4. Procesamiento Unificado del Contexto: Para abordar la observabilidad parcial introducida por la descomposición del problema (donde el contexto completo de una ruta parcial es desconocido hasta que se completa la división), el marco introduce un módulo de contexto mejorado con historial. Este módulo utiliza una arquitectura LSTM para mantener un estado oculto temporal que agrega información de decisiones históricas durante todo el proceso de construcción de la ruta. Esto permite que el modelo infiera estados latentes del problema y proporciona una arquitectura neuronal unificada capaz de manejar diversas variantes del CVRP sin rediseño manual.

Contribuciones Clave

• Marco Unificado con Conocimiento Incrustado: El artículo integra el RL con la heurística RFCS, combinando métodos generales basados en aprendizaje con principios de diseño algorítmico. Esto permite una adaptación flexible a diversas restricciones específicas del problema (por ejemplo, rutas abiertas, cargas de retorno, ventanas de tiempo) dentro de una única arquitectura de red.
• Módulo de Contexto Mejorado con Historial: Los autores introducen un mecanismo que preserva una arquitectura neuronal unificada a través de variantes generales del CVRP. Al codificar el contexto de decisión en evolución en un estado oculto aprendido mediante LSTM, el marco simplifica el diseño de características de contexto y maneja eficazmente restricciones complejas sin requerir ingeniería de contexto específica del problema.
• Integración de Programación Dinámica: El marco aprovecha un solucionador basado en DP para proporcionar divisiones óptimas y señales de recompensa, asegurando que la política de RL aprenda a cooperar con restricciones algorítmicas en lugar de depender exclusivamente de una aproximación de extremo a extremo.

Resultados Experimentales
Se realizaron experimentos extensos en 16 variantes del CVRP (incluyendo problemas atómicos y sus combinaciones) con 50 y 100 nodos.

• Calidad de la Solución: El marco propuesto (RFCS) superó consistentemente a los métodos basados en aprendizaje más avanzados (MTPOMO, MvMoE, RouteFinder) en la mayoría de las variantes. Logró una reducción promedio en la brecha de optimalidad del 2,60 % (mejor línea base) al 1,82 % en comparación con las soluciones de mejor conocimiento.
• Generalización Zero-Shot: El marco demostró capacidades de transferencia zero-shot superiores. Cuando se probó en distribuciones de capacidad de vehículos no vistas (50–90) y restricciones mixtas de carga de retorno, RFCS mantuvo un mejor rendimiento que las líneas base.
• Escalabilidad: El método escaló eficazmente a instancias grandes (500 y 1000 nodos) sin ajuste fino, superando a las líneas base tanto en costo como en tiempo de inferencia.
• Estudios de Ablación: Eliminar el módulo mejorado con historial (reemplazando LSTM con una capa totalmente conectada) resultó en una caída significativa del rendimiento, confirmando la necesidad de información histórica. Además, aplicar el módulo DP post-hoc a soluciones de otros métodos de aprendizaje produjo solo mejoras marginales, destacando que la señal de recompensa basada en DP es crucial durante la fase de entrenamiento para que el agente RL aprenda una cooperación efectiva.

Significado y Afirmaciones
El artículo afirma que el marco propuesto ofrece un enfoque unificado y eficiente para resolver diversas variantes del CVRP. Al incrustar conocimiento del dominio (mediante la heurística RFCS y el solucionador DP) en el bucle de entrenamiento de RL, el método supera las limitaciones de los enfoques puramente impulsados por datos que carecen de conocimiento explícito de resolución de problemas. Los autores afirman que este enfoque logra un equilibrio favorable entre la calidad de la solución y la eficiencia de inferencia, ofreciendo una arquitectura flexible que se generaliza sin problemas a través de múltiples tipos de problemas (por ejemplo, ruta abierta, carga de retorno, ventana de tiempo) sin adaptación adicional. El trabajo sugiere que integrar principios de diseño algorítmico con redes neuronales es un camino viable para mejorar la calidad de la solución en la optimización combinatoria.