A marginal increment assignment algorithm for maximal coverage location problem

Large-scale maximal coverage location problems (MCLP) are quite common in practices, but till now efficient solving methods for them are still quite limited. A new assignment algorithm was proposed in this paper to solve such large-scale MCLPs. In the proposed algorithm, the whole location space is first divided into small regions. Then a heuristic method based on marginal increment was designed to assign facilities into these regions. The assignment was proved to be optimal under some non-strict conditions. The original problem is then decomposed into sub problems with much smaller scale that can be solved easily. A bank branch location problem was studied for computational experiments, and the results show that the proposed algorithm has good performance.