Keywords

1 Introduction

Facility location analysis is one of the most well-studied areas of the operations research. In the basic model, there is a predefined cost for opening a facility and also connecting a customer to a facility, the goal is to minimize the total cost.

The typical facility location problem assumes that the locating facility is either a price taker or a monopolist, so that the market competition is neglected among the companies. However this simplified assumption does not fit in most real-life situations and the need arises to incorporate competition among the decision-makers. Indeed, competitive location models additionally incorporate the fact that location decisions have been or will be made by independent decision-makers who will subsequently compete with one another for market share, profit maximization, etc. In addition, the assignment of customers being served by these facilities and how these facilities are connected with each other are interesting decisions considered within the problem.

It is widely accepted that the competitive location analysis was initiated by Hotelling [14]. In his two ice cream vendors game, he examined location policies of an interdependently acting duopoly in a linear market of a given length. The distribution of buying power along the line segment is assumed uniform. Each customer has an inelastic demand for the good and pays the transportation cost of obtaining the good. Therefore, he patronizes the nearest facility in order to minimize his expenditures. He proved that a “back to back” location in the middle of the market constitutes a long-run equilibrium. Since then, a vast number of publications have been devoted to the subject. Thus, different classification efforts with respect to multiple components have been proposed in the literature, see for example, [9, 10, 19, 27] among others. Spatial representation and the nature of competition are some of them.

The classification based on the spatial representation classifies the CFL models into three broad categories: (a) Continuous models, where the potential location of the facilities can be anywhere in the plane, (b) Discrete models, where facilities are allowed to locate at a finite set of possible locations, and (c) network models, where any point on a network is suitable for location. From the optimization point of view, the techniques used to cope with the problems also differ. Continuous location problems are, for most of the cases, nonlinear optimization problems, while discrete and network location problems are integer programming/combinatorial optimization problems.

When the nature of competition is used as a classification method then again three different classes of problems can be identified. (a) Static problems, which assume that a firm enters into a market, where operate same existing firms, aiming at choosing the location of p facilities such as to attract the maximum market share. The new competitor enters into the market by having full and in advance information about the characteristics and the strategies of the existing firm (s). It is assumed further that this information is fixed and no reaction is expected from the existing competitor(s). When the assumption of the non reacting competitors is eliminated, two new classes of CLF arise, (b) dynamic and (c) sequential location problems. The competing firms make a location decision simultaneously in the first case, whereas there is a hierarchy in the decision-making process in the second. The sequential location completion is mainly formulated as a Stackelberg-type game. On the other hand, in simultaneous location games, the Nash equilibrium constitutes the solution of the problem.

In this work we focus on discrete bi-level CFL problems. Our aim is to provide an up to date review of modeling and optimization approaches used in the bibliography. Moreover, we develop a new bi-level methodology for this type of problem.

2 Sequential Deterministic Facility Location Problems

The formalization of this class of problems and fundamental complexity results were established by Hakimi [11]. Following the game introduced by von Stackelberg [30] Hakimi [11] presented the two basic problems in the sequential location analysis, the centroid and medianoid problems. These two problems are faced by the leader and the follower, respectively. The leader attempts to locate p ≥ 1 facilities knowing that the follower will in turn locate his r ≥ 1 facilities based on the leader’s chosen location; this is the (r|p)-centroid problem. The follower knows the set X p that indicates where the leader’s facilities are located and solves an (r|X p )-medianoid problem. Customers choose among the facilities according to a function of the distance between them and the facilities, preferring always the closest. This is the so-called binary customer choice. The formulation of the problems is based on the assumption that co-location is not allowed and if, by any chance, the distance from a customer to the closest facility of the two competitors is the same, the customer always prefers the leader’s facility. The demand of the customer is also considered to be inelastic with respect to distance travelled.

Given the set I of m potential facilities location and J the set of n customers locations, let x ij defines the distance between customer j and facility i. It is assumed further that w j is the weight (profit, demand, etc.) of customer j.

If X and Y denote the location occupied by the leader and the follower, respectively, and d(j,X) and d(j,Y) the distance between customer j and his nearest facility from X and Y, respectively, then customer j will prefer Y over X if d(j,Y) < d(j,X) and he prefers X over Y otherwise. If \(J(Y \prec X)\) is the set of customers who prefer Y over X then \(W(Y \prec X) =\sum _{j\in J(Y \prec X)}w_{j}\) denotes the total weight of the customers who prefer Y over X.

For each X the follower’s strategy is the set of other location Y that provides the maximal market share, W ∗(X), to him. This maximal market share is obtained by solving the following problem:

$$\displaystyle{ \max _{Y,\vert Y \vert =r}W(Y \prec X). }$$
(1)

The leader on the other hand is interested in maximizing his own market share. Thus, his optimal location strategy X ∗ is the one that minimizes the follower’s market share. Therefore, the leader’s maximal market share is obtained by solving the following problem:

$$\displaystyle{ \min _{X,\vert X\vert =p}\ \ \max _{Y,\vert Y \vert =r}W(Y \prec X). }$$
(2)

