Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

Cet article présente une approche hybride nommée RL-CMSA, combinant l'apprentissage par renforcement et l'optimisation exacte, qui surpasse les algorithmes génétiques existants pour résoudre le problème du voyageur de commerce multiple en version min-max.

L'essentiel

🚚 Le Problème : La Course de Camions Équilibrée

Imaginez que vous gérez une entreprise de livraison avec un entrepôt central et plusieurs camions (disons 10, 20 ou même 50). Vous avez des centaines de colis à distribuer dans une ville.

Le défi classique (le "Problème du Voyageur de Commerce") consiste à trouver le chemin le plus court pour un seul camion. Mais ici, nous avons plusieurs camions et un objectif très spécifique : l'équité.

Ce n'est pas seulement de réduire la distance totale parcourue par tous les camions. Le vrai but est de s'assurer que le camion qui travaille le plus (celui qui fait le plus long trajet) travaille le moins possible. C'est comme si vous vouliez que tous vos livreurs rentrent à la maison à peu près à la même heure, sans que l'un d'eux fasse un tour de la ville pendant que les autres finissent en 10 minutes.

🧠 La Solution : Une Équipe de Détectives et un Chef Cuisinier

Les auteurs de l'article proposent une nouvelle méthode appelée RL-CMSA. Pour comprendre comment ça marche, imaginons une équipe de détectives très organisée qui travaille en boucle.

Cette méthode combine trois ingrédients magiques :

1. L'Intelligence Artificielle (Apprentissage par Renforcement) : Un cerveau qui apprend de ses erreurs.
2. La Méthode "Construire, Fusionner, Résoudre" : Une façon intelligente de mélanger les pièces du puzzle.
3. La Puissance de Calcul Exacte : Un super-calculateur qui vérifie les mathématiques.

Voici comment ils procèdent, étape par étape :

1. La Construction (Le Dessin des Quartiers)

Au lieu de donner un itinéraire tout fait, l'algorithme commence par dessiner des "quartiers" pour chaque camion.

• L'analogie : Imaginez que vous devez diviser une ville en plusieurs zones pour des livreurs. Au début, vous ne savez pas exactement qui va où. L'algorithme utilise une sorte de "boussole magique" (les valeurs Q) pour décider quels quartiers sont proches les uns des autres.
• L'apprentissage : Si deux rues sont souvent utilisées ensemble dans de bons itinéraires, la "boussole" dit : "Hé, ces deux-là vont bien ensemble !". Si elles ne vont pas bien ensemble, la boussole les sépare.

2. La Fusion (La Boîte à Pièces de Voiture)

L'algorithme génère beaucoup de solutions différentes (des milliers de façons de dessiner les routes). Il ne garde pas tout, mais il sélectionne les meilleurs "segments de route" (les meilleurs trajets pour un seul camion) et les met dans une boîte à pièces.

• L'analogie : C'est comme si vous aviez une boîte remplie des meilleurs morceaux de puzzle trouvés jusqu'ici. Chaque morceau est un trajet possible pour un camion.

3. La Résolution (Le Chef Cuisinier)

C'est ici que la magie opère. Au lieu de chercher une solution parfaite d'un seul coup, l'algorithme prend la boîte à pièces et demande à un super-calculateur (un solveur mathématique) : "Peux-tu assembler exactement 10 de ces morceaux pour couvrir toute la ville, en faisant en sorte que le plus long trajet soit le plus court possible ?"

• L'analogie : Le calculateur est comme un chef cuisinier qui prend les meilleurs ingrédients de la boîte pour créer un plat parfait. Il essaie des combinaisons mathématiques pures pour trouver la structure idéale.

4. L'Adaptation et l'Amélioration (Le Nettoyage)

Parfois, le chef cuisinier assemble des pièces qui se chevauchent (deux camions passent par la même rue). L'algorithme intervient alors pour "nettoyer" : il déplace un colis d'un camion à l'autre ou échange deux rues entre deux camions pour lisser les charges.

• Le vieillissement : Si un morceau de route (un trajet) n'a pas été utilisé depuis longtemps pour faire une bonne solution, il est jeté de la boîte. On garde la boîte fraîche et à jour.

🏆 Les Résultats : Qui Gagne ?

Les chercheurs ont testé cette méthode contre le meilleur concurrent actuel (un algorithme génétique, un peu comme une évolution naturelle des solutions).

