Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Facility location models deal, for the most part, with the location of plants, warehouses, distribution centers and other industrial facilities [38, 57, 70, 73, 100, 105]. In this chapter we review the game theoretical concept of the leader-follower in two facilities location models which addresses specific circumstances: the competitive facility location problem and the defensive maximal covering location model on a network. A framework of facility location models that can be investigated in a game theoretical environment is depicted in Fig. 1. The models reviewed in this chapter are marked in boldface italics. Four reliable competitive models (on the plane or network) and one unreliable model on a network with the cover objective are investigated.

Fig. 1
figure 1

A framework of common facility location models

Full size image

There are two well researched two players’ games: Nash equilibrium [108] and the leader-follower game also termed the von-Stackelberg equilibrium [136] which in voting theory is known as Simpson’s problem [131]. In the Nash equilibrium game no player can improve his objective when the other player does not change his strategy. In many cases no equilibrium exists. In the leader-follower game the leader adopts a strategy and the follower adopts his best strategy knowing the leader’s strategy. The follower’s goal is to maximize his objective function while the leader’s goal is to maximize his objective function following the follower’s action.

Early contributions to Nash equilibrium location problems include Hotelling [92], Lerner and Singer [103], Eaton and Lipsey [66], Wendell and McKelvey [146]. The leader-follower location problem was introduced by Hakimi [84], and published in Hakimi [85–87], for location on network nodes using the Hotelling [92] premise that each customer patronizes the closest facility. See also Hansen and Labbè [88].

We first provide an overview the covering and competitive facility location models, and models addressing the location of unreliable facilities. We then review five different leader-follower models:

  • Competitive location of two facilities (leader and follower) anywhere on the plane [33]. The proximity rule is assumed.

  • Covering a large area by chain facilities so that a future competitor will not be able to attract much demand [59]. The proximity rule is assumed.

  • Competitive location of two facilities (leader and follower) applying the gravity (Huff) rule [47].

  • Competitive location of multiple facilities (leader’s and follower’s) using the cover-based rule [65].

  • Locating facilities on the nodes of a network to cover as much demand as possible following a disruption of a link by a follower [16].

2 Overview of Covering Models

There are two basic types of covering models: set covering and max-covering. In the set covering model the entire demand is to be covered with the minimum number of facilities [124]. In the max-covering model the objective is to cover as much demand as possible with a given number of facilities [24, 27, 98].

Many extensions to the two basic covering models were proposed. Some papers investigate the hierarchical covering problem where a set of different possible radii is given and the two possible objectives apply [23]. A hierarchy of objectives is considered by Daskin and Stern [31]. The max-covering problem with variable radii is investigated in Berman et al. [18]. The expected maximal covering problem is investigated in Daskin [29], Batta et al. [6], Tavakkoli-Mogahddam et al. [142].

Another stream of research is the gradual covering problem. In one version of the problem the demand covered is a decreasing stepwise function of the radius [12]. In another version there is a minimum and maximum covering distance. The demand is fully covered within the minimum distance and is not covered at all beyond the maximum distance. Between these two distances the coverage is gradually declining either linearly or otherwise [14, 61]. In Drezner et al. [61] the single facility case in the plane using Euclidean distances is optimally solved. The stochastic gradual covering problem is investigated in Drezner et al. [62] and the multiple facilities gradual cover with the maximin objective is investigated in Drezner and Drezner [55].

Carrizosa and Plastria [22] and Plastria and Carrizosa [115] studied covering problems with varying radii. They developed the efficient frontier between the covering radius and the maximal cover with that radius.

Berman et al. [19, 20], Averbakh et al. [5] investigated the cooperative covering location problem. Each facility emits a (possibly non-physical) “signal” which decays over the distance and each demand point receives the aggregate signal emitted by all facilities. A demand point is considered covered if its aggregate signal exceeds a given threshold. Facilities cooperate to provide coverage, compared to the classical coverage location model where coverage is only provided by the closest facility. Examples include: locating warning sirens, heaters or fans in restaurants, light posts in parking lots.

For recent reviews of covering models see Schilling et al. [128], Daskin [30], Current et al. [27], Plastria [114], Snyder [132], García and Marín [76].

3 Overview of Competitive Facility Location Problems

Typical location models do not account for competition or for differences among facilities therefore allocate consumers to facilities by proximity. In reality, retail facilities operate in a competitive environment with an objective of profit and market share maximization. The basic problem is the optimal location of one or more new facilities in a market where competition already exists or will exist in the future. When the budget invested in expanding market share is fixed, profit increases when market share increases, thus maximizing profit is equivalent to maximizing market share. For a discussion of the equivalence of maximization of profit and maximization of market share see Dasci and Laporte [28], Jensen [96], Winerfert [148]. It follows, then, that the location objective is to locate the retail outlet at the location which maximizes its market share. Recent reviews of competitive location models are Berman et al. [17], Drezner [41, 44], Eiselt et al. [71].

Competitive location models are investigated in planar continuous space and in discrete space, in particular in a network environment. Continuous models seek the location of facilities anywhere in the plane thus there is an infinite number of potential locations for the facilities. Discrete models restrict the location of facilities to a pre-specified set of potential locations, typically the nodes of a network.

Most models assume that all the buying power is distributed among the competing facilities. Lost demand is addressed in [2, 11, 52, 54, 63–65, 120].

The underlying theme of competitive models is the existence of an interrelationship among four variables: buying power (demand), distance, facility attractiveness, and market share, with the first three variables being the independent variables and the market share the dependent variable. Many rules were proposed for formulating this relationship:

  • Proximity [92].

  • Minimum Utility [35, 90].

  • Random Utility [45, 102].

  • Cover-based [63, 64].

  • Gravity (Huff) Model [93, 94].

3.1 The Proximity Rule

Hotelling [92] analyzed location on a line assuming that each consumer patronizes the closest facility. Eiselt [67] and Eiselt and Laporte [69] extended the model to a tree environment. Hotelling [92] showed that when two competitors charge the same price (they do not compete on price) an equilibrium exists. However, when competitors can compete on price, no equilibrium exists. For a discussion of the equilibrium issue the reader is referred to the seminal paper by d’Aspremont et al. [32] and Wong and Yang [150], Yang and Wong [152], Eiselt [68].

3.2 The Minimum Utility Rule

