The Maximal Covering Location Problem with Capacities on Total Workload

TLDR

The Maximal Covering Location Problem has attracted extensive research and practice, but adding capacity limits makes the model harder to solve and can produce pathological assignment of uncovered demand. This paper seeks to extend the capacitated MCLP to mitigate such pathologies by addressing workload limits on facilities. We propose an efficient solution procedure that applies to both simple and extended capacitated MCLP formulations. Extensive testing shows the procedure’s effectiveness, and a real‑world scale example demonstrates its practical implications.

Abstract

The Maximal Covering Location Problem (MCLP) has been the focus of considerable attention both in research and practice for some time, and numerous extensions have been proposed to broaden its appeal and enhance its applicability. In this paper, we are concerned with the addition of workload limits on the facilities. While not generally difficult to formulate, these capacity constraints make the model substantially more difficult to solve, as well as create certain pathological results, particularly in the assignment of uncovered demand to facilities. First we discuss these pathologies and extend the capacitated MCLP to address them. Then, we present an efficient solution procedure that is applicable to both simple and extended problem formulations. Finally, results of extensive tests on the solution procedure are presented and a “real-world” scale example is solved to explore the implications of the model.