#PAGE_PARAMS# #ADS_HEAD_SCRIPTS# #MICRODATA#

A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold


Authors: Wuyang Yu aff001
Authors place of work: School of Management, Hangzhou Dianzi University, Zhejiang, China aff001
Published in the journal: PLoS ONE 14(12)
Category: Research Article
doi: https://doi.org/10.1371/journal.pone.0225693

Summary

When consumers are faced with the choice of competitive chain facilities that offer exclusive services, current rules do not properly describe the behavior pattern of these consumers. To eliminate the gap between the current rules and this kind of customers behavior pattern, the partially proportional rule with a threshold is proposed in this paper. A leader-follower model for discrete competitive facility location problem is established under the partially proportional rule with a threshold. Combining with the greedy strategy and the 2-opt strategy, a heuristical algorithm (GFA) is designed to solve the follower’s problem. By embedding the algorithm (GFA), an improved ranking-based algorithm (IRGA) is proposed to solve the leader-follower model. Numerical tests show that the algorithm proposed in this paper can solve the leader-follower model for discrete competitive facility location problem effectively. The effects of different parameters on the market share captured by the leader firm and the follower firm are analyzed in detail using a quasi-real example. An interesting finding is that in some cases the leader firm does not have a first-mover advantage.

Keywords:

Algorithms – Decision making – Florida – Pennsylvania – Ranking algorithms – Mississippi – New York – Louisiana

1 Introduction

