用强化学习快速解决城市设施选址难题，效率提升千倍。
Large-scale Urban Facility Location Selection with Knowledge-informed Reinforcement Learning
- 用图神经网络模拟局部搜索的交换操作，避免繁重计算
- 在4个美国城市测试中，性能接近商用求解器，损失<5%
- 适合城市规划、交通设计等需要快速决策的场景
设施选址问题（FLP）是一类经典的组合优化挑战，旨在战略性地布局设施以最大化可达性。本文提出一种针对大规模城市FLP的强化学习方法，可在极快推理速度下生成近似最优解。我们从局部搜索中提炼出核心的交换操作，并通过知识引导的图神经网络智能选择城市区域图上的边来模拟该操作，从而规避了局部搜索的高耗计算。在四个具有不同地理空间条件的美国城市上进行的大量实验表明，该方法在不到5%可达性损失的前提下，相较商用求解器实现最高达1000倍的速度提升。我们已将模型部署为在线地理空间应用，地址为 https://huggingface.co/spaces/randommmm/MFLP。
原文摘要 · Abstract (English)
The facility location problem (FLP) is a classical combinatorial optimization challenge aimed at strategically laying out facilities to maximize their accessibility. In this paper, we propose a reinforcement learning method tailored to solve large-scale urban FLP, capable of producing near-optimal solutions at superfast inference speed. We distill the essential swap operation from local search, and simulate it by intelligently selecting edges on a graph of urban regions, guided by a knowledge-informed graph neural network, thus sidestepping the need for heavy computation of local search. Extensive experiments on four US cities with different geospatial conditions demonstrate that our approach can achieve comparable performance to commercial solvers with less than 5\% accessibility loss, while displaying up to 1000 times speedup. We deploy our model as an online geospatial application at https://huggingface.co/spaces/randommmm/MFLP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。