Résumé Technique : Regroupement Neuronal d'Abord, Routage Ensuite

Définition du Problème

L'article aborde le Problème de Routage de Véhicules à Capacité Limitée (CVRP), un défi fondamental en logistique du dernier kilomètre où une flotte de véhicules de capacité uniforme $Q$ doit desservir un ensemble de clients ayant des demandes spécifiques depuis un dépôt central, en minimisant la distance totale parcourue.

Les auteurs identifient des limitations critiques dans les approches actuelles d'Optimisation Combinatoire Neurale (NCO) :

1. Goulots d'étranglement Autoregressifs (AR) : Les méthodes NCO dominantes construisent les solutions token par token, entraînant des coûts de décodage séquentiels, une sensibilité aux symétries spatiales et une généralisation fragile hors distribution (OOD).
2. Déconnexion Méthodologique : Alors que le Problème du Voyageur de Commerce (TSP) est purement une tâche de routage, le CVRP implique fondamentalement un problème de partitionnement (regroupement des clients en clusters compatibles avec la capacité) couplé au routage. Les méthodes NCO existantes traitent souvent le CVRP comme une tâche de génération de tournée, laissant les contraintes de capacité à être imposées par une recherche post-hoc coûteuse.
3. Inadéquation des Benchmarks : Les benchmarks standards rééchantillonnent les coordonnées des nœuds de manière i.i.d., ignorant le support géographique fixe (par exemple, le réseau routier d'une ville) typique de la logistique réelle où la même zone est routée quotidiennement avec des demandes variables.

Méthodologie : Neural CFRS

Les auteurs proposent Neural CFRS, le premier cadre neuronal purement non-autoregressif (NAR), en un seul passage, basé sur le paradigme classique Regroupement d'Abord, Routage Ensuite (CFRS). Au lieu de générer des routes séquentiellement, le modèle effectue une affectation globale et différentiable des clients aux clusters de véhicules, après quoi des TSP indépendants sont résolus en parallèle.

L'architecture opère en trois phases :

1. Pré-entraînement et Prior de Support Spatial ($\Psi$)

Pour répondre à la géographie fixe de la logistique réelle, les auteurs pré-entraînent un Autoencodeur Masqué Spatial (SMAE) sur un ensemble fixe de emplacements potentiels de clients ($X$).

• Le SMAE apprend des embeddings $E(2)$-invariants (invariants par translation, rotation, réflexion) en reconstruisant les distances euclidiennes paires et la connectivité locale $k$-NN sans consommer de coordonnées absolues.
• Ces embeddings figés ($\Psi$) servent de « vocabulaire spatial », permettant au modèle en aval de généraliser à de nouvelles instances de demande sur la même carte sans réapprendre la géométrie.

2. Phase 1 : Génération de Graines

Un Transformateur de Graines (ST) identifie un sous-ensemble de nœuds pour servir de centres de clusters initiaux (« graines »).

• Il prédit des probabilités marginales pour les nœuds agissant comme graines et apprend des représentations contrastives pour regrouper des nœuds similaires.
• Une stratégie de Décodage Gourmand Sensible à la Capacité sélectionne $K$ graines (où $K$ est la taille estimée de la flotte) et regroupe de manière gourmande les nœuds voisins dans ces graines en fonction de la similarité contrastive, assurant une dispersion spatiale et une faisabilité de capacité.

3. Phase 2 : Affectation Globale via Transport Optimal Différentiable

Un Transformateur de Clustering (CT) calcule les distances latentes ($\Delta_{ij}$) entre les clients et les graines sélectionnées.

• Relaxation Différentiable : Pour imposer les contraintes globales de capacité de bout en bout, le Problème d'Affectation à Capacité Limitée (CAP) discret est relâché en un problème de Transport Optimal (OT) continu.
• Algorithme Sinkhorn-Knopp (SK) : Le modèle minimise un objectif de OT régularisé entropiquement, produisant un plan de transport continu ($\hat{Y}$) qui satisfait les contraintes de capacité. Ce plan agit comme un substitut différentiable pour la matrice d'affectation discrète.

4. Phase 3 : Décodage par Recherche Opérationnelle (OR)

Le plan de transport continu $\hat{Y}$ guide un solveur exact de Programmation Linéaire en Nombres Entiers (MIP) pour récupérer les clusters discrets finaux.

• Sparsification : Le modèle utilise des seuils de confiance pour soit fixer les affectations à haute confiance (Affectation Rigide) soit élaguer les arêtes à faible probabilité (Sparsification Guidée par Sinkhorn).
• Cela réduit considérablement l'espace de recherche pour le solveur exact, qui résout ensuite les sous-problèmes restants comme des TSP indépendants en utilisant des solveurs standards (par exemple, LKH-3).

Contributions Clés

1. Cadre Non-Autoregressif : Introduit le premier solveur neuronal purement NAR pour le CVRP qui contourne les goulots d'étranglement du décodage séquentiel en présentant le problème comme une tâche de partitionnement global.
2. Contraintes de Capacité Différentiables : Développe une nouvelle couche différentiable de bout en bout utilisant le Transport Optimal entropique pour imposer les contraintes de capacité de la flotte, comblant le fossé entre l'affectation neuronale et la programmation en nombres entiers exacte.
3. Abstraction de Symétrie : Fournit des garanties théoriques formelles que l'architecture abstrait intrinsèquement les symétries spatiales $E(2)$, les permutations inter-routes et les symétries de parcours intra-routes par construction, éliminant le besoin d'augmentation de données coûteuse.
4. Prior de Support Spatial : Démontre que l'exploitation d'un vocabulaire spatial pré-entraîné sur une géographie fixe permet une efficacité paramétrique extrême et une mise à l'échelle zero-shot vers de grandes tailles de problèmes.

Résultats Expérimentaux

Le cadre a été évalué à la fois sur des configurations opérationnelles à capacité constante (géographie fixe) et sur des benchmarks standards (coordonnées i.i.d.).

• Généralisation Zero-Shot : Neural CFRS s'étend de manière robuste aux instances hors distribution jusqu'à $N=1000$ clients.
  • Dans un cadre de capacité constante ($Q=50$), il atteint un écart d'optimalité de < 4% sur des instances $N=1000$ en moins de 30 secondes.
  • De manière remarquable, une architecture ultra-légère à une seule couche (682K paramètres) conserve un écart d'environ 5% à cette échelle, remettant en question l'idée que des architectures profondes sont requises pour le routage à grande échelle.
• Benchmarks Standards : Sur le benchmark CVRP100 standard, la variante de décodage exact atteint un écart d'optimalité de 2,73%, surpassant les bases autoregressives gourmandes (par exemple, POMO, BQ, LEHD) et rivalisant avec les heuristiques classiques.
• Efficacité : La méthode élimine entièrement la dépendance à la recherche locale post-hoc pour le clustering initial, s'appuyant plutôt sur la capacité du modèle neuronal à guider le solveur exact.

Signification et Revendications

L'article soutient que Neural CFRS représente un changement structurel dans la NCO pour les problèmes de routage :

• Alignement avec les Forces de l'Apprentissage Profond : Il exploite la capacité de l'apprentissage profond à apprendre la similarité et l'affectation sur un contexte global, plutôt que de le forcer à construire des tournées séquentielles longues.
• Viabilité Réelle : En respectant les supports spatiaux fixes et les capacités constantes, le cadre s'aligne sur le régime amorti et sensible à la latence de la logistique réelle, offrant une voie viable pour le routage quotidien dans des zones de service statiques.
• Changement de Paradigme : Les résultats suggèrent que l'adaptation spécifique à la tâche (par exemple, le pré-entraînement sur le support spatial) peut produire des résultats de pointe sans ajustage fin extensif, et que des architectures simples et peu profondes peuvent être hautement efficaces lorsqu'elles sont associées aux bons biais inductifs (décomposition CFRS et priors spatiaux).

Les auteurs concluent que bien que le cadre soit compétitif, les travaux futurs devraient se concentrer sur l'amélioration de la mise à l'échelle zero-shot vers des instances encore plus grandes et sur le raffinement de la capacité du modèle à équilibrer l'utilisation de la capacité avec l'efficacité spatiale dans des cas limites.