Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Este artículo presenta un nuevo enfoque computacional para el problema de enrutamiento dinámico de vehículos que integra una búsqueda de inserción rápida para la confirmación inmediata de solicitudes anticipadas con un algoritmo de optimización continua guiado por aprendizaje por refuerzo, logrando así aumentar significativamente el número de solicitudes atendidas en servicios de microtránsito en comparación con métodos existentes.

Lo esencial

Imagina que eres el director de una flota de taxis o autobuses pequeños (llamados "microtransit") que operan en una ciudad. Tu trabajo es recibir llamadas de personas que necesitan un viaje, decidir si puedes llevarlos y, si es así, planificar la ruta perfecta para que todos lleguen a tiempo.

Este problema es como intentar resolver un rompecabezas gigante que cambia constantemente: cada vez que alguien llama, las piezas se mueven, y tienes que reorganizar todo al instante.

Aquí te explico qué hace este paper, usando una analogía sencilla:

1. El Problema: La Duda del "Sí" o "No"

Antes, las agencias de transporte tenían dos opciones, pero ninguna era perfecta:

• Opción A (El "Sí" rápido pero rígido): Cuando alguien llamaba, le decían "¡Sí, te llevamos!" en 1 segundo. Pero una vez dicho "sí", el conductor tenía que seguir ese plan exacto. Si llegaba otro pasajero que podría haber hecho el viaje más eficiente, no podían cambiar la ruta. Era como si te comprometieras a una cita y luego, aunque tuvieras una oportunidad mejor, no pudieras cambiar de planes.
• Opción B (El "Tal vez" flexible pero lento): Esperaban a tener más información para planear la ruta perfecta, pero esto significaba que el pasajero tenía que esperar mucho tiempo para saber si lo aceptarían. Era como si el conductor dijera: "Déjame pensarlo... quizás mañana te digo". Eso no sirve para alguien que necesita ir al trabajo ahora.

El nuevo enfoque de este paper quiere tener lo mejor de los dos mundos: decirte "Sí" o "No" en menos de un segundo, pero luego seguir ajustando el plan en secreto para que sea lo más eficiente posible.

2. La Solución: El "Cocinero Rápido" y el "Chef de Alta Cocina"

Los autores proponen un sistema con dos "cerebros" trabajando juntos:

• El Cerebro Rápido (Confirmación Prompt): Cuando llega una nueva solicitud, este cerebro actúa como un cocinero rápido. Mira la cocina (las rutas actuales de los conductores) y en una fracción de segundo decide: "¿Puedo meter este nuevo pedido en la ruta sin romper nada?". Si la respuesta es sí, le dice al pasajero: "¡Listo, te recogemos!". Esto da tranquilidad al pasajero.
• El Cerebro Lento (Optimización Continua): Mientras el pasajero espera, el Chef de Alta Cocina (un algoritmo llamado "Anytime") empieza a trabajar. Este chef no tiene prisa por responder al pasajero, pero sí tiene tiempo hasta que llegue la siguiente llamada. Mientras tanto, reorganiza las rutas, cambia el orden de las paradas y busca formas de que los conductores no pierdan tiempo. Es como si, mientras cocinas la cena, reorganizaras los ingredientes para que la comida salga más rica y rápida.

3. El Secreto: El "Oráculo" (Aprendizaje por Refuerzo)

Aquí viene la parte mágica. ¿Cómo sabe el sistema qué ruta es la mejor?
Antes, los sistemas usaban reglas simples (como "llena el autobús lo más posible"). Pero a veces, llenar el autobús ahora significa que no podrás aceptar a 10 personas más tarde que necesitan ir a otro lado.

Este paper usa una Inteligencia Artificial entrenada como un "Oráculo".

• Imagina que entrenamos a un perro sabio con miles de simulaciones de días de tráfico.
• Este perro aprende a no mirar solo el "ahora" (miopicamente), sino a pensar en el "futuro" (no miope).
• Aprende que a veces es mejor decir "no" a un pasajero hoy, o cambiar una ruta, para poder aceptar a 5 pasajeros más mañana.
• Este "Oráculo" guía tanto al "Cocinero Rápido" como al "Chef Lento" para que tomen decisiones que maximicen el número total de personas que pueden ser transportadas a lo largo del día.

