🤖 machine learning

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

Este artículo presenta un nuevo enfoque de aprendizaje por refuerzo profundo, basado en un modelo JAMPR modificado, que resuelve eficazmente problemas de recogida y entrega de tamaño mediano con restricciones de capacidad y ventanas de tiempo (CPDPTW) en tiempo real y proporciona soluciones subóptimas rápidas para instancias de gran escala que superan los 200 nodos.

Autores originales: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Publicado 2026-08-17

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres el capitán de una flota de camiones de reparto en una ciudad bulliciosa y en constante crecimiento. Tu trabajo es entregar paquetes y recoger devoluciones para cientos de clientes, pero tienes un conjunto estricto de reglas: tus camiones solo pueden transportar cierta cantidad de carga, y cada cliente tiene un horario específico en el que está en casa para recibir un paquete. Si llegas demasiado temprano o demasiado tarde, o si intentas meter demasiadas cajas en la parte trasera de una furgoneta, el plan falla. Este es el "Problema de Recogida y Entrega", un rompecabezas masivo que se vuelve más difícil a medida que se añade más gente a la mezcla.

Durante décadas, las computadoras han intentado resolver esto actuando como calculadoras superrápidas, probando millones de rutas posibles una por una para encontrar el camino perfecto. Pero a medida que las ciudades crecen y el número de paradas explota, estas calculadoras se quedan trabadas. Tardan horas en calcular una ruta que un humano podría esbozar en minutos, o peor aún, se rinden por completo y dicen: "No puedo resolver esto". Aquí es donde entra en juego un nuevo tipo de cerebro informático: el Aprendizaje por Refuerzo Profundo (Deep Reinforcement Learning). No pienses en esto como una calculadora, sino como un personaje de un videojuego que aprende jugando. En lugar de calcular cada posibilidad, juega al juego de las entregas miles de veces, volviéndose más rápido e inteligente con cada ronda, aprendiendo a detectar los mejores movimientos sin necesidad de comprobar cada una de las opciones.

En este artículo, Andrew Soroka y su equipo de la Universidad Estatal de Moscú y el Instituto de Investigaciones Espaciales del RAS decidieron enseñarle a este "cerebro de videojuego" cómo manejar las reglas desordenadas del mundo real de las entregas: el espacio limitado del camión y los estrictos horarios. Tomaron un modelo inteligente ya existente llamado JAMPR y le dieron una mejora especial para entender las reglas de "recogida y entrega", donde un camión podría tener que recoger un paquete en una parada y entregarlo en otra, todo esto mientras hace malabares con los límites de capacidad.

Los investigadores descubrieron que su modelo mejorado es un demonio de la velocidad para ciudades de tamaño pequeño a mediano (con 50 a 200 paradas). En estos escenarios, la IA puede escupir una ruta casi perfecta en los primeros segundos, superando a los métodos tradicionales de "calculadora" que tardan mucho más tiempo incluso para empezar. Es como tener un repartidor que conoce la ciudad tan bien que puede gritar instantáneamente la mejor ruta, mientras que la computadora de la vieja escuela todavía está intentando leer el mapa.

Sin embargo, la historia se vuelve un poco más complicada cuando la ciudad es enorme (400 a 1,000 paradas). Aquí, la IA sigue ganando la carrera de velocidad, ofreciendo una solución "suficientemente buena" casi instantáneamente, mientras que los métodos tradicionales luchan por encontrar cualquier ruta válida en el primer minuto. Pero la IA no es perfecta todavía. Para obtener la ruta absolutamente mejor en estas ciudades gigantes, la IA necesita "entrenar" durante días, lo cual es mucho tiempo. Incluso después del entrenamiento, para los problemas más grandes, la ruta final de la IA sigue siendo aproximadamente un 20% más costosa (en términos de distancia) que la mejor solución que un método tradicional podría encontrar eventualmente si tuviera tiempo ilimitado. De hecho, una vez que el tiempo de optimización pasa apenas unos minutos, los métodos tradicionales realmente superan a la IA, encontrando mejores rutas que la IA no puede igualar sin un entrenamiento significativamente mayor.

El equipo también probó qué tan resistente es su IA cuando las reglas cambian. Descubrieron que la IA es increíblemente confiable dentro de las condiciones de prueba específicas utilizadas: nunca falló en dar alguna solución, incluso cuando el método tradicional se rindió y dijo "imposible" para la misma distribución de problemas. Sin embargo, si el diseño de la ciudad cambia drásticamente —por ejemplo, de una dispersión aleatoria de casas a un patrón donde todos viven en un círculo apretado— el rendimiento de la IA decae un poco, aunque todavía logra superar a los métodos tradicionales durante la primera hora de resolución.

En resumen, el artículo sugiere que este enfoque de aprendizaje profundo es una herramienta poderosa para la logística en tiempo real. No reemplaza totalmente a los métodos antiguos, especialmente para los rompecabezas más grandes y complejos donde se necesita la respuesta absolutamente perfecta. Pero para situaciones en las que necesitas una respuesta rápida y confiable ahora mismo —como un servicio de mensajería reaccionando al tráfico o un aumento repentino en los pedidos— esta IA es un cambio de juego, ofreciendo una solución robusta y rápida donde las herramientas tradicionales a menudo se estancan o fallan.

Resumen Técnico: Aprendizaje por Refuerzo Profundo para CPDPTW

Definición del Problema

El artículo aborda el Problema de Recogida y Entrega con Capacidad y Ventanas de Tiempo (CPDPTW). Este es un problema de optimización combinatoria donde una flota de vehículos debe transportar mercancías desde ubicaciones de recogida específicas hacia ubicaciones de entrega. El problema se caracteriza por tres restricciones principales del mundo real:

Capacidad: Los vehículos tienen un límite de volumen máximo ( $Q$ ).
Ventanas de Tiempo: Los clientes solo están disponibles durante intervalos de tiempo específicos.
Recogida y Entrega (PDP): A diferencia de los Probleos de Rutas de Vehículos (VRP) estándar, las mercancías pueden recogerse en un depósito o en un cliente y entregarse en otro cliente, lo que requiere una secuenciación estricta (recogida antes de la entrega).

Los autores señalan que, aunque existen enfoques clásicos (Programación de Enteros Mixtos, heurísticas), estos tienen dificultades con instancias a gran escala (por ejemplo, >200 nodos) bajo restricciones del mundo real, sufriendo a menudo de altas cargas computacionales, falta de flexibilidad para manejar nuevas restricciones o incapacidad para encontrar soluciones factibles en un tiempo razonable.

Metodología

Los autores proponen un enfoque de Aprendizaje por Refuerzo Profundo (DRL) basado en una arquitectura JAMPR (Modelo de Atención Conjunta para Recogida y Rutas) modificada.

Arquitectura del Modelo

Base: El modelo se basa en el marco JAMPR, que extiende el Modelo de Atención (AM) y las Redes de Punteros (Pointer Networks). Utiliza una estructura de codificador-decodificador con mecanismos de autoatención.
Representación del Estado: El problema se modela como un Proceso de Decisión de Markov (MDP).
- Codificador: Codifica las características de los nodos (coordenadas, demandas, ventanas de tiempo) en vectores de incrustación (embeddings) ocultos.
- Contexto ( $C(t)$ ): Incluye la incrustación del grafo del problema, el índice del depósito, el último nodo añadido y la capacidad restante del vehículo.
- Contexto Extendido: Para manejar el PDP y las ventanas de tiempo, el modelo incorpora incrustaciones específicas para las rutas construidas y las características del vehículo (capacidad residual, nodo actual, tiempo actual) en redes neuronales totalmente conectadas. Esto permite la construcción paralela de múltiples rutas.
Espacio de Acción: La acción se define como un par $(r, i)$ , que representa la selección de un nodo $i$ para ser añadido a una ruta activa $r$ . Se aplica una máscara de factibilidad para asegurar que no se violen las restricciones (capacidad, ventanas de tiempo y orden de PDP).
Política: El decodificador calcula las puntuaciones de atención para los nodos factibles. Estas puntuaciones se utilizan para la selección codiciosa (greedy) o se muestrean mediante una distribución softmax durante el entrenamiento.

Modificaciones para CPDPTW

Los autores introdujeron modificaciones específicas al modelo JAMPR estándar para abordar la naturaleza de PDP del problema:

Máscara de PDP: Se añadió una máscara adicional a la función feasible() para imponer las restricciones de orden de entrega (una recogida debe ocurrir antes de su entrega correspondiente).
Manejo de Restricciones Suaves: Reconociendo que a veces es imposible encontrar una solución 100% factible para todos los clientes en formulaciones estrictas, los autores adoptaron una configuración SUAVE (SOFT setting). La función de costo final es una combinación lineal de la distancia total recorrida y el número de clientes perdidos (ponderados 13:10, respectivamente). Esto asegura que el modelo siempre produzca una solución, incluso si es parcial.

Entrenamiento y Datos

Generación de Datos: Las instancias se generaron basadas en la distribución Solomon R201. Los tamaños del problema variaron de 50 a 1000 nodos. Las capacidades de los camiones y los horizontes temporales se escalaron según el tamaño del problema.
Entrenamiento: Los modelos se entrenaron utilizando aprendizaje por refuerzo con criterios de parada temprana (sin reducción de costo durante 10 pasos). Los tiempos de entrenamiento variaron significamente según el tamaño del problema, oscilando entre 3 horas para problemas de 50 nodos y más de 336 horas para problemas de 1000 nodos.
Línea Base (Baseline): El modelo propuesto se comparó contra Google OR-Tools, un resolvedor heurístico estándar utilizado en aplicaciones del mundo real.

