A review of competitive facility location in the plane

The first modern paper on competitive facility location is generally agreed to be Hotelling’s [59] paper on duopoly in a linear market. Hotelling considered the location of two competing facilities on a segment (for example, vendors on Main Street). The distribution of buying power along the segment is assumed uniform, there is no price differential, and therefore consumers patronize the closest facility. When one facility is located and there is no competition, all consumers patronize the existing facility. However, when a competing facility is introduced and is located at a different point on the segment, the consumers on one side of the midpoint between the two facilities patronize one facility and the customers on the other side of the midpoint patronize the second facility. If one facility is held fixed in place, the best location for the second is either immediately left or right of the fixed one, depending on which segment—left or right of the existing facility—is longer. Drezner [41] analyzed the proximity model in the plane.

Hotelling [59] showed that when the two competitors charge the same price (they do not compete on prices), an equilibrium exists. However, when competitors can compete on price, no equilibrium exists. The existence of an equilibrium is discussed in the literature. For a discussion of the equilibrium issue, the reader is referred to the seminal paper by d’Aspremont et al. [15] and [89, 90].

The assumption that consumers patronize the facility closest to them implies that the competing facilities are equally attractive or that consumers consider only distance in their selection. For equally attractive facilities, the plane is partitioned by a Voronoi diagram [4, 67, 68] and the demand points in each polygon are attracted to the same facility. This, in turn, implies an “all or nothing” property. The combined buying power at a demand point is assigned entirely to one facility and none is assigned to other facilities, unless two or more facilities are equidistant. A solution procedure for solving the multiple competitive facility location in the plane is proposed in Suzuki et al. [83].

The proximity assumption is appropriate either for central planning where planners allocate demand to facilities, or for public facilities, or when consumers are highly price sensitive and will always select the cheapest option. However, when consumers select facilities to patronize on their own, they do not necessarily select by proximity. There are several reasons why not to use the proximity approach:

Deficiencies of the proximity approach

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 [16]. Hodgson [57] also suggested to incorporate attractiveness in the competitive location model. In the deterministic utility approach, we assume that all consumers residing at the same demand point apply the same utility. This assumption can be relaxed by stratifying the consumers residing at a demand point by categories, such as income, and defining these subgroups as different demand points located at the same location. Hotelling’s approach is extended by relaxing the proximity assumption. The proximity approach is a special case of the discrete utility approach when the utility function consists of distance only (in negative sign or a reciprocal of the distance). This generalization rectifies only deficiency #2 of the proximity approach in Sect. 2.1. Consumers are known to make their choice of a facility based on factors other than distance alone. This utility function is a composite index of facility attributes and the distance to the facility, representing the expected satisfaction from that facility (either an additive or a multiplicative utility function). It is generally agreed that consumers, through a decision-making process, choose the facility with the highest utility, the facility which is expected to maximize their satisfaction. This choice is determined by some formula according to which consumers evaluate alternative facilities’ attributes weighted by their personal salience to arrive at an overall facility attractiveness.

A trade-off between distance and attractiveness takes place. Based on this premise, the degree of expected satisfaction with each alternative as a function of the relevant characteristics of that facility is measured. 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 because of the value of travel time. For example, factory outlet centers at the fringe of the city which offer price discounts, or, in another context, paramedics transporting a motor vehicle accident victim will bypass a nearby hospital in favor of a farther, better equipped trauma center as long as the difference in quality of care exceeds the adverse effect to the patient caused by the extra distance and time delay. The attractiveness of a facility can be transformed into a distance markup. 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. All consumers at a demand point will patronize the new facility if it is located within the break-even distance. While consumers are no longer assumed to patronize the closest facility, consumers at a certain demand point are assumed to apply the same utility function; therefore, they all patronize the same facility. The “all or nothing” property is maintained in this extension.

To address the three deficiencies of the proximity assumption listed in Sect. 2.1, a random utility model was introduced by Leonardi and Tadei [64] and Drezner and Drezner [23]. 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. This formulation eliminates the “all or nothing” property since a probability that a consumer will patronize a particular facility can be established and is no longer either 0 or 100 %. To circumvent the mathematically complicated formulation of the random utility model, Drezner et al. [36] suggested using a simple S-shaped function. The utility declines very slowly for small distances, declines sharply for intermediate distances, and remains around zero for large distances.

Drezner et al. [38, 39] introduced the cover-based approach to estimating market share. Each competing facility has a “sphere of influence” [77] represented by a radius of influence which depends on the attractiveness of the facility. 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. [38], adding additional facilities of a given radius of influence is considered as an expansion strategy. In Drezner et al. [39], three 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. All these expansions have a defined cost and the best expansion strategy for a given budget is found. All three models are investigated in a unified approach. The authors are currently investigating the leader–follower model premised on the cover-based competitive location model.

The gravity approach also addresses the three deficiencies of the proximity approach listed in Sect. 2.1 and is more commonly used. Most competitive location problems in the plane have recently used gravity-based models. According to the gravity rule [76], 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. Evaluating market share based on the gravity approach was introduced by Huff [60, 61] and is used by marketers. Drezner [17, 18] was the first to introduce the gravity model to location analysis. Huff proposed that the probability that a consumer patronizes a retail facility (a mall) is proportional to its size (floor area) and inversely proportional to a power of the distance to it. Huff depicted equi-probability lines. A consumer located on such a line between two facilities patronizes the two facilities with equal probability. These equi-probability lines divide the region into catchment areas, each dominated by a facility, in a manner similar to the Voronoi diagram [68]. These lines do not define an “all or nothing” assignment of consumers to facilities, rather, 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, and thus, the best location for new facilities whose individual measures of attractiveness is known.

Suppose, there are k existing facilities and n demand points. The attractiveness of facility j is A _j for i = 1,…,k, and the distance between demand point i and facility j is d _ij . The buying power at demand point i is b _i . Therefore, the proportion of the buying power (market share) M _j attracted by facility j is: \( M_{j} = \mathop \sum \limits_{i = 1}^{n} b_{i} \frac{{{\raise0.7ex\hbox{${A_{j} }$} \!\mathord{\left/ {\vphantom {{A_{j} } {d_{ij}^{\lambda } }}}\right.\kern-0pt} \!\lower0.7ex\hbox{${d_{ij}^{\lambda } }$}}}}{{\mathop \sum \nolimits_{m = 1}^{k} \left( {{\raise0.7ex\hbox{${A_{m} }$} \!\mathord{\left/ {\vphantom {{A_{m} } {d_{im}^{\lambda } }}}\right.\kern-0pt} \!\lower0.7ex\hbox{${d_{im}^{\lambda } }$}}} \right)}} \) where λ is the power to which distances are raised. The gravity approach can be classified as a special case of the random utility approach as was done by Benati and Hansen [9] on the network. The utility is \( ln\left( {\frac{{A_{j} }}{{d_{ij}^{\lambda } }}} \right) + \varepsilon_{j} \) where ɛ _j is an iid distribution. The issue is also discussed in Anas [5]. The original gravity approach lacks theoretical underpinnings but estimates market share quite well in practice. The issue of existing substitutable alternatives is addressed in lost demand and market expansion models discussed in Sect. 4.6.

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 [66] 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. Each factor in the product is raised to a power. Thus, the attractiveness of a facility is a composite index of a set of attributes rather than the floor area alone. Nakanishi and Cooper’s idea was elaborated on and applied by Jain and Mahajan [62] to food retailing using specific attractiveness attributes. Gravity-based models suggest the evaluation of market share for a user-provided discrete set of potential sites for the location of a new facility.

The general model can be formulated as maximizing the market share captured using a distance decay function. The two most common distance decay functions are: \( \frac{1}{{ d^{\lambda } }} \) (the original decay function suggested by Huff) or e^−λd. Exponential decay [58, 87] was found by Drezner [20] to be empirically superior and has been recently used extensively (for example, Aboolian et al. [1, 2], Berman and Krass [10], Bozkaya et al. [13]).

Once buying power, distance, and attractiveness are known, market share can be calculated by the approaches discussed in Sect. 2.

Data about the following parameters are required in order to operationalize the models and evaluate the market share attracted by each facility:

Attractiveness levels: 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. Varying importance assigned to each of these attributes by different consumers will result in a selective set of consumers patronizing each facility. Assessing attractiveness levels is addressed in many marketing studies. Huff [60, 61] used floor area as a surrogate for attractiveness of shopping malls. Nakanishi and Cooper [66] proposed the MCI coefficient which is a product of attractiveness attributes. Commonly used attractiveness components of shopping malls are: (1) variety of stores, (2) appearance, (3) favorite brand names. Other techniques for inferring or deriving attractiveness levels were also proposed [20, 27].

Distance: 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 are: where α = 0.24 is recommended [24]. Plastria and Vanhaverbeke [72] addressed the issue of aggregation (see also [50] 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. A preprocessing aggregation method is presented to reduce the number of demand points which prevents this loss of information and therefore avoids the possible loss of optimality. This issue is related to the modifiable areal unit problem [69] which investigates the effect of the scale of the unit area on the optimal solution.

In this section, we briefly describe solution methods used for solving planar location problems based on the gravity model. Finding the best location for a new facility (or multiple facilities) in a continuous space using the gravity model objective is discussed in Drezner [17] and Drezner and Drezner [28] for the single-facility case, and in Drezner [19], Drezner et al. [34] and Toth et al. [85] for the location of multiple facilities.

An extension to Hotelling’s approach to the selection of sites for facilities that serve a spatially dispersed population is the location-allocation model Ghosh and Rushton [53]. Both the facilities’ locations and the allocation of consumers to them are determined simultaneously. The allocation of consumers to facilities is made using Hotelling’s proximity assumption—each facility attracts the consumers closest to it. The market share attracted by each facility is calculated, and the best locations for the new facilities are then found. Multi-facility location-allocation models analyze the system-wide interactions among all facilities.

Revelle [77] introduced location-allocation models to competitive location. Goodchild [54] suggested the location-allocation market share model. A retail firm is planning to open a chain of outlets in a market in which a competing chain already exists. The entering firm’s goal is to maximize the total market share captured by the entire chain. Most location-allocation solution methods rely on heuristic approaches that do not guarantee an optimal solution. Rather, they provide good solutions for implementation. The best locations are selected from a user-provided, pre-specified set of potential sites. Typically, these problems are formulated on a network and the location solution is on a node. A book edited by Ghosh and Rushton [53] provides a collection of papers on the subject. A comprehensive review of location-allocation models can be found in Ghosh and Harche [51].

Drezner [19] investigated the location of multiple competing facilities in an area where other facilities already exist. The budget for constructing new facilities is given and it is up to the planner’s discretion to allocate that budget among them. Both the optimal allocation of the budget among the new facilities and the best locations for them are found.

The optimal budget allocation among the new facilities depends on the functional relationship between the investment in a new facility and its attractiveness. It is assumed that an increase in the budget invested in a facility results in an increase in the attractiveness of that facility. This relationship is referred to as the investment-attractiveness curve. Such a curve can exhibit an increasing marginal return relationship (when the attractiveness as a function of investment increases in a faster than linear rate, which means that the curve is convex), a fixed marginal return (or in other words, a linear curve), or a decreasing marginal return one (when the curve is concave). As discussed in Quirk [75], in the first phases of a new firm, the return on investment typically exhibits an increasing marginal return. New entrants to a market dominated by large, mature competitors exhibit an increasing marginal return on attractiveness with an increase in budget. This means that with any additional funds invested in a facility, the increase in its attractiveness exceeds a linear rate. Mature, well established firms typically experience decreasing marginal returns on investment, that is, the rate of increase in attractiveness is slower than linear. Moderately established firms experience a linear relationship, or close to it. It is implicitly assumed that a positive relationship exists between facility attractiveness and market share, that is, an increase in attractiveness yields an increase in the market share captured. This provides an incentive to invest in a facility in order to increase its attractiveness.

Drezner [19] concludes with the following interesting and useful findings:

Constructing facilities on a network when facility attractiveness is a variable with a cost function depending on the attractiveness is termed “design”, leading to location models with design. Such a model was first proposed by Plastria and Carrizosa [72] suggesting a multitude of approaches for calculating the market share attracted by the facilities. Location of facilities on the nodes of a network was investigated in Aboolian et al. [2]. Such a model in the plane was analyzed in Fernandez et al. [47] and extended to sequential location of two facilities in Toth et al. [85].

Fernandez et al. [47] considered locating a single new facility in a planar market using the gravity model. Both the location and the attractiveness of the new facility are to be found so as to maximize the profit obtained by the chain. Several types of constraints and costs are considered. Two solution methods are developed and tested: The first is a repeated local optimization heuristic with locational constraints. The second is an exact global optimization technique using interval analysis, incorporating several novel features.

Toth et al. [85] analyzed the improvement in the quality of the solution when two facilities are located sequentially rather than simultaneously. They compare three different strategies: simultaneous location and independent design of two facilities in the plane, simultaneous location with equal designs, and the sequential approach of determining each facility in turn. The basic model is chain’s profit maximization, taking market share, location costs and design costs into account. The market share captured by each facility is calculated by the gravity model. Toth et al. [85] proposed an exact algorithm that finds optimal solutions for more than one facility. They developed an exact interval branch and bound algorithm to solve both simultaneous location and design two-facility problems.

Drezner [21] found the location of a new facility when future market conditions are unclear using the minimax regret objective. There are several defined scenarios concerning future market conditions:

The minimax regret objective is formulated and solved in two phases:

1) The best solution for each scenario is found,

