Solveur Hiérarchique Neuronal Constructif pour des Scénarios du TSP dans le Monde Réel

Les solveurs constructifs neuronaux existants pour les problèmes de routage ont principalement utilisé des architectures de transformateurs, conceptualisant la construction de routes comme une tâche d'apprentissage de séquence à ensemble. Cependant, leur efficacité a principalement été démontrée sur des instances de problèmes totalement aléatoires qui ne capturent pas adéquatement les scénarios du monde réel. Dans cet article, nous introduisons des scénarios réalistes de Problème du Voyageur de Commerce (TSP) pertinents pour les environnements industriels et tirons les conclusions suivantes : (1) Le prochain nœud (ou ville) optimal à visiter se trouve souvent à proximité du nœud actuel, suggérant les avantages potentiels de biaiser les choix en fonction des emplacements actuels. (2) Résoudre efficacement le TSP nécessite un suivi robuste des nœuds non visités et justifie des stratégies de regroupement succinctes. En s'appuyant sur ces conclusions, nous proposons d'intégrer une couche de choix apprenable inspirée des Hyperréseaux pour prioriser les choix en fonction de l'emplacement actuel, et un algorithme de clustering approximatif apprenable inspiré de l'algorithme d'Expectation-Maximization pour faciliter le regroupement des villes non visitées. Ensemble, ces deux contributions forment une approche hiérarchique pour résoudre le TSP réaliste en tenant compte à la fois des voisinages locaux immédiats et de l'apprentissage d'un ensemble intermédiaire de représentations de nœuds. Notre approche hiérarchique donne de meilleures performances par rapport aux modèles de transformateurs classiques et récents, montrant l'efficacité des conceptions clés.