When the facilities are not equally attractive, the proximity premise for allocating consumers to facilities is no longer valid. To account for variations in facility attractiveness, a deterministic utility approach was introduced by Drezner [35]. Hodgson [90] also suggested to incorporate attractiveness in the competitive location model. A trade-off between distance and attractiveness takes place. It is suggested that a consumer will patronize a better and farther facility as long as the extra distance to it does not exceed its attractiveness advantage [35]. The attractiveness of a facility can be transformed into a distance mark-up. A break-even distance is defined. At the break-even distance the attractiveness of two competing facilities is equal. This break-even distance, therefore, is the maximum distance that a consumer will be willing to travel to a farther facility (new or existing) based on his perception of its attractiveness and advantage relative to other facilities.

3.3 The Random Utility Rule

A random utility model was introduced by Leonardi and Tadei [102] and Drezner and Drezner [45]. The deterministic utility model is extended by assuming that each consumer draws his utility from a random distribution of utility functions. The probability that a consumer will prefer a certain facility over all other facilities is calculated by applying the multivariate normal distribution. Once the probabilities are calculated, the market share captured by a certain facility (new or existing) can be calculated as a weighted sum of the buying power at all demand points. To circumvent the mathematically complicated formulation of the random utility model, Drezner et al. [60] suggested using a simple S-shaped function. The utility declines very slowly for short distances, declines sharply for intermediate distances, and remains around zero for large distances.

3.4 The Cover-Based Rule

Drezner et al. [63, 64] introduced the cover-based approach to estimating market share. Each competing facility has a “sphere of influence” [123] represented by a radius of influence which depends on the facility’s attractiveness. A consumer at a distance within the radius of influence is attracted to the facility. Consumers’ demand within the sphere of influence of no facility is lost. In Drezner et al. [63] adding additional facilities of a given radius of influence is considered an expansion strategy. In Drezner et al. [64] three market expansion models are analyzed: (1) increasing the radius of influence of existing facilities thereby increasing their attractiveness, (2) adding new facilities (and determining the radius of influence of each), and (3) a combination of both.

3.5 The Gravity (Huff) Rule

The gravity approach is the most commonly used model in recent papers. According to the gravity rule [122] two cities attract retail trade from an intermediate town in direct proportion to the populations of the two cities and in inverse proportion to the square of the distances from them to the intermediate town. Drezner [36, 37] was the first to introduce the gravity model to location analysis. Evaluating market share based on the gravity rule was introduced by Huff [93, 94] and is used by marketers. Huff proposed that the probability a consumer patronizes a retail facility is proportional to its size (floor area) and inversely proportional to a power of the distance to it. At any demand point, the proportion of consumers attracted to each facility is a function of the facility’s square footage (attractiveness) and distance. The model finds the market share captured at each potential site, thereby the best location for new facilities whose individual measures of attractiveness are known.

In the original Huff formulation, facility floor area serves as a surrogate for attractiveness. An improvement on Huff’s approach was suggested by Nakanishi and Cooper [107], Jain and Mahajan [95] who introduced the multiplicative competitive interaction (MCI) model. The MCI coefficient replaces the floor area with a product of factors, each a component of attractiveness.

In the gravity model a distance decay function f(d) is defined. It represents the decline in facility attractiveness as a function of the distance from the facility and thus the probability that a consumer patronizes that facility. In the original gravity model [122], it is assumed that the distance decay parallels the gravity decay and thus \(f(d) = \frac{1} {d^{2}}\). Huff [93, 94] suggested a decay function of \(f(d) = \frac{1} {d^{\lambda }}\) where the power λ depends on retail category. λ = 3 was found for grocery stores [94], λ = 3. 191 for clothing stores [93], λ = 2. 723 for furniture stores [93], and λ = 1. 27 for shopping malls [40, 49]. Wilson [147] suggested an exponential decay e −λ d which was used in many subsequent papers [1–3, 52, 91]. Drezner [40] compared power and exponential decay on a real data set of shopping malls in Orange County, California and found that exponential decay fits the data better than power decay. The decay function \(f(d) = e^{-1.705d^{0.409} }\) was used in Bell et al. [9] who investigated grocery stores. A Logit function \(f(d) = \frac{1} {1+e^{\alpha +\beta d+\gamma d^{2}}}\) was used in Drezner et al. [60]. Goodchild and Noronha [81] applied gravity based models to the location of gas stations, and Drezner [43] applied them to the hotel industry.

There are other location models that apply the gravity rule to various objectives. This is the appropriate approach if demand is not necessarily satisfied by the closest facility because the assignment of demand is not centralized. Examples:

  • In the hub location problem [21], a set of hubs needs to be selected from a list of airports so that flyers change planes at a hub on the way to their destination. It is reasonable to assume that customers do not necessarily select the hub that yields the shortest total distance to their destination. The total distance is used in the gravity rule to assess the probability that customers select a particular hub [48].

  • In the p-median problem [82, 83], p facilities are to be located such that each demand point gets its services from the closest facility with the objective of minimizing the total weighted distances for all demand points. When the assumption that each customer gets his service from the closest facility is replaced by the gravity rule we obtain the gravity p-median problem [51]. The planar version of this problem is proposed and analyzed in Drezner and Drezner  [50].

  • The multiple server location problem [10] combines travel time and service time at servers using M/M/k queueing systems. A given number of servers are to be located at nodes of a network. Demand for these servers is generated at each node, and a subset of nodes needs to be selected for locating one or more servers in each. Each customer at a node selects the closest server. The objective is to minimize the sum of travel time and the average time spent at the server, for all customers. The gravity multiple server problem is defined when customers do not necessarily use the server with the shortest travel time plus service time [53].

3.6 Implementation Issues

Once buying power, distance, and attractiveness are known, market share can be calculated by any of the approaches discussed above.

Buying power (demand), sometimes referred to as purchasing power, is available in secondary data sources. Geographic information systems data bases, such as those provided by ESRI,Footnote 1 also have data about buying power.

Facility attractiveness is assessed using one of a variety of methods. The attractiveness of a facility is a composite index of a set of attributes. Examples of attractiveness components of shopping malls are: (1) floor area (2) variety of stores, (3) appearance, (4) favorite brand names. Other techniques for inferring or deriving attractiveness levels were proposed in Drezner [40], Drezner and Drezner [49].

The distance between two points can be easily measured. However, since demand points represent areas, the distance correction for an area A and distance d is \(\sqrt{d^{2 } +\alpha A}\) where α = 0. 24 is recommended by Drezner and Drezner [46].

