Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

Resumen Técnico: Heurística de Densidad de Recompensa para el Enrutamiento Dinámico de Múltiples Vehículos

Definición del Problema
El artículo aborda una variante dinámica y en línea (online) del Problema de Enrutamiento de Vehículos (VRP) que integra elementos del Problema de Oriente (Orienteering Problem, OP). En esta formulación, una flota de vehículos opera dentro de un horizonte de tiempo fijo para maximizar la recompensa acumulada. A diferencia de las variantes estáticas de VRP, las tareas llegan de forma dinámica (online), lo que requiere una replanificación continua. El problema está limitado por un presupuesto de tiempo por vehículo, donde un vehículo solo puede ser asignado a una tarea si la suma del tiempo de viaje y el tiempo de servicio no excede su presupuesto restante. Esta estructura modela escenarios del mundo real como la asignación de tareas de drones autónomos y el despacho de taxis urbanos, donde las decisiones de asignación deben tomarse en milisegundos a medida que surgen nuevas solicitudes.

Metodología
Los autores proponen y evalúan una "Heurística de Densidad de Recompensa" (denominada la heurística de Eficiencia) frente a cuatro heurísticas de construcción y tres algoritmos metaheurísticos.

1. Enfoque Propuesto (Heurística de Eficiencia):
   El núcleo del método es una función de puntuación basada en la densidad de recompensa, definida como la relación entre la recompensa de una tarea ($R$) y su costo de tiempo total (tiempo de viaje $d$ + tiempo de servicio $s$):
   $$\eta(\tau) = \frac{R(\tau)}{d(v, \tau) + s(\tau)}$$
   Se prueban dos instancias:

   • Greedy-Efficiency (Eficiencia Codiciosa): Asigna cada vehículo disponible al objetivo factible no reclamado con la puntuación más alta de forma secuencial.
   • Hungarian-Efficiency (Eficiencia Húngara): Formula la asignación como un Problema de Asignación Lineal (LAP) utilizando la densidad de recompensa negativa ($-\eta$) como matriz de costos, resuelto de forma óptima mediante el algoritmo húngaro.

2. Líneas Base Comparativas:

   • Heurísticas de Construcción: Greedy-Nearest (minimiza la distancia), Greedy-Reward (maximiza la recompensa bruta), Hungarian-Time (minimiza el tiempo de viaje) y Hungarian-Reward (maximiza la recompensa bruta mediante LAP).
   • Metaheurísticas: Búsqueda de Vecindad Grande Adaptativa (ALNS), Algoritmo Genético (GA) y Recocido Simulado (SA). Estas se reinicializan en cada evento de replanificación para adaptarse al panorama cambiante.

3. Configuración Experimental:
   El estudio utiliza un simulador basado en eventos donde la replanificación se activa tras la finalización de una tarea. Las evaluaciones se realizan en dos dominios:

   • Entorno de Drones Sintéticos: 12, 20 y 50 drones operando en un mapa de $5000 \times 5000$ con 50–200 objetivos.
   • Despacho de Taxis del Mundo Real: 50 y 200 taxis operando durante 120 minutos contra aproximadamente 7,600 tareas derivadas del conjunto de datos NYC TLC Yellow Cab 2024.
     El rendimiento se mide mediante la recompensa acumulada (o ingresos) y el tiempo de planificación (costo computacional).

Resultos Clave
Los experimentos demuestran un claro dominio de Pareto de las heurísticas de Eficiencia sobre todos los métodos competidores:

• Calidad de la Solución: Las heurísticas de Eficiencia (tanto las variantes Greedy como las Hungarian) logran una calidad de solución estadísticamente indistinguible de las metaheurísticas con mejor desempeño (ALNS, GA, SA) en todos los tamaños de flota y dominios. En contraste, las heurísticas más simples (Greedy-Nearest, Greedy-Reward, Hungarian-Time, Hungarian-Reward) rinden consistentemente por debajo, con déficits estadísticamente significativos en recompensa/ingresos.
• Eficiencia Computacional: Las heurísticas de Eficiencia requieren de dos a tres órdenes de magnitud menos de tiempo de planificación que las metaheurísticas.
  • En el escenario de 50 drones, Hungarian-Efficiency requirió ~128 ms, mientras que GA requirió ~1.1 millones de ms, ALNS ~42,654 ms y SA ~5,247 ms.
  • En el escenario de 200 taxis, Hungarian-Efficiency requirió ~363 ms, mientras que GA requirió ~4.58 millones de ms.
• Greedy vs. Optimalidad Global: El estudio encontró que el enfoque Greedy-Efficiency, computacionalmente más barato, produce resultados estadísticamente equivalentes al enfoque Hungarian-Efficiency, que es globalmente óptimo, lo que sugiere que la garantía de optimalidad global del algoritmo húngaro confiere un beneficio práctico limitado en estos entornos dinámicos de alta frecuencia.

Significancia y Reivindicaciones
El artículo sostiene que la elección del criterio de optimización (densidad de recompensa/eficiencia) es más impactante que la sofisticación del mecanismo de asignación.

• Ventaja Estructural: El éxito de la heurística de Eficiencia sugiere que, en el enrutamiento dinámico de maximización de recompensas, la relación entre la recompensa y el costo (eficiencia) es un proxy superior para la generación de valor a nivel de flota en comparación con la optimización de la recompensa bruta o el tiempo de viaje por sí solos.
• Viabilidad Práctica: Las metaheurísticas, aunque capaces de alcanzar techos de calidad de solución similares, incurren en tiempos de planificación que las hacen impracticables para el despacho en tiempo real. Un ciclo de planificación que toma minutos se describe como "activamente perjudicial" en operaciones en vivo porque el entorno cambia materialmente antes de que se produzca una solución.
• Dominio de Pareto: Las heurísticas de Eficiencia establecen el dominio de Pareto en la frontera de recompensa-computación, ofreciendo un rendimiento cercano al óptimo con un overhead computacional mínimo.

Los autores concluyen que, para el despacho de flotas en tiempo real, el diseño cuidadoso de la función objetivo (específicamente la puntuación de densidad de recompensa) supera a la complejidad algorítmica, haciendo de la heurística de Eficiencia un candidato robusto para sistemas operativos donde el tiempo de planificación es una restricción vinculante. El estudio reconoce las limitaciones respecto a la naturaleza basada en simulaciones de los experimentos y el enfoque en los ingresos como un objetivo único, señalando que trabajos futuros deberían explorar restricciones multiobjetivo y demanda no estacionaria.