Resumen Técnico: Agrupación Neuronal Primero, Enrutamiento Después

Definición del Problema

El artículo aborda el Problema de Enrutamiento de Vehículos con Capacidad (CVRP), un desafío fundamental en la logística de última milla donde una flota de vehículos con capacidad uniforme $Q$ debe atender un conjunto de clientes con demandas específicas desde un depósito central, minimizando la distancia total de viaje.

Los autores identifican limitaciones críticas en los enfoques actuales de Optimización Combinatoria Neuronal (NCO):

1. Cuellos de botella Autoregresivos (AR): Los métodos NCO dominantes construyen soluciones token por token, lo que genera costos de decodificación secuencial, sensibilidad a simetrías espaciales y una generalización frágil fuera de la distribución (OOD).
2. Desconexión Metodológica: Mientras que el Problema del Viajante de Comercio (TSP) es puramente una tarea de enrutamiento, el CVRP involucra fundamentalmente un problema de partición (empaquetar clientes en clusters factibles por capacidad) acoplado con el enrutamiento. Los métodos NCO existentes a menudo tratan el CVRP como una tarea de generación de recorridos, dejando que las restricciones de capacidad se impongan mediante búsquedas post-hoc costosas.
3. Desalineación de Referencias: Las referencias estándar re-muestrean coordenadas de nodos de forma independiente e idéntica (i.i.d.), ignorando el soporte geográfico fijo (por ejemplo, la red de calles de una ciudad) típico de la logística real, donde la misma área se enruta diariamente con demandas variables.

Metodología: CFRS Neuronal

Los autores proponen Neural CFRS, el primer marco neuronal puramente no autoregresivo (NAR) y de un solo paso basado en el paradigma clásico Agrupación Primero-Enrutamiento Después (CFRS). En lugar de generar rutas secuencialmente, el modelo realiza una asignación global y diferenciable de clientes a clusters de vehículos, tras lo cual se resuelven TSPs independientes en paralelo.

La arquitectura opera en tres fases:

1. Pre-entrenamiento y Prior de Soporte Espacial ($\Psi$)

Para abordar la geografía fija de la logística real, los autores pre-entrenan un Autoencoder enmascarado espacial (SMAE) sobre un conjunto fijo de ubicaciones potenciales de clientes ($X$).

• El SMAE aprende incrustaciones invariantes a $E(2)$ (invariantes a traslación, rotación y reflexión) reconstruyendo distancias euclidianas entre pares y conectividad local $k$-NN sin consumir coordenadas absolutas.
• Estas incrustaciones congeladas ($\Psi$) sirven como un "vocabulario espacial", permitiendo que el modelo aguas abajo generalice a nuevas instancias de demanda en el mismo mapa sin re-aprender la geometría.

2. Fase 1: Generación de Semillas

Un Transformador de Semillas (ST) identifica un subconjunto de nodos para servir como centros de cluster iniciales ("semillas").

• Predice probabilidades marginales para nodos que actúan como semillas y aprende representaciones contrastivas para agrupar nodos similares.
• Una estrategia de Decodificación Greedy Consciente de la Capacidad selecciona $K$ semillas (donde $K$ es el tamaño estimado de la flota) y empaqueta de manera greedy nodos cercanos en estas semillas basándose en la similitud contrastiva, asegurando dispersión espacial y factibilidad de capacidad.

3. Fase 2: Asignación Global mediante Transporte Óptimo Diferenciable

Un Transformador de Agrupación (CT) calcula distancias latentes ($\Delta_{ij}$) entre clientes y las semillas seleccionadas.

• Relajación Diferenciable: Para imponer restricciones globales de capacidad de extremo a extremo, el Problema de Asignación con Capacidad (CAP) discreto se relaja en un problema continuo de Transporte Óptimo (OT).
• Algoritmo Sinkhorn-Knopp (SK): El modelo minimiza un objetivo de OT regularizado entrópico, produciendo un plan de transporte continuo ($\hat{Y}$) que satisface las restricciones de capacidad. Este plan actúa como un sustituto diferenciable para la matriz de asignación discreta.

4. Fase 3: Decodificación OR

