Resumen Técnico: COAgents – Marco de Agentes Múltiples para Problemas de Ruteo

Enunciado del Problema

Los Problemas de Ruteo de Vehículos (VRP), incluido el Problema de Ruteo de Vehículos con Capacidad (CVRP) y el Problema de Ruteo de Vehículos con Ventanas de Tiempo (VRPTW), son centrales en la logística y la fabricación, pero siguen siendo computacionalmente intratables a gran escala debido a su complejidad combinatoria. Los métodos heurísticos tradicionales dependen de reglas diseñadas a mano para mejoras locales y diversificación (saltos) para escapar de mínimos locales. Sin embargo, estos conjuntos de reglas estáticas a menudo carecen de generalización entre instancias diversas, requieren experiencia de dominio extensa para su ajuste y no pueden adaptarse a distribuciones de problemas en evolución. Aunque han surgido enfoques de "Aprender a Buscar" (L2S), muchos se centran únicamente en la selección de operadores o en decisiones basadas en el estado actual sin modelar eficazmente el historial de búsqueda ni la estructura más amplia del espacio de búsqueda.

Metodología: El Marco COAgents

Los autores proponen COAgents, un marco de agentes múltiples cooperativos que modela el proceso de búsqueda del VRP como un recorrido por un grafo. La innovación central es el Grafo de Búsqueda Parcial (PSG), un subgrafo dinámicamente construido donde los nodos representan soluciones exploradas y las aristas representan movimientos locales o grandes perturbaciones (saltos).

1. El Grafo de Búsqueda Parcial (PSG)

El PSG sirve como una codificación de estado consciente del historial. Es un grafo dirigido y desconectado donde:

• Nodos: Representan soluciones individuales encontradas durante la búsqueda.
• Aristas: Representan movimientos de vecindad (refinamientos locales) o saltos (grandes perturbaciones).
• Estructura: El grafo se descompone en componentes conexos (muestras), cada uno explorando la vecindad de un óptimo local. Esta estructura permite al sistema rastrear la trayectoria de la búsqueda e identificar patrones en la exploración.

2. Arquitectura de Agentes Múltiples

COAgents emplea tres agentes aprendidos que operan sobre el PSG, todos compartiendo una columna vertebral neuronal común compuesta por Redes de Convolución Gráfica con Puertas (GGCN) y Transformadores:

• Agente de Selección de Nodos (NSA): Selecciona una solución candidata (nodo) del PSG para servir como la actual para el siguiente paso de búsqueda local. Prioriza regiones prometedoras del espacio de búsqueda basándose en datos históricos.
• Agente de Selección de Movimientos (MSA): Predice el operador de vecindad (movimiento) más prometedor para aplicar a la solución seleccionada, impulsando la intensificación local.
• Agente de Salto (JA): Se activa cuando la búsqueda se estanca (indicado por intentos fallidos repetidos); este agente genera una solución completamente nueva desde cero basándose en el historial de búsqueda. A diferencia de los operadores estándar, el Agente de Salto realiza un reinicio aprendido para escapar de mínimos locales y dirigir la búsqueda hacia regiones inexploradas.

3. Arquitectura del Modelo y Entrenamiento

• Codificación: Las soluciones se codifican en características de nodo ($u_i$) que capturan atributos globales (valor objetivo, factibilidad) y matrices de estructura interna ($V_i$). Las incrustaciones posicionales se derivan mediante codificadores de paseos aleatorios para la estructura del PSG y codificadores específicos del problema para la topología de la solución.
• Bloques Centrales: La red utiliza capas GGCN entrelazadas para capturar patrones estructurales locales dentro del PSG y capas de Transformador para modelar dependencias de largo alcance entre todos los nodos. Módulos específicos del problema de Extremo a Extremo (E2E) refinan la estructura interna del problema combinatorio.
• Entrenamiento:
  • NSA y MSA: Entrenados conjuntamente como tareas de clasificación binaria para identificar la solución más cercana al óptimo y el mejor movimiento siguiente, respectivamente, minimizando la entropía cruzada binaria conjunta.
  • Agente de Salto: Entrenado por separado para predecir una matriz de adyacencia estocástica que representa una nueva solución. Se entrena contra un conjunto de soluciones de referencia casi óptimas para reducir la ambigüedad de las etiquetas.