2) The location problem with an objective of minimizing the maximum deviation from the best objective value is then solved.

Drezner et al. [35] discussed the location of a new retail facility. They propose a different objective function observing that there is a market share threshold to be captured, below which a firm will not survive. The appropriate objective function, then, is to minimize the probability that the firm will not achieve the threshold and thus will not survive. It follows that rather than locating a facility to maximize market share, a firm should locate so as to minimize the probability of falling short of obtaining this minimum threshold.

The problem is solved in the plane using the gravity model. The threshold optimal location tends to be different from the location at which the expected market share is maximized. For a set of test problems, it was found that the location is different especially when the probability of failure to obtain the threshold is relatively low (<50 %). When the probability of failure is low, the firm should concentrate on minimizing the variance thus reducing the uncertainty. This may yield a location in a different region of the market area. When the probability of failure is high (50 % or more), the company should concentrate on maximizing the expected market share and locate close to the location at which the market share is maximized.

Blanquero et al. [12] considered the objective of robustness that is defined as the extent to which the system is able to carry out its functions despite some damage done to it, such as the removal of some of the nodes and/or links in a network. The robustness objective is to minimize the probability of not meeting a threshold. The best location for a facility is found by applying the Big Triangle Small Triangle technique proposed in Drezner and Suzuki [43].

Most competitive facility location models discussed above (with the exception of location under conditions of uncertainty) attempt to find the optimal location for a new facility (facilities) by maximizing current market share against existing competition without considering future changes in the competitive environment. A different approach to competitive location focuses on anticipating and preempting future competition. It is assumed that a new competing facility (the follower) will enter the market at some point in the future. The competitor will establish his facility at the location which maximizes his market share. Therefore, one’s (the leader’s) present location decision will affect the competitor’s location decision. Conversely, a future competitive entry has implications for one’s (the leader’s) present location decision. The objective is to find the location that maximizes the market share captured by one’s own facility (the leader’s) following the competitor’s entry. This problem is known in the economic literature as the Stackelberg equilibrium problem or the leader–follower problem and as the Simpson’s problem in voting theory [79, 81, 82]. Drezner [41] analyzed the problem in the plane. Drezner and Zemel [45] showed that the solution for uniform continuous demand in the whole plane is to arrange the leader’s facilities in an hexagonal pattern. Drezner and Drezner [25] solved this problem in the plane heuristically applying the gravity model.

Such models are usually very difficult to solve. The value of the leader’s objective function can be calculated for a given location if the follower’s best location can be calculated. If the follower’s optimal location cannot be guaranteed, the objective function is not well-defined. Drezner and Drezner [25] proposed three heuristic algorithms for the solution of the single-facility location problem (for both the leader and the follower) in the plane.