Plastria and Vanhaverbeke [117], Francis et al. [74] addressed the issue of aggregation and its effect on the optimality of the location solution. Demand points often have to be aggregated due to computational intractability. However, this spatial aggregation typically introduces a bias to the value of the objective function thus the optimality of the solution cannot be guaranteed.

3.7 Extensions

Many extensions to the basic model were suggested. The following two extensions are incorporated in this chapter.

Budget Constraints: :

Combining the location decision with facility design (treating the attractiveness level of the facility as a variable) was recently investigated in [1, 39, 63, 64, 72, 116, 119, 144]. Drezner [39] assumed that facilities attractiveness levels are variables. In that paper it is assumed that a budget is available for locating new facilities and for establishing their attractiveness levels. One needs to determine the facilities attractiveness levels so that the available budget is not exceeded. Plastria and Vanhaverbeke [118] combined the limited budget model with the leader-follower model. Aboolian et al. [1] studied the problem of simultaneously finding the number of facilities, their respective locations and attractiveness (design) levels.

Leader-Follower: :

The leader-follower model [136] considers a competitor’s reaction to the leader’s action. The leader decides to expand his chain. The follower is aware of the action taken by the leader and expands his facilities to maximize his own market share. The leader’s objective becomes maximizing his market share following the follower’s reaction [33, 47, 99, 118, 119, 121, 125, 126].

4 Leader-Follower Models in Competitive Models

In this section we review four leader-follower models in a competitive environment.

4.1 The Leader-Follower Model Locating Two Facilities in the Plane

Drezner [33] analyzed two competitive location models in the plane. One is the location of a new facility that will attract the most buying power from an existing facility (the follower’s problem). The other is the location of a facility that will secure the most buying power against the best location of a competing facility to be set up in the future (the leader’s problem). The proximity rule using Euclidean distances is assumed.

Let n demand points be located on the plane. A weight, or buying power, b i  > 0 is associated with demand point i for i = 1, …, n. The leader locates his facility at X and the follower locates his facility at Y. Customers will patronize the follower’s facility Y if the Euclidean distance between the customer and Y is less than the distance between the customer and X. Two problems are considered:

Problem 1 (the follower’s problem): :

Given the location of an existing facility X serving the demand points, find a location for a new facility Y that will attract the most buying power from demand points.

Problem 2 (the leader’s problem): :

Find a location for X such that it will retain the most buying power against the best possible location for the follower’s facility Y.

For given locations X and Y, the distribution of the buying power can be found by constructing the perpendicular bisector to the segment connecting X and Y. This perpendicular bisector divides the plane into two half-planes. All points in the closed half-plane which includes X (including points on the perpendicular bisector itself) will patronize X and all the points in the other open half-plane which includes Y, will patronize Y. This is a generalization of Hotelling’s analysis on a line [92].

It is shown in Drezner [33] that one of the optimal locations for Y when X is given is infinitesimally close to X but not on X. It follows that a solution to Problem 1, Y ∗, is ‘adjacent’ (close) to X. The variable yet to be determined is the direction in which Y is ‘touching’ X. In conclusion, finding an optimal location for Y is equivalent to finding the best line through X such that the open half plane defined by this line contains the most buying power for Y. Finding the best line by simple enumeration is detailed in Drezner [33].

The algorithm that solves Problem 2 is based on the algorithm used for solving Problem 1. It can be found whether attracting a certain market share P 0 or higher by Y is possible by finding whether there is a feasible solution to a linear program. The algorithm is based on a bisection on the value of P 0. Complete details are given in Drezner [33].

  1. 1.

    Calculate all \(\frac{1} {2}n(n - 1)\) lines through pairs of points and find the market share P i for each open half-plane defined by the lines.

  2. 2.

    Sort P i in decreasing order. Set P min and P max to the smallest and largest P i , respectively.

  3. 3.

    Set P 0 to the median value in the P i vector for all P min < P i  < P max. If the set P min < P i  < P max is empty go to Step 7.

  4. 4.

    Find if there is a feasible point to all half-planes for which P i  ≥ P 0. This can be done by linear programming.

  5. 5.

    If there is a feasible solution point to the linear program then set P max to P 0 and go to Step 3.

  6. 6.

    Otherwise, set P min to P 0 and go to Step 3.

  7. 7.

    A feasible location for the last P max is an optimal solution. The value of the objective function is P min.

The two problems can be modified by an extra restriction that the follower cannot construct his facility closer than a given distance R from the leader’s facility. To solve the modified Problem 1 for a given X it can be shown that the best solution for Y is determined by open half planes defined by tangent lines to the circle centered at X with a radius of \(\frac{1} {2}R\) rather than lines through X. The details of the algorithms for solving the modified Problems 1 and 2 are available in Drezner [33].

4.2 A Leader-Follower Model for Covering a Large Area with Numerous Facilities

Drezner and Zemel [59] considered the following problem: a large number of customers are spread uniformly over a given region \(A \subseteq \mathbb{R}^{2}\). What configuration of facilities that cover the area will best protect against a future competing facility? The proximity rule is assumed. Each customer patronizes the closest facility.

Drezner and Zemel [59] found the solution to the problem of covering the whole \(\mathbb{R}^{2}\) plane. Then they analyzed the finite area problem and found bounds on the difference between the configurations as the number of facilities increases.

There are three evenly spread configurations that cover the whole \(\mathbb{R}^{2}\) plane with equilateral polygons depicted in Fig. 2: a triangular grid where facilities are located at the centers of equilateral triangles; a square grid where facilities are located at the centers of squares; and an hexagonal grid (beehive) where facilities are located at the centers of hexagons. No other cover of the plane by identical equilateral polygons exists.

Fig. 2
figure 2

Various configurations

Full size image

