A genetic algorithm-based solution for multi-type maximal covering location problem (MMCLP): application to defense and deterrence

Abstract

Purpose

We study the problem of finding optimal locations for a suite of defense assets in order to protect high-value tactical and strategic infrastructure across a vast geographical area. To this end, we present a multi-type with non-overlapping coverage requirement as an extension to the classical formulation for the maximal covering location problem (MCLP).

Design/methodology/approach

In our case study, we use open source geographic and demographic data from Canadian sources as inputs to our optimization problem. Due to the complexity of the MIP formulation, we propose a hybrid metaheuristic solution approach, for which a genetic algorithm (GA) is proposed and integrated with local and large neighborhood search operators.

Findings

Extensive numerical experiments over different instances of the proposed problem indicate the effectiveness of the GA-based solution in reducing the solution time by a factor of ten compared to the CPLEX commercial solver while both approaches obtain solutions of similar quality.

Research limitations/implications

This research is limited to location planning of defense assets leveraging geospatial data of Canada. However, the diverse Canadian geography is among the most challenging given broad variability in population density and the vast size of the country leading to a large search space having substantial variability in fitness performance.

Practical implications

Our findings demonstrate that for large-scale location searches, the GA with a local neighborhood search performs very well in comparison to CPLEX but at a fraction of the execution time.

Originality/value

Our findings provide insight into how to make improved decisions for the placement of deterrence and defense systems and the effectiveness of a hybrid metaheuristic in addressing associated computational challenges.

Citation

Lessan, J.D. and Pond, G. (2024), "A genetic algorithm-based solution for multi-type maximal covering location problem (MMCLP): application to defense and deterrence", Journal of Defense Analytics and Logistics, Vol. 8 No. 2, pp. 160-178. https://doi.org/10.1108/JDAL-04-2024-0007

Introduction

Air defense power and dominance of homeland air and space domains is becoming increasingly important for countries across the globe. With a limited number of defense assets, one strategy for addressing a large number of potential threats is to properly deploy and utilize available assets to detect and neutralize any incoming threats. However, determining where to locate air defense assets like radars or missile batteries in order to protect high-value infrastructure, cover dense populations or establish a shield over strategic points presents several challenges. Every candidate point or defense system, for instance, has its own geographic, logistic requirements and strategic importance. Based on these considerations, we examine the question of how to best locate the resources needed to population areas. We propose the multi-type, maximal covering location problem (MMCLP) with non-overlapping coverage requirement as an extension to the classic MCLP. As a case study, we use open-source geographic and demographic data from Canada in our optimization problem. The complexity of the MIP formulation leads us to propose a metaheuristic solution, for which a GA-based solution is proposed and integrated with local and large neighborhood refinement strategies to solve the problem. Results from solving different instances of the location problem support the effectiveness and consistency of the proposed GA-based solution for the MMCLP in reducing the computational cost relative to the CPLEX commercial solver. Our findings provide insights into how to make improved decisions for the placement of deterrence and defense systems. While our case study involves air defense, the model also has applicability to radar applications, telecommunications and emergency services.

The paper is structured as follows: in the next section, we present a review of the relevant literature; we then discuss our methodology and present the formulation of the proposed optimization model, followed by a description of our case study data. We then present our GA-based solution method and share the results of our numerical experiments. In the last section, we conclude with a summary of findings, insights and directions for further research.

Literature review

Background

Problems relating to location analysis are an integral part of strategic and operational planning. Several variants of location analysis and planning problems can be found in the literature. These problems differ in terms of their objectives, operational requirements, performance metrics and side constraints. Nonetheless, “demand points/sites” and “candidate points/sites” are among the key components of any location planning problem. A candidate point (area) is a discrete point (continuous area) where service-providing facilities such as defense assets (e.g. radars or surface-to-air missile (SAM) batteries) can be located, while service-receiving points or areas that must be covered are considered as demand points. Both candidate points and demand points can be critical from various aspects such as logistic, geographic and strategic perspectives. It is usually assumed that demand areas and candidate locations of servers are discrete sets. When either one (or both) sets are continuous, the common approach is to transform it into discrete sets by superimposing a grid over the continuous area and representing each grid space with a single point. The performance metric (objective) is another common component of any location planning problem. Common objectives that are considered in location problems include centrality (e.g. median, center) and covering, and dispersion objectives which are generally defined in the form of some service-related criteria. In most of the location planning problems, the metric generally indicates the distance (time or their cost equivalent) between demand points and candidate points (ReVelle and Eiselt, 2005). In what follows, a review of the median (minisum) problem (Cooper, 1963), center (minimax) problem (Hakimi, 1964) and covering problem (Toregas et al., 1971; Church and ReVelle, 1974) is presented, examining different models and their applications to military settings and algorithms used to solve the corresponding problems.

