@inproceedings{
ahmed2024districtnet,
title={DistrictNet: Decision-aware learning for geographical districting},
author={Cheikh Ahmed and Alexandre Forel and Axel Parmentier and Thibaut Vidal},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=njwYBFau8E}
}
Districting is a complex combinatorial problem that consists in partitioning a geographical area into small districts. In logistics, it is a major strategic decision determining operating costs for several years. Solving districting problems using traditional methods is intractable even for small geographical areas and existing heuristics often provide sub-optimal results. We present a structured 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. To train this pipeline in a decision-aware fashion, we show how to construct target solutions embedded in a suitable space and learn from target solutions. Experiments show that our approach outperforms existing methods as it can significantly reduce costs on real-world cities.
DistrictNet: Decision-aware learning for geographical districting
Cheikh Ahmed Alexandre Forel Axel Parmentier Thibaut Vidal