Accelerated Benders decomposition and local branching for dynamic maximum covering location problems
针对动态最大覆盖选址问题，提出加速Benders分解和局部分支法两种精确求解方法，通过计算实验验证了其在大规模实例上的有效性。
The maximum covering location problem (MCLP) is a key problem in facility location, with many applications and variants. One such variant is the dynamic (or multi-period) MCLP, which considers the installation of facilities across multiple time periods. To the best of our knowledge, no exact solution method has been proposed to tackle large-scale instances of this problem. To that end, in this work, we expand upon the current state-of-the-art branch-and-Benders-cut solution method in the static case, by exploring several acceleration techniques. Additionally, we propose a specialised local branching scheme which exploits the separability of the problem by time period. This scheme uses a novel distance metric in its definition of subproblems and features a new method for efficient and exact solving of the subproblems. These methods are then compared through extensive computational experiments, highlighting the strengths of the proposed methodologies. • We extend the state-of-the-art approach for the static MCLP to the dynamic case. • We detail acceleration techniques for this extended Benders decomposition method. • We develop a specialised local branching scheme which exploits separability. • The accelerated Benders decomposition method outperforms the state-of-the-art. • The local branching method can find better quality solutions in hard instances.