Abstract:

The maximal covering location problem is widely applied in real life, and it is demonstrated to be an NP-Hard problem in combinatorial optimization. First, the algorithms for the upper and lower bound are proposed. Then, the mathematical properties, including the properties that can determine batches of facilities that must engage or not, are addressed. After that, a backtracking algorithm with reduction that returns a global best solution based on sub-algorithms for the upper and lower bound and these mathematical properties is presented, which is able to quickly reduce the scale of the question. Finally, an instance is illustrated to describe the steps of the algorithm.

Key words: maximal covering location problem, exact algorithm, upper bound algorithm, lower bound algorithm

摘要：

最大覆盖选址问题在实际生活中有广泛的应用，是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法，接着研究数学性质，其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后，利用上下界子算法和这些数学性质设计出一种可以快速减小问题规模且能求出最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程。

关键词: 最大覆盖选址问题, 精确算法, 上界算法, 下界算法