Median, center and covering problems

The p-median problem is one of the most well-known location planning problems (Cooper, 1963). The objective of this problem is to determine the optimum location of p service facilities among a number of candidate sites by minimizing the total coverage cost (e.g. weighted cost equivalent of time or travel distance) between all demand locations and their nearest service-providing facilities. Depending on its application, it is usually assumed that the serving/covering cost of a demand at each point is determined by the magnitude (value) of the demand, the importance of satisfying that demand or the travel (distance or time) cost needed to acquire the demand from its nearest facility. One important issue with the p-median problem is its tendency to favor those demand points which are naturally located near to the located facility (service) centers. To address this shortcoming, the p-center (also called minimax) location planning problem was introduced by Hakimi (1964). The objective of the p-center location planning problem is minimizing the maximum service cost from all demand points to their nearest facility.

The coverage problems are concerned with optimally locating facilities using a performance measure called coverage. In these problems, however, when a (demand) point is within a maximum distance of a service providing facility, it is considered as a covered demand point. The set covering location problem (SCLP) was introduced by Toregas et al. (1971) who defined coverage as a measure of effectiveness in locating facilities. By doing so, the problem formulation determines the minimum number of facilities that should be located such that at least one facility is located within a specified maximum distance of each demand point. In the SCLP, all facilities within reach (S) of the demand point can provide coverage for that demand point. As a result, the SCLP may provide several facilities to cover a single demand point. The MCLP is similar to the p-median problem as the number of facilities which must be located is limited to a predetermined number, p. The MCLP is commonly used for location problems with resource constraints (ReVelle and Williams, 2001). The objective, however, is maximizing the total covered demand which falls within a critical distance or desired maximum distance.

Military application of location planning problems

Infrastructure protection

Infrastructure protection is one of the areas where location planning problems are utilized for military purposes, in order to build or maintain some level of preparedness or to protect critical infrastructure from hostile attacks.

With regards to the median and center facility location approach, in the context of military and defense location planning, Murty and Djang (1999) applied a p-median model for determining optimal sites for a base, secondary and mobile trainers. Church (2004) and Church and Scaparra (2007) determined the most critical r-facilities out of p-facilities with highest impact during a possible interdiction. Scaparra and Church (2008) then used a p-median formulation for the deployment of protective measures to minimize the effect of attacks on facilities. Dong et al. (2009) identified a solution strategy for protecting critical facilities while maximizing system satisfaction in the event that only a subset of those critical facilities is destroyed. Sathe and Miller-Hooks (2005) located a limited number of protecting forces to cover the highest number of facilities under travel times and the demand uncertainties while minimizing cost and maximizing secondary coverage. Dawson et al. (2007) applied the p-median model in US Air Force Intercontinental Ballistic Missile (ICBM) systems for optimally locating defensive elements. Both Boardman et al. (2017) and Han et al. (2016) employed game theory to identify optimal locations for surface-to-air missile batteries defending against attacking missiles.

As discussed in the previous section, SCLP and MCLP are other integral parts of the literature on facility location models applied to various military settings. In this regard, Arslan (2009) located optimal alert sites to protect Turkish airspace when anticipating a changing threat. Sarikaya (2009) used an MCLP to cover airspace regions by optimally allocating airborne early warning and control aircraft. Overholts et al. (2009) applied an MCLP for improving military maintenance scheduling activities of ICBM systems within a geographically dispersed service area and in consideration of desired security levels. Ghanmi (2011) determined optimal hub location and aircraft routes used in the Canadian Forces.

