Intelligent Optimization Algorithms for Disruptive Anti-covering Location Problem

Given a set of potential sites for locating facilities, the disruptive anti-covering location problem (DACLP) seeks to find the minimum number of facilities that can be located on these sites in such a way that each pair of facilities are separated by a distance which is more than R from one another and no more facilities can be added. DACLP is closely related with anti-covering location problem (ACLP), which is concerned with finding the maximum number of facilities that can be located such that all the facilities are separated by a distance which is more than R from each other. The disruptive anti-covering location problem is so named because it prevents the best or maximal packing solution of the anti-covering location problem from occurring. DACLP is an NP-hard problem and plays an important role in solving many real world problems including but not limited to forest management, locating bank branches, nuclear power plants, franchise stores and military defence units. In contrast to ACLP, DACLP is introduced only recently and is a relatively under-studied problem. In this paper, two intelligent optimization approaches namely genetic algorithm (GA) and discrete differential evolution (DDE) are proposed to solve the DACLP. These approaches are the first heuristic approaches for this problem. We have tested the proposed approaches on a total of 80 DACLP instances containing a maximum of 1577 potential sites. The effectiveness of the proposed approaches can be observed from the results on these instances.

Automated summary

Given a set of potential sites, the DACLP aims to find the minimum number of facilities that can be located on these sites while maintaining a minimum distance requirement between them. This problem is closely related to the ACLP, which seeks to maximize the number of facilities with the same distance requirement. The DACLP is an NP-hard problem and has significant implications in various real-world applications. In this paper, two intelligent optimization approaches, GA and DDE, are proposed as the first heuristics to solve the DACLP, and their effectiveness is demonstrated through extensive testing.