Hakimi [12] extended the initial formulation of the problem by considering elastic demand and different customer choice rules, apart from the binary choice rule, such as partially binary choice and the proportional preference choice of the customers. Under the partially binary choice the customer uses the closest facility of each firm. Under the proportional choice the customer proportionally distributes his demand among the operating facilities. He came up with six different scenarios and he stated several vertex optimality results. Particularly, he proved the existence of a nodal solution for the partially binary problem, under both inelastic and elastic demands. He proved also that a nodal solution exists in the proportional choice-elastic demand case only if the demand captured by the facilities is a linear function of the distance. Suárez-Vega et al. [28] extended his result by considering a concave function of the demand capture.

A 3-level formulation for both leader’s and follower’s problem and a heuristic solution procedure based on the elimination procedure in a candidate list are proposed in [6]. They formulated the problem as a three-stage optimization process which included the customer selection problem, the follower location problem, and the leader location problem. The corresponding problem, (r|p)-centroid problem, with inelastic demand is as follows:

$$\displaystyle\begin{array}{rcl} & \max & \sum _{i=1}^{m}\left [\sum _{ k=1}^{n}h_{ k}z_{ki}\right ]x_{i}{}\end{array}$$
(3)
$$\displaystyle\begin{array}{rcl} & s.t& \sum _{i=1}^{m}x_{ i} = p{}\end{array}$$
(4)
$$\displaystyle\begin{array}{rcl} & & x_{i} \in \{ 0,1\},i \in [1,\ldots,m]{}\end{array}$$
(5)

where z solves

$$\displaystyle\begin{array}{rcl} & CUS(x,y)& \min \sum _{k=1}^{n}\sum _{ i=1}^{m}d_{ ki}h_{k}z_{ki}{}\end{array}$$
(6)
$$\displaystyle\begin{array}{rcl} & & st\ \sum _{i=1}^{m}z_{ ki} = 1,k \in [1,\ldots,n]{}\end{array}$$
(7)
$$\displaystyle\begin{array}{rcl} & & z_{ki} \leq \bar{ x_{i}} +\bar{ y_{i}},k \in [1,\ldots,n],i \in [1,\ldots,m]{}\end{array}$$
(8)
$$\displaystyle\begin{array}{rcl} & & z_{ki} \in \{ 0,1\},k \in [1,\ldots,n],i \in [1,\ldots,m]{}\end{array}$$
(9)

where y solves

$$\displaystyle\begin{array}{rcl} & FLO_{r}& \max \sum _{i=1}^{m}\sum _{ k=1}^{n}h_{ k}z_{ik}{}\end{array}$$
(10)
$$\displaystyle\begin{array}{rcl} & & st\ \sum _{i=1}^{m}y_{ i} = r,{}\end{array}$$
(11)
$$\displaystyle\begin{array}{rcl} & & \sum _{i=1}^{m}z_{ ki} \leq 1,k \in [1,\ldots,n]{}\end{array}$$
(12)
$$\displaystyle\begin{array}{rcl} & & z_{ki} - c_{ki}y_{i} \leq 0,k \in [1,\ldots,n],i \in [1,\ldots,m]{}\end{array}$$
(13)
$$\displaystyle\begin{array}{rcl} & & z_{ki},y_{i} \in \{ 0,1\},k \in [1,\ldots,n],i \in [1,\ldots,m]{}\end{array}$$
(14)

In the above model m is the number of possible facility locations and n is the number of customer locations. d ki = d(c k ,f i ) is the distance between the kth customer location c k and the ith facility point f i . h k is the total demand of the customers located at c k . A set z of location points is identified by a binary vector \(z = (z_{i}: i \in [1,\ldots,m])\) where z i = 1 if f i ∈ z and z i = 0 if f i ∉Z. The decision variables in the leader and follower location problems are the m-vectors x and y of 0 − 1 or binary decision variables corresponding to sets X and Y. z ki is the 0–1 decision variables indicating whether the customers located at the k customer location c k prefer the location f i for the facility and c ki = 1 if \(d_{ki} <\min \{ d_{kj}\bar{x_{j}} = 1\}\). The CUS(x,y) is the customer selection problem. The objective function of this problem represents the total distance travelled by the customers to arrive at the corresponding facility points. The constraints state that each customer has to go to one location in the leader location set or in the follower location set. FLO r corresponds to the follower’s location problem. Campos Rodríguez et al. [6], based on the observation that the mathematical programming formulation of the minimax problem that corresponds the leader’s problem (3)–(14) is

$$\displaystyle\begin{array}{rcl} \max & & W{}\end{array}$$
(15)
$$\displaystyle\begin{array}{rcl} st& & \vert x\vert = p{}\end{array}$$
(16)
$$\displaystyle\begin{array}{rcl} & & W(Y \prec X) \leq W,\forall Y \in L^{r},{}\end{array}$$
(17)

proposed a heuristic based on an elimination procedure in a candidate list in order to solve the leaders problem. In the procedure, a leader solution provides an upper bound for the leader follower problem. A family F of good follower candidates is used to conclude that the upper bound provided by a leader solution cannot be improved, and therefore, this solution is an optimal solution.

The bi-level formulation of Hakimi’s model proposed by Alekseeva et al. [1] employs three kinds of binary variables:

$$\displaystyle\begin{array}{rcl} x_{i}& =& \left \{\begin{array}{lll} 1&\mbox{ if facility}\ i\ \mbox{ is opened by leader,}\\ 0 &\mbox{ otherwise,} \end{array} \right.{}\end{array}$$
(18)
$$\displaystyle\begin{array}{rcl} y_{i}& =& \left \{\begin{array}{lll} 1&\mbox{ if facility }\ i\ \mbox{ is opened by follower,}\\ 0 &\mbox{ otherwise,} \end{array} \right.{}\end{array}$$
(19)
$$\displaystyle\begin{array}{rcl} z_{j}& =& \left \{\begin{array}{lll} 1&\mbox{ if customer}\ j\ \mbox{ is served by leader,}\\ 0 &\mbox{ otherwise,} \end{array} \right.{}\end{array}$$
(20)

It assumes also that for a given solution, x, used by the leader, the set

$$\displaystyle{J_{j}(x) =\{ i \in I\vert d_{ij} <\min _{l\in I\vert x_{i}=1}d_{lj}\},j \in J}$$

defines the set of facilities which allows the follower to capture customer j.

$$\displaystyle\begin{array}{rcl} & \max _{x}\sum _{i\in J}w_{j}z_{j}^{{\ast}}(x)&{}\end{array}$$
(21)
$$\displaystyle\begin{array}{rcl} st.\qquad & \sum _{i\in I}x_{i} = p,&{}\end{array}$$
(22)
$$\displaystyle\begin{array}{rcl} & x_{i} \in \{ 0,1\},\forall i \in I&{}\end{array}$$
(23)

where z j ∗(x) solves

$$\displaystyle\begin{array}{rcl} & \max _{y,z}\sum _{i\in J}w_{j}(1 - z_{j})&{}\end{array}$$
(24)
$$\displaystyle\begin{array}{rcl} st.\qquad & \sum _{i\in I}y_{i} = r&{}\end{array}$$
(25)
$$\displaystyle\begin{array}{rcl} 1 - z_{j} \leq \sum _{i\in I_{j}(x)}y_{i},j \in J,& &{}\end{array}$$
(26)
$$\displaystyle\begin{array}{rcl} & x_{i} + y_{i} \leq 1,i \in I&{}\end{array}$$
(27)
$$\displaystyle\begin{array}{rcl} y_{i},z_{i} \in \{ 0,1\},i \in I,j \in J.& &{}\end{array}$$
(28)

Thereafter, a hybrid memetic algorithm is used for the solution of the problem. The improvement of the elements of population at each iteration is done through a probabilistic Tabu search procedure.

An upper bound is obtained by reformulating the bi-level problem as a single level mixed integer problem with an exponential number of constraints and variables. If \(\mathcal{F}\) is a family of follower solutions and \(I_{j}(y) =\{ i \in I\vert d_{i}j \leq \min _{l\in I}(d_{lj}\vert y_{l} = 1)\},\) \(y \in \mathcal{F},j \in J\) is the set of facilities which allow the leader to keep the customer j if the follower uses solution y, and if \(\mathcal{F}\) contains all possible solutions of the follower then problem (21)–(28) is equivalent to the following 0 − 1 program:

$$\displaystyle\begin{array}{rcl} & \max \ \ \ W&{}\end{array}$$
(29)
$$\displaystyle\begin{array}{rcl} st& &{}\end{array}$$
(30)
$$\displaystyle\begin{array}{rcl} & \sum _{j\in J}w_{j}x_{iy} \geq W,y \in \mathcal{F},&{}\end{array}$$
(31)
$$\displaystyle\begin{array}{rcl} & z_{iy} \leq \sum _{i\in J_{j}(y)}x_{i},j \in Jy \in \mathcal{F},&{}\end{array}$$
(32)
$$\displaystyle\begin{array}{rcl} & \sum _{i\in I}x_{i} = p,&{}\end{array}$$
(33)
$$\displaystyle\begin{array}{rcl} & x_{i},z_{iy} \in \{ 0,1\},i \in I,j \in J,y \in \mathcal{F}&{}\end{array}$$
(34)

where W ≥ 0 is the total market share of the leader and z iy is binary variable indicating whether customer j is serviced by the leader when the follower uses a solution y.

This single level model is also used to find the global optimum. An iterative exact algorithm is developed for this purpose. Alekseeva et al. [2] have used the single level formulation proposed by [26] in order to improve exact iterative method previously developed in [1].

The authors in [7], based on the bi-level representation (21)–(28), approached leader’s–follower’s problem using two metaheuristics methods: local search with variable neighborhoods and stochastic Tabu search.

The bi-level models proposed by Beresnev [3] contain the fixed cost for opening facilities. The author considers two settings of the problem that differ in the objective functions of the follower firm: In the first, it is assumed that the goal of the leader firm as well as the follower firm is the maximization of the profit, while in the second, the objective of the follower is maximization of his income. It is also assumed that each facility opened by the follower firm cannot be loss-making. The author uses the following notation in order to build up the proposed models

  • \(I =\{ 1,\ldots,m\}\) is the set of possible sites for location;

  • \(J =\{ 1,\ldots,n\}\) is the set of clients;

  • p ij is the profit realized by facility i ∈ I opened by the leader when serving client j ∈J

  • ≺ j is a linear order on I determining the preferences of client j ∈ J, and i ≺ j k means that of the two open facilities i and k ∈ I client j selects facility i; the relation i⪯ j k means that either i ≺ j k or i = k;

  • f i is the fixed cost of the leader firm for opening facility i ∈ I;

  • g i is the fixed cost of the follower firm for opening facility i ∈ I.

  • x i is the variable indicating if facility i ∈ I is opened by the leader firm,

  • x ij is the variable indicating if facility i ∈ I opened by the leader firm is selected by client j ∈ J;

  • z i is the variable indicating if the follower firm opens facility i ∈ I;

  • z ij is the variable indicating if client j ∈ J selects facility i ∈ I opened by the follower firm

When the goal of the follower firm is to maximize the profit, it is written as follows:

$$\displaystyle\begin{array}{rcl} \max _{(x_{i}),(x_{ij})}& \left \{-\sum _{i\in I}f_{i}x_{i} +\sum _{j\in J}\left (\sum _{i\in I}p_{ij}x_{ij}\right )\left (1 -\sum _{i\in I}\tilde{z}_{ij}\right )\right \}&{}\end{array}$$
(35)
$$\displaystyle\begin{array}{rcl} st\qquad \qquad \qquad \sum _{i\in I}x_{ij} = 1,j \in J& &{}\end{array}$$
(36)
$$\displaystyle\begin{array}{rcl} & x_{i} \geq x_{ij},i \in I,j \in J,&{}\end{array}$$
(37)
$$\displaystyle\begin{array}{rcl} & x_{i} +\sum _{i\prec _{j}l}x_{lj} \leq 1,i \in I,j \in J&{}\end{array}$$
(38)
$$\displaystyle\begin{array}{rcl} & x_{i},x_{ij} \in \{ 0,1\},i \in I,j \in J&{}\end{array}$$
(39)

\((\tilde{z}_{i}),(\tilde{z}_{ij})\) is the optimal solution of the problem

$$\displaystyle\begin{array}{rcl} \max _{(z_{i}),(z_{ij})}& \left \{-g_{i}z_{i} +\sum _{j\in J}\sum _{i\in I}q_{ij}z_{ij}\right \}&{}\end{array}$$
(40)
$$\displaystyle\begin{array}{rcl} st\qquad \qquad \qquad \sum _{i\in I}z_{ij} \leq 1,j \in J& &{}\end{array}$$
(41)
$$\displaystyle\begin{array}{rcl} & z_{i} \geq z_{ij},i \in I,j \in J&{}\end{array}$$
(42)
$$\displaystyle\begin{array}{rcl} & x_{i} + z_{i} +\sum _{i\prec _{j}l}z_{lj} \leq 1,i \in I,j \in J&{}\end{array}$$
(43)
$$\displaystyle\begin{array}{rcl} & z_{i},z_{ij} \in \{ 0,1\}i \in I,j \in J&{}\end{array}$$
(44)

Objective function (35) shows the value of profit received by the leader taking into account that a part of his consumers will be captured by the follower. Constraint (36) guarantees that each client can select one facility from the leader and inequalities (37) that only one open facility can be selected. Inequalities (38) implement the rule for choosing a facility opened by the leader to service a consumer. The same inequalities guarantee that to service each consumer one can choose only one facility opened by the Leader. Objective function (40) of problem shows the value of the profit received by the follower. Inequalities (43) implement conditions for the follower capturing consumers for given facilities opened by the Leader.

The computational complexity of problem (35)–(44) is discussed in [23] where the author proved that the problem is Σ 2 p-hard when the cost of opening facilities are considered null.

In a series of publication [3–5, 24], a number of solution methods of the problem have been proposed. Their main characteristic is that they are based on the maximization of a pseudo-Boolean function of the form

$$\displaystyle\begin{array}{rcl} \max _{x}& f(x)&{}\end{array}$$
(45)
$$\displaystyle\begin{array}{rcl} st& x \in B^{m}&{}\end{array}$$
(46)

3 Sequential Probabilistic Competitive Facility Location Models

Models presented in the previous sections assume that the distance traveled is the only criterion affecting the patronizing behavior of the customers. However, in more realistic situations, customers consider other attributes of the facilities during their decision-making process such as size, quality of product, and service provided.

Huff [15] suggested to measure the attraction felt by a customer for a facility as a measure of his patronizing probability. In his model the attraction felt by a customer at zone i towards a facility j located at place x j is proportional to the size of the facility and inversely proportional to a power of the distance between zone i and x j . A general formulation of the attraction function is given by

$$\displaystyle{ u_{ij} = \frac{A_{j}} {f(d_{ij})} }$$
(47)

where A j is the attractiveness or quality of the facility j and f is a non-decreasing function of distance.

In the multiplicative competitive interaction (MCI) model of Nakanishi and Cooper [25] different attributes of the facility were used together by taking their product after weighting them by raising each to a power:

$$\displaystyle{ u_{ij} =\prod _{ k=1}^{s}x_{ ijk}^{\beta _{k} } }$$
(48)

where s is the set of facility’s attributes, x ijk is the kth attribute describing a facility j by customers at i, and β k is the weight of the kth attribute.

The additive utility function is utilized in [8]. A general form of this function can be

$$\displaystyle{ U =\sum _{ k=1}^{s}\beta _{ k}f_{k}(x_{k}) }$$
(49)

where x k is the kth attribute and β k its associated weight.

Other models (see for example [13]) make use of the exponential attraction function which is generally given by

$$\displaystyle{ A_{ij} = a_{j}^{\alpha }e^{-\beta d_{ij} } }$$
(50)

where a j measures the quality of the facility j and α,β are parameters determined empirically.

The aim of the model proposed in [21] is to determine the optimal location and the attractiveness of the new facilities to be opened by a firm in a market where there are r existing facilities that belong to a competitor or several competitors. The goal is the maximization of the firm’s profit. The customers are aggregated at \(N = 1,\ldots,n\) demand points and the number of candidate facility site is \(M = 1,\ldots,m.\) The parameters of the problem are

  • a j annual buying power at point j

  • c i unit attractiveness cost at site i

  • f i annualized fixed cost of opening and operating a facility at i

  • d ij Euclidean distance between site i and point j

  • b j total utility of the existing facility depending on its attractiveness and distance from point j

  • u i maximum attractiveness level of facility to be opened at site i

  • q k attractiveness of existing facility j

and variables

  • Q i attractiveness of the facility opened at site i

  • X i binary variable that is equal to 1 if a facility is opened at site i and 0 otherwise.

By using Huff’s model the utility of a facility opened at site i with attractiveness Q i is defined by Q i ∕d ij 2. By using the same rule the total utility felt by customers at j for the existing facilities is \(b_{j} =\sum _{ k=1}^{r}q_{ k}/d_{kj}^{2}\), where d kj is the distance between demand point j and existing facility k. Hence, the market share of the facility at i is expressed as

$$\displaystyle{ P_{ij} = \frac{Q_{i}/d_{ij}^{2}} {\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2}) +\sum _{ k=1}^{r}q_{k}/d_{kj}^{2}} }$$
(51)

As a result the total revenue captured by the new facility is given by

$$\displaystyle{ \sum _{j=1}^{n}a_{ j} \frac{\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2})} {\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2}) +\sum _{ k=1}^{r}(q_{k}/d_{kj}^{2})} }$$
(52)

Then the problem can be formulated as

$$\displaystyle\begin{array}{rcl} \max _{\mathbf{Q,X}}z& =& \sum _{j=1}^{n}a_{ j} \frac{\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2})} {\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2}) +\sum _{ k=1}^{r}(q_{k}/d_{kj}^{2})} \\ & -& \sum _{i=1}^{m}f_{ i}X_{i} -\sum _{i=1}^{m}c_{ i}Q_{1} {}\end{array}$$
(53)
$$\displaystyle\begin{array}{rcl} & s.t& Q_{i} \leq u_{i}X_{i},i = 1,\ldots,m{}\end{array}$$
(54)
$$\displaystyle\begin{array}{rcl} & & X_{i} \in \{ 0,1\},i = 1,\ldots,m{}\end{array}$$
(55)
$$\displaystyle\begin{array}{rcl} & & Q_{i} \geq 0,i = 1,\ldots,m{}\end{array}$$
(56)

To solve the problem three solution methods are presented. One is a heuristic based on the Lagrangian relaxation of the model, while the other two are exact procedures based on the branch and bound technique.

The model proposed in [20] allows the competitor to react in every location decision made by the firm by adjusting the attractiveness level of his own existing facilities with the objective to maximize his profit. The resulting formulation is a bi-level programming model where the entering firm is consider as the leader and the existing competitor as the follower. In this bi-level formulation, the attractiveness level at the competitor’s facility q k becomes the decision variable of the follower.

Thus, the leader solves problem (53)–(56), while the follower the problem

$$\displaystyle\begin{array}{rcl} & \max _{\mathbf{q}}& \sum _{j=1}^{n}a_{ j} \frac{\sum _{i=1}^{r}(q_{k}/d_{kj}^{2})} {\sum _{i=1}^{m}(Q_{i}/d_{ij}^{2}) +\sum _{ k=1}^{r}(q_{k}/d_{kj}^{2})} - \\ & &-\sum _{k=1}^{r}\tilde{c}_{ k}(q_{k} -\tilde{ q}_{k}), {}\end{array}$$
(57)
$$\displaystyle\begin{array}{rcl} & s.t.& q_{k} \leq \bar{ q}_{k},k = 1,\ldots,r{}\end{array}$$
(58)
$$\displaystyle\begin{array}{rcl} & & q_{k} \leq 0,k = 1,\ldots,r{}\end{array}$$
(59)

where the first term of the objective function represents the follower’s market share, and \(\tilde{q}_{k},\bar{q}_{k},\tilde{c}_{k}\) are parameters representing the current attractiveness level, the maximum attractiveness level, and the unit attractiveness cost of the competitor’s facility k, respectively. The author proves the concavity of the follower’ objective function with respect to attractiveness level q. Making use of this property the author transforms the bi-level model into an equivalent single level mixed integer program so that it can be solved by global optimization methods. The transformation is done by substituting the KKT first order conditions into the leader’s problem.