Finally, there are studies that apply a combination of covering, median, center or other metrics such as risk. Eberlan (2004), for example, applied SCLP, p-center and p-median formulations for optimally allocating strip alert sites (sites where aircraft are kept on a level of high-readiness) for intercepting potential threats. A two-stage MILP formulation was leveraged by Brown et al. (2005) to defend against ballistic missiles. Similarly, Bell et al. (2011) applied SCLP along with p-median formulations to determine optimal locations for alert sites for homeland defense by selecting aircraft sites to cover critical areas. Çetinkaya and Haffar (2018) allocated different weapon types based on a risk-based location-allocation approach. Tanergüçlü et al. (2012) optimally located radar and air defense weapon systems to cover the approach routes of incoming weapons. Murphy et al. (2010) developed a dynamic defensive strategy that uses dynamic missile defense to reduce risk, make best use of existing assets, and keep the cost of developing and acquiring new systems at a minimum. Haywood et al. (2022a) studied an asset location problem to detect and interdict intruders over paths using multi-objective optimization. Haywood et al. (2022b) used a bi-level programming approach for ballistic missile defense asset location.

Surveillance, sensor and warning

Location planning problems are also used for deploying different surveillance or detection sensors such as sonar and radar. In this context, Schick (1992) applied an MCLP model for locating imaging radars for identifying space-borne objects in Canada; Kierstead and DelBalzo (2003) planned search paths in continuous space and time; Gencer et al. (2008) used MCLP and maximum expected coverage location problem (MEXCLP); and Daskin (1983) optimally located detectors and alarms to protect the facilities in a military region from asymmetric threats. Tanergüçlü et al. (2012) optimally located weapon and radar positions, and Karatas and Akman (2015) optimally located and deployed a configuration of sensors in a bi-static setting; multiple works (Washburn and Karatas, 2015; Karatas and Craparo, 2015; Karatas et al., 2016) evaluated the performance of multi-static sonar fields, pattern optimization and maximized area coverage. Craparo et al. (2017) and Craparo and Karatas (2018) leveraged the point (critical facility) coverage problem; Jourdan and de Weck (2004) optimally located wireless sensors in a hostile region for monitoring critical facilities. Karatas et al. (2016) identified the best locations out of a set of candidate sites on a barrier line to improve the probability of detecting intruders trying to cross a barrier line; Karatas (2018) optimally deployed different sensors utilized for a hybrid barrier and point coverage. Chen et al. (2015), Wang et al. (2016) and Gong et al. (2014) optimally placed receivers and bi-static radar sources to build belt barrier coverage to prevent illegal crossings. Lessin et al. (2018) improved border security based on the exposure-oriented sensor location problem. Karatas (2020) optimally located heterogeneous sensor networks assuming a hub-spoke location topology; Yakıcı and Karatas (2021) modeled a multi-objective optimal location formulation of a heterogeneous sensor network for improved network performance, with a genetic algorithm (GA). In a similar stream, Shi and Xue (2016) determined the least number of watch-points for maximizing the overall coverage over a large-scale digital area; Li et al. (2015) optimized the coverage of wireless sensor networks. Dambreville (2006) optimized the geographic locations and parameters of the sensors to maximize track covering; Han et al. (2013) optimized the posture of a terminal air defense system. Jia et al. (2007) maximized the coverage of a wireless sensor network in a given target area; and Brown et al. (2011) optimally located onshore radar sites and defending vessels.

Algorithms to solve location planning problems

Different solution methods to solve location planning problems can be categorized into: (1) metaheuristic methods such as GAs (Jourdan and de Weck, 2004; Yakıcı and Karatas, 2021) and simulated annealing (Bell, 2003); (2) heuristic methods such as greedy algorithms (Chan et al., 2008), GRASP (Dawson et al., 2007) and decomposition (Murty and Djang, 1999) and (3) mathematical programming approaches (Schick, 1992; Amouzegar et al., 2004a, b; Church, 2004; Eberlan, 2004; Church and Scaparra, 2007; Gencer et al., 2008; Arslan, 2009). Here we provide a brief overview of these solution approaches and compare their advantages and limitations. For a detailed list of different solutions used for location planning problems in the military, see Karatas et al. (2019) and Argun (2019).