In a market environment, competing facilities are those provided similar products or services for customers’ patronage. In a market competition already exists or will exist in the future, the competitive facility location problem is to find the best locations for some of the new facilities. The goal of the competitive facility location problem is to maximize the market share captured by these facilities. Many competitive location models have been proposed for this purpose (see survey papers ([13]). These models can be categorized according to three kinds of features [4]: competition type, location space, and customer behavior.

Competition types are usually divided into two categories [5]: (1) static competition. This kind of competition is based on such assumption that the competitors already exist in the market, but they will not take action on new firms entering the market. (2) competition with foresight. There are two major situations in this kind of competition. One situation is when the firm wants to enter a virgin market in the knowledge that other competing actors will enter it soon. Another situation is when the firm wants to enter a competing market and considers the opponent’s reaction (see [6]–[9]). Optimization models of the competitive facility location problems with foresight usually consist of the following two stages [5]: Both with the objective of maximizing market share, the leader locates new facilities in the first stage by considering the reaction of the follower, then the follower determines his facilities in the second stage. The location space is the second key ingredient, which is usually categorized as: (1) discrete space, where the location space is discrete and known in advance; (2) network space, assume that the customers and facilities are located in a given network; (3) plane space, where the new facilities can be located continuously on a two-dimensional plane. Most literature of the competitive facility location problem focuses on discrete space and less on network or plane space (see [10]–[15]).

Suppose there are several competitive facilities offer similar products or services, customer behavior refers to the way that a customer how to spend his buying power on these facilities. Hence, determining the type of customer behavior is the foundation to estimate the market share captured by a firm. Therefore, customer behavior plays a very important role in the location of competitive facilities. Different customer behaviors can be described in a precise manner with different rules. These rules are often expressed as functional forms of attraction that customers feel from different facilities [16]. Three customer behavior rules are usually employed in literature of the competitive facility location problem: (1) Binary Rule. This rule dates back to the duopoly model proposed by Hotelling [17]. It is assumed that the customer always patronizes the most attractive facility. (2) Proportional Rule. This rule is first addressed by Huff [18], which assumes that the customer patronizes each facility in proportion to its attraction. (3) Partially Binary Rule. Following the partially binary rule, the customer first selects the most attractive facility from each firm in the market, then splits his demand among those facilities proportionally to its attraction [19]. Some variants of these customer choice rules, mainly of the proportional rule, are proposed in some research works (see [20]–[28]). For example, Fernández et al. [27] proposed two new heuristic algorithms to solve competitive facility location problems with the binary rule and the partially binary rule. Qi et al. [28] considered a kind of customer behavior that customer only patronizes facilities within a range.

Ashtiani [29] indicated that some new features (such as relocation, design etc.) are included in the recent progress of competitive facility location problem. For example, Wang and Ouyang [30] presented a competitive service facility location design model by considering facility disruption risks. Nasiri et al. [31] studied the competitive facility location problem under the assumption of capacity constraints. Kung and Liao [32] constructed a discrete competitive facility location model considered the endogenous customer demands and network effects. Casas-Ramírez et al. [33] studied the competitive facility location problem with the customers’ patronize behavior based on a predetermined list of preferences. Zhang et al. [34] studied the competitive facility location problem in the Stackelberg game framework. In their paper, facilities face disruption risks, and each customer patronizes the nearest operational facility.

Table 1 lists some of the relative studies, classifying them in terms of competitive type (Foresight (F) and Static (S)), location space (Discrete (D), Network (N), and Plane (P)), and customer behavior (Binary (B), Proportional (P), and Partially binary (PB)).

Tab. 1. Selected researchers and classification.
Selected researchers and classification.

The above three rules can describe most of the customer behavior in the competitive facility location problem. However, when customers faced with the choice of competitive chain facilities offer exclusive services, none of these three rules can describe the customer behavior involved very well. For example, when somebody wants to apply for a bank account for deposit/withdrew or other services, usually he (or she) compares different banks at first then selects the most attractive bank to obtain the bank card. Because each bank has several business service points (including manual service points and ATMs), customers usually use the total attraction of all business service points to evaluate the bank. After getting the bank card, he (or she) will patronize each business service points of this bank in proportion to its attraction. The process of a customer applies for a bank account can be regarded as a typical description of customer behaviors when customers facing competitive facilities that offer exclusive services. This kind of customer behavior pattern can also be observed in another scene. Suppose the consumer plans to do a lot of activities such as shopping, entertainment, eating, etc. at a weekend, he (or she) is likely to choose a comprehensive mall where all these activities can be performed. If there are multiple optional comprehensive malls, he (or she) will compare the total appeal of these malls and then chooses the one that is most attractive to him (or her) to carry out the planned activities. When we consider the comprehensive mall as a firm and treat the different services as different facilities, we will find that the consumer choice behavior pattern is similar to the previous example. Unfortunately, none of the binary rule, the proportional rule, and the partially binary rule can illustrate this kind of customer behavior very well. To eliminate the gap between current rules and this kind of customer behavior is the motivation of our paper. In fact, the partially proportional rule with a threshold is proposed for this purpose.

The remainder of the paper is organized as follows: Section 2 is devoted to present the definition of the partially proportional rule with a threshold and to propose a competitive facility location model with foresight. Section 3 proposes an improved ranking-based greedy algorithm to solve the presented model. Section 4 illustrates the effectiveness of the algorithm through numerical tests, the effects of different factors on the market share are also analyzed in a quasi-real example. Finally, some conclusions are presented in section 5.

2 Model description

2.1 Customer choice behavior

In this section, we first propose a suitable rule to describe the behavior of customers when they faced the choice of competitive chain facilities that offer exclusive services. Suppose there are several firms in the competitive market, each firm offers exclusive service through its facilities. The attraction of a firm is defined as the sum of attraction of its facilities. A customer only chooses one of these services due to the exclusiveness of these services. If a customer chooses one of the firms, he (or she) can be serviced by any chain facility of this firm. In order to describe well the behavior pattern of customers when faced with this choice. The Partially Proportional Rule defined as follows: A customer chooses the most attractive firm from all firms at first, then splits his (or her) demands on facilities of the selected firm in proportion to its attraction. In addition, in many cases, when the attractiveness of two firms is not much different for the customer, the customer will think that the two firms have o essential difference, and therefore any firm will be selected for consumption with the same probability. Hence, the Partially Proportional Rule with a Threshold can be regarded as a generalized version of the former defined rule. That is, let the maximal attraction of all firms be G. For firms with attraction in the interval [Gδ, G], the customer selects any of these firms with the same probability and then patronizes the facilities of the selected firm in proportion to their attractiveness.

We present an example to illustrate the partially proportional rule with a threshold. Suppose that there are three firms A, B, and C in the competing market. Firm A has four facilities 1, 4, 5, 9; firm B has three facilities 3, 6, 7; and firm C has three facilities 2, 8, 10. Suppose that for the customer, the attraction a(k) of each facility k is equal to its number, i.e. a(k) = k. The patronizing patterns under the partially proportional rule with different thresholds are shown in Fig 1 as follows.

Example for the partially proportional rule with a threshold.
Fig. 1. Example for the partially proportional rule with a threshold.

In Fig 1, the total attraction of the firm A, B, C are 19, 16 and 20, respectively. Hence, if the customer following the partially proportional rule with a threshold δ = 0.5, he chooses the firm C and splits his demand on facilities 2, 8, 10 in proportional to 2/20, 8/20 and 10/20. If the customer following the partially proportional rule with the threshold δ = 1, then firm A and C are no different for this customer. Hence, the customer first selects firm A or C with the same probability, i.e. p = q = 1/2, and then patronizes the facilities of the selected firm in proportion to its attractiveness.

2.2 Proposed model

A two-dimensional market region is considered in this paper. Suppose that the demand is concentrated on M points. Two competitive firms are referred to as the leader and the follower. The leader intends to open p chain facilities in the set of potential facility locations, with belief that the follower will respond to his action by launching q facilities. It is assumed that only one facility can be opened at each potential location. Both firms offer exclusive services through their chain facilities to compete for market share. So the partially proportional rule with a threshold is suitable to describe the customer behavior for this kind of competitive facility location problem.

The following notations are used:

i, I: index and set of demand points (customers);

JL: potential facility locations of the leader firm;

JF: potential facility locations of the follower firm;

δ: the threshold in the partially proportional rule;

wi: demand of the customer i;

dij: distance between customer i and facility j;

qij: quality that customer i feels from facility j;

p: the number of new facilities that the leader firm want to open;

q: the number of new facilities that the follower firm want to open;

y j L , j ∈ J L : binary variable y j L = 1 if new facility j is open by leader firm and 0 otherwise;

y j F , j ∈ J F : binary variable y j F = 1 if new facility j is open by follower firm and 0 otherwise;

M i L : the proportion of demand that the leader firm captured from customer i;

M i F : the proportion of demand that the follower firm captured from customer i.

In this paper, the facility attractiveness level is relate to quality and a reverse one with the distance between the facility and the customer. According to this, the attractiveness level of facility j for customer i equals:


In Eq (1), 1 is added to (dij)α to avoid the denominator becoming 0 when the distance between the facility and the customer is 0. The parameter α usually takes the value 1 or 2. The total attractions that customer i feels from the leader firm and the follower firm are ∑ j ∈ J L A i j y j L and ∑ j ∈ J F A i j y j F, respectively. Suppose that the location plan (yL) of the leader firm has been determined, then the proportion of demand that the follower firm captured from customer i can be expressed as:


Obviously, the proportion of demand that the leader firm captured from customer i is M i L = 1 - M i F. Therefore, the competitive facility location problem with foresight can be formulated as the following bi-level programming model:

Upper level (Leader Model):



Here, yF, for each value of yL, is the optimal solution of the lower level problem:

Lower level (Follower model):



Although the expression of Mi looks difficult to establish linear model, the follower problem can be formulated as an integer model by introducing two 0-1 variables x+ and x:



Note that if ∑ j ∈ J L A i j y j L + δ < ∑ j ∈ J F A i j y j F then maximizing the objective function makes x i + = 1 while at the same time ∑ j ∈ J L A i j y j L - δ ≤ ∑ j ∈ J F A i j y j F implies x i - = 1. In this case, the follower firm get the total demand of customer i. If ∑ j ∈ J L A i j y j L - δ ≤ ∑ j ∈ J F A i j y j F ≤ ∑ j ∈ J L A i j y j L + δ, then x i + = 0 and x i - = 1 are true, the proportion of demand that the follower firm captured from customer i is 1/2. At last, ∑ j ∈ J F A i j y j F < ∑ j ∈ J L A i j y j L - δ implies that x i + = 0 , x i - = 0, the demand of customer i is totally captured by the leader firm.

3 Solution method

Hansen et al. [35] indicated that the bi-level programming model is NP-hard even for the simplest linear-linear problem. Bi-level programming problems are very sensitive to constraints, so the solution space is completely changed by the very different constraints in our lower-level model (7-8). Mirzaei et al. [36] introduced four types of exact algorithms to solve the bi-level competitive facility location problem. But these algorithms cannot solve our problem directly due to the special structure of our lower-level model. In addition, for large scale problems, these algorithms cannot get an exact solution in a short time.

Two heuristic algorithms that based on ranking strategy are proposed by Fernández et al. [27]. Numerical tests show that the ranking strategy is effective to find near optimal solutions of the static competitive facility location problems. In order to solve the leader-follower model of the competitive facility location problem under the partially proportional rule with a threshold. We adopt the ranking-based heuristic algorithm as the framework of the main algorithm. Then for any given solution of the leader model, an efficient sub-algorithm is presented to solve the follower model. This sub-algorithm is designed on the greedy strategy and the 2-opt strategy as follows:

Greedy-based Follower Algorithm (GFA):

0. Input a solution of the leader firm yL and the lower bound Z ¯ F _;

1. Let y j N : = 0 , ∀ j ∈ J F, and let J F 1 = { j ∈ J F | y j L = 1 }; % here y j N is used to indicate the current location of the follower firm;

2. While q ≥ 1 do:

   Let J F N : = { j ∈ J F | y j N = 0 } \ J F 1; % here J F N is used to represent the set of all current optional locations of the follower firm;

   For each k ∈ J F N:

    Let y k F : = 1 , y j F : = 0 , ∀ j ∈ J F , j ≠ k;

    Let yFyF + yN calculate Z k F ≜ Z F ( y L , y F );

    If Z k F ≥ Z ¯ F _,

     then stop and return y ˜ F : = y F , Z ˜ F : = Z F ( y L , y ˜ F ) _;

    End if;

   End for;

   Select y ˜ F : = a r g m a x { Z k F | k ∈ J F N }, and let Z ˜ F : = Z F ( y L , y ˜ F ) , y N : = y ˜ F and qq − 1;

3. End while;

4. Let D 1 : = { j ∈ J F | y ˜ F = 1 } , D 0 : = { j ∈ J F | y ˜ F = 0 } \ J F 1;

5. For each iD1

   For each jD0

     y t e m p : = y ˜ F , y t e m p ( i ) : = 0 , y t e m p ( j ) : = 1 ; Calculate z t e m p : = Z j F ( y L , y t e m p );

     If Z ˜ F < z t e m p,

      then y ˜ F : = y t e m p , Z ˜ F : = z t e m p;

     End if;

   End for;

  End for;

6. Stop and return y ˜ F and Z ˜ F.

Note that (GFA) is an algorithm based on the greedy strategy and the 2-opt strategy. The step (2-3) is the greedy strategy that follower chooses the best facility one by one. The step 5 of the algorithm (GFA) is the 2-opt strategy. Note that if we take Z ¯ F : = ∞, it is obvious that the result of the algorithm (GFA) is not affected by this lower bound. In fact, the underlined parts about the lower bound Z ¯ F are used to accelerate the algorithm from the viewpoint of the leader firm. The lower level problem can be solved quickly by this algorithm while maintaining a relatively high approximation of the solution. The comparison of the algorithm (GFA) and the direct method to solve model (7-8) is presented in the next section.

Before we give the algorithm to solve the problem, let’s take a look at the following conclusion: Suppose that among all the leader’s facility location schemes currently known, the maximal market share captured by the leader firm is Z ¯ L. Then for any new solution of the leader (y ˜ L), once there is a solution of the follower (yF) such that ∑ i ∈ I w i M i L ( y ˜ L , y F ) = ∑ i ∈ I w i ( 1 - M i F ( y ˜ L , y F ) ) < Z ¯ L, the optimal solution of the leader cannot be y ˜ L, this is equivalent to the abort condition in step 2 of the sub-algorithm (GFA): Z k F ≥ Z ¯ F. Based on the above conclusion, we proposed an improved ranking-based greedy algorithm by embedding the algorithm (GFA) as follows:

Improved Ranking-Based Greedy Algorithm (IRGA):

1. Input the parameter T, which indicates the number of iterations of the algorithm. Generate a random solution yLD(L), call algorithm (GFA) to get y ˜ and Z ˜ F by inputting the leader’s solution yL and the lower bound Z ¯ F : = ∞, then update Z ¯ F : = Z ˜ F ( y L , y ˜ F ) _;

2. While T > 0, do:

  Let Y 1 = { j ∈ J L | y j L = 1 } , Y 0 = { j ∈ J L | y j L = 0 };

  Randomly choose j1Y1, j2Y0, let y ˜ L : = y L , y ˜ L ( j 1 ) : = 0 , y ˜ L ( j 2 ) : = 1;

  Call (GFA) with y ˜ L _ and the lower bound Z ¯ F _ to get y ˜ F and Z ˜ F ( y ˜ L , y ˜ F ), update Z ¯ F : = min { Z ¯ F , Z ˜ F ( y ˜ L , y ˜ F ) } _.

  If Z F ( y ˜ L ) < Z F ( y L ),

   then r j 1 : = r j 1 - 1 , r j 2 : = r j 2 + 1;

   else r j 1 : = r j 1 + 1 , r j 2 : = r j 2 - 1;

  End if;

  If any rj = 0,

   then set rjrj + 1 for all jJL;

  End if;

  Generate a new solution yLD(L) according to the probability p j : = r j / ∑ j ∈ J L r j, and update TT − 1.

3. End while.

4. Return yL, ZF(yL), and Z L = ∑ i ∈ I w i − Z F ( y L ).

From (IRGA), we know that the lower bound Z ¯ F interacts between the leader problem and the follower problem. By updating the minimal known Z ¯ F timely, numerous calculating process can be eliminated while maintaining the optimality of the solution.

4 Numerical example

In this section, we first provide computational experiments to evaluate the performance of the proposed algorithm. For this purpose, we generate some problems with different scales to test the proposed algorithm. After proving the effectiveness of the algorithm, we present a quasi-real example to analysis affections of different factors.

4.1 Performance of the algorithm

To evaluate the performance of the algorithm (IRGA), we make three type of numerical tests as follows: (1) Test the performance of the sub-algorithm (GFA), the key performance measure is the average gap between ZF(yL) given by (GFA) and Z e x a c t F ( y L ) given by the exact method, where yL is given randomly; (2) Test the performance of the algorithm (IRGA) for small scale problems, the key performance measure is the average gap between the value of ZL obtained by (IRGA) and the exact optimum Z e x a c t L obtained by the enumeration method; (3) Test the performance of the algorithm (IRGA) for large scale problems, the key performance measure is the gap between the average value of ZL and the maximum value of ZL for multiple random calculations.

For the first type of tests, we generate 9 problems with different scales to test the effectiveness of (GFA). In these random test problems, customers and potential facility locations are all locate in the region [1, 100] × [1, 100]. The coordinates of these points are taken from the integer points of this region in random. The qualities of the facilities are taken as 1. The demands of customers’ wi are random integer numbers chosen from the interval [0, 100]. The distance between two points (xi, yi) and (xj, yj) is the Euclidean distance (d i j = ( x i - x j ) 2 + ( y i - y j ) 2). The distances used in numerical tests are relatively small due to the limitation of the region, so we set the value of α to 2 to avoid the situation where the attractiveness of firms are too close. According to subsection 2.2, we know that the equivalent model (7-8) of the follower problem can be solved directly using some commercial software. For each test problem, we generate 10 solutions for the leader’s firm in random, then compare solutions of the follower’s problem that get from the direct method and the algorithm (GFA). The direct method is implemented by using the Cplex software. The algorithm (GFA) is implemented in the Matlab R2015b and run on a portable computer with an Intel Core i5 Processor (2.5 GHZ) and 8 GB memory. Comparisons of this direct method and the algorithm (GFA) are presented in Table 2. Note that here the lower bound is Z ¯ F : = ∞.

Tab. 2. Comparison of direct method with greedy-based follower algorithm (p = q).
Comparison of direct method with greedy-based follower algorithm (<i>p</i> = <i>q</i>).

In Table 2, the average times of the direct method and the algorithm (GFA) are TD and TG, respectively. For a given leader’s solution yL, suppose that the market shares captured by the follower according to the direct method and the (GFA) are Z D F ( y L ) and Z G F ( y L ), respectively. For these randomly generated leader’s solutions yL, the Gap1 in Table 1 is the average of gap(yL) which is defined as follows: g a p ( y L ) : = Z D F ( y L ) - Z G F ( y L ) Z D F ( y L ). From Table 2, we know that solutions get from the algorithm (GFA) are very close to the corresponding exact solutions get from the direct method. On the other hand, the times required by the algorithm (GFA) is dramatically less than the times required by the direct method, especially when the scales of problems are relatively large. It can also be seen from Table 2 that for a given solution of the leader firm, the average gap between the sub-algorithm (GFA) and the exact method increases with q. Alekseeva et al. [37] observed that under fixed value of M and N, the leader-follower competitive facility location problem becomes more difficult when p = q = [N/3]. In this case, a lot of calculation time is required to solve the follower’s problem and check the feasibility of the bi-level structure. Most of the literature mentioned in Table 1 that considers foresight can only solve small scale problems within q < 10. So from a perspective of computation time, we believe that for medium scale problem, (GFA) is a good heuristic method to solve the follower’s problem.

For the second type of tests, we generate 12 smaller-scale random problems as described above to evaluate the gap between the solution obtained by the algorithm (IRGA) and the exact solution. Each random problem has the number of customers is M = 50 and the number of potential facility locations is N = 20, the exact solution of the problem is solved by the enumeration method. The algorithm (IRGA) run 10 times for each problem. The maximum (Z m a x L), the minimum (Z m i n L), the average (Z a v g L), and the standard deviation (Z s t d L) of these 10 objective function values are list in Table 3. The Gap2 in Table 3 is defined as follows: G a p 2 = Z e x a c t L - Z a v g L Z e x a c t L. From Table 3, we know that the optimal performance of (IRGA) is good. The percentage of gap between the solution obtained by (IRGA) and the optimal solution is quite small in all test problems.

Tab. 3. Optimal performance tests of the (IRGA) (M = 50, N = 20).
Optimal performance tests of the (IRGA) (<i>M</i> = 50, <i>N</i> = 20).

For the third type of tests, we generate 9 large-scale examples to evaluate the stability of the algorithm (IRGA). For each example, the algorithm (IRGA) run 10 times to get solutions. All of the results are presented in Table 4. The Gap3 in Table 4 is defined as follows: G a p 3 : = Z m a x L - Z a v g L Z m a x L. From Table 4, it is obvious that the algorithm (IRGA) is stability both in the standard deviation of ZL and the gap between the average and the maximal of ZL.

Tab. 4. Stability of the algorithm (IRGA) for large scale examples.
Stability of the algorithm (IRGA) for large scale examples.

4.2 A quasi-real example

In this subsection, we consider the 49-nodes data set that described in Daskin [34]. In this data set, the 49-nodes denote the capitals of the continental United States plus Washington, DC. The demands are proportional to the 1990 state populations. The latitudes and longitudes of these 49 nodes are given in the data set. So we take the geodesic distances as the dij. Since the geodesic distances are relatively large, we set the value of α to 1 to more clearly reflect the effect of the threshold δ. The leader firm aims at opening p facilities and knows that the follower will open q facilities after her action. Each customer’s location can be used as a potential facility location both for the leader firm and the follower firm.

For different p and q, suppose that the customers following the partially proportional rule with a threshold δ = 0.001, the optimal solutions are presented in Table 5 as follows. From Table 5, the number of the opening facility is most important for the market share captured by the leader firm or follower firm. If p > q, then the market share captured by the leader firm large than the market share captured by the follower firm, and vice versa. For a fixed number of q, the market share captured by the leader firm increases with the increases in the number of p. Conversely, for a given p, the market share gained by the leader firm decreases as q increases.

Tab. 5. Optimal solutions for different (p, q) (δ = 0.001).
Optimal solutions for different (<i>p</i>, <i>q</i>) (<i>δ</i> = 0.001).

In order to investigate the effect of the threshold δ, let δ change from 0.001 to 0.010 in steps of 0.001. Suppose that the leader firm has the same number of facilities as the follower firm, that is p = q = 3. The optimal solutions corresponding to these different thresholds are listed in Table 6. From Table 6, we know that even if the location of the leader’s facilities remains the same, the location of the follower’s facilities may change with the threshold δ. From the overall trend, the market share captured by the leader firm ZL increases with the increases of the threshold δ. Another interesting result is: although the leader firm can choose the facility locations before the follower firm, it does not have a first-mover advantage when the threshold δ is small.

Tab. 6. Effect of the threshold δ (p = q = 3).
Effect of the threshold <i>δ</i> (<i>p</i> = <i>q</i> = 3).

The patronizing patterns of the customers between the leader firm and the follower firm when δ = 0.003 and δ = 0.004 are shown in Table 7. In Table 7, the second and the third columns denote the customers completely captured by the leader firm and by the follower firm, respectively. The states with underlines denote the facility locations of the two firms. For each δ, the demands of all remaining customers not mentioned in Table 7 are evenly distributed between the two firms. From Table 7, we find that as δ changes from 0.003 to 0.004, the leader firm’s facility location scheme remains the same, but the follower firm’s location scheme is completely changed. If the follower firm’s location scheme remains unchanged, i.e. in states of Mississippi, New York and Ohio, then the market share captured by the follower firm is 1187.1. However, by changing its location scheme to new locations of Alabama, Louisiana, and New Jersey. The market share captured by the follower firm can be added to 1255.6.

Tab. 7. Customers completely captured by the leader and the follower firms for different δ (p = q = 3).
Customers completely captured by the leader and the follower firms for different <i>δ</i> (<i>p</i> = <i>q</i> = 3).

Suppose that p = q, for threshold δ = 0 and δ = 0.02, the effects of different p on the market share captured by the leader firm and the follower firm are presented in Table 8.

Tab. 8. Effect of the number of facilities p for small and large threshold (p = q).
Effect of the number of facilities <i>p</i> for small and large threshold (<i>p</i> = <i>q</i>).

In order to illustrate the relationship between the market share and p clearly, the results of Table 8 are shown in Fig 2. From Fig 2, we find that for small δ, the value of ZL(p) decreases first and then increases with the increases of p. For large δ, the value of ZL(p) increases with the increases of p. Suppose that p = q, then we can get an interesting conclusion. That is, only for the competitive facility location problem with a large δ or a large p, there is a first-mover advantage for the leader firm.

Example for the partially proportional rule with a threshold.
Fig. 2. Example for the partially proportional rule with a threshold.

5 Conclusion

In this paper, we studied the competitive facility location problem in the framework of the leader-follower game. The partially proportional rule with a threshold is presented in this paper. This rule is suitable to describe customer behaviors when they are facing the choice of competitive chain facilities that offer exclusive services. A greedy based algorithm is proposed to solve the follower’s problem after given the facility locations of the leader. By embedding the greedy-based follower algorithm, an improved ranking based facility location algorithm is given to solve the problem. Numerical tests about the greedy-based follower algorithm and the ranking-based greedy algorithm show that the algorithm proposed in this paper can solve the competitive facility location problem effectively. Through detailed analysis of a quasi-real example, the effects of different parameters on the market share captured by the leader firm and the follower firm are presented. An interesting conclusion is that in some cases, there is no first-mover advantage for the leader firm.

As future directions, one can consider the competitive facility location problem with a limited budget under the partially proportional rule with a threshold. And the uncertainty of the threshold can be considered in the problem. From the computational point of view, the design of effective algorithms to solve these problems is another field for research.

Supporting information

S1 File [xlsx]
The data set of the 49-nodes example in subsection 4.2 is provided as S1 File.


Zdroje

1. Santos-Peñate DR, Suárez-Vega R, Dorta-González P. The leader-follower location model. Networks & Spatial Economics. 2007 Mar;7(1):45–61. doi: 10.1007/s11067-006-9007-2

2. Floudas CA, Pardalos PM. Encyclopedia of optimization. Berlin, Heidelberg and New York: Springer-Verlag.; 2009.

3. ReVelle CS, Eiselt HA, Daskin MS. A bibliography for some fundamental problem categories in discrete location science. European Journal of Operational Research. 2008 Feb;184(3):817–848. doi: 10.1016/j.ejor.2006.12.044

4. Plastria F. Static competitive facility location: An overview of optimisation approaches. European Journal of Operational Research. 2001 Mar;129(3):461–470. doi: 10.1016/S0377-2217(00)00169-7

5. Ashtiani MG, Makui A, Ramezanian R. A robust model for a leader-follower competitive facility location problem in a discrete space. Applied Mathematical Modelling. 2013 Jan;37(1-2):62–71. doi: 10.1016/j.apm.2011.12.013

6. Drezner T, Drezner Z. Finding the optimal solution to the Huff based competitive location model. Computational Management Science. 2004 July;1(2):193–208. doi: 10.1007/s10287-004-0009-6

7. Drezner T, Drezner Z, Zerom D. Competitive facility location with random attractiveness. Operations Research Letters. 2018 May;46(3):312–317. doi: 10.1016/j.orl.2018.02.008

8. Campos CM, Santos-Peñate DR, Moreno JA. An exact procedure and LP formulations for the leader-follower location problem. TOP. 2010 July;18(1):97–121. doi: 10.1007/s11750-009-0117-0

9. Bilir C, Ekici SO, Ulengin F. An integrated multi-objective supply chain network and competitive facility location model. Computers & Industrial Engineering. 2017 June;108:136–148. doi: 10.1016/j.cie.2017.04.020

10. Suárez-Vega R, Santos-Peñate DR, Dorta-González P. The follower location problem with attraction thresholds. Papers in Regional Science. 2007 Mar;86(1):123–137. doi: 10.1111/j.1435-5957.2007.00104.x

11. Grohmann S, Urošević D, Carrizosa E, Mladenović N. Solving multifacility huff location models on networks using metaheuristic and exact approaches. Computers & Operations Research. 2017 Feb;78:537–546. doi: 10.1016/j.cor.2016.03.005

12. Shiode S, Yeh KY, Hsia HC. Optimal location policy for three competitive facilities. Computers & Industrial Engineering. 2012 Apr;62(3):703–707. doi: 10.1016/j.cie.2011.12.019

13. Shiode S, Drezner Z. A competitive facility location problem on a tree network with stochastic weights. European Journal of Operational Research. 2013 Aug;149(1):47–52. doi: 10.1016/S0377-2217(02)00459-9

14. Fernández J, G.-Tóth B, Redondo JL, Ortigosa PM. A planar single-facility competitive location and design problem under the multi-deterministic choice rule. Computers & Operations Research. 2017 Feb;78:305–315. doi: 10.1016/j.cor.2016.09.019

15. Fernández J, G.-Tóth B, Redondo JL, Ortigosa PM. The probabilistic customer’s choice rule with a threshold attraction value: effect on the location of competitive facilities in the plane. Computers & Operations Research. 2019 Jan;101:234–249. doi: 10.1016/j.cor.2018.08.001

16. Gilbride TJ, Allenby GM. A choice model with conjunctive, disjunctive, and compensatory screening rules. Marketing Science. 2004 June;23(3):391–406. doi: 10.1287/mksc.1030.0032

17. Hotelling H. Stability in competition. The Economic Journal. 1929 Mar;39(153):41–57. doi: 10.2307/2224214

18. Huff D. Defining and estimating a trade area. Journal of Marketing. 1964 July;28(3):34–38. doi: 10.2307/1249154

19. Hakimi SL. Location with spatial interactions, competitive locations. In Mirchandani PB, Francis RL, editors. Discrete location theory. John Wiley & Sons, New York: 1990.

20. Suárez-Vega R, Santos-Peñate D, Dorta-González P. Discretization and resolution of the (r|Xp)-medianoid problem involving quality criteria. TOP. 2004 June;12(1):111–133. doi: 10.1007/BF02578927

21. Peeters PH, Plastria F. Discretization results for the huff and pareto-huff competitive location models on networks. TOP. 1998 Dec;6(2):247–260. doi: 10.1007/BF02564790

22. Serra D, Colomé R. Consumer choice and optimal location models formulations and heuristics. Papers in Regional Science. 2001 Oct;80(4):439–464. doi: 10.1111/j.1435-5597.2001.tb01213.x

23. Beresnev V. Branch-and-bound algorithm for a competitive facility location problem. Computers & Operations Research. 2013 Aug;40(8):2062–2070. doi: 10.1016/j.cor.2013.02.023

24. Fernández J, Hendrix EM. Recent insights in Huff-like competitive facility location and design. European Journal of Operational Research. 2013 June;227(3):581–584. doi: 10.1016/j.ejor.2012.12.032

25. Fernández J, Salhi S, Tóth BG. Location equilibria for a continuous competitive facility location problem under delivered pricing. Computers & Operations Research. 2014 Jan;41:185–195. doi: 10.1016/j.cor.2013.08.004

26. Biesinger B, Hu B, Raidl G. Models and algorithms for competitive faciltity location problems with different customer behaviour. Annals of Mathematics and Artificial Intelligence. 2016 Feb;76(1-2):93–119. doi: 10.1007/s10472-014-9448-0

27. Fernández P, Pelegrín B, Lačinskas A, Žilinskas J. New heuristic algorithms for discrete competitive location problems with binary and partially binary customer behavior. Computers & Operations Research. 2017 Mar;79:12–18. doi: 10.1016/j.cor.2016.10.002

28. Qi M, Xia M, Zhang Y, Miao L. Competitive facility location problem with foresight considering service distance limitations. Computers & Industrial Engineering. 2017 Oct;112:483–491. doi: 10.1016/j.cie.2017.04.024

29. Ashtiani MG. Competitive locaiton: a state-of-art review. International Journal of Industrial Engineering Computations. 2016 Sep;7(1):1–18. doi: 10.5267/j.ijiec.2015.8.002

30. Wang X, Ouyang Y. Acontinuum approximation approach to competitive facility location design under facility disruption risks. Transportation Research Part B. 2013 Apr;50:90–103. doi: 10.1016/j.trb.2012.12.004

31. Nasiri M, Mahmoodian V, Rahbari A, Farahmand S. A modified genetic algorithm for the capacitated competitive facility location problem with the partial demand satisfaction. Computers & Industrial Engineering. 2018 Aug;124(1):435–448. doi: 10.1016/j.cie.2018.07.045

32. Kung LC, Liao WH. An approximation algorithm for a competitive facility location problem with network effects. European Journal of Operational Research. 2018 May;267(1):176–186. doi: 10.1016/j.ejor.2017.11.037

33. Casas-Ramírez M, Camacho-Vallejo J, Martínez-Salazar I. Approximating solutions to a bilevel capatitated facility location problem with customer’s patronization toward a list of preferences. Applied Mathematics and Computation. 2018 Feb;319:369–386. doi: 10.1016/j.amc.2017.03.051

34. Zhang Y, Snyder LV, Ralphs TK, Xue Z. The competitive facility location problem under disruption risks. The Transportation Research Part E. 2016 Sep;93:453–473. doi: 10.1016/j.tre.2016.07.002

35. Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming. SIAM Journal of Scientific and Statistical Computing. 1992 Sep;13(5):1194–1217. doi: 10.1137/0913069

36. Mirzaei E, Bashiri M, Shemirani HS. Exact algorithms for solving a bi-level location-allocation problem considering customer preferences. Journal of Industrial Engineering International. 2019 Sep;15(3):423–433. doi: 10.1007/s40092-018-0302-6

37. Alekseeva E, Kochetova N, Kochetov Y, Alexandr P. Heruistic and exact methods for the discrete (r|p)-centroid problem. Evolutionary Computation in Combinatorial Optimization. New York: Springer, 2010.

38. Daskin MS. Network and discrete location: models, algorithms, and applications. New York: Wiley, 1995.


Článok vyšiel v časopise

PLOS One


2019 Číslo 12
Najčítanejšie tento týždeň
Najčítanejšie v tomto čísle
Kurzy

Zvýšte si kvalifikáciu online z pohodlia domova

Získaná hemofilie - Povědomí o nemoci a její diagnostika
nový kurz

Eozinofilní granulomatóza s polyangiitidou
Autori: doc. MUDr. Martina Doubková, Ph.D.

Všetky kurzy
Prihlásenie
Zabudnuté heslo

Zadajte e-mailovú adresu, s ktorou ste vytvárali účet. Budú Vám na ňu zasielané informácie k nastaveniu nového hesla.

Prihlásenie

Nemáte účet?  Registrujte sa

#ADS_BOTTOM_SCRIPTS#