Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Resumen Técnico: Modelo de Fundación Asistido por Visión para Resolver Problemas de Enrutamiento de Vehículos Multitarea

Definición del Problema
Los Problemas de Enrutamiento de Vehículos (VRP) multitarea implican la optimización de los costes de enrutamiento mientras se satisfacen diversas restricciones de los clientes, tales como demandas de retorno (B), rutas abiertas (O), límites de duración (L) y ventanas de tiempo (TW). La combinación de estas restricciones crea un número exponencial de variantes de VRP (por ejemplo, 16 variantes a partir de cuatro restricciones). Los resolvedores neuronales existentes suelen depender de modalidades basadas en grafos, codificando las restricciones como atributos de los nodos. Sin embargo, estos enfoques enfrentan limitaciones: les cuesta aprender relaciones espaciales complejas e interacciones de restricciones a medida que las tareas se vuelven más intrincadas, y entrenar modelos separados para cada variante es computacionalmente prohibitivo. Además, los métodos basados en visión existentes para la optimización combinatoria se han limitado a escenarios de tarea única (por ejemplo, TSP) y a menudo no logran codificar atributos específicos de la tarea, como las demandas o las ventanas de tiempo, dentro de la representación visual.

Metodología: Modelo de Fundación Asistido por Visión (VaFM)
Los autores proponen VaFM, un modelo de fundación que integra modalidades de visión y de grafos para resolver 16 variantes diferentes de VRP simultáneamente. La arquitectura consta de tres componentes principales:

1. Generación de Imágenes de VRP Multitarea: Para abordar la falta de representación de restricciones en las imágenes de VRP existentes, los autores diseñan dos imágenes de entrada por instancia: una "imagen de demanda" y una "imagen de ventana de tiempo (TW)".

   • Codificación Visual: Las coordenadas de los clientes se mapean a índices de píxeles. La intensidad del color del nodo representa variables continuas (magnitud de la demanda o duración de la ventana de tiempo).
   • Representación de Restricciones: Las restricciones discretas se codifican mediante pistas visuales: las Rutas Abiertas (O) se indican mediante la inversión del color de fondo; los Límites de Duración (L) se muestran cambiando la forma de los nodos (de rectángulos a signos más); las demandas de retorno (B) utilizan colores de nodo distintos (verde para el transporte de ida, azul para el de retorno).
   • Entrada: Las dos imágenes se concatenan y son procesadas por un codificador de visión basado en CNN (ResNet-18).

2. Módulo de Fusión de Atención Cruzada Híbrida: Para superar el campo receptivo fijo de los estándares de incrustación de parches (patch embeddings) y adaptarse a los requisitos variables de las tareas, VaFM emplea un mecanismo de fusión híbrida.

   • Mecanismo: Se extraen mapas de características de las dos últimas capas del codificador de visión. Las incrustaciones de parches se derivan de estos mapas y se alinean con las incunciones de los nodos del grafo.
   • Campo Receptivo Adaptativo: Se utiliza un mecanismo de atención cruzada donde las incrustaciones de los nodos actúan como consultas (queries) y los mapas de características aplanados de la capa más profunda actúan como claves (keys) y valores (values). Esto permite al modelo agregar información global relevante (de las capas profundas) mientras retiene el contexto local detallado (de las capas superficiales), creando efectivamente campos receptivos adaptativos para diferentes restricciones.

3. Tarea Auxiliar Consciente de las Restricciones: Para mitigar el problema de la distribución desequilibrada de píxeles (donde las restricciones como O o L ocupan más píxeles que B o TW, lo que podría causar que el modelo pase por alto estas últimas), se introduce una tarea auxiliar.

   • Implementación: Se adjunta un clasificador al codificador de visión para predecir la presencia de cada una de las cuatro restricciones (O, L, B, TW).
   • Función de Pérdida: Se aplica una pérdida de Entropía Cruzada Binaria (BCE) a esta tarea auxiliar, asegurando que el modelo aprenda representaciones equilibradas para todas las restricciones, independientemente de su prominencia visual.
   • Objetivo de Entrenamiento: La pérdida total es una suma ponderada de la pérdida de Aprendizaje por Refuerzo (RL) para la minimización del coste de enrutamiento y la pérdida de clasificación auxiliar.

Contribuciones Clave

• Primer Modelo de Fundación Asistido por Visión para VRPs Multitarea: El trabajo introduce el primer marco que combina modalidades de grafo y visión para manejar múltiples variantes de VRP simultáneamente, yendo más allá de los resolvedores de visión de tarea única.
• Novedosa Codificación Visual y Fusión: El artículo propone diseños de imagen específicos para codificar diversas restricciones y un módulo de fusión de atención cruzada híbrida que permite campos receptivos adaptativos, abordando las limitaciones de los tamaños de parche fijos en entornos multitarea.
• Aprendizaje de Restricciones Equilibrado: La introducción de una tarea auxiliar consciente de las restricciones con pérdida BCE evita eficazmente que el modelo descuide las restricciones con menos píxeles visuales.

Resultados Experimentales
El modelo fue evaluado en 16 variantes de VRP con 50 y 100 nodos de clientes, comparándolo contra métodos de vanguardia (SOTA) incluyendo HGS-PyVRP, OR-Tools y varios resolvedores neuronales (MTPOMO, MVMoE, RF-MoE-L).

• Rendimiento: VaFM (específicamente la variante VaFM-MoE-L) logró el mejor rendimiento en 15 de 16 casos para N=50 y en 12 de 16 para N=100.
• Restricciones Complejas: La brecha de rendimiento entre VaFM y las bases de solo grafos se amplió a medida que aumentaba el número de restricciones. Por ejemplo, en tareas con 3 o 4 restricciones, VaFM mostró mejoras significativas en la brecha de optimalidad en comparación con la base RF-MoE-L.
• Generalización: Aunque VaFM mostró una fuerte generalización zero-shot a escalas mayores (N=200) y combinaciones de restricciones no vistas (backhaul mixto), exhibió cierta inestabilidad en conjuntos de datos del mundo real y tareas específicas con mucha carga de ventanas de tiempo, lo que sugiere limitaciones en la discriminación basada en color a escalas mayores.
• Eficiencia: VaFM requiere un tiempo de inferencia ligeramente mayor que las bases de solo grafos debido a la rama de visión, pero sigue siendo significativamente más rápido que los resolvedores heurísticos como HGS-PyVRP.

Significado y Reivindicaciones
El artículo afirma que VaFM demuestra el potencial de integrar modalidades de visión en los resolvedores neuronales basados en grafos para mejorar la representación de problemas de optimización complejos con múltiples restricciones. Los autores sostienen que su enfoque captura con éxito la semántica a nivel de parche (distribuciones espaciales de la demanda y patrones de tiempo de servicio) que son difíciles de aprender para los modelos de grafos puros. Los resultados sugieren que los modelos asistidos por visión son particularmente superiores para las variantes de VRP con restricciones complejas e interactivas. Sin embargo, los autores reconocen modestamente las limitaciones, señalando que la codificación visual actual (que depende de la intensidad de un solo color) puede tener dificultades con la discriminación fina en instancias a gran escala y que se necesita trabajo futuro para mejorar la generalización en conjuntos de datos del mundo real y restricciones no vistas, potencialmente a través de modelos de lenguaje de gran tamaño multimodales.