El plan de transporte continuo $\hat{Y}$ guía a un solucionador exacto de Programación Entera Mixta (MIP) para recuperar los clusters discretos finales.

• Esparsificación: El modelo utiliza umbrales de confianza para fijar asignaciones de alta confianza (Asignación Dura) o podar bordes de baja probabilidad (Esparsificación Guiada por Sinkhorn).
• Esto reduce drásticamente el espacio de búsqueda para el solucionador exacto, que luego resuelve los sub-problemas restantes como TSPs independientes utilizando solucionadores comerciales (por ejemplo, LKH-3).

Contribuciones Clave

1. Marco No Autoregresivo: Introduce el primer solucionador neuronal puramente NAR para CVRP que elude los cuellos de botella de la decodificación secuencial al plantear el problema como una tarea de partición global.
2. Restricciones de Capacidad Diferenciables: Desarrolla una nueva capa diferenciable de extremo a extremo utilizando Transporte Óptimo regularizado entrópico para imponer restricciones de capacidad de flota, cerrando la brecha entre la asignación neuronal y la programación entera exacta.
3. Abstracción de Simetría: Proporciona garantías teóricas formales de que la arquitectura abstrae intrínsecamente las simetrías espaciales $E(2)$, la permutación entre rutas y las simetrías de recorrido dentro de la ruta por construcción, eliminando la necesidad de aumentación de datos costosa.
4. Prior de Soporte Espacial: Demuestra que aprovechar un vocabulario espacial pre-entrenado en geografía fija permite una eficiencia extrema de parámetros y una escalabilidad zero-shot a tamaños de problema grandes.

Resultados Experimentales

El marco fue evaluado tanto en configuraciones operativas de capacidad constante (geografía fija) como en referencias estándar (coordenadas i.i.d.).

• Generalización Zero-Shot: Neural CFRS escala robustamente a instancias fuera de la distribución de hasta $N=1000$ clientes.
  • Bajo una configuración de capacidad constante ($Q=50$), logra una brecha de optimalidad de < 4% en instancias de $N=1000$ en menos de 30 segundos.
  • Remarkablemente, una arquitectura ultra-ligera de una sola capa (682K parámetros) mantiene una brecha aproximada de 5% a esta escala, desafiando la noción de que se requieren arquitecturas profundas para el enrutamiento a gran escala.
• Referencias Estándar: En la referencia CVRP100 estándar, la variante de decodificación exacta logra una brecha de optimalidad de 2.73%, superando a las líneas base autoregresivas greedy (por ejemplo, POMO, BQ, LEHD) y compitiendo con heurísticas clásicas.
• Eficiencia: El método elimina por completo la dependencia de la búsqueda local post-hoc para la agrupación inicial, confiando en su lugar en la capacidad del modelo neuronal para guiar al solucionador exacto.

Significado y Afirmaciones

El artículo argumenta que Neural CFRS representa un cambio estructural en la NCO para problemas de enrutamiento:

• Alineación con las Fortalezas del Aprendizaje Profundo: Aprovecha la capacidad del aprendizaje profundo para aprender similitud y asignación sobre un contexto global, en lugar de forzarlo a construir recorridos secuenciales largos.
• Viabilidad en el Mundo Real: Al respetar soportes espaciales fijos y capacidades constantes, el marco se alinea con el régimen amortizado y sensible a la latencia de la logística real, ofreciendo un camino viable para el enrutamiento diario en áreas de servicio estáticas.
• Cambio de Paradigma: Los resultados sugieren que la adaptación específica de la tarea (por ejemplo, pre-entrenamiento en soporte espacial) puede producir resultados de vanguardia sin un ajuste fino extensivo, y que arquitecturas simples y poco profundas pueden ser altamente efectivas cuando se emparejan con los sesgos inductivos correctos (descomposición CFRS y priores espaciales).

Los autores concluyen que, aunque el marco se desempeña de manera competitiva, el trabajo futuro debería centrarse en mejorar la escalabilidad zero-shot a instancias aún más grandes y en refinar la capacidad del modelo para equilibrar la utilización de la capacidad con la eficiencia espacial en casos límite.