Large-scale Urban Facility Location Selection with Knowledge-informed Reinforcement Learning
This work addresses the combinatorial optimization challenge of urban facility location selection, offering a scalable and efficient solution for urban planning applications.
The paper tackles the facility location problem in urban settings by proposing a reinforcement learning method that achieves near-optimal solutions with superfast inference speed, demonstrating up to 1000 times speedup and less than 5% accessibility loss compared to commercial solvers in experiments on four US cities.
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.