The Maximal Expected Covering Location Problem: Revisited

The Maximal Expected Coverage Location Problem (MEXCLP) addresses the problem of optimally locating servers so as to maximize the expected coverage of demand while taking into account the possibility of servers being unavailable when a call enters the service system. In this paper, an attempt is made to relax three of MEXCLP's assumptions: servers operate independently, servers have the same busy probabilities, and server busy probabilities are invariant with respect to their locations. We embed the hypercube queueing model in a single node substitution heuristic optimization procedure, to determine a set of server locations which “maximize” the expected coverage. Our empirical findings indicate that there is disagreement between the expected coverage predicted by the MEXCLP model and the hypercube optimization procedure. There is substantial agreement, however, between the locations generated by the two procedures. We also consider a simple “adjustment” to the MEXCLP model, based upon random sampling of servers without replacement; the same adjustment has been used previously to derive a hypercube approximation procedure. We discuss modifications and enhancements to the MEXCLP's heuristic solution procedure for this adjusted model. Our empirical findings indicate that there is better agreement between the expected coverage predicted by the adjusted model and the hypercube optimization procedure. The locations generated by the adjusted model, however, are of the same overall quality as those generated by the MEXCLP model. Readers should view the results of this paper in light of the fact that we are able to relax the MEXCLP by assuming that the operating characteristics of the service system fit the description of the hypercube queueing model, such as Poisson arrivals and exponential service times, which may not be strictly true in practice.