The capacitated maximal covering location problem with backup service

The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions — workload capacities on facilities and the allocation of multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach.