🤖 machine learning

FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing

Le papier propose FiLMMeD, un modèle neuronal unifié novateur qui exploite la modulation linéaire par caractéristique, l'optimisation des préférences et l'apprentissage par curriculum pour résoudre efficacement 24 variantes diverses du problème de routage de véhicules à plusieurs dépôts, surpassant les références de l'état de l'art existantes.

Auteurs originaux : Arthur Corrêa, Paulo Nascimento, Samuel Moniz

Publié 2026-05-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Arthur Corrêa, Paulo Nascimento, Samuel Moniz

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes le directeur d'une entreprise de livraison massive. Vous disposez de camions, de chauffeurs et de milliers de clients. Votre tâche consiste à déterminer le moyen le plus efficace d'acheminer les colis de vos entrepôts jusqu'aux portes des clients. C'est le Problème de Routage de Véhicules (PRV).

Maintenant, imaginez que votre entreprise se développe. Vous n'avez plus un seul entrepôt ; vous avez plusieurs dépôts répartis dans toute la ville. Cela rend le casse-tête beaucoup plus difficile. C'est le PRV Multi-Dépôts (PRV-MD).

Pour rendre les choses encore plus chaotiques, la vie réelle lance des courbes chaque jour :

Parfois, un client souhaite qu'un colis soit ramassé (un Retour).
Parfois, un camion a une limite de temps stricte pour la durée de sa conduite (Limite de Longueur d'Itinéraire).
Parfois, un client n'accepte les livraisons qu'entre 9 h et 11 h (Fenêtre de Temps).
Parfois, un camion est autorisé à s'arrêter à un autre entrepôt en milieu d'itinéraire pour se recharger (Itinéraire Inter-Dépôt).

Traditionnellement, résoudre ces casse-têtes nécessitait d'embaucher un expert différent pour chaque combinaison unique de règles. Si vous ajoutiez une nouvelle règle, vous deviez recommencer à zéro.

Ce papier présente FiLMMeD, un nouveau "super-solveur" conçu pour gérer toutes ces différentes combinaisons de règles à la fois, sans avoir besoin d'être reentraîné à chaque fois. Voici comment cela fonctionne, en utilisant des analogies simples :

1. Les "Lunettes Intelligentes" (Modulation Linéaire par Caractéristique)

Imaginez que vous portez une paire de lunettes intelligentes. Lorsque vous regardez une carte, les lunettes modifient votre perception du monde en fonction des règles du jour.

Si la règle est "Fenêtres de Temps", les lunettes mettent en évidence les horloges sur la carte et assombrissent le reste.
Si la règle est "Retours", les lunettes mettent en évidence les points de collecte et changent la couleur des points de livraison.

Dans l'article, cela s'appelle FiLM (Modulation Linéaire par Caractéristique). Au lieu de construire un nouveau cerveau pour chaque règle, l'IA utilise un seul cerveau mais enfile ces "lunettes intelligentes" (ajustements mathématiques) pour adapter instantanément sa réflexion interne aux contraintes spécifiques du problème actuel. Cela lui permet de comprendre qu'une règle de "Fenêtre de Temps" modifie l'importance de certains points de données, tandis qu'une règle de "Retour" en modifie d'autres.

2. Le "Camp d'Entraînement" (Apprentissage par Curriculum)

Si vous essayiez d'enseigner à un élève à résoudre un problème mathématique complexe en lui jetant toutes les variables possibles dès le premier jour, il échouerait probablement. Vous avez besoin d'un Curriculum.

Les auteurs ont réalisé que pour les problèmes multi-dépôts, on ne peut pas simplement mélanger toutes les règles au hasard. Il faut augmenter la difficulté progressivement :

Phase 1 : Enseigner à l'IA des problèmes simples avec une seule règle supplémentaire (par exemple, uniquement des Fenêtres de Temps).
Phase 2 : Une fois qu'elle a maîtrisé cela, introduire des problèmes avec deux règles.
Phase 3 : Enfin, lui permettre d'affronter les "batailles de boss" avec quatre ou cinq règles combinées.

Cette stratégie d'Apprentissage par Curriculum agit comme un camp d'entraînement, garantissant que l'IA apprend les bases de l'interaction entre les règles avant d'être submergée par les scénarios les plus complexes.

3. Le "Feedback du Coach" (Optimisation par Préférence)

Habituellement, l'IA apprend en essayant de deviner la réponse et en obtenant un score (Récompense) à la fin. Si le score est faible, elle réessaie. Cela peut être désordonné et lent, surtout lorsqu'il faut jongler avec de nombreux types de problèmes différents.

Les auteurs ont essayé une approche différente appelée Optimisation par Préférence (PO). Au lieu de demander : "Quelle est la qualité de cet itinéraire ?" (en donnant un nombre), ils demandent à l'IA de comparer deux itinéraires : "L'itinéraire A est-il meilleur que l'itinéraire B ?"

Pensez-y comme un coach observant deux athlètes courir. Le coach n'a pas besoin de connaître la vitesse exacte ; il a juste besoin de savoir qui a terminé en premier.
L'article affirme que cette méthode est plus stable et aide l'IA à apprendre plus vite et mieux que la méthode traditionnelle "basée sur le score", en particulier lorsqu'il s'agit de gérer de nombreux types de problèmes différents simultanément.

Qu'ont-ils accompli ?

L'équipe a testé son nouveau modèle, FiLMMeD, sur 24 versions différentes du problème multi-dépôts (incluant 8 nouveaux types qu'ils ont inventés) et 16 problèmes à dépôt unique.

