Reinforcement Learning for Weighted p-median Problem

This paper presents and explores the possibility of using reinforcement learning to solve the weighted p-median problem. The weighted p-median problem is formulated as a gradual build-up of centers generating admissible solutions. The agent is based on the Proximal Policy Optimization method. Several designs of environment state representations, reward functions, and artificial neural network architectures are tested and compared. The proposed approach is applied to solve the weighted p-median problem at the level of regions and the whole Slovak Republic. For the largest problem with the number of vertices 2916 and parameter
$p=273$
, the proposed method found solution differing from the optimal solution by 5.7
^%
which shows the potential of using reinforcement learning to solve the weighted p-median problem.