DistrictNet : Optimisation des districts avec l'apprentissage automatique pour une planification efficace à long terme

Le partitionnement des districts, ou districting, est un problème combinatoire complexe qui consiste à partitionner une zone géographique composée de petites unités en unités plus grandes appelées districts. Dans le domaine de la logistique, il représente une décision stratégique majeure déterminant les coûts d’exploitation pour plusieurs années. Le résoudre avec des méthodes traditionnelles est extrêmement difficile, même pour de petites zones géogra-phiques, et les heuristiques existantes, bien que rapides, offrent souvent des résultats sous-optimaux. Nous présentons une approche d’apprentissage axée sur la décision pour trouver des solutions de haute qualité aux problèmes de districting dans le monde réel en quelques minutes. Cette approche repose sur l’intégration d’une couche d’optimisation combinatoire le problème de l’arbre de recouvrement minimum avec contraintes de capacité dans une architecture de réseaux de neurones en graphes. Pour entraîner notre modèle de manière orientée vers la décision, nous développons un algorithme qui reconstruit les solutions cibles dans un espace de représentation adapté, utilisé pour l’apprentissage par imitation. Nous utilisons des villes synthétiques pour l’entraînement et des villes réelles pour les tests. Les expériences montrent que notre approche surpasse les méthodes existantes et peut réduire les coûts jusqu’à 10% dans les villes réelles. De plus, nous démontrons que notre approche généralise efficacement aux instances inédites et reste robuste face à des paramètres d’instance variables.