Le problème du voyageur de commerce est un casse-tête classique qui défie les mathématiciens et les logisticiens depuis des décennies. Imaginez un chauffeur de livraison qui doit visiter une liste spécifique de villes exactement une fois et revenir à son point de départ, tout en essayant de trouver l'itinéraire le plus court pour économiser du carburant et du temps. Bien que les règles soient simples, le nombre de routes possibles augmente de manière si explosive avec chaque nouvelle ville ajoutée que même les superordinateurs les plus puissants peinent à trouver le meilleur chemin absolu pour de grands groupes de villes. C'est pourquoi ce problème est considéré comme un test central pour toute nouvelle méthode de résolution de puzzles complexes. Ces dernières années, les scientifiques se sont tournés vers l'intelligence artificielle, plus précisément un type d'apprentissage qui imite la façon dont le cerveau humain traite les modèles, pour relever ce défi. Ces systèmes d'apprentissage ne calculent pas chaque possibilité ; au lieu de cela, ils étudient des milliers d'exemples pour apprendre un ensemble de règles qui mènent généralement à une solution très bonne, sinon parfaite. L'objectif est de créer un système assez rapide pour être utile dans la vie réelle, mais assez intelligent pour ne pas rester bloqué sur un mauvais itinéraire.

Une équipe de chercheurs de Shanghai a développé une nouvelle approche de ce problème qui équilibre la vitesse et la précision d'une manière novatrice. Leur travail, intitulé DA-GAT-CADS, aborde une difficulté spécifique qui a entravé les tentatives précédentes : la tension entre l'examen des options proches et l'examen des options lointaines. Sur une carte de ville, la prochaine étape d'un bon itinéraire est généralement un voisin, mais parfois le conducteur doit sauter par-dessus plusieurs villes proches pour relier deux groupes de villes distants. Les anciens modèles d'IA devaient souvent choisir entre deux extrêmes. Ils pouvaient examiner chaque ville non visitée pour s'assurer de ne pas manquer une connexion lointaine, mais cela était lent et lourd en termes de calcul. Ou bien, ils pouvaient ne regarder que les voisins les plus proches pour gagner du temps, mais cela les faisait souvent manquer les sauts de longue distance cruciaux nécessaires pour terminer le circuit efficacement. Les chercheurs ont réalisé que la solution n'était pas de choisir un côté ou l'autre, mais de construire un système qui utilise le voisinage local comme une valeur par défaut sûre, tout en gardant un mécanisme prêt à se déployer lorsque la situation l'exige.

Le cœur de leur nouvelle méthode implique deux parties principales travaillant ensemble. Premièrement, le système construit une carte mentale des villes basée sur leur disposition géométrique, utilisant spécifiquement une structure mathématique appelée triangulation de Delaunay. Considérez cela comme le fait de tracer des lignes entre les villes qui sont naturellement proches les unes des autres, créant ainsi un réseau de connexions locales. Les chercheurs ont conçu un encodeur qui prête une attention particulière à ces lignes locales, utilisant la distance réelle entre les villes pour pondérer l'importance de chaque connexion. Cela garantit que le système comprend la géographie immédiate du problème. Cependant, ils ont également ajouté une boucle de rétroaction globale légère, permettant au système de garder une conscience de l'ensemble de la carte en son esprit, et pas seulement de l'environnement immédiat. Cette combinaison aide le système à construire une compréhension solide de la position des villes sans être submergé par des détails inutiles.

La seconde partie du système est le décodeur, qui est responsable du choix effectif de la prochaine ville à visiter. Au lieu de vérifier aveuglément chaque ville ou de s'en tenir rigidement aux voisins les plus proches, ce système utilise une méthode d'échantillonnage dynamique. Il conserve toujours les voisins non visités de la carte locale comme une liste de candidats sûre. Mais il possède également une « porte » qui peut s'ouvrir pour laisser entrer des villes lointaines si le parcours actuel suggère qu'elles sont nécessaires. Cette porte n'est pas fixe ; elle apprend à décider en fonction de l'état du circuit. Si le conducteur est coincé dans un groupe de villes et doit faire un saut vers un groupe lointain pour éviter un mauvais itinéraire, la porte s'ouvre davantage pour considérer ces options distantes. Si les voisins locaux sont suffisants, la porte reste fermée, maintenant la recherche concentrée et rapide. Ce processus de prise de décision est entraîné à l'aide d'un système de récompense spécial qui pénalise le modèle s'il est trop restrictif (ignorant de bonnes options lointaines) ou trop expansif (vérifiant trop de villes et gaspillant du temps).

Lorsque les chercheurs ont testé ce nouveau système sur des groupes de cinquante, cent et deux cents villes, les résultats ont montré une amélioration claire de la manière dont l'IA équilibre la qualité et la vitesse. Sur un test standard avec cent villes, leur méthode a réduit le taux d'erreur par rapport à un modèle standard de 0,65 % à 0,28 %. Plus important encore, lorsqu'ils ont comparé leur système de porte dynamique à un système fixe qui ne regardait qu'un nombre déterminé de voisins, la nouvelle méthode a trouvé de meilleurs itinéraires tout en examinant beaucoup moins de villes en moyenne. Plus précisément, le nouveau système n'a eu besoin de considérer qu'environ 24 % des villes non visitées pour atteindre une qualité de solution presque aussi bonne que si l'on vérifiait chaque ville. Cette efficacité s'est traduite par des avantages concrets dans le monde réel : le système s'est exécuté plus rapidement et a utilisé moins de mémoire informatique que les modèles qui vérifient toutes les options, sans sacrifier la qualité de l'itinéraire final.

L'étude a également exploré la sensibilité du système à ses paramètres, plus précisément à la mesure dont il est encouragé à gagner du temps par rapport à la recherche du trajet parfait. Ils ont découvert qu'en ajustant un seul contrôle, ils pouvaient modifier le comportement du système. S'ils le poussaient trop fort vers la parcimonie, il manquait des connexions lointaines importantes et les itinéraires devenaient moins bons. S'ils le laissaient vérifier trop de villes, il devenait lent. Cependant, ils ont identifié un point d'équilibre optimal où le système maintenait des itinéraires de haute qualité tout en gardant bas le nombre de villes vérifiées. Cette capacité à ajuster l'équilibre suggère que la méthode est robuste et adaptable. De plus, lors de tests sur des données de cartes réelles provenant d'une bibliothèque publique de problèmes de référence, le système s'est montré compétitif face à d'autres méthodes avancées, prouvant que son intuition géométrique fonctionne bien même sur des cartes qui ne faisaient pas partie de son entraînement.

Les chercheurs précisent avec prudence que leur travail est une avancée dans un domaine spécifique : les cartes de petite à moyenne taille avec des villes dispersées sur un plan plat. Ils ne prétendent pas avoir résolu le problème pour tous les scénarios possibles ou pour des réseaux massifs et complexes. Leur contribution est un principe de conception spécifique : utiliser la géométrie comme une ancre fiable pour les décisions locales tout en utilisant le contexte appris pour récupérer sélectivement les options distantes lorsque cela est nécessaire. En traitant le choix des villes à considérer comme une action flexible et apprenable plutôt que comme une règle fixe, ils ont créé un solveur qui est à la fois efficace et performant. Cette approche offre une voie prometteuse pour les futures applications de logistique et de routage, où trouver une très bonne solution rapidement est souvent plus précieux qu'attendre une solution parfaite.