Le Résultat : FiLMMeD a systématiquement battu les meilleurs modèles d'IA précédents. Il a trouvé de meilleurs itinéraires, plus rapidement, et a pu gérer des combinaisons complexes de règles avec lesquelles d'autres modèles luttaient.
La Victoire "Zero-Shot" : Même lorsqu'ils ont testé le modèle sur des combinaisons de règles qu'il n'avait jamais vues auparavant, il a encore très bien performé, prouvant que l'approche des "lunettes intelligentes" et du "camp d'entraînement" l'a aidé à véritablement comprendre la logique du problème, et non pas seulement à mémoriser des réponses.

Résumé

L'article présente un nouveau système d'IA qui agit comme un planificateur de livraison universel. En utilisant des lunettes intelligentes pour s'adapter à des règles spécifiques, un camp d'entraînement étape par étape pour apprendre la complexité, et un style de coaching comparatif pour apprendre efficacement, il résout des casse-têtes logistiques complexes mieux que toute méthode précédente, le tout sans avoir besoin d'un nouveau modèle pour chaque nouveau scénario.

1. Définition du Problème

L'article aborde le Problème de Routage de Véhicules Multi-Dépôts (MDVRP), un problème d'optimisation combinatoire (CO) complexe central à la logistique moderne, en particulier dans le commerce électronique. Contrairement au VRP à dépôt unique classique, le MDVRP implique l'expédition de véhicules depuis plusieurs dépôts pour desservir des clients.