• Sur les petits problèmes : Les deux méthodes sont à peu près aussi bonnes.
• Sur les gros problèmes (beaucoup de camions et beaucoup de colis) : La méthode RL-CMSA gagne haut la main.
  • Elle trouve des solutions plus équilibrées.
  • Elle est plus fiable : si vous lancez le programme 40 fois, elle donne presque toujours le même excellent résultat.
  • Le concurrent (l'algorithme génétique), lui, est plus "instable" : parfois il trouve une solution géniale, parfois il rate le coche. C'est comme un joueur de fléchettes qui tire parfois au centre, mais souvent à côté.

💡 Pourquoi ça marche si bien ?

L'astuce principale est l'apprentissage. L'algorithme ne devine pas au hasard. Il se souvient : "La dernière fois que j'ai mis ces deux rues ensemble, le camion était très content (courte route). Je vais le noter."

Plus il y a de camions, plus cette méthode est efficace, car elle peut mélanger beaucoup de petits trajets courts pour créer un équilibre parfait. C'est comme si, au lieu de chercher une seule grande route parfaite, elle assemblait des milliers de petits chemins optimaux.

En Résumé

Cette recherche nous donne un nouvel outil pour gérer des flottes de véhicules (livraisons, drones, robots). Au lieu de chercher une solution unique et parfaite, elle utilise l'intelligence artificielle pour apprendre de ses succès, mélange les meilleures idées trouvées, et utilise la puissance des maths pour assembler le puzzle final. Le résultat ? Des livraisons plus équitables, plus rapides et plus fiables, surtout quand la tâche devient très complexe.

Résumé technique

Titre

Construction, Fusion, Résolution et Adaptation avec Apprentissage par Renforcement pour le Problème du Voyageur de Commerce Multiple (mTSP) Min-Max

1. Le Problème : mTSP Min-Max

Le papier s'intéresse au Problème du Voyageur de Commerce Multiple (mTSP) dans sa variante Min-Max.

• Définition : Il s'agit de généraliser le TSP classique en $m$ itinéraires qui partent et reviennent à un dépôt commun, visitant chacun des clients exactement une fois.
• Objectif : Contrairement à la variante classique qui minimise le coût total (somme des distances), la variante Min-Max vise à minimiser la longueur du plus long itinéraire parmi les $m$ routes.
• Importance : Ce critère est crucial pour l'équilibrage de la charge de travail (workload balance) dans des applications réelles comme la livraison du dernier kilomètre avec des véhicules identiques, la patrouille coordonnée de robots multiples, ou la planification de sorties de drones (UAV), où l'équité et les contraintes de niveau de service sont prioritaires.
• Complexité : Le problème est NP-difficile, même pour des instances métriques, ce qui rend les algorithmes exacts inapplicables aux grandes tailles, nécessitant l'usage d'heuristiques et de méta-heuristiques hybrides.

2. Méthodologie : RL-CMSA

Les auteurs proposent une approche hybride novatrice appelée RL-CMSA (Reinforcement Learning - Construct, Merge, Solve & Adapt). Cette méthode combine la génération constructive de solutions, l'optimisation exacte et l'apprentissage par renforcement.

Le cycle de l'algorithme se déroule en six phases itératives :

1. Construction (Construct) :

   • Génération de $n_{solutions}$ solutions candidates via un processus probabiliste en deux étapes :
     • Clustering : Partitionnement des villes en $m$ clusters. Les centres sont sélectionnés via une méthode de type $k$-means++ biaisée par des valeurs $q$ (issues de l'apprentissage par renforcement). Les villes sont assignées aux clusters en tenant compte de la distance angulaire, du coût d'insertion approximatif et de la compatibilité $Q$ (fréquence de co-occurrence apprise).
     • Routage : Construction d'un itinéraire par cluster via une heuristique d'insertion gloutonne, suivie d'une recherche locale intra-route (2-opt, Or-opt).
   • Des améliorations inter-routes (suppression, déplacement, échange) sont appliquées, en se concentrant sur la route la plus longue pour réduire le coût computationnel.

2. Fusion (Merge) :

   • Les routes générées sont ajoutées à un pool de candidats ($R_{cand}$).
   • Un mécanisme de "signature canonique" (tri des villes non-dépôt) permet de ne garder qu'une seule représentation (la plus courte) pour chaque ensemble de villes visitées.
   • Élagage des routes trop longues par rapport à la meilleure solution actuelle.

3. Résolution (Solve) :

   • Un Programme Linéaire en Nombres Entiers (MILP) de type "Set Covering" est résolu (via CPLEX).
   • L'objectif est de sélectionner exactement $m$ routes du pool $R_{cand}$ qui couvrent tous les clients tout en minimisant la longueur du plus long itinéraire sélectionné.
   • Cela permet de recombinaisonner de manière optimale les segments de routes prometteurs.

4. Amélioration (Improve) :

   • La solution obtenue par le MILP (qui peut contenir des doublons de villes) est rendue faisable et optimisée via des opérateurs locaux :
     • Remove : Suppression des doublons en choisissant la suppression offrant le meilleur gain.
     • Shift : Déplacement d'une ville d'une route à une autre.
     • Swap : Échange de deux villes entre routes différentes.
   • Ces opérateurs utilisent des probabilités de sélection basées sur le gain d'amélioration et la longueur de la route cible.

5. Apprentissage (Learn) :

   • Mise à jour des valeurs $q$ (probabilités de co-occurrence) pour les paires de villes.
   • Si une paire de villes apparaît dans une route de la meilleure solution ($R_{best}$), sa valeur $q$ est renforcée (tendance vers 0, favorisant leur regroupement). Sinon, elle est découragée (tendance vers 1).
   • Un mécanisme de réinitialisation est prévu si la convergence stagne.

6. Adaptation (Adapt) :

   • Gestion du pool $R_{cand}$ via un système d'âge. Les routes présentes dans la nouvelle meilleure solution sont réinitialisées à l'âge 0, tandis que celles absentes voient leur âge augmenter. Les routes trop vieilles sont supprimées pour maintenir la diversité et la compacité du pool.

3. Contributions Clés

• Intégration RL-CMSA : C'est la première application de l'extension par apprentissage par renforcement du framework CMSA au problème mTSP Min-Max.
• Guidage par l'Apprentissage : L'utilisation de valeurs $q$ pour guider le processus de clustering (seeding et assignment) permet d'adapter dynamiquement la construction des solutions en fonction des structures découvertes dans les solutions de haute qualité.
• Hybridation Puissante : La combinaison d'une construction probabiliste guidée, d'un solveur MILP exact pour la recombinaison, et d'opérateurs locaux permet d'équilibrer efficacement l'exploration et l'exploitation.
• Analyse de la Dynamique de Recherche : Utilisation de réseaux de trajectoires de recherche (STN) et de distances structurelles pour démontrer que l'algorithme converge plus rapidement vers des régions de haute qualité avec une plus grande robustesse que les algorithmes génétiques.

4. Résultats Expérimentaux

Les performances de RL-CMSA ont été évaluées sur des instances aléatoires et des benchmarks TSPLIB, comparées à un Algorithme Génétique Hybride (HGA) de l'état de l'art.

• Qualité des Solutions :

  • RL-CMSA surpasse systématiquement le HGA en termes de valeur moyenne de l'objectif et de fréquence d'obtention de la meilleure solution (#b), en particulier pour les instances de grande taille ($n=100, 200$) et un nombre élevé de vendeurs ($m$).
  • Pour les petites instances ($n=50$) et un petit nombre de routes ($m=1\%$), les deux méthodes sont comparables, le HGA étant parfois légèrement plus rapide.
  • Sur les instances TSPLIB, RL-CMSA atteint ou dépasse les meilleures solutions connues dans la majorité des cas.

• Robustesse et Temps d'exécution :

  • RL-CMSA est plus robuste : il trouve la meilleure solution dans presque toutes les exécutions (40 runs) pour la plupart des configurations, tandis que le HGA montre plus de variabilité.
  • En termes de temps CPU, RL-CMSA est généralement plus rapide pour trouver la meilleure solution, surtout sur les instances moyennes et grandes.

• Analyse Statistique :

  • Les tests de Wilcoxon appariés confirment que RL-CMSA est statistiquement supérieur au HGA pour la plupart des configurations ($n=100, 200$ et $m \ge 5\%$), avec des tailles d'effet importantes.

• Comportement de Recherche :

  • L'analyse des STN montre que RL-CMSA converge rapidement vers une région unique de haute qualité, tandis que le HGA explore plus largement mais avec moins de précision vers l'optimum global.

5. Signification et Conclusion

Ce travail démontre que l'intégration de l'apprentissage par renforcement dans le framework CMSA est particulièrement efficace pour les problèmes de routage complexes avec des objectifs d'équilibrage (Min-Max).

• Avantage Principal : La capacité de l'algorithme à apprendre quelles paires de villes doivent être regroupées permet de construire des solutions initiales de meilleure qualité et de guider le solveur exact vers des combinaisons plus prometteuses.
• Limites et Perspectives : La méthode montre une légère baisse de performance relative sur les très grandes instances avec un très petit nombre de routes ($m=1\%$), car la complexité de combinaison des routes longues augmente.
• Travaux Futurs : Les auteurs prévoient d'enrichir le pool de routes avec des voisinages à grande échelle, d'étendre l'apprentissage à des caractéristiques d'ordre supérieur (au-delà des paires), et d'adapter la méthode à des problèmes de routage avec contraintes supplémentaires (fenêtres de temps, capacités).

En résumé, RL-CMSA représente une avancée significative pour la résolution du mTSP Min-Max, offrant une alternative robuste et performante aux méta-heuristiques génétiques classiques.