The model was further developed in [22] so as to allow the follower to make decisions not only regarding the attractiveness level but also regarding location.

4 Competitive Facility Location with Competition of Customers

The research work dealing with the bi-level formulation of location problems is limited only to the competition among the locators, that is, it is supposed that either both the locator and the allocator are the same or the customer knows the optimality criterion of the locator and agrees passively with it. Customers’ preferences as well as externalities such as road congestion, facility congestion and emissions caused by the location decisions are either ignored or “controlled” by incorporating constraints in order to “ensure” the achievement of a predetermined target. However, this approach treats customers as irresolute beings. Thus, if, for example, the customers travel to the facilities to obtain the offered service, then there is no compulsion or incentive for them to attend the designated facility. This means that, once the facilities are open, what the locator wishes the customers to do may not coincide with their own wish and behavior.

The first attempt to study the influence of market competition on location decisions is done by Tobin and Friesz [29]. They analyze the case of a profit maximizing firm which is entering into spatially separated markets and knows that its location decisions will have impact on market prices.

To address the problem they proposed two different models to capture the market competition and its effect on price and production quantities: a spatial price equilibrium (SPE) which determines equilibria in price and production levels for perfectly competitive market and a Cournot Nash oligopolistic model in which a few profit maximizing firms compete in spatially separated markets. They used sensitivity analysis on variational inequalities to relate changes in price to changes in production to obtain optimal locations.

In [16] a bi-level programming model is presented to seek the optimal location for logistics distribution centers. The upper-level model is to determine the optimal location by minimizing the planner’s cost and the lower gives an equilibrium demand distribution by minimizing the customer’s cost:

$$\displaystyle\begin{array}{rcl} & \min & \sum _{i=1}^{m}\sum _{ j=1}^{n}C_{ ij}(X_{ij})X_{ij} +\sum _{ j=1}^{n}f_{ j}z_{j}{}\end{array}$$
(60)
$$\displaystyle\begin{array}{rcl} & st& \sum _{J=1}^{n}z_{ j} \geq 1{}\end{array}$$
(61)
$$\displaystyle\begin{array}{rcl} & & z_{j} \in \{ 0,1\}{}\end{array}$$
(62)

where X ij solves

$$\displaystyle\begin{array}{rcl} & \min & \sum _{i=1}^{m}\sum _{ j=1}^{n}\int _{ 0}^{X_{ij} }D^{-1}(w)dw{}\end{array}$$
(63)
$$\displaystyle\begin{array}{rcl} & st& \sum _{j=1}^{n}X_{ ij} = w_{i},\forall i = 1,\ldots,m,{}\end{array}$$
(64)
$$\displaystyle\begin{array}{rcl} & & \sum _{i=1}^{m}X_{ ij} \leq s_{j},\forall j = 1,\ldots,n,{}\end{array}$$
(65)
$$\displaystyle\begin{array}{rcl} & & X_{ij} \leq Mz_{j},\forall i = 1,\ldots,m,j = 1,\ldots,n,{}\end{array}$$
(66)
$$\displaystyle\begin{array}{rcl} & & X_{ij} \geq 0,\forall i = 1,\ldots,m,j = 1,\ldots,n{}\end{array}$$
(67)

where C ij (⋅) is the unit generalized cost of meeting the demand of customer i from the distribution center j, and it is usually a nonlinear function; X ij is the demand of the customer i supplied by distribution center j; f j is the fixed investment associated with building distribution center j; z j is a 0 − 1 variable, if distribution center j is built, then z j takes the value of 1, and 0 otherwise; D 1(⋅) is the inverse of demand functions; w i is the total demand of customer i; s j is the capacity of distribution center j; M is an arbitrarily large positive constant.

From the point of decision-makers, the first term of objective function (60) represents the total costs of meeting customers’ demand. Constraint (61) ensures that at least one distribution center is built, and constraint (62) represents the binary restrictions of the decision variables. The lower-level problem represents the customers’ choice behaviors. Constraint (64) ensures that the total demand of each customer must be met by supply from some distribution centers. Constraint (65) is the capacity constraint, which ensures that all the demands distributed in a distribution center will not exceed its capacity. Constraint (66) prohibits the demand on any proposed distribution center that is not actually constructed. Based on the special form of constraints (66), a simple reaction function is proposed. This reaction function is obtained by transforming (66) into the form

$$\displaystyle{ X_{ij} = Mz_{j} - y_{ij}^{{\ast}} }$$
(68)

where y ij ∗ is the optimal relaxation variable obtained after solving the second-level problem by any existing algorithm. This reaction function is substituted in the first level of the problem which results to an integer programming problem with variables z which can be solved by any well-known non-linear programming model

In [17] and [18] the effects of customers’ competition for the offered service level on the facility location decisions are examined. Two types of decision-makers are considered, the producer who tries to provide at facilities the best level of service at minimum cost and the customers who make their choices in order to minimize their perceived costs. The customers are involved in a Nash-type game in their effort to ensure the best level of services for themselves. A bi-level programming model is formulated in order to take into consideration the effects of customers’ competition. Furthermore an extension is also proposed. It is assumed that there are two producers who constitute a duopoly in the network. The producers compete with one another with respect to the service level they offer in order to attract customers. A bi-level model with two leaders is proposed in order to take into account both the competition between producers and the competition among customers.