4. Los Resultados: ¿Funciona?

Los autores probaron su sistema con datos reales de una ciudad de EE. UU. y con datos de taxis de Nueva York.

• Velocidad: Pueden confirmar un viaje en 0.2 segundos (¡más rápido que un parpadeo!).
• Eficiencia: Logran rechazar mucho menos viajes que los sistemas actuales. Es decir, logran llevar a más personas a su destino sin que nadie se quede esperando.

En Resumen

Este paper presenta un sistema inteligente para transporte a la demanda que actúa como un buen anfitrión:

1. Te responde inmediatamente si puedes venir a tu fiesta (confirmación rápida).
2. Mientras tanto, reorganiza la música y la comida en la cocina para que todos los invitados lleguen cómodos y a tiempo (optimización continua).
3. Usa una "intuición" aprendida por una computadora (el Oráculo) para tomar decisiones que beneficien a todos los invitados del día, no solo a los que llegan ahora.

Es una gran mejora para hacer que el transporte público a la demanda sea más rápido, más fiable y más eficiente.

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Resumen Técnico: Problema de Enrutamiento Dinámico de Vehículos con Confirmación Rápida de Solicitudes Anticipadas

1. El Problema

El artículo aborda una brecha crítica en la operación de servicios de transporte bajo demanda (microtránsito), específicamente en el Problema de Enrutamiento Dinámico de Vehículos (DVRP).

• Contexto: Las agencias de tránsito reciben solicitudes de viaje de forma secuencial mientras los vehículos están en operación. Estas solicitudes pueden ser inmediatas o anticipadas (reservadas con horas de antelación).
• El Dilema Actual: Las aproximaciones existentes se dividen en dos categorías, ninguna de las cuales satisface completamente las necesidades prácticas:
  1. Confirmación Rápida: Deciden aceptar/rechazar inmediatamente y asignan la ruta, pero carecen de la capacidad de optimizar continuamente las rutas de las solicitudes ya aceptadas, lo que limita la eficiencia a largo plazo.
  2. Optimización Continua: Optimizan constantemente los itinerarios para maximizar la tasa de servicio, pero retrasan la confirmación a los pasajeros, lo que reduce la usabilidad del servicio.
• Objetivo: Desarrollar un enfoque que ofrezca confirmación inmediata (en fracciones de segundo) para cada solicitud, garantizando que las solicitudes aceptadas puedan ser servidas, mientras se permite la optimización continua de las rutas entre la llegada de nuevas solicitudes para maximizar la tasa de servicio a largo plazo.

2. Metodología

Los autores proponen un marco computacional novedoso que integra dos algoritmos complementarios dentro de un proceso de toma de decisiones basado en Aprendizaje por Refuerzo (RL).

• Formulación del Problema (MDP):

  • El problema se modela como un Proceso de Decisión de Markov (MDP).
  • Estado ($s_t$): Incluye la ubicación de los vehículos, la lista de solicitudes aceptadas, los planes de ruta actuales y la nueva solicitud entrante.
  • Acción ($a_t$): Decidir aceptar o rechazar la solicitud y generar un nuevo conjunto de planes de ruta factibles.
  • Recompensa: 1 si se acepta la solicitud, 0 si se rechaza. El objetivo es maximizar la recompensa acumulada a largo plazo (tasa de servicio).

• Arquitectura de Dos Etapas:

  1. Confirmación Rápida (Quick Insertion Search):
     • Al llegar una solicitud, se ejecuta un algoritmo de búsqueda rápida.
     • Restringe la búsqueda a inserciones simples (agregar la nueva solicitud a los planes existentes sin reordenar solicitudes previas) para garantizar una respuesta en milisegundos.
     • Utiliza una función objetivo aprendida para decidir la aceptación.
  2. Optimización Continua (Anytime Algorithm):
     • Entre la llegada de dos solicitudes consecutivas, el sistema ejecuta un algoritmo Anytime (en este caso, Recocido Simulado).
     • Este algoritmo mejora iterativamente los planes de ruta (mediante operaciones de intercambio, movimiento, desplazamiento y reversión) para acomodar mejor las solicitudes futuras.
     • Puede detenerse en cualquier momento (cuando llega la siguiente solicitud) entregando la mejor solución encontrada hasta ese instante.