Mathematical programming optimization (e.g. exact and exhaustive search), heuristics and metaheuristics are three different solution techniques used in the literature to solve location planning problems. Ideally, mathematical programming-based methods can obtain optimal solutions in small- and medium-size instances of the location planning problems including SCLP and MCLP. However, they perform poorly in large-scale instances of these problems because of the computational complexity of location planning problems. In these situations, the heuristic and metaheuristic methods can be fast and efficient in identifying solution alternatives. These methods, however, do not guarantee the global optimality of their solutions. Heuristic methods like greedy algorithms (Chan et al., 2008) and GRASP (Dawson et al., 2007) are problem-specific while metaheuristics and metaheuristic approaches (Bell, 2003; Jourdan and de Weck, 2004) are problem-independent. This allows metaheuristics to solve a wide range of problems. Metaheuristic techniques include a broad range of methods. At a high level, they are categorized into either single- or population-based methods. As a comparison, typical single solution metaheuristics rely on a single candidate solution and refine it until certain criteria are met; examples include variable neighborhood search (VNS), Tabu search (Wang et al., 2014), iterated local search, guided local search, and simulated annealing (Bell, 2003). On the other hand, population-based approaches seek to identify multiple candidate solutions and guide the search based on the characteristics of the population. Particle swarm optimization, evolutionary computation and GAs (Jourdan and de Weck, 2004) are examples of population-based metaheuristics. Moreover, hybrid algorithms like a metaheuristic in combination with other techniques are also employed for solving location planning problems (Pond et al., 2015; Yakıcı and Karatas, 2021).

Methodology

Problem definition

The underlying idea of the MMCLP is that an organization has a suite of defense facilities of different types, each of which can have unique characteristics such as detection radius, weather and visibility limitations, and suitable geographic or zone placement regulations. Moreover, it is reasonable to assume that suitable points may vary depending on the facility type. In our application, we assume that the facility types are different only in terms of their detection radius or effective coverage range. We also assume there should be limited overlap between the coverage of different facilities, although this may not be a strict requirement in practice.

Parameters

ai:

Population density at grid cell i

pb:

Maximum number of facilities of type b to be placed

Sb:

The coverage range of facility b

Sets

I:

Set of demand points (grid cells), indexed by i∈I={1,...,|I|}

J:

Set of candidate locations (grid cells), indexed by j∈J={1,...,|J|}

B:

Set of facility types, indexed by b∈B={1,...,|B|}

Nbi:

Set of potential sites (grid cells) within Sb coverage distance of point i

Nbj:

Set of demand points (grid cells) within Sb coverage distance of point i

Decision Variables

ybi:ybi=1

if a grid cell i is covered by a nearby facility of type b and 0 otherwise

xbj:xbj=1

if a facility of type b is located at candidate location j and 0 otherwise

Both of the above decision variables ybi and xbj are binary decision variables.

Given these definitions, the MMCLP formulation writes as follows:

(1)Max F=∑i∈I∑b∈Baiybi

subject to:

(2)∑j∈Nbixbj≥ybi ∀ i∈I,b∈B

(3)∑j∈Jxbj≤pb ∀ b∈B

(4)∑b∈B∑j∈Nbixbj≤1 ∀ i∈I

(5)xbj+xb'j'≤1 ∀ j′<j,j and j′∈J

(6)∀ b,b′≠b∈B,Nbi∩Nb'i'

(7)xbj,ybi∈{0,1} ∀ j∈J,i∈I,b∈B

where I and J are the sets of demand (population) and candidate points for defense system installation, respectively. Variable ai is the weight or demand for coverage (population density) at demand point i. Set xbj is the first set of decision variables that take the value of 1 if a facility of type b is located at candidate point j∈J, and 0 otherwise. Set ybi is another set of decision variables that take the value of 1 if demand at point i∈I receives coverage service from (or covered by) a nearby facility of type b and 0 otherwise. Set Nbi={j∈J|dij≤Sb} ∀ i∈I is the set of potential facility placement sites that fall within the (exogenous) maximum coverage distance Sb of demand point i, dij is the distance between a demand point i and candidate facility point j. In the same way, Nbj={i∈I|dij≤Sb} ∀ j∈J is the set of demand points that falls within the maximum coverage distance Sb of candidate facility point j.

The objective function maximizes the total demand-weighted population area for coverage. The constraint set (2) specifies that a demand point is considered covered by facility type b if at least one facility of that type is located within S units of distance from the demand point. The constraint set (3) ensures that a maximum number of p facilities of type b should be sited. The constraint set (4,5) imposes the non-overlapping requirement for the set of facilities to make sure that at most one facility among all facility types is located at an eligible site. The constraint set (6) imposes the non-overlapping requirement for each demand point to make sure that each demand point is not covered by more than one nearby facility (of any types). The constraint set (7) enforces the integrality condition.

Data description and processing