It is assumed that the producer tries to provide to the customers the best service level at minimum cost. The evaluation of the offered service is based on the delay faced by the customers at each distribution center i. If x ij is the amount that the customer j buys from the distribution center i, then the performance function d i (x i ) measures the level of service offered by the distribution center i where \(x_{i} =\sum _{ j=1}^{n}x_{ ij}\). Suppose that m is the set of potential sites for the location of the distribution centers. We assume that the establishment of a distribution center to the candidate site i implies a fixed location cost f i . Furthermore, suppose r j is the demand of customer \(j(j = 1\ldots,n\)), p i is the unit price paid by customers, and q i is the capacity of the distribution center \(i(i = 1\ldots,m)\). Under the assumption that a central coordinator chooses the location of the distribution center in such a manner that the total cost of the system is minimized, the mathematical model can be formulated as follows:

$$\displaystyle\begin{array}{rcl} \mathbf{(SO - FL)}\ \min & & \sum _{i=1}^{m}d_{ i}(x_{i})x_{i} +\sum _{ i=1}^{m}p_{ i}x_{i} +\sum _{ i=1}^{m}\sum _{ j=1}^{n}t_{ ij}x_{ij}{}\end{array}$$
(69)
$$\displaystyle\begin{array}{rcl} & +& \sum _{i=1}^{m}F_{ i}y_{i} \\ \qquad \mbox{ s.t}& & \sum _{i=1}^{m}x_{ ij} = r_{j},\ \forall j{}\end{array}$$
(70)
$$\displaystyle\begin{array}{rcl} & & x_{i} \leq y_{i}q_{i},\ \forall i{}\end{array}$$
(71)
$$\displaystyle\begin{array}{rcl} & & x_{i} -\sum _{j=1}^{n}x_{ ij} = 0,\ \forall i{}\end{array}$$
(72)
$$\displaystyle\begin{array}{rcl} & & y_{i} \in \{ 0,1\},\forall i{}\end{array}$$
(73)
$$\displaystyle\begin{array}{rcl} & & x_{ij} \geq 0,\ \forall i,\ \forall j{}\end{array}$$
(74)

The objective function of problem (70) minimizes the total cost consisting of the cost of the delay, plus the transportation and purchasing costs plus the cost involved in setting up a distribution center. Constraints (70) ensure that the quantities purchased by the customer j at all distribution centers meet his overall demand. Constraints (71) impose that the total amount of the product available at each distribution center i does not exceed its capacity. In addition, it enables the assignment of the customers’ demand only in sited distribution. Relations (72) are the defining constraints of the model, ensuring the maintenance of flow in the network.

In a second model producer takes into account the free will and the competitive preference of the customers and determines the final location of the distribution centers based on the prediction of their behavior as delivered by the outcome of a Nash game. Thus, problem is formulated as bi-level programming model:

$$\displaystyle\begin{array}{rcl} \mathbf{(BSO - FL)}\ \min _{[y_{i}]}& & \sum _{i=1}^{m}F_{ i}y_{i} +\sum _{ i=1}^{m}d_{ i}(\bar{x}_{i})\bar{x}_{i} \\ & +& \sum _{i=1}^{m}p_{ i}\bar{x}_{i} +\sum _{ i=1}^{m}\sum _{ j=1}^{n}t_{ ij}\bar{x}_{ij}{}\end{array}$$
(75)
$$\displaystyle\begin{array}{rcl} \ \ \ \mbox{ s.t}& & y_{i} \in \{ 0,1\},\ \forall i{}\end{array}$$
(76)

where \([\bar{x}_{i}]\ \text{and}\ [\bar{x}_{ij}]\) solve

$$\displaystyle\begin{array}{rcl} \mathbf{(UO - TP)}\ \min & & \sum _{i=1}^{m}\int _{ 0}^{x_{i} }d_{i}(t)dt \\ & +& \sum _{i=1}^{m}p_{ i}x_{i} +\sum _{ i=1}^{m}\sum _{ j=1}^{n}t_{ ij}x_{ij}{}\end{array}$$
(77)
$$\displaystyle\begin{array}{rcl} \ \ \ \mbox{ s.t}& & \sum _{i=1}^{m}x_{ ij} = r_{j},\ \forall j{}\end{array}$$
(78)
$$\displaystyle\begin{array}{rcl} & & x_{i} \leq q_{i}y_{i},\ \forall i{}\end{array}$$
(79)
$$\displaystyle\begin{array}{rcl} & & x_{i} -\sum _{j=1}^{n}x_{ ij} = 0,\ \forall i{}\end{array}$$
(80)
$$\displaystyle\begin{array}{rcl} & & x_{ij} \geq 0\ \forall i,j{}\end{array}$$
(81)

