1 Introduction

The literature on the facility location problem began with Weber’s (1909) well-known paper. Subsequently, operations researchers, traffic engineers, economists and others have discussed the location of diverse facilities, such as service facilities (Xia et al. 2015; Farahani et al. 2019), medical facilities (Zhang and Atkins 2019), emergency facilities (Lado-Sestayo and Fernandez-Castro 2019), and utility facilities (Ahmadi-Javid et al. 2016). Hotelling (1929) analyzed the location choice and pricing decision of two competitors on a finite line with uniformly spread consumers, which differs from the classic facility location problem. This is generally regarded as the first paper on the competitive facility location problem. In the competitive facility location literature, authors have typically incorporated the fact that other facilities already are (or will be) in the market and that any new facility or facilities will have to compete with them for market share (Plastria 2001).

In the competitive facility location problem, the customer choice rule for patronising facilities is of great concern. The two most widely used rules are the deterministic utility and random utility rules. The deterministic utility rule states that customers only visit the facility that gives them the highest utility; for example, they only visit the closest facility or the facility offering the cheapest product. In the random utility rule, customers are assumed to distribute their demand according to a certain probability. The gravity-based rule proposed by Reilly (1931) and later used by Huff (1964, (1966) is the most widely used random utility rule, in which a customer’s probability of patronising a facility is proportional to the facility’s attractiveness and inversely proportional to the distance between the customer and the facility. Some new customer choice rules have been proposed in recent years. For example, Fernández et al. (2017) proposed the multi-deterministic utility rule (also called the partially binary rule), which assumes that customers neither visit only one facility nor distribute their demand to all facilities. They only visit the most attractive facility of each company, and they distribute their demand amongst all of these most attractive facilities according to the gravity-based rule. Kung and Liao (2018) explained that consumer demand is affected by the number of facilities such that total demand increases with the number of new facilities. Fernández et al. (2019) proposed a probabilistic customer’s choice rule in which customers only patronise facilities to which they feel an attraction greater than or equal to a threshold value. In this paper, we use the classical gravity-based rule to deal with the competitive facility location problem, which is the most widely used rule and the basis of the aforementioned new rules.

According to the competition pattern, the competitive facility location problem can be classified into four categories (Kress and Pesch 2012): (1) static competition, in which the competitors are fixed and the players know all of the information; (2) dynamic competition, in which the players repeatedly re-optimise their locations; (3) simultaneous competition, in which two rational competitors make decisions simultaneously to reach the Nash equilibrium; and (4) sequential competition, which includes two types of player: leaders who choose locations at given instants and followers who make their location decisions based on the past decisions of the leaders. The solution concept generally used in sequential location problems is the Stackelberg equilibrium: assuming rational players, the location of each player is determined through backward induction. In this paper, we focus on sequential competition and call it a leader–follower facility location problem.

Hakimi (1983) first introduced the leader–follower issue in the competitive facility location problem. He formally introduced the terms (r|p)-centroid problem and \((r|X_{p})\)-medianoid problem with one leader and one follower locating p and r facilities, respectively. In an (r|p)-centroid problem, the leader locates p new facilities with the belief that the follower will invest in r new facilities later. In the \((r|X_{p})\)-medianoid problem, the follower locates r new facilities to maximise its market share, knowing that the leader has located p new facilities. Furthermore, Hakimi proved that the leader–follower problems in (r|p)-centroid and \((r|X_{p})\)-medianoid cases are N-P hard. Moore and Bard (1990) pointed out that the leader and follower always conflict when both aim to optimise their objective functions, which means if one competitor’s market share grows, the other’s will decrease.

Most researchers have assumed that the leader knows exactly how many new facilities will be opened by the follower, such that the leader–follower problem can be formulated as a deterministic model. Hakimi (1986) solved the deterministic leader–follower model by relaxing the condition of fixed demand in a network space. Serra and Revelle (1994) proposed two heuristic algorithms for the leader–follower model in which the leader and follower locate the same number of facilities, and customers only patronise the closest facility. Fischer (2002) formulated a model in a discrete space with the assumption that a certain number of new facilities would be built. In this model, the leader and follower wanted to decide their new locations and the price of their product, and a heuristic algorithm was developed to solve the problem. Peréz et al. (2003) formulated a leader–follower model in a tree and assumed that the leader and follower would locate only one facility each. Further, two algorithms were proposed to generate all of the optimal locations for the leader, and then the entire set of Stackelberg solutions was formed. Sáiz et al. (2009) also assumed that the leader and follower only locate one facility, but they formulated their model in a continuous space and proposed a branch-and-bound method to solve their problem. Drezner and Drezner (1998) developed three heuristic methods to deal with a model similar to that of Sáiz et al. (2009). Qi et al. (2017) introduced service distance limitations in the leader–follower issue with the assumption that both the leader and follower plan to open a certain number of facilities. Gentile et al. (2018) considered three pairs of objective functions for the leader and follower with a predetermined number of facilities, and branch-and-cut algorithms were used to solve the proposed models. Some recent studies have also considered how to decide service quality, radius of influence, product variety, routing and so on, but the number of the follower’s new facilities was still deterministic in these studies (Aboolian et al. 2007; Saidani et al. 2012; Wang and Ouyang 2013; Lopes et al. 2016; Sedghi et al. 2017; Dilek et al. 2017).

As the leader acts ahead of the follower and they are in competition, it is reasonable to assume that the leader has no advance information regarding the follower’s number of new facilities. Ashtiani et al. (2013) built a robust model for the leader–follower problem with an inaccurate number of the follower’s new facilities in a discrete space. They defined their model as a risk model with a known probability distribution, which made a trade-off between expected value and deviation of the leader’s market share. A review of the literature shows that previous studies have modelled the leader’s problem with the assumption that either the number of the follower’s new facilities or their probability distribution is known. However, in a competitive market, information regarding the number or probability distribution of a follower’s new facilities cannot be easily captured by a leader. Even worse, an incorrect estimation of the probability distribution might lead to greater loss for the leader. A realistic example of the leader–follower problem is retail store location. Jingdong (JD), a leading company in China, has invested a considerable amount of capital in the retail industry. According to an interview with the CEO of JD, the company opened more than 1000 convenience stores each week in 2018, and it aimed to open 1000 stores in China each day in 2019. At the same time, market competition is strong. Local convenience store brands are JD’s main competitors in each province. For example, Everyday is a convenience store company in Shaanxi province that has opened new stores each day since 2018, and information regarding Everyday’s decisions is unknown to JD.

The contributions of this paper are as follows. (i) We propose a minimax regret model for the competitive facility location problem that consists of a leader and a follower, in which the leader has no advance information regarding the number or probability distribution of the follower’s new facilities when making its decision. (ii) Based on the structural characteristics of the proposed model, a set of solving procedures is provided that transforms the follower’s nonlinear (fraction) programming model into a linear model. (iii) The numerical experiments show that the minimax regret model is brilliant when the follower’s response is unknown, better controlling the maximum possible loss compared with the deterministic and risk models.

The rest of this paper is organised as follows. In Sect. 2, a minimax regret model for the leader–follower problem is formulated. In Sect. 3, the model is linearised, and the solving procedures are introduced. In Sect. 4, the computational experiments and the results of the analysis are presented in detail. In Sect. 5, our conclusions and future research directions are provided.

2 Problem description and formulation

We consider a facility location problem that consists of two competitors, a leader and a follower, that have established \(N_{l}\) and \(N_{f}\) facilities, respectively. Now, they plan to open new facilities. The decision sequence is that the leader launches its new facilities first, and the follower then launches its new facilities. Both the leader and the follower are assumed to be rational, such that the follower opens stores at the optimal locations after the leader makes its decisions. The notations in Table 1 are used to formulate the problem.

The leader will launch p new facilities in candidate locations, and the follower will respond by opening some new facilities. The two competitors provide identical services, and the demand for the services is considered inelastic and is assumed to be concentrated at K demand points in the market. It is also assumed that the number of facilities in each candidate location is no more than one, i.e., facilities cannot overlap. As there are already \(N_{l}+N_{f}\) facilities, there are \(M=K-(N_{l}+N_{f})\) candidate locations for the leader and follower.

As the leader acts first and chooses p locations, it knows nothing about the follower’s later decision. That is, the leader knows nothing about the number or the probability distribution of the follower’s new facilities, which carries risk. Based on the follower’s subsequent decision, the leader’s optimal decision could change. Therefore, an unreasonable location would lead to the leader’s losing market share, and it must consider how to avoid this risk. The leader has no idea of the exact number of the follower’s new facilities or their probability distribution, but the maximum number of the follower’s new facilities W is assumed to be known to the leader. We accordingly define W scenarios, and in scenario \({\omega }\), the follower will open \(p_{\omega }\) new facilities. The follower is assumed to open \(1,2, \ldots , p_{W}\) new facilities in each scenario. The leader’s problem is determining where to locate its p new facilities facing W scenarios.

Table 1 List of notations
Full size table

2.1 Attractiveness

The gravity-based model is widely used in the competitive facility location problem. According to the Huff rule (Huff 1964, 1966), a facility’s attractiveness to customers should be proportional to its quality and inversely proportional to the squared distance between the customer and the facility. It is supposed that the quality of all existing and new facilities and the distance between candidate locations and the demand point are predetermined.

Denote \(q_{nk}\) as the quality of existing facility n for demand point k, and use \({l_{nk}}\) to denote the distance between existing facility n and demand point k. Therefore, the attractiveness of existing facility n to customers at demand point k is

$$\begin{aligned} a_{nk}=q_{nk}/ \left( \varepsilon +{l_{nk}}^{\,2}\right) , \quad \forall n\in \mathbb {N}, \ k\in \mathbb {K}, \end{aligned}$$
(1)

where \(\varepsilon \) is a small real number added to prevent the denominator from becoming 0 in the case of candidate location n overlapping with demand point k. Similarly, the attractiveness of the leader’s and follower’s new facilities to customers at demand point k is

$$\begin{aligned} {a}_{mk}^{l}={q}_{mk}^{l}/ \left( \varepsilon +{l_{mk}}^{\,2}\right) , \quad \forall m\in \mathbb {M}, \ k\in \mathbb {K}, \end{aligned}$$
(2)
$$\begin{aligned} {a}_{mk}^{f}={q}_{mk}^{f}/ \left( \varepsilon +{l_{mk}}^{\,2}\right) , \quad \forall m\in \mathbb {M}, \ k\in \mathbb {K}. \end{aligned}$$
(3)

Define two binary variables \(x_{m}\) and \(y_{m}^{\omega }\) to represent the leader’s and follower’s decisions, respectively. If \(x_{m}\) takes the value of 1, then candidate location m is occupied by the leader. If \(y_{m}^{\omega }=1\), then candidate location m is occupied by the follower in scenario \(\omega \). If \(x_{m}=y_{m}^{\omega }=0\), then candidate location m is not occupied by either. Next, the total attractiveness level of all of the leader’s facilities for customers at demand point k is calculated by summing the attractiveness of both existing and new facilities, that is,

$$\begin{aligned} L_{k}(X)=\sum \limits _{n\in \mathbb {N}_{l}}a_{nk}+\sum \limits _{m\in \mathbb {M}}{a}_{mk}^{l}x_{m},\quad \forall k\in \mathbb {K}. \end{aligned}$$
(4)

In Eq. (4), we have \(X=\{x_{1}, x_{2},\ldots , x_{m}\}\), which represents one leader’s location strategy.

As the follower locates its facility after the leader does, once the leader makes its decision X, the follower’s optimal location \(Y_{\omega }=\{y_{1}^{\omega }, y_{2}^{\omega },\ldots , y_{m}^{\omega }\}\) in scenario \({\omega }\) can be obtained. Similarly, in each scenario \({\omega }\), the total attractiveness level of all of the follower’s facilities for customers at demand point k is

$$\begin{aligned} F_{k}^{\omega }(Y_{\omega }|X)=\sum \limits _{n\in \mathbb {N}_{f}}a_{nk}+\sum \limits _{m\in \mathbb {M}}{a}_{mk}^{f}y_{m}^{\omega },\quad \forall k\in \mathbb {K},\ {\omega } \in \mathbb {W}, \end{aligned}$$
(5)

where the first term is the attractiveness of existing facilities and the second term is the attractiveness of the new facilities. In the equation, \(Y_{\omega }|X\) is used to denote the follower’s location decision in scenario \(\omega \) with the leader’s decision X.

As a result, the total attractiveness level of all of the facilities in the market for customers at demand point k in scenario \(\omega \) is formulated as

$$\begin{aligned} T_{k}^{\omega }(X,Y_{\omega })=\sum \limits _{n\in \mathbb {N}}a_{nk}+\sum \limits _{m\in \mathbb {M}}{a}_{mk}^{l}x_{m}+\sum \limits _{m\in \mathbb {M}}{a}_{mk}^{f}y_{m}^{\omega },\quad \forall k\in \mathbb {K},\ {\omega } \in \mathbb {W}. \end{aligned}$$
(6)

The three terms on the right represent the attractiveness of all of the existing facilities, the leader’s p new facilities and the follower’s \(p_{\omega }\) new facilities, respectively.

Remark 1

The quality values \({q}_{mk}^{l}\) and \({q}_{mk}^{f}\) are related to both location and demand point, consistent with Ashtiani et al. (2013) and Qi et al. (2017), because the quality of a facility is affected by its location and because customers’ preferences vary at different demand points.

2.2 Constraints

The leader’s behaviour in our model is similar to the (r|p)-centroid problem, in which the leader launches p new facilities after anticipating the follower’s response. The difference is in the follower’s response. In the (r|p)-centroid problem, the follower will surely invest in r new facilities, but in our model, the follower’s number of new facilities is unknown. Constraint (7) ensures that p new facilities are launched by the leader, that is,

$$\begin{aligned} \sum \limits _{m\in \mathbb {M}}x_{m}=p. \end{aligned}$$
(7)

As stated previously, the follower is likely to open \(1,2,\ldots ,p_{W}\) new facilities associated with W scenarios. Then, for each scenario \(\omega \in \mathbb {W}\), constraint (8) ensures that \(p_{\omega }\) of the candidate locations are selected by the follower to launch new facilities, that is,

$$\begin{aligned} \sum \limits _{m\in \mathbb {M}}y_{m}^{\omega }=p_{\omega },\quad \forall {\omega } \in \mathbb {W}. \end{aligned}$$
(8)

Note that the value and probability distribution of \(p_{\omega }\) are unknown to the leader in advance.

Constraint (9) limits the number of new facilities to be opened at each candidate location to one or fewer; thus, the leader and the follower cannot locate facilities in the same candidate location.

$$\begin{aligned} x_{m}+y_{m}^{\omega }\le 1, \quad \forall m\in \mathbb {M},\ {\omega } \in \mathbb {W}. \end{aligned}$$
(9)

Constraint (10) gives the range of the decision variables \(x_{m}\) and \(y_{m}^{\omega }\), that is,

$$\begin{aligned} x_{m} \in {\{0,1\}},\ y_{m}^{\omega } \in {\{0,1\}}, \quad \forall m\in \mathbb {M},\ {\omega } \in \mathbb {W}. \end{aligned}$$
(10)

2.3 Minmax regret model

The Huff rule is used to describe customers’ choice behaviour. We set \(b_{k}\) as the buying power at demand point k, which is distributed to each facility with a certain probability. That probability is equal to the proportion of the facility’s attractiveness to the total attractiveness of all of the facilities. The demand captured by this facility from demand point k can be calculated by multiplying \(b_{k}\) by the probability. Thus, we can obtain the leader’s market share by summing the demand captured by each of its facilities. Similarly, we can obtain the follower’s market share. As mentioned, the two competitors are rational, so they both try to look for optimal locations for their new facilities. In each scenario \({\omega }\), once the leader launches p new facilities, the follower’s problem is choosing a strategy \(Y_{\omega }\) for its new locations. With a given leader’s strategy \(X=\{x_{1}, x_{2}, \ldots , x_{m}\}\), the follower’s problem in each scenario \(\omega \in \mathbb {W}\) can be formulated as

$$\begin{aligned}&\mathrm{max} \sum \limits _{k \in \mathbb {K}}b_{k}\frac{F_{k}^{\omega }(Y_{\omega }|X)}{T_{k}^{\omega }(X,Y_{\omega })} \end{aligned}$$
(11)
$$\begin{aligned}&\text{ s. } \text{ t. } \sum \limits _{m\in \mathbb {M}}y_{m}^{\omega }=p_{\omega }, \end{aligned}$$
(12)
$$\begin{aligned}&x_{m}+y_{m}^{\omega }\le 1, \quad \forall m\in \mathbb {M}, \end{aligned}$$
(13)
$$\begin{aligned}&y_{m}^{\omega } \in {\{0,1\}}, \quad \forall m\in \mathbb {M}. \end{aligned}$$
(14)

The objective function (11) maximises the follower’s market share of all of its facilities, in which \(F_{k}^{\omega }(Y_{\omega }|X)/T_{k}^{\omega }(X,Y_{\omega })\) represents the aforementioned probability. Note that there is a total of W scenarios, and each scenario represents a different number of new facilities located by the follower. Constraints (12)–(14) are explained in the previous subsection.

By solving the follower’s model, the optimal locations for the follower’s new facilities and the corresponding market share in each scenario can be obtained. Next, we make decisions for the leader. In reality, it is reasonable for the leader to decide on the most likely scenario (in its judgement) and act accordingly. However, the consequences could be serious if that scenario does not materialise. The minimax regret criterion, which can control this risk by minimising the maximum possible loss under any of the likely scenarios, is used to solve the leader’s problem. For each scenario, the regret value for the leader that is associated with a strategy is the difference between the maximum possible market share captured with the optimal strategy and the market share captured with the relevant strategy. By using \(\mathbb {X}\) to denote the set of the leader’s strategies and X to denote each strategy, we set \(\pi _{\omega }(X)\) as the leader’s market share associated with strategy X and scenario \(\omega \), and set \(\pi _{\omega }^{*}\) as the maximum value of \(\pi _{\omega }(X)\), that is,

$$\begin{aligned} \pi _{\omega }^{*}=\mathop {\mathrm{max}}\limits _{X\in \mathbb {X}}\pi _{\omega }(X)=\mathop {\mathrm{max}}\limits _{X\in \mathbb {X}}\sum \limits _{k \in \mathbb {K}}b_{k}\frac{L_{k}(X)}{T_{k}^{\omega }(X,{Y}_{\omega }^{*}(X))}. \end{aligned}$$
(15)

In Eq. (15), we use \({Y}_{\omega }^{*}(X)\) to denote the follower’s optimal location in scenario \({\omega }\) when facing the leader’s strategy X.

According to the minimax regret criterion, the leader’s problem is formulated as

$$\begin{aligned}&\mathop {\mathrm{min}}\limits _{X\in \mathbb {X}} \mathop {\mathrm{max}}\limits _{\omega \in \mathbb {W}} \left[ \pi _{\omega }^{*}- \pi _{\omega }(X)\right] \end{aligned}$$
(16)
$$\begin{aligned}&\text{ s. } \text{ t. } \sum \limits _{m\in \mathbb {M}}x_{m}=p, \end{aligned}$$
(17)
$$\begin{aligned}&x_{m} \in {\{0,1\}}, \quad \forall m\in \mathbb {M}. \end{aligned}$$
(18)

Objective function (16) minimises the maximum regret value for the leader in all of the potential scenarios. As the leader will launch p new facilities in M candidate locations, there are \(C_{M}^{p}\) potential strategies available to it; thus X takes values from 1 to \(C_{M}^{p}\). Under this criterion, we can choose the strategy for the leader in which the maximum regret value for all of the leader’s possible locations is minimised.

3 Model linearization and solution

The leader has \(C_{M}^{p}\) possible strategies, and the follower has W scenarios. Given the leader’s strategy and scenario, the follower’s model (11)–(14) becomes deterministic. Therefore, the leader–follower facility location problem can be resolved by solving the follower’s model (11)–(14) \(C_{M}^{p}\times W\) times. By solving the follower’s model for each scenario, the follower’s optimal locations and market share are obtained, and then the leader’s corresponding market share can be determined. When the leader’s market share for each of these \(C_{M}^{p}\) strategies and W scenarios is obtained, the minimax criterion is applied to find the leader’s optimal locations amongst all of the potential strategies. The solving procedures are depicted in Fig. 1.

Fig. 1
figure 1

The solving procedures of minimax regret model

Full size image

The most important but most difficult step in the solving procedures is solving the follower’s model (11)–(14), which is essentially a nonlinear programming problem, because the objective function (11) contains the fractional terms of the decision variables. In the following, we transform the follower’s model (11)–(14) into a linear model, and then it can be efficiently solved by optimisation solvers such as LINGO and CPLEX. Following Kochetov et al. (2013), two new variables, \(z_{k}^{\omega }\) and \(u_{mk}^{\omega }\), are introduced, which are defined as

$$\begin{aligned} z_{k}^{\omega }= & {} \frac{1}{T_{k}^{\omega }}, \quad \forall k\in \mathbb {K}, \end{aligned}$$
(19)
$$\begin{aligned} u_{mk}^{\omega }= & {} z_{k}^{\omega }y_{m}^{\omega }, \quad \forall m\in \mathbb {M}, \quad k\in \mathbb {K}. \end{aligned}$$
(20)

In Eq. (19), \(z_{k}^{\omega }\) is basically the reciprocal of the total attractiveness of all of the facilities for a fixed k. In Eq. (20), \(u_{mk}^{\omega }\) is formed by the multiplication of two variables, \(z_{k}^{\omega }\) and \(y_{m}^{\omega }\). We use the 0-1 property of variable \(y_{m}^{\omega }\) to transform the nonlinear follower’s model to a linear model. Note that for convenience of description, X, Y and \(Y_{\omega }^{*}(X)\) do not appear in the following formula. On this basis, we can derive the theorem.

Theorem 1

For each \({\omega } \in \mathbb {W}\), the follower’s model (11)–(14) is equivalent to the following linear form

$$\begin{aligned}&\mathrm{max} \sum \limits _{k \in \mathbb {K}}\sum \limits _{n \in \mathbb {N}_{f}}b_{k}a_{nk}z_{k}^{\omega }+\sum \limits _{k \in \mathbb {K}}\sum \limits _{m \in \mathbb {M}}b_{k}a_{mk}^{f}u_{mk}^{\omega } \end{aligned}$$
(21)
$$\begin{aligned}&\text{ s. } \text{ t. } \text{(12)--(14) } \ \mathrm{and}\nonumber \\&\sum \limits _{n \in \mathbb {N}_{f}}b_{k}a_{nk}z_{k}^{\omega }+\sum \limits _{m \in \mathbb {M}}b_{k}a_{mk}^{f}u_{mk}^{\omega }+b_{k}z_{k}^{\omega }L_{k}\le b_{k}, \quad \forall k\in \mathbb {K}, \end{aligned}$$
(22)
$$\begin{aligned}&0\le u_{mk}^{\omega }\le y_{m}^{\omega },\forall m\in \mathbb {M}, k\in \mathbb {K}, \end{aligned}$$
(23)
$$\begin{aligned}&u_{mk}^{\omega }\le z_{k}^{\omega } \le u_{mk}^{\omega }+S(1-y_{m}^{\omega }),\forall m\in \mathbb {M}, k\in \mathbb {K}. \end{aligned}$$
(24)

In the above linear equivalent form, the decision variables are \(y_{m}^{\omega }\), \(z_{k}^{\omega }\) and \(u_{mk}^{\omega }\). Note that S is a large enough constant in constraint (24).

Proof

For each \(k\in \mathbb {K}\) and \(\omega \in \mathbb {W}\), a constraint should be added to fulfil Eq. (19), that is,

$$\begin{aligned} z_{k}^{\omega } \le 1/T_{k}^{\omega }. \end{aligned}$$

If both sides of the inequality are multiplied by \(b_{k}T_{k}^{\omega }\), we have

$$\begin{aligned} b_{k}z_{k}^{\omega }T_{k}^{\omega }\le b_{k}. \end{aligned}$$

Because \(T_{k}^{\omega }=F_{k}^{\omega }+L_{k}\), we get

$$\begin{aligned} b_{k}z_{k}^{\omega }F_{k}^{\omega }+b_{k}z_{k}^{\omega }L_{k}\le b_{k}. \end{aligned}$$

The first term is equal to \(\sum \nolimits _{n \in \mathbb {N}_{f}}b_{k}a_{nk}z_{k}^{\omega }+\sum \nolimits _{m \in \mathbb {M}}b_{k}a_{mk}^{f}u_{mk}^{\omega }\), thus we get the linear constraint (22).

Constraints (23) and (24) fulfil Eq. (20), in which we use the 0–1 property of variable \(y_{m}^{\omega }\). When \(y_{m}^{\omega }=0\), for each \(m\in \mathbb {M}\), \(k\in \mathbb {K}\) and \(\omega \in \mathbb {W}\), Eq. (20) becomes

$$\begin{aligned} u_{mk}^{\omega }= 0, \end{aligned}$$

which is restricted by constraint (23). For constraint (24), as \(y_{m}^{\omega }=0\), it becomes

$$\begin{aligned} u_{mk}^{\omega } \le z_{k}^{\omega }\le u_{mk}^{\omega }+S, \end{aligned}$$

which is always satisfies.

Similarly, when \(y_{m}^{\omega }=1\), for each \(m\in \mathbb {M}\), \(k\in \mathbb {K}\) and \(\omega \in \mathbb {W}\), Eq. (20) becomes

$$\begin{aligned} u_{mk}^{\omega }=z_{k}^{\omega }, \end{aligned}$$

which is restricted by constraint (24), while constraint (23) always satisfies. Note that when \(y_{m}^{\omega }=1\), \(z_{k}^{\omega } \le y_{m}^{\omega }\) is a permanent inequality because

$$\begin{aligned} z_{k}^{\omega }=\frac{1}{\sum \nolimits _{n\in \mathbb {N}}a_{nk}+\sum \nolimits _{m\in \mathbb {M}}{a}_{mk}^{l}x_{m}+\sum \nolimits _{m\in \mathbb {M}}{a}_{mk}^{f}y_{m}^{\omega }}\le 1=y_{m}^{\omega }, \end{aligned}$$

then we have

$$\begin{aligned} 0\le u_{mk}^{\omega }=z_{k}^{\omega } \le y_{m}^{\omega }, \end{aligned}$$

which means that constraints (23) and (24) do not conflict with each other. Thus, no matter the value of \(y_{m}^{\omega }\), Eq. (20) is always fulfilled. On this basis, constraints (22)–(24) ensure that Eqs. (19) and (20) are valid.

As for the objective function (21), it is equivalent to (11) because

$$\begin{aligned}&\sum \limits _{k \in \mathbb {K}}\sum \limits _{n \in \mathbb {N}_f}b_k a_{nk}z_k^\omega +\sum \limits _{k \in \mathbb {K}}\sum \limits _{m \in \mathbb {M}}b_k a_{mk}^f u_{mk}^\omega \\&\quad =\sum \limits _{k \in \mathbb {K}}b_k\left( \sum \limits _{n\in \mathbb {N}_f}a_{nk}+\sum \limits _{m\in \mathbb {M}}a_{mk}^f y_m^\omega \right) z_k^\omega \\&\quad =\sum \limits _{k \in \mathbb {K}}b_k F_k^\omega z_k^\omega \\&\quad =\sum \limits _{k \in \mathbb {K}}b_k\frac{F_k^\omega }{T_k^\omega }. \end{aligned}$$

In the above equation, both \(\sum \nolimits _{k \in \mathbb {K}}\sum \nolimits _{n \in \mathbb {N}_{f}}b_{k}a_{nk}z_{k}^{\omega }+\sum \nolimits _{k \in \mathbb {K}}\sum \nolimits _{m \in \mathbb {M}}b_{k}a_{mk}^{f}u_{mk}^{\omega }\) and \(\sum \nolimits _{k \in \mathbb {K}}b_{k}\frac{F_{k}^{\omega }}{T_{k}^{\omega }}\) represent the follower’s market share, which we maximise.

As a result, the follower’s problem (21)–(24) is the linear equivalent of (11)–(14). Based on the transformation, part of the optimal solution of the linear model (\(y_{m}^{\omega }\)) is the optimal solution to (11)–(14). The proof is completed. \(\square \)

4 Numerical experiments

In this section, numerical experiments are conducted to verify the validity of the proposed model and test the efficiency of the linearisation. To further explain the necessity of our hypothesis that the number of the follower’s new facilities is unknown or has an unknown probability distribution, comparisons with two different location models are provided to show the advantages of the proposed model.

4.1 An illustration of the minimax regert model

We consider an instance with 16 demand points and 5 existing facilities in the market, as shown in Fig. 2. Three of the existing facilities belong to the leader, whose locations are (3, 2), (4, 3) and (1, 4), and the other two belong to the follower, whose locations are (3, 1) and (3, 3). The leader aims to open two new facilities knowing that the follower will open some facilities afterwards. However, it does not know the exact number of the follower’s new facilities, but it knows that the maximum number is four, i.e., the follower will open 1, 2, 3 or 4 new facilities. New facilities cannot be opened in demand points that are occupied by existing facilities. Therefore, the number of candidate locations for both the leader’s and follower’s new facilities is 11. The buying power at each demand point is randomly generated from 1 to 10, and we set the unit of buying power as 1 million yuan. The buying power and coordinates of the demand points are shown in Table 2. Quality values are also given randomly from 1 to 5 for the new and existing leader and follower facilities, which are shown in Table 3.

Table 2 Coordinate and buying power of each demand point
Full size table
Fig. 2
figure 2

The locations of the leader’s and follower’s existing facilities

Full size image
Table 3 The quality levels of the demand points
Full size table
Table 4 Potential strategies of the leader
Full size table

According to the solving procedures in Sect. 3, for each given strategy of the leader, we first solve the follower’s model. Then, the leader’s market share can be obtained for each scenario. There are \(C_{11}^{2}=55\) potential choices for the leader to choose 2 locations from amongst the 11 demand points as its strategy, and scenarios 1, 2, 3 and 4 in the following tables represent the follower opening 1, 2, 3 and 4 facilities, respectively. The coordinates of strategies 1–55 for the leader are listed in Table 4. For example, if the leader chooses strategy 1, i.e., locations (1, 1) and (2, 1) to open two new facilities, the follower’s problem is solved in the candidate locations for the different scenarios. In scenario 1 (the follower opens one new facility), the leader’s maximum market share is 53.23 million yuan, whereas in scenario 2 (the follower opens two new facilities), the leader’s maximum market share is 45.55 million yuan. Similarly, the market shares are 41.67 million yuan for scenario 3 (the follower opens three new facilities) and 38.60 million yuan for scenario 4 (the follower opens four new facilities). This is done for all 55 strategies and 4 scenarios in Table 5.

As shown in Table 5, the optimal strategy for the leader in scenarios 1 and 2 is 33, i.e., locations (1, 2) and (3, 4) are chosen, in which the market shares are 58.80 million yuan and 51.71 million yuan, respectively. The optimal strategy in scenarios 3 and 4 is 32, i.e., (1, 2) and (2, 4), in which the market shares are 48.13 million yuan and 45.39 million yuan. This reveals that with respect to the follower’s different decisions, the leader’s optimal strategy may differ. If the leader’s optimal strategy under different scenarios is unchanged, we can easily make decisions for the leader. However, the optimal strategy changes with the scenario, so we must deal with the issue of the unknown number of the follower’s new facilities. As the probability distribution of the four scenarios is unknown to the leader, the minimax regret value rule is applied to make the decision. The leader’s optimal strategies for these four scenarios are displayed in Fig. 3.

The regret values for the leader’s 55 potential strategies in the 4 scenarios are calculated and displayed in Table 6. Each regret value means the loss of market share for one strategy when compared with the maximum market share of that scenario. For example, strategy 33 is the location with the highest market share for the leader in scenario 1, so the regret value of strategy 1 in scenario 1 is calculated as \(58.80 - 53.23 = 5.57\), in which the two terms on the left represent the market shares of strategy 33 and strategy 1 in scenario 1, respectively. The same method is used to calculate the regret value of all of the leader’s strategies in the four scenarios. As a result, for each strategy, we get four regret values that correspond to the four scenarios. The maximum regret value of each strategy is listed in Table 6. Our purpose is to launch the leader’s new facilities in locations that ensure the maximum regret value is minimised among all of the leader’s strategies. According to the maximum regret value list in Table 6, the optimal strategy for the leader is strategy 3, i.e., (1, 1) and (1, 2), because the maximum regret value in this location is only 0.99 million yuan, which is the lowest of all of the leader’s potential strategies.

By choosing strategy 3, we control the leader’s maximum loss to the lowest pitch. With the other 54 strategies, the leader’s maximum loss would be more than that with strategy 3 because the number of the follower’s new facilities is uncertain. The locations of strategy 3 are depicted in Fig. 4.

Table 5 The leader’s market share by scenario
Full size table
Table 6 The leader’s regret value by scenario
Full size table
Fig. 3
figure 3

Optimal locations for the leader in different scenarios

Full size image
Fig. 4
figure 4

The optimal locations for the leader in the minimax regret model

Full size image

4.2 Comparison

This paper studies the leader–follower location problem in which the leader knows neither the number nor the probability distribution of the follower’s new locations, and proposes the minimax regret model to control the leader’s possible loss. In the literature, the deterministic and risk models have been widely studied in location problems. In this section, the minimax regret model is compared with the deterministic and risk models to highlight the advantages of the minimax regret model and the serious consequences of blindly using the deterministic and risk models in the uncertain environment that this paper considers. If the leader enterprise blindly uses these two models to make its location decision, severe consequences could occur, i.e., a loss of market share arising from using an incorrect estimation of the number/distribution of the follower’s new facilities.

4.2.1 Comparison with the deterministic model

Starting with Hakimi’s (1983) well-known paper on the leader–follower problem, most researchers have considered a specific number of the follower’s new facilities, (see Sáiz et al. 2009; Kochetov et al. 2013; Gentile et al. 2018). For simplicity, we label this kind of model as deterministic, in which the leader will open p new facilities, and it knows that r new facilities will be opened by the follower.

In this subsection, we compare the deterministic model and the minimax regret model. Again, we assume that the leader has no idea of the follower’s number of new facilities. If the leader acts as if it knows a definite number of the follower’s new facilities, the leader is more likely to incur greater loss. This comparison is made to show this loss. As shown in the numerical experiments, if the follower only opens one new facility, strategy 33 is optimal for the leader. However, in a competitive market, this kind of information cannot be captured by the leader in advance, i.e., the number of the follower’s new facilities is unknown. For example, if the leader believes that the follower will only open one new facility and acts accordingly, the leader will choose strategy 33. However, the follower actually launches three new facilities after the leader’s action, so the optimal strategy would have been 32. As a result, the leader would lose 1.52 million yuan. However, if the minimax regret model were applied to this situation, the loss would be only 0.08 million yuan with strategy 3.

It seems obvious that no matter which scenario is considered, strategy 3 is not the optimal solution for the leader. Therefore, even if the leader opens new facilities based on the most likely scenario, it would not choose strategy 3. It is more likely that it will choose strategy 32 or 33 because for scenarios 1 and 2, strategy 33 is optimal and for scenarios 3 and 4, strategy 32 is optimal. However, in the minimax regret model, strategy 3 is optimal, with a maximum loss of only 0.99 million yuan. In contrast, if the leader chooses strategy 32 or 33, which are the optimal strategies with the deterministic model, the maximum loss could reach 1.71 and 1.86 million yuan, respectively. The results show that if the leader cannot know the follower’s response, the minimax regret model can control the possible loss as compared with the deterministic model. The maximum loss and coordinates of strategies 3, 32 and 33 are shown in Table 7.

Table 7 Comparison with the deterministic model
Full size table

4.2.2 Comparison with the risk model

In Ashtiani et al. (2013), the follower was assumed to open \(1, 2, \ldots , p_{W}\) new facilities with probabilities of \(P_{1}, P_{2}, \ldots , P_{W}\). The leader’s objective function is formulated as “Expected Value \(- \lambda \) \(\cdot \) Variance”, that is

$$\begin{aligned} \mathrm{max} \sum \limits _{\omega \in \mathbb {W}}\sum \limits _{k \in \mathbb {K}}P_{\omega }b_{k}\frac{L_{k}}{T_{k}^{\omega }}-\lambda \sum \limits _{\omega \in \mathbb {W}}P_{\omega }\left( \sum \limits _{k \in \mathbb {K}}b_{k}\frac{L_{k}}{T_{k}^{\omega }}-P_{\omega }\sum \limits _{k \in \mathbb {K}}b_{k}\frac{L_{k}}{T_{k}^{\omega }}\right) ^{2}. \end{aligned}$$

This objective function simultaneously maximises the expected value of the leader’s market share and minimises the degree of deviation between the expected value and the scenarios’ optimal solution. In the objective function, \(\lambda \) is a weight coefficient that measures the importance of variance. The rest of the notations have the same meaning as in our proposed minimax regret model.

It is a robust optimisation for the leader, but its results might be affected by both the value of \(\lambda \) and the probability distribution of \(P_{1}, P_{2}, \ldots , P_{W}\). To verify the possibility of the supposed events, we test the risk model using different values of \(\lambda \): 1, 0.8, 0.6, 0.4, 0.2 and 0 in sequence. Then, for each \(\lambda \), we randomly generate 10,000 probability distributions. As shown in Fig. 5, the leader is likely to choose strategy 3, 17, 32, 33 and 47 in the risk model with the change of \(\lambda \) and probability distribution, demonstrating the risk model’s high level of sensitivity. In practice, both \(\lambda \) and the probability distribution are decided by the leader’s experience, so their values might also be subjective, thus leading to unreasonable location choices. For example, when \(\lambda =1\), for 8296 probability distributions, the leader chooses strategy 47 to launch new facilities. For 927 probability distributions, the leader chooses strategy 32, and for 148, the leader chooses strategy 17. As the leader’s market share in the scenarios under strategy 47 varies little compared with the other strategies, even though the market share of this strategy is not high in each scenario, it is still the optimal strategy in most cases. The market share of strategy 17 is even worse. The situations are analogous when \(\lambda =0.8\) and \(\lambda =0.6\).

Again, we assume that the leader has no idea of the probability distribution of the number of the follower’s new facilities. If the leader acts as if it knows the probability distribution, it is more likely to incur greater loss. This model comparison demonstrates this loss. To compare the risk model and the minimax regret model, we calculate the weighted average of the maximum loss associated with each \(\lambda \), where the probability of choosing one strategy is denoted by frequency. For example, when \(\lambda =1\), the leader chooses strategy 47 with a probability of 82.96%, and the maximum regret value is 5.82 million yuan. Similarly, the probability and maximum regret value for strategy 32 are 9.27% and 1.71 million yuan, respectively, and for strategy 17, they are 1.48% and 7.63 million yuan. Thus, the weighted average of the possible maximum loss for \(\lambda =1\) is \(\overline{\mathrm{Loss}}=82.96\%*5.82+9.27\%*1.71+1.48\%*7.63=5.10\) million yuan. The values of \(\overline{\mathrm{Loss}}\) for each \(\lambda \) are displayed in Table 8. The \(\overline{\mathrm{Loss}}\) for all \(\lambda \) in the risk model are greater than the possible maximum loss in the minimax regret model. The maximum loss is only 0.99 million yuan when the minimax regret model is applied, but the values of \(\overline{\mathrm{Loss}}\) with the risk model are 5.10 million yuan, 5.29 million yuan, 4.88 million yuan, 3.08 million yuan, 1.71 million yuan and 1.07 million yuan, respectively. Even if we do not consider the variance, the minimax regret model still reduces the regret value from 1.07 million yuan to 0.99 million yuan, and this reduction is because of the incorrect estimation of the probability distributions.

All in all, when the minimax regret value criterion is applied to the leader’s decision, more stable and less risky locations are obtained. At the same time, there is no need to assume that the information regarding the number or probability distribution of the follower’s new facilities is known by the leader in advance, which is more practical in reality.

Table 8 Comparison with the risk model
Full size table
Fig. 5
figure 5

The results of the risk model with different \(\lambda \)

Full size image

4.3 The efficiency of linearisation

In the solving procedures, we transform the follower’s nonlinear model (11)–(14) into a linear model. In this subsection, we use 10 instances of different scales to test the efficiency of this linearisation. For each instance, the number of the follower’s new facilities, candidate locations and existing facilities vary. The other required parameters are extracted as stated previously. The nonlinear models are solved using LINGO, whereas the linear models are solved using CPLEX. The results are recorded in Table 9. Note that “–” in Table 9 means that the model cannot be solved in 1000 min.

Table 9 Computation time for different sizes of the follower’s model
Full size table

Table 9 shows that for the first eight instances, the follower’s market share is the same for the linear and nonlinear models, but the computation time of the linear model is significantly less than that of the nonlinear model. For example, for the first instance with \(p_{W}=2\), \(K=81\), \(N_{l}=6\) and \(N_{f}=4\), the nonlinear model takes 10.23 min to be solved, whereas the linear model takes only 0.75 min. For the last two instances, the linear model can be optimally solved within an acceptable time, but the nonlinear models do not obtain the optimal solution within 1000 min.

5 Conclusion and future research

This paper studies the leader–follower facility location problem. Its main contribution is the formulation of a minimax regret model to control the leader’s possible loss based on location decisions made without knowing the follower’s response. In the solving procedures, we transform the follower’s model from a nonlinear (fraction) programming problem to a linear programming problem by introducing new variables and constraints. Numerical experiments and comparisons are provided to verify the validity and advantages of the proposed model, and the efficiency of linearisation is tested using 10 instances of different scales. The results reveal that, compared with the deterministic and risk models, the proposed model is more applicable when there is no information about the number or probability distribution of the follower’s new facilities. The nonlinear model is time-consuming or even unsolvable within 1000 min, whereas the linear model significantly decreases the computation time.

Future research could consider take-out shops. Goods can be delivered, so the delivery cost rather than distance would be an influencing factor of the facility’s attractiveness. Also, with the development of a delivery industry, goods can be delivered to distant customers. Therefore, it is necessary to develop efficient meta-heuristic algorithms to solve large-scale problems. In addition, we could consider the elastic demand for each demand point. For example, the buying power of demand points rises with an increase in the number of new facilities, thus the market situation for both the leader and follower will be more complex.