Resultados Clave

El rendimiento fue evaluado en tres categorías de tamaño de problema:

1. Tamaño Pequeño (50 nodos)

Rendimiento: El modelo JAMPR entrenado proporcionó una solución óptima rápida, superando la solución heurística en costo durante los primeros segundos de optimización.
Costo: A medida que el tiempo de optimización aumentaba, los resultados del modelo JAMPR se acercaban gradualmente a los de OR-Tools. Tras un entrenamiento extensivo (723 épocas), los resultados finales diferían de la línea base de OR-Tools en no más de un 0.3%.
Factibilidad: JAMPR resolvió el 100% de las instancias, mientras que OR-Tools falló en encontrar soluciones para un número creciente de instancias a medida que crecía la complejidad del problema.

2. Tamaño Medio (100–200 nodos)

Rendimiento: El modelo proporcionó soluciones subóptimas rápidas que fueron superiores a las metaheurísticas en los segundos iniciales de optimización (15–200% mejor costo que OR-Tools).
Convergencia: Aunque el rendimiento del modelo se estancó rápidamente, superó consistentemente a OR-Tools en velocidad. OR-Tools requirió tiempos de optimización significativamente más largos para acercarse a niveles de costo similares.
Factibilidad: JAMPR mantuvo una tasa de fallo del 0%, resolviendo todas las instancias, mientras que OR-Tools falló en encontrar soluciones factibles para un porcentaje creciente de instancias a medida que aumentaba el tamaño.

3. Tamaño Grande (400–1000 nodos)

Rendimiento: Para problemas de alta dimensionalidad, el modelo neuronal aún proporcionó una solución subóptima rápida que fue significativamente mejor que OR-Tools en los primeros 60 segundos (donde OR-Tools a menudo no encontraba ninguna solución).
Limitaciones: A medida que el tiempo de optimización aumentaba, las metaheurísticas (OR-Tools) eventualmente superaban al modelo neuronal. El resultado final de JAMPR con el tiempo de optimización máximo perdió aproximadamente un 20% del costo de la ruta en comparación con la metaheurística.
Costo de Entrenamiento: El entrenamiento para instancias grandes fue computacionalmente costoso (por ejemplo, 336 horas para 1000 nodos), lo que limitó la capacidad de optimizar completamente el modelo dentro de marcos de tiempo razonables en una sola GPU.

Análisis de Robustez

Desplazamiento de Distribución (Distribution Shift): El modelo demostró robustez ante cambios en la distribución de los datos. Al probarse con una mezcla de distribuciones uniforme y normal, el modelo mantuvo su capacidad de proporcionar soluciones subóptimas rápidas incluso con hasta un 25% de datos de la nueva distribución.
Invarianza de Métrica: El rendimiento del modelo se mantuvo constante cuando los cálculos de distancia se cambiaron de métrica Euclídea a Manhattan.

Significación y Reivindicaciones

El artículo afirma ser la primera aplicación exitosa de un enfoque de aprendizaje por refuerzo profundo (específicamente un modelo JAMPR modificado) para resolver el problema CPDPTW.

Los autores destacan tres contribuciones principales:

Compromiso Velocidad vs. Calidad: El modelo ofrece una solución subóptima rápida (en décimas de segundo) que a menudo es superior a las heurísticas clásicas en las etapas iniciales de optimización. Esto es particularmente valioso para sistemas dinámicos con límites de tiempo estrictos.
Robustez y Factibilidad: A diferencia de las metaheurísticas tradicionales que pueden fallar al encontrar cualquier solución factible para instancias grandes o complejas, el modelo neuronal garantiza una solución (incluso si es parcial, bajo la configuración SUAVE donde se penalizan los clientes perdidos) para todas las instancias del problema, independientemente de su tamaño.
Escalabilidad de la Existencia de Soluciones: La tasa de fallo del modelo neuronal permanece en cero en todos los tamaños probados, mientras que la tasa de fallo de OR-Tools aumenta con el tamaño del problema.

Los autores concluyen que, si bien los modelos de aprendizaje por refuerzo profundo requieren actualmente un tiempo de entrenamiento significativo para problemas de gran escala y pueden no alcanzar aún la optimalidad final de las metaheurísticas para instancias muy grandes, representan una dirección prometedora para la optimización de rutas en tiempo real donde la velocidad y la existencia de la solución son críticas. Sugieren que el trabajo futuro podría implicar la combinación de estos modelos de RL con resolvedores de Programación de Enteros Mixtos (MIP) o el uso de políticas de partición aprendidas para manejar de manera más efectiva los problemas de alta dimensionalidad.