A Deep Reinforcement Learning Framework for Capacitated Facility Location Problems with Discrete Expansion Sizes

Capacitated facility location problem (CFLP) is a classical combinatorial optimization problem widely applied in the domains of distribution, transportation planning, and telecommunication. As a typical NP-hard optimization problem, CFLPs featured by combinatorially high-dimensional decision spaces are not easily solved by most conventional methods. To appropriately handle the hard nature of CFLPs, we propose a deep reinforcement learning (DRL)-based framework to address CFLPs with discrete expansion sizes. Since a solution to the investigated CFLP can be sequentially constructed by partial solutions, we reformulated the CFLP as a Markov decision process with an unfixed and discrete time horizon. A deep Q-network (DQN)-based framework is adopted to learn the policy parameters and location solution. We experimentally demonstrate that our proposed approach can effectively find near-optimal solutions for CFLPs.