Since customers are attracted to the closest facility, the market share captured by each facility is proportional to the area attracted to the closest facility. This is similar to the Voronoi diagram concept [113, 140, 145]. In the configurations depicted in Fig. 2, the market share attracted by each facility is the area of the polygon. Let A be the area attracted by each facility. It is shown in Drezner and Zemel [59] that:

  • For the triangular grid the competitor’s facility can attract a maximum of \(\frac{2} {3}A = 0.6667A\). The best location for the follower is at a vertex of a triangle (see Fig. 2).

  • For a square grid the competitor’s facility can attract a maximum of \(\frac{9} {16}A = 0.5625A\). The best location for the competitor is at the center of the side of the square.

  • For an hexagonal grid the competitor’s facility can attract a maximum of 0. 5127A, i.e., 51.27% of the leader facility’s market share. All regions inside the equilateral triangles with the leader’s facilities at its vertices (see Fig. 2) are equivalent. Also, because of symmetry, the market share at any location, except at the center of the triangle, has two more equivalent locations. The best locations for the follower inside such triangles are depicted in Fig. 3. The minimum market share of half the area of the hexagon is captured by the follower at the three vertices of the triangle and at its center. The factor 0.512713 has a contrived formula developed in Drezner and Zemel [59]: Define \(\theta = \frac{1} {3}\arctan \frac{9\sqrt{1077}} {347}\); \(\alpha = \frac{1} {9}\left (16 -\sqrt{94}(\cos \theta +\sqrt{3}\sin \theta )\right )\); then the factor is: \(\frac{1} {2} + \frac{\alpha (2-3\alpha )^{2}} {24(1-\alpha )(2-\alpha )}\). The follower’s facility location in Fig. 3 is on the line connecting the vertex of the triangle and its center. Its distance from the leader’s facility is α = 0. 2955766 times the distance between the vertex and the center of the triangle or \(\frac{2} {3}\alpha\) of the triangle’s height.

    Fig. 3
    figure 3

    Best follower’s locations

    Full size image

The hexagonal pattern provides the best protection from a future competitor. It is interesting that for hexagonal and square grids the competitor captures at least half of A at any point in the plane.

Hexagonal pattern is optimal for many location problems with numerous facilities covering a large area. For example:

  • packing the most number of circles in an area [26, 89, 141],

  • p-median [112], p-center [138] and p-cover [58],

  • p-dispersion [56, 104, 106, 109],

  • equalizing the load covered by facilities [139].

It is also the preferred arrangement for a bee-hive in nature which has developed over the years in the evolutionary process.

4.3 The Leader-Follower Problem Using the Gravity (Huff) Rule

It is assumed that a new competing facility will enter the market at some point in the future. The competitor will establish his facility at the location which maximizes his market share given the leader’s location. The leader’s objective is to find the location that maximizes the market share captured by his facility following the competitor’s entry [47]. Ghosh and Craig [77] solved a similar problem by discretizing all variables and assuming a given set of possible locations for both the entrant and the future competitor. They formulated the problem as an integer programming problem which limits the solution procedure to relatively small problems. We briefly summarize the results in Drezner and Drezner [47]. For complete information the reader is referred to that paper.

4.3.1 Calculating the Market Share

Drezner and Drezner [47] applied a power distance decay function as suggested by Huff [93, 94]. As described in Sect. 3, other distance decay functions were also investigated in the literature. The notation is depicted in Table 1.

Table 1 Notation for gravity (Huff) based models
Full size table

The market share captured by the leader’s new facility as a function of X and U using the gravity model, M 1(X, U), is:

$$\displaystyle{ M_{1}(X,U)\ =\ \sum _{i=1}^{n}b_{ i}\ \frac{ \frac{S} {d_{i}^{\lambda }(X)}} { \frac{S} {d_{i}^{\lambda }(X)}\ +\ \frac{C} {d_{i}^{\lambda }(U)}\ +\ \sum _{j=1}^{k} \frac{S_{j}} {d_{ij}^{\lambda }}} }$$
(1)

The market share captured by the follower’s facility as a function of X and U, M 2(X, U), is:

$$\displaystyle{ M_{2}(X,U)\ =\ \sum _{i=1}^{n}b_{ i}\ \frac{ \frac{C} {d_{i}^{\lambda }(U)}} { \frac{S} {d_{i}^{\lambda }(X)}\ +\ \frac{C} {d_{i}^{\lambda }(U)}\ +\ \sum _{j=1}^{k} \frac{S_{j}} {d_{ij}^{\lambda }}} }$$
(2)

4.3.2 The Optimization

The leader’s objective is to maximize his market share M 1(X, U) in the long run by selecting the best location X, taking into consideration that the follower selects its location U so as to maximize his market share M 2(X, U). The best location for the follower, U, is a function of the leader’s selected location X. In a mathematical formulation, for a given X, let U(X) be the maximizer of M 2(X, U). The leader’s objective is converted to:

$$\displaystyle\begin{array}{rcl} & & \max \limits _{X}\{\ M_{1}(X,U(X))\ \} \\ \text{subject to:}& & U(X)\text{ is the maximizer of }M_{2}(X,U){}\end{array}$$
(3)

The leader-follower problem (3) is a complicated problem. The functions M 1(X, U) and M 2(X, U) are not concave and may have many local maxima. The problem may have many local maxima. The constraint of (3) is unusual and cannot be formulated into a mathematical programming formulation. Such a constraint is not in the form of an equality or an inequality.

Drezner and Drezner [47] proposed three heuristic approaches for finding a good solution: brute force, pseudo mathematical programming, and gradient search.

The Brute Force Approach: :

A grid of locations X that cover the area is generated. For each location X the value of U(X) is found and the value of M 1(X, U(X)) is calculated. If the grid is dense enough, the vicinity of the global maximum can be identified. If a more precise location is sought, a finer grid can be evaluated in that vicinity.

The Pseudo Mathematical Programming Approach: :

If the functions M 1(X, U) and M 2(X, U) were concave, the following mathematical programming formulation (termed the “pseudo” problem) would have solved the problem:

$$\displaystyle\begin{array}{rcl} & \max \limits _{X,U}\{\ M_{1}(X,U)\ \} & \\ \text{subject to:}& & \\ & \frac{\partial } {\partial U}M_{2}(X,U)\ =\ 0& {}\end{array}$$
(4)
The Gradient Search Approach: :

A gradient search that directly finds a local maximum for the leader-follower problem (3) is suggested. It guarantees termination at a local maximum of problem (3) once U(X) can be found. It is recommended that this procedure is repeated many times in order to have a reasonable chance of “landing” at the global optimum.

4.3.3 Computational Experiments

Two sets of problems were tested. The first one (problem 1) consists of 100 demand points evenly distributed in a 10 by 10 miles area, each with buying power of “1” for a total buying power of 100. There are seven existing facilities in the area, each of an attractiveness level of “1” (equally attractive). The data are given in [35–37] and are depicted in Fig. 4. The attractiveness of both one’s new facility and the future competing facility are also equal to one.

Fig. 4
figure 4

Problem 1

Full size image