The data for our case study used in this analysis are gathered from different open-source geospatial and demographic databases from unclassified Canadian sources. The compiled data provide an approximation, but not an exact representation, of the distribution of population and critical infrastructure. Population estimates for each dissemination area are taken from Statistics Canada (2016a, b). There are millions of people and hundreds of valuable resources that must be covered. We utilized different open-source geographic and demographic information for Canadian cities/dissemination areas and merged and stacked them on different layers. Figure 1 is a representation of all critical infrastructure and population areas superimposed on the map of Canada. As we can see, the critical assets are distributed non-uniformly in continuous space throughout the country. By superimposing a grid over our continuous geographic area and representing each grid space by a point, we transformed our continuous data into discrete sets. Different grid size leads to different resolution, requiring different computation and storage requirements. We approach the problem at different resolution levels ranging from a low resolution to the highest possible resolution reasonably permitted by our computational resources. For instance, with a grid size of 25 km, our original data (in complete format) consists of up to 50,000 grid squares.

Solution

Proposed GA-based solution for the MMCLP

The GA is a bio-inspired population-based optimization method introduced by Holland (1992). The broad idea of a GA is to generate an initial population of solutions and then improve population fitness gradually using reproduction mechanisms, such as crossover and mutation through generations. In this study, we integrate local search and large neighborhood search strategies to mitigate the probability of premature convergence. The overall workflow of the GA-based solution of the MMCLP is presented in Figure 2. In what follows, we explain different steps of the solution algorithm.

Chromosome encoding and fitness computation

A potential solution for the MMCLP is the set of potential locations of size ∑b∈Bpb chosen out of the set of all candidate sites. Here a chromosome is a ∑b∈Bpb-tuple integer string {{t11,t21,...,tp11},{t12,t22,...,tp22},...,{t1b,t2b,...,tpbb}} of sub-chromosomes of length pb,b∈B, each representing the indices of candidate sites chosen as the placement sites for facility type b. A chromosome’s fitness represents the quality of the solution based on the values of the objective functions of the MMCLP. In other words, the fitness of a chromosome shows the amount of potential coverage that is achieved by the selected facility sites encoded in that chromosome.

Selection mechanism

In each iteration (generation) a set of individual solutions (also called parents) are entered into a mating pool and exchange their genetic information to create two offspring solutions. For the chromosome selection process we use a binary tournament selection process (Goldberg, 2002). In the binary tournament process two chromosomes are selected randomly from the population pool and put in the mating pool for the crossover operation.

Crossover and mutation operators

We use single-point crossover and bit string mutation operators in our GA-based solution. Figure 3 depicts the process of a single-point crossover operation and a bit string mutation. The crossover and mutation operations are controlled by crossover and mutation rate parameters to produce the child population with offspring solutions produced by crossover and mutation operations.

Local neighborhood search operator

Local neighborhood search is a chromosome refinement process under which a percentage of chromosomes (solutions) are locally perpetuated. The process of local improvement is such that one gene of a chromosome that represents a potential site is replaced randomly by one of its own neighborhood sites that are within the maximum coverage range. This refinement leads to a small perturbation on the fitness of the chromosome.

Large neighborhood search operator

Unlike the local neighborhood search, the large neighborhood search is a chromosome refinement process under which one of the chromosome’s genes is replaced randomly by a candidate site that is not within its neighborhood range. This leads to a larger perturbation on the chromosome fitness and may help escape local optima.

We note that there is a subtle difference between the mutation and local and large neighborhood search process such that in the mutation process a chromosome changes genetic information with that of another chromosome in the population. While in the local neighborhood search, a chromosome exchanges information within itself and in the large neighborhood search the chromosome changes information on a genetic level but not necessarily with itself nor with other chromosomes.

Termination criteria

The individual members of each population for a particular generation are evaluated based on a selection strategy (e.g. their fitness values) and then the best solutions are propagated to the next generation. This procedure is iterated until the termination criteria is met. Here we use the termination criterion based on the variance of the fitness values within each generation. Therefore, when the variance of the fitness in a generation falls below a specified threshold the GA-based solution procedure stops.

Numerical results

In this section, we perform a comprehensive numerical analysis to examine the performance of the proposed GA-based solution method and different search-space resolutions on the solution.

