Resumen Técnico: Aprendizaje con Previsión (MnLP)

Enunciado del Problema

Los Problemas de Enrutamiento de Vehículos (VRP), incluido el Problema del Viajante de Comercio (TSP) y el Problema de Enrutamiento de Vehículos con Capacidad (CVRP), son desafíos NP-difíciles prevalentes en logística y planificación industrial. Si bien las políticas de enrutamiento neuronales, particularmente aquellas basadas en arquitecturas Transformer, han surgido como alternativas eficientes a las heurísticas tradicionales, los paradigmas de entrenamiento actuales enfrentan una limitación fundamental.

La mayoría de los enfoques de aprendizaje supervisado (SL) para el enrutamiento neuronal se basan en la predicción del siguiente nodo. En este paradigma, el modelo se entrena para predecir únicamente el nodo inmediato siguiente en un recorrido basándose en el estado actual. Los autores argumentan que este enfoque conduce a una toma de decisiones miope. Dado que la construcción de soluciones para VRP es una tarea de planificación de largo horizonte que involucra cientos o miles de nodos, optimizar únicamente para el paso inmediato siguiente falla en capturar el contexto de largo alcance necesario para la optimalidad global. Esto resulta en acumulación de errores y una tendencia a estancarse en óptimos locales, particularmente a medida que escalan los tamaños del problema.

Metodología: Predicción de Avance Multinodo (MnLP)

Para abordar la miopía de la predicción estándar del siguiente nodo, el artículo propone la Predicción de Avance Multinodo (MnLP), una estrategia de entrenamiento novedosa que extiende el paradigma de aprendizaje supervisado.

Concepto Central

MnLP introduce un mecanismo donde el modelo se entrena para predecir múltiples nodos futuros simultáneamente (por ejemplo, los siguientes $K$ nodos) además del nodo inmediato siguiente. Esto se logra mediante módulos MnLP causales y desechables que operan exclusivamente durante la fase de entrenamiento.

Arquitectura

El marco propuesto se basa en el modelo Codificador Ligero y Decodificador Pesado (LEHD):

1. Codificador Compartido: Un codificador ligero procesa características de nodo crudas (por ejemplo, coordenadas) en incrustaciones de nodo.
2. Decodificador Principal: Predice el nodo inmediato siguiente ($x_t$) utilizando mecanismos de atención estándar.
3. Módulos MnLP: Se añade una serie de $K$ módulos auxiliares ($k=1, \dots, K$).
   • Cadena Causal: El módulo $k$-ésimo predice el nodo en el paso $t+k$ ($x_{t+k}$). Recibe información contextual del módulo $(k-1)$-ésimo y de la incrustación de verdad fundamental del nodo en el paso $t+k-1$. Esto impone una cadena causal donde las predicciones para pasos futuros dependen de la secuencia de pasos anteriores.
   • Factibilidad: Los módulos respetan las restricciones del problema (por ejemplo, nodos no visitados para TSP, restricciones de capacidad para CVRP) enmascarando nodos no factibles en los logits de salida.
   • Desechable: Crucialmente, estos módulos MnLP se eliminan durante la inferencia. Solo se utiliza la cabecera principal del siguiente nodo, asegurando cero sobrecarga computacional adicional en el momento de la prueba.

Objetivo de Entrenamiento

La pérdida de entrenamiento es una suma ponderada de la pérdida de la tarea principal y las pérdidas de avance auxiliares:
$$\mathcal{L} = \mathcal{L}_{\text{main}} + \gamma \mathcal{L}_{\text{MnLP}}$$
Donde:

• $\mathcal{L}_{\text{main}}$ es la pérdida estándar de entropía cruzada para la predicción del siguiente nodo.
• $\mathcal{L}_{\text{MnLP}}$ es la pérdida promedio de entropía cruzada a través de los $K$ módulos de avance.
• $\gamma$ es un hiperparámetro que controla el peso de la supervisión auxiliar, el cual se incrementa linealmente durante un período de calentamiento para evitar que la tarea auxiliar domine el entrenamiento temprano.

Esta supervisión de múltiples profundidades actúa como un regularizador, alentando al codificador a aprender representaciones que capturen dependencias de largo alcance y mejorando la asignación de crédito a través de la secuencia.

Contribuciones Clave

1. Diseño Arquitectónico Novel: La introducción de módulos MnLP que permiten la predicción de múltiples pasos durante el entrenamiento sin alterar la arquitectura de inferencia ni añadir latencia en el momento de la prueba.
2. Supervisión Auxiliar de Múltiples Profundidades: Una estrategia de entrenamiento que guía al modelo para anticipar decisiones futuras más allá del paso inmediato siguiente, mitigando efectivamente el sesgo de exposición y el comportamiento miope.
3. Validación Empírica: Experimentos extensos que demuestran que MnLP mejora la generalización a través de diferentes tamaños de problema, distribuciones y puntos de referencia del mundo real.

Resultados Experimentales

Los autores evaluaron MnLP en instancias de TSP y CVRP de tamaños variables (de 100 a 1000 nodos) y distribuciones (uniforme, rotación, explosión y puntos de referencia del mundo real como TSPLib y CVRPLib).

• Ganancias de Rendimiento: MnLP superó consistentemente al modelo LEHD de referencia. Por ejemplo, en TSP con 1000 nodos, la brecha de optimalidad mejoró del 3.563% (LEHD) al 2.852% (MnLP), una mejora relativa del 20%.
• Generalización: El método demostró una superioridad en la generalización cruzada por tamaño y distribución. En instancias a gran escala ($n=1000$), la brecha de rendimiento entre MnLP y las líneas base se amplió, lo que sugiere que el mecanismo de avance es particularmente efectivo para la planificación compleja de largo horizonte.
• Puntos de Referencia del Mundo Real: MnLP logró resultados del estado del arte entre las políticas neuronales en TSPLib y CVRPLib, superando a otras estrategias de entrenamiento avanzadas como POMO (basada en RL) y SA-DABL (SL con aumento).
• Eficiencia: Dado que los módulos MnLP se descartan en la inferencia, el método mantiene la misma velocidad de inferencia que el modelo LEHD de referencia.

Significado y Afirmaciones

El artículo afirma que MnLP aborda un cuello de botella crítico en la optimización combinatoria neuronal: la incapacidad de la predicción estándar del siguiente nodo para capturar señales de planificación de largo horizonte. Al inyectar comprensión contextual de largo alcance en el proceso de entrenamiento sin comprometer la eficiencia de la inferencia, MnLP ofrece una forma escalable y efectiva de mejorar las políticas de enrutamiento neuronal.

Los autores posicionan a MnLP como una estrategia de entrenamiento generalizable que puede integrarse sin problemas en diversas arquitecturas neuronales. Argumentan que el éxito de MnLP valida la hipótesis de que la supervisión de múltiples pasos es esencial para entrenar políticas neuronales robustas capaces de resolver problemas de enrutamiento complejos y a gran escala, cerrando la brecha entre la toma de decisiones local y la optimalidad global.