According to this model, the leader (producer) decides the location of distribution centers solving problem (75)–(76), but he does not control the variables x i and x ij since they describe the choices of his customers. The values of the variables \([\bar{x}_{i}]\) and \([\bar{x}_{ij}]\) are derived from model (77)–(81) corresponding to an oracle. In other words, the leader uses (77)–(81) as an oracle to discover trends/reactions of the customers in each potential location and tries to minimize the total cost of the system based on these discoveries.

In a supply chain network where there are more than one producers, none of them have the power to direct customers to distribution centers. Thus, as a result, the offered service level and customer satisfaction are the basic differentiation and discrimination components among economic units of the same sector. In order to take into account both levels of competition we formulate the following bi-level problem with two leaders:

Let us assume that the potential location of distribution centers \(i = 1,\ldots,m\) is dispersed between the two producers who in turn are involved in a competition for customer attraction through the provided service level. Let M 1 and M 2 \((m = \vert M_{1}\vert + \vert M_{2}\vert )\) be the nodes of the two producers. Then, under the assumption that both producers “announce their strategies simultaneously,” we obtain a Nash game with two players who are dealing (for K = 1,2) with the following problems:

The facility location problem of producer 1::
$$\displaystyle\begin{array}{rcl} \mathbf{(CFL_{1})}\ \min & & \sum _{i\in M_{1}}F_{i}y_{i} \\ & +& \sum _{i\in M_{1}}d_{i}(\bar{x}_{i})\bar{x}_{i} +\sum _{i\in M_{1}}p_{i}\bar{x}_{i} +\sum _{i\in M_{1}}\sum _{j=1}^{n}t_{ ij}\bar{x}_{ij} {}\end{array}$$
(82)
$$\displaystyle\begin{array}{rcl} \mbox{ s.t }& & y_{i} \in \{ 0,1\},\forall i \in M_{1} {}\end{array}$$
(83)
The facility location problem of producer 2::
$$\displaystyle\begin{array}{rcl} \mathbf{(CFL_{2})}\ \min & & \sum _{i\in M_{2}}F_{i}y_{i} \\ & +& \sum _{i\in M_{2}}d_{i}(\bar{x}_{i})\bar{x}_{i} +\sum _{i\in M_{2}}p_{i}\bar{x}_{i} +\sum _{i\in M_{2}}\sum _{j=1}^{n}t_{ ij}\bar{x}_{ij} {}\end{array}$$
(84)
$$\displaystyle\begin{array}{rcl} \mbox{ s.t}& & y_{i} \in \{ 0,1\},\forall i \in M_{2} {}\end{array}$$
(85)

\(\mbox{ where $[\bar{x}_{i}]$ and $[\bar{x}_{ij}]$ solve (77)\textendash (81)}\)

The producers compete with each other with respect to the service level they offer in order to attract customers involved in a Nash game. A Nash equilibrium for this duopolistic game corresponds to a set of location and capacity choices (strategies), which ensure that none of the players are better off by unilaterally changing his strategy.

Let Y ={ y i |y i ∈{ 0,1},∀i ∈ M k } be the feasible sets of the players for k = 1,2, \(\mathbf{y}_{k} = [y_{i}]_{i\in M_{k}}\) and \(\mathbf{y} = \left [\begin{array}{cc} \mathbf{y}_{1} \\ \mathbf{y}_{2} \end{array} \right ]\). We have already mentioned the existence of optimal solutions \(\bar{x}_{i}\) and \(\bar{x}_{ij}\) for given capacity \([\bar{q}_{i}]\). Thus, there is a function from \(\mathbb{R}^{m}\) to \(\mathbb{R}^{m}\), such that for a given \(\bar{\mathbf{y}}\) it returns the unique equilibrium point \([\bar{x}_{i}]\) from (77)–(81) and a corresponding mapping from \(\mathbb{R}^{m}\) to \(\mathbb{R}^{m\cdot n}\) such that for a given \(\bar{\mathbf{y}}\) it returns an optimal transportation plan \([\bar{x}_{ij}]\) which corresponds to the equilibrium point \([\bar{x}_{i}]\), thus it holds that \(\bar{x}_{i} = x_{i}(\bar{\mathbf{y}})\) and \(\bar{x}_{ij} = x_{ij}(\bar{\mathbf{y}})\), respectively.

Hence problems (CFL k ) could be formulated as a single level problems:

$$\displaystyle\begin{array}{rcl} \mathbf{(SCFL_{k})}\ \ \ \min _{\mathbf{y}_{k}\in Y _{k}}& & \sum _{i\in M_{k}}d_{i}(x_{i}(\mathbf{y}),y_{i})x_{i}(\mathbf{y}) +\sum _{i\in M_{k}}p_{i}x_{i}(\mathbf{y}){}\end{array}$$
(86)
$$\displaystyle\begin{array}{rcl} & +& \sum _{i\in M_{k}}\sum _{j=1}^{n}t_{ ij}x_{ij}(\mathbf{y}){}\end{array}$$
(87)

Each problem (SCFL k ) corresponds to player k who is involved in the Nash game.

5 Conclusion and Future Research

The literature concerning the competitive facility location is vast. The main contribution of our study is that it provides a broad review of modeling and optimization approaches of the discrete bi-level version of the problem. The proposed taxonomy can be meaningfully enhanced based on time, evolution, and content of the subject. In addition it could be the basis of a framework for future studies.