GA-related parameters (e.g. the size of population, the number of generations, the mutation and crossover rates, and the local and large neighborhood search rates) must be carefully decided to ensure solution convergence along with exploitation and exploration capabilities. The values of these parameters highly depend on the size of the problem (i.e. eligible facilities and maximum number of facilities to be open, the number of decision variables and constraints). Basu et al. (2015) conduct a detailed review of metaheuristic solutions on facility location problems. Their overview identified two distinct ways by which authors determined the size of the GA population: constant and varied. They identified cases of constant population size from 20 to 500. For the varied population size approach, they specified that the population size should be the maximum of either 75% of the number of grid squares, or 100. Genetic operators represent the algorithm’s exploitation and exploration capabilities and have a significant impact on algorithm performance. In the papers studied, they found that the crossover probability is typically much higher than the mutation probability. Specifically, they listed the value of these parameters for different location planning problems. According to Basu et al. (2015), a crossover rate in range (0.4, 0.6] and mutation rate in range (0.2,1.0] is commonly used by GAs for the MCLP problem and other location problems. We chose crossover and mutation probabilities as 0.4 and 0.2, which are within the proposed ranges.

The authors discuss three types of termination criteria: (TC1) maximum number of generations, (TC2) maximum number of generations without any improvement in the best solution value, and (TC3) execution time. This study used a new TC that uses TC1 along with a threshold for the variance of the fitness in a generation as a termination criterion. We set the variance threshold for our termination criteria to be 1×10−5, and maximum number of iterations to be 150 if the GA-based solution does not stop based on the variance criteria.

These parameter values are chosen based on initial experiments that showed them to be appropriate for any instance of the proposed problem.

Lastly, we selected parameter values for the local and large neighborhood search operators. These operators balance exploitation and exploration in the search. We set the exploitation to be twice the exploration rate at a fixed rate of 0.5, and the large neighborhood search rate at 0.25 to adhere to a similar ratio (0.5/.25 = 2) as in the crossover and mutation rates (0.4/0.2 = 2).

The experiments aim to evaluate the GA-based method with input data based on different grid size resolutions for Canada (see Figure 1). Eliminating areas with no population or critical assets helps reduce the complexity of the optimization model and allow it to be solvable with off-the-shelf solvers. These solutions served as benchmarks in low resolution instances of the optimization problem.

Results from the CPLEX commercial solver served as a benchmark to examine the effectiveness of solutions and the efficiency of computation time required for executing the GA algorithm compared to optimized solutions. We considered two facility types with an effective coverage range of 100  and 200 km, respectively. We varied the number of available facilities (p=p100 km=p200 km) of each type from 2 to 10 to see how the total coverage changed when adding more facilities. In the last part of our comparisons we show an instance of a solution obtained for a multi-type location problem. Each problem instance is solved 50 times. All algorithms and optimization processes are coded in Python. The optimization models were coded using the Pyomo package (Hart et al., 2011) and solved by invoking ILOG CPLEX 20.1.0.

Figure 4 depicts the solutions obtained for coverage for different problem instances when p varies from 2 to 10. The percentage of coverage is calculated based on the percentage of population coverage. As we can see the total coverage from both GA and CPLEX solutions increases as p increases. Overall, these results support the efficiency of the solutions obtained by the GA-based method and that the optimality gap decreases and solution consistency increases as the number of facilities to be built increases.

In terms of computational effort Figure 5 shows the higher efficiency of the GA-based solution strategy compared to CPLEX. The experiments with a grid size of 25 km show that the GA-based solution strategy is at least eight times faster than CPLEX.

Figure 6 depicts the solutions obtained at a higher resolution grid size of 10 km. At this resolution CPLEX was not able to handle the optimization problem due to running out of memory. Our analysis found that the optimization problem at 10 km resolution consists of over 9,900,000 non-zeros and over 28,000 constraints. However, the GA-based solution solved all the problem instances. The coverage from the GA-based solution is improved and in agreement with the solutions obtained from a lower resolution when the grid size is 25 km depicted in Figure 4. Similar to the results from our previous experiments, the results here also support the consistency of the solutions obtained by the GA-based method.

Figure 7 shows the performance of the GA-based solution strategy in terms of computational effort with regards to different p. These results confirm that as the problem size grows, due to increasing p, it takes more time for the GA-based solution to terminate with a solution. This can be attributed to the combinatorial nature of the problem. Overall, the experiments with a grid size of 10 km show that the GA-based solution strategy can be an alternative solution strategy when CPLEX cannot handle the solution due to limited computational resources.