• Inferencia: El marco ejecuta un bucle donde el NSA selecciona un nodo, el MSA selecciona un movimiento y el PSG se actualiza. Si ocurre estancamiento, se invoca el JA. Esto continúa hasta alcanzar un presupuesto computacional (límite de tiempo o de nodos).

Contribuciones Clave

1. Nuevos Agentes Aprendidos: Introducción del Agente de Selección de Nodos y el Agente de Salto junto con un Agente de Selección de Movimientos. Estos agentes reemplazan colectivamente las reglas diseñadas a mano, permitiendo políticas de decisión adaptativas y basadas en datos para la selección de soluciones, aplicación de operadores y diversificación.
2. Arquitectura Unificada con Pesos Compartidos: Todos los agentes comparten una columna vertebral neuronal común, facilitando un entrenamiento eficiente en datos, transferibilidad a nuevas variantes de problemas y una menor necesidad de ajuste experto.
3. Representación del Grafo de Búsqueda Parcial: Formalización del PSG como una codificación de estado general y consciente del historial que impulsa las decisiones de los agentes, diferenciando este enfoque de los métodos que dependen únicamente del estado actual.
4. Marco Adaptativo al Solucionador y al Problema: COAgents envuelve rutinas de búsqueda local existentes y solucionadores neuronales, mejorándolos con políticas adaptativas que se adaptan perfectamente a diferentes variantes del VRP.

Resultados Experimentales

El marco se evaluó en los puntos de referencia CVRP y VRPTW utilizando 10,000 instancias de entrenamiento y conjuntos de prueba estándar (por ejemplo, 1,000 instancias de VRPTW).

• Rendimiento en VRPTW: COAgents estableció un nuevo estado del arte entre los métodos basados en aprendizaje.
  • Redujo la brecha de optimalidad con respecto a las soluciones de mejor conocimiento en un 14% (en N=100) y un 44% (en N=50) en relación con el solucionador neuronal más fuerte (POMO).
  • Redujo la brecha en un 21% (N=100) y un 40% (N=50) en relación con la Búsqueda de Vecindad Grande Adaptativa (ALNS).
  • Superó a todos los puntos de referencia neuronales, OR-Tools y ALNS en el conjunto de pruebas VRPTW.
• Rendimiento en CVRP: COAgents se mantuvo competitivo con los puntos de referencia de aprendizaje para buscar de última generación, demostrando efectividad incluso con un módulo de codificación compacto y específico del problema.
• Estudio de Ablación: Eliminar el Agente de Salto casi duplicó la brecha de optimalidad (de 3.7% a 7.8%), destacando su papel crítico para escapar de mínimos locales. Los agentes de Selección de Nodos y Movimientos también contribuyeron significativamente al rendimiento.
• Comparación con ALNS: Incluso cuando ALNS tuvo acceso a un grupo más grande de operadores diseñados a mano (incluyendo 27 pares adicionales de destrucción-reparación), COAgents lo superó consistentemente, validando la superioridad de las políticas aprendidas sobre las heurísticas estáticas.

Significado y Afirmaciones

El artículo afirma que COAgents representa un cambio significativo desde las heurísticas estáticas y diseñadas a mano hacia sistemas de agentes múltiples adaptativos que aprenden del historial de búsqueda. Al modelar explícitamente el espacio de búsqueda como un grafo y utilizar un Grafo de Búsqueda Parcial, el marco permite a los agentes tomar decisiones informadas sobre intensificación y diversificación que los métodos tradicionales no pueden lograr.

Los autores posicionan a COAgents como una alternativa convincente a las heurísticas clásicas y a los métodos existentes de aprendizaje para construir/buscar, particularmente para problemas complejos como el VRPTW, donde la generalización y la adaptabilidad son cruciales. Si bien reconocen que la implementación actual en Python es más lenta que las heurísticas basadas en C/C++ (como LKH3 y HGS) y que la escalabilidad a instancias muy grandes sigue siendo un desafío debido a los costos de atención cuadrática, el marco demuestra que el control de búsqueda aprendido y consciente del historial puede reducir significativamente la brecha hacia las soluciones de mejor conocimiento en problemas de ruteo.