As explained in Drezner and Drezner [46], the accuracy of the market share estimate is enhanced by replacing the square of the distance d 2 with d 2 +α A where A is the estimated area represented by a demand point. This “distance correction” compensates for the fact that demand points are not mathematical points and if, for example, a facility is located on a demand point, not all customers at that demand point are at distance zero from the facility. It provides for the averaging of the distance between all customers assigned to a demand point and the facility. A distance correction factor of α A = 0. 24 was used, because the area surrounding a demand point is A = 1, as suggested in Drezner and Drezner [46].

The second problem (Problem 2) applies real data. It is based on sixteen communities in Orange County, California, and six existing major shopping malls. The data are given in Table 2. The total buying power for this problem is 1346.5. Both the leader’s new facility and the follower’s facility have an attractiveness of 5. The distance correction factor [47] is α A = 1 because the demand points are farther apart than in Problem 1.

Table 2 Data for problem 2
Full size table

The results reported in Drezner and Drezner [47] indicate that local maxima of problem (3) are encountered more frequently by the gradient search approach than by the pseudo mathematical programming approach. The gradient search approach is recommended as the approach of choice for solving the problem. The pseudo mathematical programming approach is recommended for users who do not wish to code a special program but rather use standard software. The brute force approach is recommended if the value of the market share captured as a function of location is of value to the user.

The sensitivity analysis reported in Drezner and Drezner [47] indicates that the increase in captured market share, compared with the market share at the location that does not anticipate a follower’s reaction, increases as competitor’s attractiveness increases. In Problem 1 there is a clear shift in location as the attractiveness of the competitor reaches 3.0. The additional market share, using the leader-follower model, reaches an increase of 22.7% in market share. The gain in market share is more modest when solving Problem 2. For an attractiveness of 50, the gain is only 2.4% and the best location does not change significantly. We conclude that in some problems the model significantly improves the location, and therefore the market share captured, when compared with the model that does not consider a follower, and in some problems the improvement is not as significant.

4.4 The Leader-Follower Model Using the Cover-Based Rule

Drezner et al. [65] investigated a leader-follower (Stackelberg equilibrium) competitive location model incorporating facilities’ attractiveness (design) subject to limited budgets for both the leader and follower. The competitive model is based on the concept of cover [63, 64]. The leader and the follower, each has a budget to be spent on the expansion of their chains either by improving their existing facilities or constructing new ones. We are interested in the best strategy for the leader assuming that the follower, knowing the action taken by the leader, will react by investing his budget to maximize his market share. The objective of the leader is to maximize his market share following the follower’s reaction.

4.4.1 Estimating Market Share

The cover-based competitive location model [63, 64] is applied for estimating market share. Each facility has a sphere of influence (catchment area) for patronage defined by a distance termed “radius of influence”. Consumers patronize a facility if they are located within the facility’s radius of influence. More attractive facilities have a larger radius of influence, thus they attract consumers from greater distances. Demand at demand points which are not attracted by any facility is lost. When the total captured market share is estimated, it is assumed that if a consumer is attracted to more than one facility, his buying power is equally divided between the attracting facilities.

Models based on this rule are simpler to implement than those based on the gravity rule or the utility-based rule. One only needs to estimate the catchment area of competing facilities which yields their radius of influence. There are established methods for estimating the radius of influence of a facility [8, 143]. For example, license plates of cars in the parking lot are recorded and the addresses of the cars’ owners obtained. Drezner [40] conducted interviews with consumers patronizing different shopping malls asking them to provide the zip code of their residence and whether they came from home.

The location of p new facilities with a given radius is sought so as to maximize the market share captured by one’s chain. In Drezner et al. [64], three strategies were investigated: In the improvement strategy (IMP) only the improvement of existing chain facilities is considered; in the construction strategy (NEW) only the construction of new facilities is considered; and in the joint strategy (JNT) both improvement of existing chain facilities and construction of new facilities are considered. All three strategies are treated in a unified model by assigning a radius of zero to potential locations of new facilities.

The leader employs one of the three strategies and the follower also implements one of these three strategies. This setting gives rise to nine possible models. Each model is a combination of the strategy employed by the leader and the strategy employed by the follower. For example, the leader employs the JNT model, i.e., considers both improving existing facilities and establishing new ones, while the follower employs the IMP model, i.e., only considers the improvement of his existing facilities. The most logical model is to employ for both the leader and the follower the JNT strategy which yields the highest market share. However, constructing new facilities or improving existing ones may not be a feasible option for the leader or the follower.

The set of potential locations for the facilities is discrete. The notation is given in Table 3.

Table 3 Notation for cover based models
Full size table

Note that the radii r j are continuous variables. However, it is sufficient to consider a finite number of radii in order to find the optimal solution. Consider the sorted vector of distances between facility j and all n demand points. A radius between two consecutive distances covers the same demand points as does the radius equal to the shorter of the two distances yielding the same value of the objective function. Since the improvement cost is an increasing function of the radius, an optimal solution exists for radii that are equal to a distance to a demand point.

For demand point i, the numbers L i and F i can be calculated by counting the number of leader’s facilities that cover demand point i, and the number of follower’s facilities that cover it. For a given strategy R = { r j },   j = 1, …, p we define these values as L i (R) and F i (R). The objective functions for the leader and the follower, before locating new facilities, are:

$$\displaystyle{ MS_{L}(R) =\sum \limits _{ i=1}^{n}b_{ i} \frac{L_{i}(R)} {L_{i}(R) + F_{i}(R)}, }$$
(5)
$$\displaystyle{ MS_{F}(R) =\sum \limits _{ i=1}^{n}b_{ i} \frac{F_{i}(R)} {L_{i}(R) + F_{i}(R)}. }$$
(6)