These results support the effectiveness of the GA-based solution compared to CPLEX in handling large scale instances of the optimization problem. The experiments with grid size of 25 km shows that GA-based solutions are obtained at least 8 times faster than CPLEX. The comparison of results for the grid size of 10 km to those with a grid size of 25 km indicates that problem size and thus the solution time depends on the resolution level (grid size). Solution time is also dependent on other input parameters, such as number of available resources, that affect the length of the chromosomes in the GA-based solution. We observed that as the resolution level increases the GA-based solution strategy is not affected as much as CPLEX. We also note that in almost all of the test instances the GA stops in less than 150 iterations, which is the maximum iteration limit. This suggests that the variance-based termination criteria is an appropriate measure for the GA-based solution strategy while achieving objective values close enough to the optimal solution in these test instances.

To give an estimate about the sizes of the MMCLP instances solved in this paper, we note that ReVelle et al. (2008) define problems with 900 nodes (n=900), and 20 candidate locations (p=20) as the large instances of maximal covering location problems. Based on these values, we can say that our smallest problem instance includes n=2,756, and p=2,...,20, which is considerably larger than those instances defined in ReVelle et al. (2008). This can be verified as the MCLP can be defined as a simplified version of the MMCLP by setting |B|=1. Our higher resolution data (10 km grid size) is parameterized by n over 9,000 and p=2,...,20, which can be seen as very large-scale instance problem in comparison and according to the samples solved in Cordeau et al. (2019).

Finally, Figures 8 and 9 show a comparison of the solution from the GA-based method and CPLEX for a multi-type facility location problem. In these figures dashed circles represent the defensive covers. Here, we assume there are two types of facility, one with an effective coverage range of 100 km and another type with an effective coverage range of 200 km. We also assumed there are three facilities available of each type, i.e. p100=3 and p200=3. As we can see, the solution obtained by the GA (Figure 8) closely matches the solution from CPLEX (Figure 9). Both of the solutions provide about 90% coverage.

The behavior of the GA-based solution for this instance is illustrated in Figure 10. This figure shows how the GA-based solution continues to improve the fitness of the best and worst solutions as well as the mean (average) fitness within the population. This demonstrates how the variance-based termination criteria works in accordance with fitness convergence and makes the GA-based solution stop before it reaches the maximum number of iterations limit.

Conclusions

We studied the problem of optimally locating a suite of defense and deterrence systems over a vast geographic area. We presented a MMCLP problem and proposed a GA-based solution with local and large neighborhood solution refinement strategies. Our comprehensive experiments using realistic data supports the effectiveness and consistency of the GA-based solution method in providing high quality and fast solutions compared to the CPLEX commercial solver for small as well as medium instances of the problem. The CPLEX solution time in these instances is heavily dependent on the grid size and other input parameters such as the number of available resources. Conversely, the computational time of the GA-based solution is not significantly affected by increasing the resolution level. Our future research will be developing a multi-objective optimization model and examining Pareto-optimal solutions under two or more objectives with different solution methods. A game-theoretic approach can be used for the inclusion of uncertainty either in the probability of attack or in the probability of detection. The economic impact of hostile attacks can also be considered to make the solution applicable to real-life scenarios.

Figures

Figure 1

Population and critical infrastructure distribution of Canada

Figure 2

Steps of the proposed GA-based solution

Figure 3

Chromosome string representation, and crossover and mutation operations on candidate solutions

Figure 4

Maximum coverage as a function of different values of p for the GA-based solution, grid size = 25 km, and 50 runs per instance

Figure 5

CPU time (Sec) as a function of different values of p for solutions from CPLEX and GA-based methods, grid size = 25 km, with 50 runs per instance

Figure 6

Maximum coverage as a function of different values of p for solutions from the GA-based solution with a grid size of 10 km and 50 runs per instance

Figure 7

CPU time (Sec) as a function of different p for solutions from the GA-based method, using a grid size of 10 km and 50 runs per instance

Figure 8

Best solution identified using the proposed GA-based method using a grid size of 25 km; p100=3 and p200=3

Figure 9

Best solution identified using CPLEX, a grid size of 25 km; p100=3 and p200=3

Figure 10

Change of best, mean, worst fitness of the population as a function of generation and run time (p100=3; p200=3), and grid size = 25 km