• Aprendizaje de la Función Objetivo (Reinforcement Learning):

  • En lugar de usar una función objetivo miope (como maximizar la tasa de servicio inmediata), los autores entrenan una función de valor de acción ($Q$) no miope.
  • Entrenamiento: Utilizan un enfoque híbrido:
    1. Pre-entrenamiento Supervisado: Se simula una política simple (aceptar siempre si es factible) para generar datos y estimar valores de $Q$ basados en recompensas futuras.
    2. Ajuste Fino con RL: Se aplica Q-learning para refinar la función $Q$ y aprender una política óptima que maximice la tasa de servicio a largo plazo.
  • Representación de Características: Se utilizan vectores de características fijos (tiempo ocioso total, disponibilidad temporal y disponibilidad espacio-temporal) para alimentar redes neuronales (MLP, KAN o CNN).

3. Contribuciones Clave

1. Nueva Formulación del Problema: Introduce formalmente el DVRP con confirmación anticipada y optimización continua, un escenario realista no cubierto por la literatura previa.
2. Algoritmo Híbrido: Propone la combinación de una búsqueda de inserción rápida (para la confirmación) con un algoritmo Anytime (para la optimización), resolviendo el conflicto entre velocidad de respuesta y eficiencia operativa.
3. Función Objetivo No Miopica: Utiliza RL para aprender una función de valor que guía tanto la decisión de aceptación como la optimización de rutas hacia soluciones que maximizan el rendimiento a largo plazo, en lugar de solo el inmediato.
4. Validación en Datos Reales: Demuestra la viabilidad del enfoque utilizando un conjunto de datos real de microtránsito de una agencia de EE. UU., superando a los enfoques existentes.

4. Resultados

Los experimentos se realizaron en dos conjuntos de datos: datos reales de microtránsito de una ciudad de EE. UU. y el conjunto de datos de taxis de NYC (adaptado). Se compararon contra Google OR-Tools, un enfoque de Horizonte Rodante (RH) y un enfoque de Búsqueda de Árbol Monte Carlo (MC VRP).

• Tiempo de Confirmación:
  • El enfoque propuesto confirma solicitudes en ~0.2 segundos (datos de microtránsito) y ~1 segundo (datos de NYC), lo cual es suficiente para la operación en tiempo real.
  • Es comparable o ligeramente superior en velocidad a OR-Tools, pero mucho más rápido que los enfoques de Horizonte Rodante (que tardan segundos o minutos).
• Tasa de Rechazo (Service Rate):
  • El método propuesto reduce drásticamente la tasa de rechazo a aproximadamente 1% en datos de microtránsito.
  • Supera significativamente a todos los métodos baselines (OR-Tools, RH, MC VRP) tanto en la tasa de rechazo como en el tiempo de confirmación.
  • Estudios de Ablación: Se demostró que la optimización continua (usar el tiempo entre solicitudes) es crucial, ya que aumentar el tiempo de ejecución del algoritmo Anytime reduce la tasa de rechazo. Asimismo, el uso de la función $Q$ aprendida (no miope) es superior a usar heurísticas simples.

5. Significado e Impacto

Este trabajo es fundamental para el desarrollo de servicios de microtránsito bajo demanda viables y eficientes.

• Experiencia del Usuario: Permite a los pasajeros reservar viajes con antelación y recibir una confirmación inmediata, lo cual es esencial para la adopción del servicio y la planificación personal.
• Eficiencia Operativa: Al permitir la reoptimización continua de las rutas, las agencias pueden servir a más pasajeros con la misma flota de vehículos, reduciendo costos y mejorando la sostenibilidad.
• Viabilidad Técnica: Demuestra que es posible combinar la rigidez necesaria para la confirmación garantizada con la flexibilidad necesaria para la optimización logística, utilizando técnicas modernas de aprendizaje automático y algoritmos heurísticos.

En resumen, el artículo presenta una solución robusta que cierra la brecha entre la necesidad de respuesta inmediata y la optimización logística continua, ofreciendo un marco escalable para el futuro del transporte público bajo demanda.