Deep Reinforcement Learning for Multi-Period Facility Location: p_k-median Dynamic Location Problem

Facility location is a crucial aspect of spatial optimization with broad applications in urban planning. Specifically, the multi-period problem involves spatial and temporal information, making it challenging to solve. Existing research mainly focuses on heuristic methods, which depend on complex hand-crafted techniques. In this paper, we propose a novel method based on Deep Reinforcement Learning (DRL) to solve p_k-median Dynamic Location Problem (DLP-p_k). Different from classical heuristic methods, our method avoids intricate designs and considers the temporal impacts of decisions. We are the first to apply DRL to the multi-period facility location problem. Our method adopts the encoder-decoder architecture and utilizes a specialized structure to capture the temporal features across different periods. On the one hand, we introduce the Gated Recurrent Units (GRU) to encode temporal information, including dynamic coverage and dynamic costs. On the other hand, we design an attention-based decoder that allows the model to capture long-term dependencies in decision-making. Experimental results from small-size to large-size demonstrate that our method can quickly provide high-quality solutions without relying heavily on expert knowledge, offering opportunities for efficiently solving multi-period facility location problems. Additionally, our method is up to two orders of magnitude faster than the exact solver Gurobi and demonstrates great generalization abilities.