The discrete version of the problem is analyzed in Plastria and Vanhaverbeke [74]. They considered the location of facilities under a budget constraint in order to maximize the remaining market share after the competitor’s later entry. They considered three strategies: the maximin strategy when a follower’s location choice is considered the worst for the leader, the minimax regret strategy, and the Stackelberg strategy in which the competitor also optimizes his market share. They developed mixed zero–one programming formulations for the solution of these models.

All models discussed above, with the exception of the cover-based competitive model [38, 39], assume that the entire demand is distributed among the competing facilities. For non-essential services, some of the demand may not be satisfied. A model assuming that some of the demand is lost is proposed in Drezner and Drezner [31]. If there is no nearby facility to patronize, consumers may use alternative products or alternative means to obtain the product. Consumers may resort to the Internet rather than drive to a far facility, consumers may decide to eat at home rather than drive to a far restaurant or rent a movie rather than drive to a theater.

Drezner and Drezner [31] proposed that the probability of patronizing a facility declines exponentially with the distance. Therefore, the probability of not patronizing any facility is the product of the probabilities of not patronizing each facility.

Drezner and Drezner [33] suggested defining a competing dummy facility at a reasonable distance from all demand points (no physical location is assumed) that attracts all lost demand. This simple scheme can be used to model and solve any “standard” competitive model by adding one additional competitor dummy facility.

The lost demand in the network environment was addressed in Aboolian et al. [2] and Berman and Krass [10]. It is called in these papers market expansion. It views recovering lost demand as an expansion of the attracted buying power [47, 72, 85].

Drezner et al. [37] analyzed the consistency of consumers’ facility choice. They suggested two consistency rules:

In the figure below, the inferior facility B attracts all demand points inside the small circle. All consumers residing in the shaded area are originally attracted to the more attractive facility A. However, when consumers follow the inconsistent rule, they enter the small circle on the way to facility A and once inside the small circle change their mind and patronize facility B.

When consumers’ choice follows the inconsistent rule, Drezner et al. [37] conclude that:

Drezner et al. [37] analyzed the issue by applying the deterministic utility approach.

The first paper on the subject is by Ghosh and Craig [52] who investigated it in discrete space. Plastria [71] and Drezner [22] solved it in the plane.

Cannibalization occurs at the retail level of chain facilities (fast food, hotels), especially in the case of franchises. In this form of cannibalization, opening a new retail outlet in close proximity to an existing outlet, the new facility cannibalizes the sales of the existing one. With the growth of franchise operations, this emerges as an important and timely issue. For as long as companies wish to grow and expand, managers will be faced with the strategic decision of optimally locating new, additional facilities such that cannibalization of existing chain members is minimized.

Plastria [71] applied the proximity approach. The market share is maximized in the intersection of circles which is usually an area. Plastria [71] found the point in the area where cannibalization is minimized. Drezner [22] analyzed maximizing market share while minimizing cannibalization using the gravity model. An efficient frontier depicting the trade-offs of these two non-compatible objectives is constructed and illustrated on an example problem.

Most multiple facility location models assume that each consumer patronizes the closest facility. While gravity models are prevalent in competitive facility location, it may well be appropriate to apply the gravity approach to other location models. This opens a new array of possible models that can be more realistic than models based on proximity. Several location problems were already analyzed using the gravity approach for consumer choice:

Gravity hub: Drezner and Drezner [26] suggested that consumers apply the gravity approach when deciding which airline route to select from a list of routes, each using one hub. The total distance through the hub is the basis for the gravity approach.

Gravity p-Median: Drezner and Drezner [30] analyzed the p-median model with the stipulation that consumers at each demand point do not necessarily patronize the closest facility. Planar Gravity p-Median and Minimum Variance: Drezner and Drezner [29] considered the p-median in the plane and minimized the variance of loads using the gravity approach.

Gravity Multiple Server: Drezner and Drezner [32] proposed models for locating facilities and service providers to serve a set of demand points. The number of facilities is unknown. However, there is a given number of servers (such as automatic teller machines) to be distributed among the facilities. Each facility acts as an M/M/k queuing system. The objective function is the minimization of the combined travel time and waiting time at the facility for all consumers.

There are many more non-competitive location models that can be analyzed by applying the gravity approach rather than the proximity approach yet to be formulated and analyzed.