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.

Abstract

Districting is a complex combinatorial problem that consists in partitioning a geographical area of small units into larger units, called districts. In logistics, it is a major strategic decision impacting operating costs for several years. Solving them using traditional methods is intractable even for small geographical areas and existing heuristics, while quick, often provide sub-optimal results. We present a Decision-Focused Learning approach to find high-quality solutions to real-world districting problems in a few minutes. It is based on integrating a combinatorial optimization layer, the capacitated minimum spanning tree problem, into a graph neural network architecture. Our method is trained in a decision-aware fashion, by constructing target solutions embedded in a suitable space and learning from them. Exper-iments show that our approach outperforms existing methods and can reduce costs by on average 10% compared to benchmarks. Additionally, we show that our approach generalizes well to unseen instances and remains robust under varying instance parameters.