用图神经网络+优化层，快速生成低成本的地理分区方案
DistrictNet: Decision-aware learning for geographical districting
- 将最小容量生成树问题嵌入GNN，实现结构化学习
- 在真实城市数据上降低运营成本，分钟级出解
- 适合需要长期规划的物流、政府等决策场景
地理分区是一个复杂的组合优化问题，涉及将地理区域划分为若干小区域。在物流领域，这是一项关键战略决策，影响未来数年的运营成本。传统方法即使对小型区域也难以求解，现有启发式算法常得次优解。本文提出一种结构化学习方法，可在几分钟内解决真实世界中的分区问题。该方法将容量受限的最小生成树问题作为组合优化层，集成到图神经网络架构中。为实现决策感知训练，我们展示了如何在合适空间构造目标解并从中学习。实验表明，该方法显著优于现有方法，在真实城市数据上可大幅降低运营成本。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。