Note that if F i (R) = L i (R) = 0, then in (5) \(\frac{L_{i}(R)} {L_{i}(R)+F_{i}(R)} = 0\), in (6) \(\frac{F_{i}(R)} {L_{i}(R)(F_{i}(R)} = 0\) and the demand b i associated with demand point i is lost.

Suppose the leader improves some of his facilities and establishes new ones. Note that F i (R) does not depend on the actions taken by the leader. The follower’s problem is thus well-defined following the leader’s action and can be optimally solved by the branch and bound algorithm detailed in Drezner et al. [64].

Once the follower’s optimal location is known, the leader’s objective function is well defined as his market share is calculated by (5) incorporating changes to the follower’s locations and radii.

The leader and follower cannot exceed their respective budgets. For a combined strategy R = { r j } by both competitors the constraints are:

$$\displaystyle{ \sum \limits _{j\in P_{L}}C(r_{j}) \leq B_{L};\ \ \ \sum \limits _{j\in P_{F}}C(r_{j}) \leq B_{F}. }$$
(7)

Once the leader’s strategy is known and thus L i  = L i (R) are defined, the follower’s problem is:

$$\displaystyle\begin{array}{rcl} & & \max \limits _{r_{j},\ j\in P_{F}}\left \{\sum \limits _{i=1}^{n}b_{ i} \frac{F_{i}(R)} {L_{i} + F_{i}(R)}\right \} \\ \text{Subject to:}& & \\ & & \sum \limits _{j\in P_{F}}C(r_{j}) \leq B_{F}. {}\end{array}$$
(8)

The leader’s problem needs to be formulated as a bi-level programming model [75, 137]:

$$\displaystyle\begin{array}{rcl} & & \max \limits _{r_{j},\ j\in P_{L}}\left \{\sum \limits _{i=1}^{n}b_{ i} \frac{L_{i}(R)} {F_{i}(R) + L_{i}(R)}\right \} \\ \text{Subject to:}& & \\ & & \sum \limits _{j\in P_{L}}C(r_{j}) \leq B_{L} \\ & & r_{j}\text{ for }j \in P_{F} = arg\left [\begin{array}{l} \max \limits _{r_{j},\ j\in P_{F}}\left \{\sum \limits _{i=1}^{n}b_{i} \frac{F_{i}(R)} {F_{i}(R)+L_{i}(R)}\right \} \\ \text{subject to:}\sum \limits _{j\in P_{F}}C(r_{j}) \leq B_{F}. \end{array} \right ]{}\end{array}$$
(9)

Note that the follower’s problem may have several optimal solutions (each resulting in a different leader’s objective) and the leader does not know which of these the follower will select. This issue exists in all leader-follower models.

The follower’s problems are identical to the three problems analyzed in [64] because market conditions are fully known to the follower. A branch and bound algorithm as well as a tabu search [78–80] were proposed in Drezner et al. [64] for the solution of each of these three strategies. For details the reader is referred to Drezner et al. [64, 65].

4.4.2 Computational Experiments

Drezner et al. [65] experimented with the 40 Beasley [7] problem instances designed for testing p-median algorithms. The problems range between 100 ≤ n ≤ 900 nodes. The number of new facilities for these problems was ignored. The leader’s facilities are located on the first ten nodes and the follower’s facilities are located on the next 10 nodes. The problems are those tested in [64]. The demand at node i is 1∕i (for testing problems with no reaction by the follower) and the cost function is f(r) = r 2. The same radius of influence was used for the existing leader’s and follower’s facilities. When new facilities can be added (Strategies NEW and JNT), n − 10 nodes are candidate locations for the new facilities (nodes that occupy one’s facilities are not candidates for new facilities) and are assigned a radius of 0. r 0 j = 20, and S j  = 0 were applied for expanding existing facilities and the same S j  > 0 were used for establishing any new facility.

A branch and bound optimal algorithm was used to solve the follower’s location problem. Since it is used numerous times in the solution procedure for the leader’s location problem, a budget of 1500 and a set-up cost of 500 were applied to both the leader and the follower. Both the leader and the follower apply the JNT strategy. Tabu search, which does not guarantee optimality, is used to solve the leader’s location problem. Therefore, the solution of each problem instance was repeated for at least 20 times to assess the quality of the tabu search solutions. Problems with up to 400 demand points were solved in reasonable run times.

The experiments conducted in Drezner et al. [65] are:

  • Solving the leader’s location problem when the follower does not react and does not change his facilities. This is performed by the branch and bound rigorous algorithm. When solving the leader-follower problem, this algorithm is performed to find the follower’s optimal location solution and consequently the leader’s objective function. As expected, one’s chain market share increases and the competitor’s market share declines. Some of the increase in the leader’s market share comes at the expense of the competitor and some comes from capturing demand that is presently lost. It is interesting that the proportion of the additional market share gained from the competitor remains almost constant for all budgets tested. The average for all 40 problems is 44.2% for a budget of 1500, 44.2% for a budget of 2000, 44.9% for a budget of 2500, and 46.7% for a budget of 5000. A larger percentage of market share gained comes from lost demand. These percentages are the complements of the percentages gained form competitors or about 55%.

  • The tabu search procedure for finding the leader’s best solution after the follower’s reaction was coded in C#. Its effectiveness was first tested by optimally solving 160 JNT instances (40 instances for each budget), i.e., assuming no follower’s reaction. The tabu search found optimal solutions to 148 out of 160 instances and sub-optimal solutions (avg. error: 0.11%, max error: 0.41%) to the remaining 12 instances. It is also observed that, for the budget of 1500, only one instance was not optimally solved by tabu search and the error was 0.04%. In the subsequent experiments, a budget of 1500 was used.

  • The leader’s location solution was extended by adding the branch and bound procedure (the follower’s solution) to the tabu search. First, the original Fortran code was recoded statement-for-statement in C# and tested on several JNT instances. It was discovered that it took the C# implementation 10 times longer to find the solution to the follower’s problem than the Fortran implementation. This inefficiency was likely caused by pointer arrays used in C#.

  • The branch and bound procedure was coded in.NET’s C++ language using native C++ arrays. This new implementation was two times slower than its Fortran counterpart. Because the branch and bound procedure is called for each tabu search move, the very efficient Fortran code was compiled to a Digital Link Library (DLL) and was called from the C# code using the.NET inter-operability technology.

  • The original parameters used for solving the leader’s problem (\(b_{i} = \frac{1} {i}\)) did not provide interesting results because the weights declined as the index of the demand point increased and thus both the leader and the follower concentrated their effort on attracting demand from demand points with a low index (high b i ) and “ignored” demand points with higher indices. Therefore, equal weights of “1” were assigned to all demand points. A budget of 1500 and a set-up cost of 500 for both the leader and the follower were used.

Twenty Beasley [7] problem instances with n ≤ 400 demand points were tested. For 13 instances all results are the same and therefore the minimum and average are 100%. On average, the market share was 99.67% of the best obtained market share and the minimum market share was 98.80% of the best one. The average standard deviation was 0.50%. The numerical simulation experiments were run in parallel as 24 separate threads distributed on 24 virtual CPU cores and four different 64-bit Windows servers. Each server was equipped with 12 to 32 GB RAM and each virtual CPU was approximately equivalent to an Intel Xeon 2 GHz physical processor. These virtual CPUs are on a “cloud” and many applications are executed on them simultaneously by many users. Applications are migrated from one physical CPU to another by the central operating system. Total run time by the “cloud” computers was about 16 months with a maximum of about 2 months for one particular problem.

It was found that the leader has a slight advantage over the follower. The leader’s market share increased by an average of 14.80% while the follower’s market share increased by 13.95%. However, this difference is not statistically significant. The leader’s market share as a percentage of his original market share increased by 84.07% while the follower’s increase was only 73.43%. This difference is also not significant.

When the leader takes no action he loses 3.29% of his market share while the follower gains 24.68%. The lost demand (demand not served by either the leader or the follower) also decreases by either action. It drops by 21.4% when the leader takes no action but drops by 28.75% when both the leader and the follower expand. By investing in expanding their chains, the leader attracts 14.80% of the lost demand while the follower attracts 13.95% of the lost demand. Lost demand was reduced on the average by 48.1% of its value prior to the leader’s and follower’s expansions. The leader and the follower may have attracted demand from one another but these exchanges cancel out. The main source of extra market share for both the leader and the follower was obtained by attracting new consumers that did not patronize any facility prior to the expansion.

Finally, the leader’s market share results found by tabu search were compared with a pure random search [153] for the leader’s strategy. The budget was allocated to some facilities by the JNT strategy. The follower’s problem is then optimally solved by the branch and bound algorithm. The procedure is repeated the same number of times that the follower’s problem was solved in the tabu search and the best leader’s market share selected. For example, in the tabu search the first problem required about 4490 solutions of the follower’s problem in each of the 100 replications. For this problem 449,000 random allocations of the budget by the leader were tested.

The results were quite surprising. For example, for the second problem the best increase in market share found by tabu search is 7 units from 18 to 25. However, the best pure random search increase is only 4 units (from 18 to 22) which is only 57.1% of the potential market share increase. The results indicate that if the leader uses his budget at random, he gets poor results even when such random allocation is repeated hundreds of thousands of times and the best “lucky” result selected! This clearly shows the value of the approach suggested in Drezner et al. [65].

5 Overview of Models Addressing the Location of Unreliable Facilities

The issue of unreliable facilities or inoperable links on the network is discussed in many papers. Wollmer [149] and Wood [151] considered the possibility that some links of the network can be destroyed. Their objective is to maximize the network flow following the loss of some links. It does not involve facility location. Location of unreliable facilities was first introduced by Drezner [34] and extended by Lee [101], Berman et al. [13], Snyder and Daskin [133], Shishebori et al. [130], Shishebori and Babadi [129]. If the closest facility is out of service, then users get their service from the second closest facility. The location of unreliable facilities on a network when the reliability of service declines with the distance from the facility is discussed in Berman et al. [13]. Church and Scaparra [25], Scaparra and Church [127] proposed a model based on the p-median objective. They assume that some of the facilities may be destroyed and a budget is available to protect several facilities. O’Hanley et al. [111] and O’Hanley and Church [110] also suggest models in which one or more facilities are destroyed retaining maximal cover. For a review of unreliable location models the reader is referred to Scaparra and Church [127], Snyder and Daskin [134], Snyder et al. [135], An et al. [4].

6 The Defensive Maximal Covering Location Problem

The defensive maximal covering location model [16] is a leader-follower game theoretic model [87, 136]. The leader locates p facilities on some nodes of a network and at some point in the future a terrorist (the follower) removes one of the links of the network. The follower’s objective is to remove the link that causes the most damage. The leader’s objective is to cover the most demand following a link removal. The model can also be applied to an accident or a natural disaster.

If the disaster is a terrorist attack, it is likely that they will sever the most damaging link. If a link becomes unusable by accident, the leader would like to “protect” himself against the worst possible scenario. This is reminiscent of the minimax regret concept in decision analysis. In both cases, the leader’s goal is to maximize coverage following the removal of the most damaging link.

The model suggested in Berman et al. [16] is based on demand coverage. For an overview of covering models see Sect. 2. The model is related to location models of unreliable facilities (see an overview in Sect. 5) and can be classified in this category.

We summarize the main results reported in Berman et al. [16]. For complete details the reader is referred to that paper.

The follower’s problem is optimally solved while the leader’s problem is solved heuristically. Consider a leader’s action locating p facilities on a set of p nodes. To solve the follower’s (attacker’s) problem one needs to find the link whose removal will inflict the maximum decline in coverage. Let F j be the number of facilities that cover node j when links are intact, and F j k be the number of facilities that cover node j following the removal of link k.

By removing link k, the follower may either remove the cover of node j or not. Clearly F j k ≤ F j . There are four possibilities:

  • F j  > 0, F j k > 0 no damage;

  • F j  > 0, F j k = 0 lose node j (damage);

  • F j  = 0, F j k = 0 no damage;

  • F j  = 0, F j k > 0 impossible since F j k ≤ F j .

Node j loses its cover if and only if F j  > 0 and F j k = 0. F j is a known number independent of k. Therefore, if F j  = 0 no damage can be done to node j because it is not covered before a removal of a link and can be removed from the follower’s problem. The follower’s problem is solved by efficiently checking the damage for every removed link and selecting the maximum damage rather than solving an integer programming formulation. It is shown in Berman et al. [16] that all links longer than the covering radius can be eliminated from the original problem.

6.1 Properties of the Problem on a Tree

If the network is a tree, some additional properties can be used in the solution approaches. All links longer than the covering radius can be removed from the tree. Each such removal breaks the tree into two sub-trees. It is clear that if K links are removed, there are K + 1 disjoint sub-trees. It is shown in Berman et al. [16] that on a tree network, in each direct path the only links that are candidates for removal are links that are adjacent to a facility. In conclusion, for a path network at most 2p links are candidates for attack by the follower.

There are other reduction schemes on a path between two facilities. When a direct path connects two facilities, if the distance between each of the end-nodes of a direct path and the node adjacent to the other end-node does not exceed the covering radius, then the whole direct path can be eliminated from consideration by the follower.

6.2 Heuristic Algorithms for the Solution of the Leader’s Location Problem

Solving the integer programming formulation for reasonably sized problems requires too much computational effort. Therefore, it is recommended to apply heuristic algorithms in order to solve moderately large problems. Three heuristic algorithms are designed and tested in Berman et al. [16]:

Ascent Algorithm :

A set P of p nodes is randomly selected for locating the p facilities. The objective function is the total cover following the follower’s move. All possible exchanges between a node in P and a node not in P are evaluated. If an improved exchange is found, the best improved exchange is performed and the next iteration starts. The algorithm terminates when no improving exchange is found. Each iteration requires p(n − p) solutions to follower’s problems, each taking O(n 3 m) time for a complexity of O(n 3 mp(n − p)).

Simulated Annealing :

The simulated annealing [97] simulates the cooling process of hot melted metals. A starting solution is generated, its value of the objective function F is calculated, and the temperature T is set to T 0. The following is repeated for I iterations:

  • The solution is randomly perturbed by removing one facility and replacing it with a non-selected facility. The change in the value of the objective function Δ F is calculated.

  • If Δ F ≥ 0 the search moves to the perturbed solution. If Δ F < 0 the search moves to the perturbed solution with probability \(e^{\frac{\varDelta F} {T} }\). Otherwise, the search stays at the same solution.

  • If the search moves to the perturbed solution, F is changed to the perturbed value of the objective function.

  • The time T is changed to α T.

The best encountered solution during the process (usually the last solution) is the result of the algorithm.

Berman et al. [16] followed the approach adopted in Berman et al. [15]. Three parameters are required for the implementation of the simulated annealing algorithm. In Berman et al. [16] the following parameters were used: the starting temperature T 0 = 10, the number of iterations I = 500p(n − p), and the factor \(\alpha = 1 -\frac{5} {I}\). By this selection of α, the last temperature is \(T_{0}(1 -\frac{5} {I})^{I} \approx T_{ 0}e^{-5} \approx 0.0067T_{ 0} = 0.067\).

Tabu Search :

Tabu search [78–80] proceeds from the ascent algorithm’s terminal solution by allowing downward moves, hoping to obtain a better solution in subsequent iterations. A tabu list of forbidden moves is maintained. Tabu moves stay in the tabu list for tabu tenure iterations. To avoid cycling, the forbidden moves are the reverse of recent moves. If a move leads to a better solution than the best solution found so far, this move is executed and the tabu list is emptied. If none of the moves leads to a better solution than the best found solution, the best permissible move (disregarding moves in the tabu list), whether improving or not, is executed.

Each move involves removing a node in P and substituting it with a node not in P. The tabu list consists of nodes recently removed from P so they are not allowed to re-enter P. The maximum possible number of entries in the tabu list is n − p. The tabu tenure is randomly generated each iteration between 0. 1(n − p) and 0. 5(n − p). Let h be the number of iterations by the ascent algorithm. The tabu algorithm is run for an additional 9h iterations.

The easiest way to handle the tabu list is to create a list of all nodes and for each node to store the iteration number at which it entered the tabu list. Emptying the tabu list means assigning a large negative number to every node. A node is in the tabu list if and only if the difference between the current iteration number and the iteration value in the tabu list does not exceed the tabu tenure. This way the length of the tabu list is changing every iteration according to the randomly generated tabu tenure.

6.2.1 Breaking Ties

A useful “trick” for the ascent and tabu algorithms is designed to break ties in the best move. This can be useful in other algorithms for other problems as well. Consider a stream of events (for example a move tying the best move found so far) received over time. It is not known how many events will occur. One event needs to be randomly selected, with equal probability for each event, as a “winner”. It is inconvenient to store the list of all events. Thus, the winner cannot be selected at the end of the process.

Drezner [42] suggested the following simple approach: the first event is selected. When the kth event is encountered, it replaces the selected event with a probability of \(\frac{1} {k}\). It is shown in Drezner [42] that at the end of the process every event is selected with the same probability. This “trick” simplifies programming algorithms, such as ascent or tabu search, when the events are moves tying for the best one. There is no need to store all tying moves in order to randomly select one.

6.3 Computational Experiments

The three heuristic algorithms were tested on the 40 Beasley [7] problems designed for testing algorithms for the solution of p-median problems. Each problem was solved 100 times by the ascent algorithm and 10 times by simulated annealing and tabu search starting with randomly generated starting solutions leading to similar run times.

We found from the computational results that:

  • The ascent algorithm found the best known solution (BK) at least once for 28 of the 40 problems, the tabu search found it in 31 of the 40 problems, while the simulated annealing algorithm found it for all 40 problems. For the 12 problems for which the ascent algorithm did not find the best known solution, the best found solution was, on the average, 1.09% below the best known solution. For the 9 problems for which the tabu search did not find the best known solution, the best found solution was, on the average, 0.50% below the best known solution.

  • The ascent algorithm found the BK 33.6% of the 4000 runs, the tabu search found it 56.5% of the 400 runs, while the simulated annealing algorithm found it 83.5% of the 400 runs.

  • The average solution of the ascent algorithm was 1.25% below the BK, the tabu search average was 0.34% below the BK, while the average solution of the simulated annealing algorithm was 0.13% below the BK.

  • Running 10 replications of the simulated annealing was faster, on the average, than running 100 replications of the ascent algorithm and 10 replications of tabu search.

6.3.1 In Conclusion

  • The simulated annealing algorithm performed better than the ascent algorithm and the tabu search.

  • The tabu search performed better than the ascent algorithm in a slightly shorter run time.

  • The ascent algorithm may be useful for solving large problems for which only one run can be afforded. In such a case, even one run of the simulated annealing or tabu search may take too long.

  • The advantage of the simulated annealing over the ascent algorithm and the tabu search is pronounced for larger values of p. For p = 5 problems, one hundred runs of the ascent algorithm require about the same time as one run of the simulated annealing, and the average result is quite comparable (of course, the best result among the 100 runs of the ascent algorithm is better than one run of the simulated annealing). One may consider the ascent approach for small values of p.

7 Summary

The leader-follower model in the context of facility location is an interesting extension to many practical location problems. Four different competitive location models and one defensive maximal covering location model are reviewed.

Many other location problems can be extended to a leader-follower framework and investigating such problems may yield interesting and useful results. For example, the variations of covering objectives in Sect. 2 suggest a plethora of defensive maximal covering location models for future investigation: hierarchical covering [23], variable radii [18], gradual cover [12, 14, 61, 62], cooperative cover [5, 19, 20].

The thirty models (five objectives, each in one of the three environments, and facilities can be reliable or unreliable) depicted in Fig. 1 can also be investigated using a game theoretic framework. For example, unreliable minisum facility location on the sphere (the follower destroys a facility) can be applied in this context and is worth exploring. There are other competitive location models that can be investigated as a leader-follower game. For example, the random utility model [36, 45, 102].