A deep learning approach for the Team Orienteering Problem.
Une approche par apprentissage profond pour le Team Orienteering Problem.
Résumé
The Team Orienteering Problem is a combinatorial challenge, recognized as NP-Hard, with various practical applications in fields such as logistics and telecommunications. Recent advances in machine learning techniques, especially in deep learning model architectures like Pointer Networks and Graph Neural Networks, have demonstrated their effectiveness in addressing complex combinatorial optimization problems. These developments have increased interest in applying such techniques to combinatorial problems. On the other hand, heuristics, while efficient, are typically handcrafted, specialized, and lack generalizability, requiring significant expertise for their development. In contrast, machine learning models make decisions and solve problems by extracting useful information directly from the data without requiring specific problem knowledge. However, as the problem size and complexity increase, the performance of neural networks may degrade if we aim to maintain reasonable computational time. To leverage the strengths of both solution methods, we propose an innovative approach that integrates an efficient splitting algorithm for the TOP within a deep learning framework. This scheme operates in two stages: first, a deep neural network generates a giant tour (a sequence of customers/locations), and then the tour is evaluated using the split algorithm. To the best of our knowledge, this hybrid approach has not yet been proposed for solving the TOP.
Le Team Orienteering Problem est un défi combinatoire, reconnu comme NP-difficile, avec de nombreuses applications pratiques dans des domaines tels que la logistique et les télécommunications. Les avancées récentes en techniques d’apprentissage automatique, en particulier dans les architectures de modèles de deep learning telles que les Pointer Networks et les Graph Neural Networks, ont démontré leur efficacité dans la résolution de problèmes d'optimisation combinatoire complexes. Ces résultats ont suscité un intérêt croissant pour l’application de ces techniques aux problèmes combinatoires. D'un autre côté, les heuristiques, bien qu'efficaces, sont généralement conçues à la main, spécialisées, manquent de généralisation et nécessitent une expertise considérable pour leur développement. En revanche, les modèles d’apprentissage automatique prennent des décisions et résolvent des problèmes en extrayant directement des informations utiles à partir des données, sans nécessiter de connaissances spécifiques sur le problème. Cependant, à mesure que la taille et la complexité du problème augmentent, la performance des réseaux neuronaux peut diminuer si l’on souhaite maintenir un temps de calcul raisonnable. Pour tirer parti des deux types de méthodes de solution, nous proposons une approche innovante qui intègre un algorithme de découpage efficace pour le TOP au sein d'un cadre de deep learning. Ce schéma fonctionne en deux étapes : d'abord, un réseau de neurones profonds génère un circuit géant (une séquence de clients/lieux), puis il est évalué à l'aide de l'algorithme de découpage. À notre connaissance, cette approche hybride n'a pas encore été proposée pour résoudre le TOP.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|