Swap-based Deep Reinforcement Learning for Facility Location Problems in
  Networks
Wenxuan Guo Yanyan Xu Yaohui Jin
Facility location problems on graphs are ubiquitous in real world and hold
significant importance, yet their resolution is often impeded by NP-hardness.
Recently, machine learning methods have been proposed to tackle such classical
problems, but they are limited to the myopic constructive pattern and only
consider the problems in Euclidean space. To overcome these limitations, we
propose a general swap-based framework that addresses the p-median problem and
the facility relocation problem on graphs and a novel reinforcement learning
model demonstrating a keen awareness of complex graph structures. Striking a
harmonious balance between solution quality and running time, our method
surpasses handcrafted heuristics on intricate graph datasets. Additionally, we
introduce a graph generation process to simulate real-world urban road networks
with demand, facilitating the construction of large datasets for the classic
problem. For the initialization of the locations of facilities, we introduce a
physics-inspired strategy for the p-median problem, reaching more stable
solutions than the random strategy. The proposed pipeline coupling the classic
swap-based method with deep reinforcement learning marks a significant step
forward in addressing the practical challenges associated with facility
location on graphs.