The disruptive anti-covering location problem

Dispersion is a desirable element inherent in many location problems. For example, dispersive strategies are used in the location of franchise stores, bank branches, defensive missile silo placement, halfway homes, and correctional facilities, or where there is need to be dispersed as much as possible in order to minimize impacts. Two classic models that capture the essence of dispersion between facilities involve: (1) locating exactly p-facilities while maximizing the smallest distance of separation between any two of them, and (2) maximizing the number of facilities that are being located subject to the condition that each facility is no closer than r-distance to its closest neighboring facility. The latter of these two problems is called the anti-covering problem, the subject of this paper. Virtually all past research has involved an attempt to solve for the “best or maximal packing” solution to a given anti-covering problem. This paper deals with what one may call the worst case solution of an anti-covering problem. That is, what is the smallest number of needed facilities and their placement such that their placement thwarts or prevents any further facility placement without violating the r-separation requirement? We call this the disruptive anti-covering location problem. It is disruptive in the sense that such a solution would efficiently prevent an optimal packing from occurring. We present an integer linear program model for this new location problem, provide example problems which indicate that very disruptive configurations exist, and discuss the generation of a range of stable levels to this problem.