DistrictNet: Decision-aware learning for geographical districting
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929624795054080 |
|---|---|
| author | Ahmed, Cheikh Forel, Alexandre Parmentier, Axel Vidal, Thibaut |
| author_facet | Ahmed, Cheikh Forel, Alexandre Parmentier, Axel Vidal, Thibaut |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08287 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | DistrictNet: Decision-aware learning for geographical districting Ahmed, Cheikh Forel, Alexandre Parmentier, Axel Vidal, Thibaut Machine Learning Optimization and Control 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. |
| title | DistrictNet: Decision-aware learning for geographical districting |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2412.08287 |