Le défi spécifique traité est la généralisation trans-problème. La logistique réelle implique des contraintes hétérogènes qui varient dynamiquement (par exemple, fenêtres temporelles, retours en charge, limites de longueur d'itinéraire, itinéraires ouverts et transferts inter-dépôts). Les solveurs basés sur les réseaux de neurones traditionnels sont généralement entraînés sur des variantes spécifiques de problèmes, ce qui les rend fragiles face à de nouvelles combinaisons de contraintes. Bien que l'Apprentissage Multi-Tâches (MTL) ait été appliqué aux VRP à dépôt unique, il a largement échoué à résoudre la complexité des variantes MDVRP, souffrant souvent de :

Conflits de Gradient : Mises à jour contradictoires lors de l'entraînement sur des ensembles de contraintes divers simultanément.
Mauvaise Généralisation : Incapacité à gérer les interactions complexes entre contraintes (par exemple, retours en charge + fenêtres temporelles) sans réentraînement.
Conditionnement Statique : Les modèles existants traitent les contraintes comme un contexte de haut niveau plutôt que de moduler dynamiquement les représentations internes.

2. Méthodologie : FiLMMeD

Les auteurs proposent FiLMMeD, un modèle unifié basé sur les réseaux de neurones conçu pour résoudre 24 variantes distinctes de MDVRP (incluant 8 formulations novatrices avec itinéraires inter-dépôts) et 16 variantes de VRP à dépôt unique. L'architecture est construite sur des cadres encodeur-décodeur basés sur Transformer (étendant spécifiquement MTPOMO, MVMoE et CaDA).

Composants Principaux :

Modulation Linéaire Spécifique aux Caractéristiques (FiLM) :
- Mécanisme : Au lieu d'une simple concaténation des caractéristiques de contraintes, FiLMMeD introduit un vecteur de conditionnement $z$ (un vecteur booléen indiquant les contraintes actives) pour moduler dynamiquement les plongements de nœuds.
- Implémentation : Le modèle calcule des paramètres d'échelle ( $\gamma$ ) et de décalage ( $\beta$ ) basés sur $z$ via des projections linéaires apprenables. Ces paramètres sont appliqués aux plongements de clients comme une transformation affine : $FiLM(h|\gamma, \beta) = \gamma \cdot h + \beta$ .
- Effet : Cela permet au modèle d'adapter ses représentations internes spécifiquement aux contraintes actives d'une instance, désintriquant efficacement l'espace latent et atténuant les conflits de gradient entre les tâches.
Stratégie d'Apprentissage par Curriculum (CL) :
- Motivation : L'échantillonnage uniforme de toutes les variantes (courant dans le MTL à dépôt unique) conduit à une mauvaise convergence dans le MDVRP en raison des interactions complexes entre contraintes.
- Stratégie : Le curriculum d'entraînement est structuré pour augmenter progressivement la complexité :
  - Phase 1 (0-30 %) : Variantes à contrainte unique + variantes spécifiques à deux contraintes connues pour être difficiles (par exemple, retour en charge + fenêtre temporelle).
  - Phase 2 (30-60 %) : Introduction de toutes les variantes à deux contraintes.
  - Phase 3 (60-90 %) : Introduction de variantes à trois contraintes.
  - Phase 4 (90-100 %) : Ensemble complet incluant les variantes à quatre contraintes.
- Objectif : Guider le modèle de l'apprentissage des effets de contraintes isolés à la maîtrise de leurs interactions complexes.
Optimisation des Préférences (PO) :
- Innovation : L'article introduit la PO comme paradigme d'entraînement pour le MTL, remplaçant la fonction de perte standard d'Apprentissage par Renforcement (RL) (REINFORCE).
- Mécanisme : Au lieu d'optimiser des récompenses scalaires, le modèle apprend à partir de préférences par paires entre des trajectoires générées pour la même instance. Si la trajectoire $A$ a un meilleur coût que $B$ , le modèle est optimisé pour augmenter la probabilité de $A$ par rapport à $B$ .
- Avantage : La PO réduit la variance du gradient et est invariante à l'échelle (non affectée par la magnitude absolue des coûts), répondant à l'instabilité et aux interférences de gradient courantes dans les configurations MTL.

3. Contributions Clés

Premier Modèle MTL Unifié pour MDVRP : FiLMMeD est le premier modèle explicitement conçu pour gérer un large éventail de variantes MDVRP (24 au total), incluant des formulations novatrices d'itinéraires inter-dépôts.
Mécanisme FiLM pour le Conditionnement par Contraintes : Démontre que la modulation dynamique des plongements basée sur les attributs de contraintes améliore significativement la généralisation et désintrique l'espace latent par rapport à la concaténation statique de caractéristiques.
Optimisation des Préférences en MTL : Fournit la première démonstration de la PO dans un cadre MTL, montrant qu'elle surpasse le RL traditionnel en termes de stabilité de convergence et de qualité de solution.
Apprentissage par Curriculum Ciblé : Établit que le MDVRP nécessite un curriculum guidé (exposition progressive à la complexité des contraintes) plutôt qu'un échantillonnage uniforme, qui suffit pour les problèmes à dépôt unique.

4. Résultats Expérimentaux

Les auteurs ont mené des expériences extensives sur 24 variantes MDVRP et 16 VRP à dépôt unique.

Performance sur MDVRP :
- FiLMMeD a constamment surpassé les références de l'état de l'art (MTPOMO, MVMoE) et les heuristiques traditionnelles (PyVRP) en termes de qualité de solution (Écart).
- Sur des instances de 50 nœuds, FiLMMeD-MTPOMO a réduit l'écart moyen de 2,888 % par rapport à sa référence.
- Sur des instances de 100 nœuds, les améliorations étaient encore plus significatives, FiLMMeD-MVMoE surpassant sa référence de 5,288 %.
- Le modèle a atteint une généralisation zero-shot supérieure sur des combinaisons de contraintes invisibles.
Performance sur VRP à Dépôt Unique :
- Lorsqu'il est affiné sur des variantes à dépôt unique, FiLMMeD (utilisant la PO) a obtenu des résultats compétitifs ou supérieurs par rapport aux références entraînées sur des ensembles de données massifs (par exemple, 100 millions d'instances), malgré un entraînement sur moins d'instances (30 millions).
- FiLMMeD-CaDA† (combinant FiLM, PO et ReLD) a obtenu la meilleure performance globale, avec un écart moyen de 1,46 % sur des instances de 50 nœuds.
Études d'Ablation :
- FiLM : La suppression de FiLM a entraîné une performance nettement inférieure sur les variantes invisibles (par exemple, l'écart est passé de 5,297 % à 5,716 % pour MVMoE).
- Curriculum : L'échantillonnage uniforme ou les stratégies d'entraînement "unifiées" ont conduit à une mauvaise convergence sur le MDVRP, validant la nécessité de la stratégie CL proposée.
- PO vs RL : Les modèles entraînés avec la PO ont montré une convergence plus rapide et des écarts moyens plus faibles par rapport à ceux entraînés avec REINFORCE sur toutes les architectures.
Complexité : Le mécanisme FiLM ajoute des paramètres négligeables (<0,01 M, <1 % d'augmentation) et une surcharge mémoire GPU minimale. Les temps d'entraînement par époque restent presque identiques à ceux des références.

5. Signification

Cet article représente une avancée significative en optimisation combinatoire neuronale pour la logistique :

Applicabilité Pratique : En résolvant 24 variantes dans un seul modèle unifié, FiLMMeD adresse le problème de "fragmentation" en logistique, où les entreprises ont actuellement besoin de solveurs séparés pour différents ensembles de contraintes.
Avancement Théorique : Il remet en question la domination de l'Apprentissage par Renforcement en CO en démontrant que l'Optimisation des Préférences offre un paradigme d'entraînement plus stable et efficace pour l'Apprentissage Multi-Tâches.
Insight Architectural : Il prouve que le conditionnement dynamique (FiLM) est supérieur à l'encodage de contexte statique pour gérer des contraintes hétérogènes, offrant un modèle pour les futurs modèles d'apprentissage trans-problème.
Généralisation : Le succès de la stratégie d'apprentissage par curriculum souligne que la complexité des interactions de contraintes dans les environnements multi-dépôts nécessite un parcours d'apprentissage structuré, une découverte qui peut s'appliquer à d'autres problèmes CO complexes.

En résumé, FiLMMeD établit un nouvel état de l'art pour les solveurs neuronaux unifiés en routage de véhicules, offrant une solution évolutive, flexible et hautement généralisable pour les défis logistiques modernes et dynamiques.