# Location and Design of Urban Facilities considering Competitors’ Responses: A Case Study of Putuo District, Shanghai

Authors: Zhizhu Lai; Ge Yan; Yulong Chen; Zheng Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In view of the problem of competitive facility location in urban planning, the response of competitors to the new facility is considered. We use Huff’s probability model to describe the market share of all facilities which depends on its service quality and its distance from customers. To maximize the market share of facilities, a two-stage method (quality decision stage and location decision stage) is adopted, which takes into account the responses of competitors. In the stage of quality decision, the competitive decision-making process is simulated as a game process and solved by Nash equilibrium. The solution of the quality decision process can be expressed as a function of the new facility’s location which can be obtained by polynomial approximation. In the location decision stage, we apply the interval analysis based on branch and bound algorithm to determine the optimal location of new facility. Then, we use the randomly generated numerical experiment to verify the effectiveness of the model and algorithm. Finally, we apply this model and algorithm to the location of a new shopping mall in Putuo district, Shanghai.


---

## Body

## 1. Introduction

Since the reform and opening-up, China’s economy has developed rapidly, and its urbanization process has also accelerated significantly. A common problem in China’s urban construction is the layout of various facilities in the city, including public facilities and commercial facilities. This type of urban facility layout issues not only include specific facilities such as schools, hospitals, security and disaster-prevention facilities, and shopping malls, but also abstract facilities such as bus lines. As the largest developing country in the world, China’s urban development is very rapid, and a large number of facilities are newly built, put into use, or die out every day. There are a lot of competitive problems in the layout of urban facilities in China, because there are many existing competitive facilities in urban space. The location of new facilities will affect the market share and profits of existing competitors in the market. How to increase their market share and profits in the process of competition is very important.The competitive facility location problem was first proposed by Hotelling [1], which studied how two manufacturers locate on the line segment and assumed that the customers always choose the nearest facility. Drezner [2] and Hakimi [3–5] investigated the competitive facility location on the plane and in a network, respectively. Huff [6, 7] proposed a more reasonable and realistic model, in which the facilities compete for market shares. In this model, it is assumed that the patronage behavior of customers is probabilistic. That is, each customer allocates its purchasing power among the facilities in the market according to their attractiveness. Drezner [8] and Salhi et al. [9] used the Huff market share model to analyze the location problem based on the known quality of the new facilities. Fernandez et al. [10], Tóth et al. [11], and Redondo et al. [12] further considered the issue of competitive facility location including quality decisions. However, most of them did not consider the response of existing facilities in the market.In recent years, with the increasing globalization of market competition, the location of competitive facilities had attracted the attention of many scholars [13–17]. For example, Saidani et al. [15] considered the responses of competitors in the market, constructed the facility’s market share as a Huff-like probability model, and proposed a new global two-stage method. This model used a simple linear function as the damping factor of the attraction of the facilities, and its calculation is simple but not in line with reality.In fact, the existing literature mostly adopts linear form of the damping factor when considering the attraction function of the facilities. Although the linear damping factor has the advantage of being simple and easy to understand, the customer’s behavior of choosing a facility is not based on the distance of the direct distance, but it shows an exponential decline. Therefore, we use the Wilson model [18] to redefine the damping factor of attraction function of the facility. In addition, the density and broad market of commercial outlets in the cities of China have further stimulated the development of various competitive facilities. It is of great practical and theoretical significance to study the layout of such competitive urban facilities.Therefore, on the basis of previous studies, this paper studies the location and design of competitive urban facilities with competitors’ response in the context of new commercial facilities in Putuo district, Shanghai. Considering the damping factor of Wilson’s form, Huff’s model and Nash equilibrium are constructed. Finally, a global two-stage heuristic method is used to solve the problem.The rest of this paper is organized as follows. In Section2, we develop the competitive facility model to determine the market share and service quality of the new facility. In Section 3, we design the two-stage approach and make an equilibrium analysis and then propose the polynomial approximation of quality function and interval branch and bound algorithm. The effectiveness of the proposed model and algorithm is verified by the random examples in Section 4, and a practical case is given in Section 5. Finally, Section 6 summarizes our findings and conclusions.


## 2. Model Construction

Given the high cost of relocating existing facilities, we assume that competitors can only compete with new facilities by improving their own service quality level to minimize the loss of market share. Fernandez et al. [10] and Tóth et al. [11] have studied the location and design of Huff’s competitive facilities, but this study did not consider the response of competitors to market share loss. The basic principle of Huff’s model is the spatial interaction force. The attraction of facilities to consumers and the resistance of customers to facilities jointly determine the scale of facilities. In short, the service quality of a facility is directly proportional to its attractiveness to customers and inversely proportional to the distance from customers to the facility.The problem can be described as how to maximize market share or profits by finding a new position in a competitive market with multiple existing facilities. On the other hand, the existing facilities can maximize their market share or profit level by updating their service quality level. In this problem, each demand point represents customers located in a small area around this point. Each demand point has a purchasing power, which represents the joint purchasing potential of all customers at this demand point. In order to estimate the market share of each facility, this study adopts the model proposed by Huff [7]. The behavior of customers seeking services from facilities in the market is probabilistic, or the facilities in the market divide the purchasing power of each customer in proportion to their attractiveness. Furthermore, we assume that the quality level of the new facility is given [8, 19]. For modelling convenience, we define the following notations (Table 1).Table 1
Notations.
SymbolsDescriptionIThe set of demand point, indexed byi and I=n.JThe set of existing facility, indexed byj and J=m.pi=pi1,pi2Location of theith demand pointwiPurchasing power of theith demand pointfj=fj1,fj2Location of thejth existing facilityx=x1,x2Location of the new facilityα0>0Quality level of the new facilityαj′,αj>0Old and new quality level of thejth existing facility, respectivelyβ0,βjUpgrade cost for unit quality level of the new andjth existing facility, respectivelyγiQuality weight of theith demand pointλiDistance weight of theith demand pointdminMinimal distance between demand point and facilitydijDistance between theith demand point and the jth existing facilitydi0Distance between theith demand point and the new facilityαmin,αmaxQuality level range for all facilitiesgi⋅Nonnegative and nondecreasing damping factor in attractive functionαij/gidijAttraction that theith demand point has for the jth facilityαi0/gidi0Attraction that theith demand point has for the new facilitycIncome from the sale of unit goodsIn this work, we choose the Euclidian distance for the distance between demand point and facilities, so we havedij=pi1−fj12+pi2−fj22 and di0=pi1−x12+pi2−x22. As for damping factor in attractive function, most existing researches define it as gidij=λidij (for example, [15]). We believe that the linear form of the damping factor cannot really express the characteristics of the space. In this study, we use Wilson’s model [18] to define the damping factor as gidij=expλidij. In our study, λi is the facility distance weight of ith demand point (while in Wilson’s model, we call it the spatial damping coefficient).How to set the spatial damping coefficient in Wilson model? Li et al. [20] calculated the damping coefficients of tourism space interactions at four scales: province, prefecture, county, and township. The results showed that the spatial damping coefficient increases with the decrease of domain scale, and the spatial damping coefficient at adjacent scales has a proportional relationship of about 3.18 times. In this study, the service distance of facilities is obviously smaller than that of township, which can be regarded as community scale. Therefore, we set the spatial damping coefficient of the Wilson model in this study to 0.05.To determine the profit function of the facility, it is necessary to determine the market share of each facility. Therefore, we split the overall market demand into different facilities to determine the market share of the new and existing facilities. According to the Huff model, the attractiveness of each facility to a demand point is proportional to its quality level and negatively exponential to the distance from facility to demand point. According to the previous attraction formula, the market share of the new facility can be expressed as(1)M0x,α0,α1,…,αm=∑i=1nwiγiα0e−λidi0γiα0e−λidi0+∑k=1mγiαke−λidik=∑i=1nwiα0e−λidi0α0e−λidi0+∑k=1mαke−λidik.The market share of thejth facility can be expressed as(2)Mjx,α0,α1,…,αm=∑i=1nwiαje−λidijα0e−λidi0+∑k=1mαke−λidik,j=1,…,m.In this study, the goal of the new facility is to maximize its profit by choosing the best location and best quality level. However, due to the inertia of existing facilities, existing facilities cannot change their locations but rather adjust their best quality level to minimize their loss of market shares or profits.For all facilities, the profit is determined by their market shares and costs, so the profit function of thejth facility can be expressed as(3)πjx,α0,α1,…,αm=FMjx,α0,α1,…,αm−Gαj.Here, the nondecreasing functionGαj gives operating cost of the facility with quality level value of αj. In this model, we consider the linear operating cost function Gαj=βjαj. F⋅ is a strictly increasing function that translates market share into expected sales revenue. According to Fernandez [10], we let profit function be FMjx,α0,α1,…,αm=cMjx,α0,α1,…,αm. Under the above assumptions, the profit function of the new facility can be described as follows:(4)π0x,α0,α1,…,αm=c∑i=1nwiα0e−λidi0α0e−λidi0+∑k=1mαke−λidik−β0α0.The profit function of thejth existing facility in the market is(5)πjx,α0,α1,…,αm=c∑i=1nwiαje−λidijα0e−λidi0+∑k=1mαke−λidik−βjαj−αj′,j=1,…,m.Therefore, the location and quality design of the new facility can be summarized as follows:(6)maxπ0x,α0,α1,…,αm=c∑i=1nwiα0e−λidi0α0e−λidi0+∑k=1mαke−λidik−β0α0s.t.di0≥dmin,∀i∈I,α0,αj≥αmin,∀j∈J,α0,αj≤αmax,∀j∈J,x∈S⊆R2,where S represents the planar area that can be used as the location of the new facility.Formula (6) gives only the location and quality design formula for the new facility. The quality level of existing facilities in the market will change with competition as new facilities enter the market. The process of competition will be described in detail in the equilibrium analysis section.


## 3. Algorithm Design

### 3.1. Two-Stage Approach

Due to the high cost of relocate existing facilities, the existing facilities in the market can only increase their market shares by improving the quality level. In addition, the location of the new facility does not change the quality level of the existing facility. Therefore, at each stage, each facility needs to make a decision to maximize its own profit, resulting in two stages of location decision and quality decision. Therefore, this study adopts a two-stage approach to solve the problem.The two-stage approach adopted in this study is quite different from the existing studies [21, 22]. Firstly, the existing studies aim to locate a new manufacturing plant on the network and determine its production level, shipment quantity, and price. The objective of this study is to find the location of a new retail facility on the plane and determine its service quality. Secondly, in the two-stage approach of quality decision and location decision, this study proposes a generally effective method for competitive facility location and design problem, which is not achieved in the existing studies. In addition, the partial derivatives generated by sensitivity analysis are used in former study to linearly approximate the response function of competitors. This method is effective only when the response function is linear or approximately linear. In this study, considering the high nonlinearity of the response function, the polynomial approximation algorithm can more effectively approximate the response function.


#### 3.1.1. Quality Decision Stage

In the quality decision-making stage, for any given location of new facilities, each facility seeks its optimal quality level as a response to other facilities’ quality decision. The quality decision process of the facility can be modelled as a game model, and the competitive decision is reflected in this process. In the competitive facility location problem, the game process means that all the facilities in the market choose strategies from their own perspective to maximize their own market shares or profits. The game process is shown in Figure1: the new facilities enter the market and make decisions on the location and quality level, while the existing facilities in the market only choose the quality level. In this way, all the facilities in the market repeatedly receive information from the market and make behavioral decisions, finally reaching a steady state. The solution of the game can be given by the Nash equilibrium equation regarding the location of the new facility. Based on the equalization analysis of all facilities in the quality decision stage, the optimal quality of new facilities is determined by maximizing their market shares or profits. In the stage of location decision, the optimal location is obtained by the interval based on the global optimization algorithm.Figure 1
Flowchart of game.In this study, the existence of Nash equilibrium is tested when there is already one or more facilities in the market. If there is only one facility in the market, the optimal-quality decision of all facilities can be obtained by Nash equilibrium analysis. When there are multiple existing facilities in the market, the best-quality decision of all facilities cannot be obtained directly. Therefore, the polynomial approximation method can be used to approximate the best-quality decision of all facilities. Tobin et al. [21] and Miller et al. [22] adopt this approximate approach and point out that a company seeking to establish new production facility on the network characterized by competition or oligopoly competition needs an economic equilibrium model to describe the existing competition on the network according to the equilibrium price, demand, production level, and shipment quantity.The two-stage approach [21, 22] consists of four steps: (1) find the equilibrium and solve the variational inequality; (2) apply the sensitivity analysis method of variational inequality to solve the economic equilibrium model; (3) use the partial derivative generated by sensitivity analysis to linearly approximate the competitor’s response function; and (4) the response function is incorporated into the profit function to solve the profit maximization problem and determine the optimal location of the new facility. This method is demonstrated by an example of Cournot–Nash oligopoly model.For any given feasible location of the new facility, each facility makes the best-quality decision to maximize its market share or profit by considering the quality choices of its competitors. At this stage, we model the competitive decision-making process of the facility as a noncooperative game, whose solution is given by Nash game equilibrium and can be used as the position function of the new facility, which is called the quality function of facility.


#### 3.1.2. Position Decision Stage

The second stage of the two-stage approach is the location decision stage, which determines the best location for the new facility. The position decision problem can be obtained by changing the quality variable (α0 and αj) of the corresponding quality function of all facilities obtained in the quality decision stage. The problem obtained in this stage is a continuous nonlinear programming with two variables (x1 and x2). To solve this problem, we use the branch and bound algorithm based on interval analysis to solve the nonlinear facility location problem on the plane.


### 3.2. Equilibrium Analysis

The competitive decision-making process of the facility can be modeled as a noncooperative game (abbreviated as quality game hereafter), and the solution of the game can be obtained through the equilibrium analysis of the new facility’s position equation. First, we set the quality level range of each facility asαmin,αmax. In the competitive noncooperative game, existing facilities will minimize their loss of market share by changing their service quality, so the quality decision of each facility is the best response to the quality decision of all other facilities (competitors). For our problem, there is always a Nash equilibrium that can be expressed as a function of new facility’s position. In competitive environment, equilibrium accords with the best-quality decision of all facilities, and this function is then called the best-quality function of facilities, or simple quality function.In the competition process, the best-response method can be derived from Nash equilibrium. According to Nash equilibrium, the optimal value of facility equality satisfies the first-order conditions [23]: the first-order partial derivatives of the profit function with respect to the quality variable must be zero, so we have ∂πj/∂αj=0j=0,…,m. Debreu [24] proved that general equilibrium always exists in perfectly competitive markets. To ensure the existence of Nash equilibrium, we have the following two theorems.Theorem 1.
(see [24]). For each player in a game, if its strategy space is compact and convex, and its profit function is continuous and quasiconcave with respect to its own strategy. Then, there exists at least one pure strategy Nash equilibrium in the game.Since any closed interval in the one-dimensional Euclidean space is compact and quasiconcave, we consider the intervalαmin,αmax as the strategy space of each player. And the profit functions πjj=0,1,2,…,m are continuous and quasiconcave with respect to each player’s quality strategy.Theorem 2.
The profit function of each facility is concave with respect to its quality strategy; then it is quasiconcave.Proof.
To verify the concavity of the profit functions, we only need to prove that the second derivative of each profit function is negative. According to the profit function of the new facility, its second-order partial derivative with respect to quality variable can be calculated as follows:(7)∂2π0x,α0,α1,…,αm∂α02=−2c∑i=1nwi1/e2λidi0∑j=1mαj/eλidijα0/eλidi0+∑k=1mαk/eλidikα0/eλidi0+∑k=1mαk/eλidik4.
According to the profit functions of the existing facilities, their second-order partial derivatives with respect to their quality variables can be calculated as follows:(8)∂2πjx,α0,α1,…,αm∂αj2=−2c∑i=1nwi1/e2λidij∑k=1k≠jmαk/eλidikα0/eλidi0+∑l=1mαl/eλidilα0/eλidi0+∑l=1mαl/eλidil4,j=1,…,m.
The second-order partial derivatives of all profit functions are negative, because the incomec, the distances, the buying power, and the qualities α0,αj are all positive. Therefore, the profit functions of all facilities are concave with respect to its quality variable.
According to Theorems1 and 2, the equilibrium of competitive game process considered in this study always exists. In the case of multiple existing facilities in the market, it is difficult to obtain the best quality of the closed form (analytic expression) in the Nash equilibrium. To obtain the best quality of the facility, we need to solve the following equations:(9)∂π0∂α0=0,∂πj∂αj=0,j=1,…,m.
That is,(10)∂π0∂α0=c∑i=1nwie−λidi0∑j=1mαje−λidijα0e−λidi0+∑j=1mαje−λidij2−β0=0,∂πj∂αj=c∑i=1nwie−λidijα0e−λidi0+∑k=1,k≠jmαke−λidikα0e−λidi0+∑k=1mαke−λidik2−βj=0,j=1,…,m.
Since the above equations are highly nonlinear, it is difficult to solve the equation form≥2. Therefore, we use polynomial approximation to find an approximate expression of the quality function of all facilities, rather than solving the equations accurately.


### 3.3. Polynomial Approximation of Quality Function

To overcome the difficulty in solving the above equations, we choose a polynomial to approximate the quality function. Firstly, a large number of new facilities are generated randomly. According to the equation set (9), the equation set corresponding to the optimal facility quality can be obtained. Second, we consider polynomial interpolation, especially multivariate Lagrange polynomial interpolation [25, 26]. Finally, we choose polynomial approximation that uses the least square method to minimize the sum of squared residuals.Since the specific form of the equation is unknown, the polynomial has the characteristics of simple form and good approximation, and the order of the polynomial determines the form of the polynomial. Therefore, we choose the order of the polynomial to minimize the error. In addition, we assume that the data can be used as a typical sample of the entire data.To evaluate the correlation between the approximate polynomial and the quality function, we first randomly generate 100 points and then calculate the approximate error. This error is a function of the order of the approximate polynomial and can be used as an evaluation criterion for the approximate model. To improve the approximation effect, we study the choice of polynomial order. Figure2 shows the trend of maximum error varying with polynomial order under random experiment involving two existing competitive facilities and a new facility. As can be seen from Figure 2, the maximum error shows a trend of decreasing-stable-rising, so there may be an optimal order to minimize the maximum error. Therefore, this study proposes a heuristic algorithm (as shown in Figure 3) to determine the optimal order of polynomial, where err, ε,degP, and Nmax are the maximum approximate error, the maximum acceptable error, the actual polynomial order, and the maximum polynomial order allowed, respectively.Figure 2
Evolution of maximum error with polynomial order.Figure 3
Flowchart of heuristic algorithm.


### 3.4. Interval Branch and Bound Algorithm

We substitute the quality function obtained in the quality decision-making stage for the best quality of all facilities in the Nash equilibrium and then derive the profit function from model (6). However, the objective function of this model is neither convex nor concave and usually has multiple local optimal solutions. Therefore, an appropriate global optimization technique is needed to obtain the global optimal solution of the nonlinear programming. The interval analysis is usually used to solve such problems. Most of the interval methods of global optimization are based on the branch and bound principle. These methods divide the search interval into subintervals (i.e., branches) and eliminate the subintervals without global minimum by using the bound of the objective function.Interval analysis method can give the bound of the objective function in the subinterval, but it does not necessarily provide an exact range, and a subinterval is required to ensure that the range is included. It is a key problem in interval analysis to find a clearer bound of objective function with appropriate computation.The main steps of interval branch and bound method are as follows:Step 1. Set Y=Y0 and initialize the interval list LW=∅,LS=∅, where Y0,LW,LS are the optimal domain, interval list with subdivided spaces, and solution list that satisfy the termination criteria, respectively.Step 2. Choose a coordinate direction to split Y.Step 3. According to the number of subdivisions, divide Y in the chosen direction and get the subspace Y1,Y2,…,Ys.Step 4. Determine whether each subspace contains an optimal solution. For each Yi, perform the following steps.(4.1) RemoveYi if it does not contain the optimal solution or reduce Yi if a part of Yi contains the nonoptimal solution.(4.2) IfYi is not removed, then save it (whole or reduced) to the interval list LW.Step 5. Stop the loop if the interval list is empty (i.e., LW=∅).Step 6. Select a space from the interval list and remove it. Let Y represent the space that can be selected.Step 7. If Y satisfies any stopping conditions, add Y to the solution list LS and return to step 5. Otherwise return to step 2.The branch and bound algorithm adopted in this paper is detailed by Fernandez et al. [10]. However, it should be noted that their competitive facility location model does not take into account the responses of existing competitors in the market.


## 3.1. Two-Stage Approach

Due to the high cost of relocate existing facilities, the existing facilities in the market can only increase their market shares by improving the quality level. In addition, the location of the new facility does not change the quality level of the existing facility. Therefore, at each stage, each facility needs to make a decision to maximize its own profit, resulting in two stages of location decision and quality decision. Therefore, this study adopts a two-stage approach to solve the problem.The two-stage approach adopted in this study is quite different from the existing studies [21, 22]. Firstly, the existing studies aim to locate a new manufacturing plant on the network and determine its production level, shipment quantity, and price. The objective of this study is to find the location of a new retail facility on the plane and determine its service quality. Secondly, in the two-stage approach of quality decision and location decision, this study proposes a generally effective method for competitive facility location and design problem, which is not achieved in the existing studies. In addition, the partial derivatives generated by sensitivity analysis are used in former study to linearly approximate the response function of competitors. This method is effective only when the response function is linear or approximately linear. In this study, considering the high nonlinearity of the response function, the polynomial approximation algorithm can more effectively approximate the response function.


### 3.1.1. Quality Decision Stage

In the quality decision-making stage, for any given location of new facilities, each facility seeks its optimal quality level as a response to other facilities’ quality decision. The quality decision process of the facility can be modelled as a game model, and the competitive decision is reflected in this process. In the competitive facility location problem, the game process means that all the facilities in the market choose strategies from their own perspective to maximize their own market shares or profits. The game process is shown in Figure1: the new facilities enter the market and make decisions on the location and quality level, while the existing facilities in the market only choose the quality level. In this way, all the facilities in the market repeatedly receive information from the market and make behavioral decisions, finally reaching a steady state. The solution of the game can be given by the Nash equilibrium equation regarding the location of the new facility. Based on the equalization analysis of all facilities in the quality decision stage, the optimal quality of new facilities is determined by maximizing their market shares or profits. In the stage of location decision, the optimal location is obtained by the interval based on the global optimization algorithm.Figure 1
Flowchart of game.In this study, the existence of Nash equilibrium is tested when there is already one or more facilities in the market. If there is only one facility in the market, the optimal-quality decision of all facilities can be obtained by Nash equilibrium analysis. When there are multiple existing facilities in the market, the best-quality decision of all facilities cannot be obtained directly. Therefore, the polynomial approximation method can be used to approximate the best-quality decision of all facilities. Tobin et al. [21] and Miller et al. [22] adopt this approximate approach and point out that a company seeking to establish new production facility on the network characterized by competition or oligopoly competition needs an economic equilibrium model to describe the existing competition on the network according to the equilibrium price, demand, production level, and shipment quantity.The two-stage approach [21, 22] consists of four steps: (1) find the equilibrium and solve the variational inequality; (2) apply the sensitivity analysis method of variational inequality to solve the economic equilibrium model; (3) use the partial derivative generated by sensitivity analysis to linearly approximate the competitor’s response function; and (4) the response function is incorporated into the profit function to solve the profit maximization problem and determine the optimal location of the new facility. This method is demonstrated by an example of Cournot–Nash oligopoly model.For any given feasible location of the new facility, each facility makes the best-quality decision to maximize its market share or profit by considering the quality choices of its competitors. At this stage, we model the competitive decision-making process of the facility as a noncooperative game, whose solution is given by Nash game equilibrium and can be used as the position function of the new facility, which is called the quality function of facility.


### 3.1.2. Position Decision Stage

The second stage of the two-stage approach is the location decision stage, which determines the best location for the new facility. The position decision problem can be obtained by changing the quality variable (α0 and αj) of the corresponding quality function of all facilities obtained in the quality decision stage. The problem obtained in this stage is a continuous nonlinear programming with two variables (x1 and x2). To solve this problem, we use the branch and bound algorithm based on interval analysis to solve the nonlinear facility location problem on the plane.


## 3.1.1. Quality Decision Stage

In the quality decision-making stage, for any given location of new facilities, each facility seeks its optimal quality level as a response to other facilities’ quality decision. The quality decision process of the facility can be modelled as a game model, and the competitive decision is reflected in this process. In the competitive facility location problem, the game process means that all the facilities in the market choose strategies from their own perspective to maximize their own market shares or profits. The game process is shown in Figure1: the new facilities enter the market and make decisions on the location and quality level, while the existing facilities in the market only choose the quality level. In this way, all the facilities in the market repeatedly receive information from the market and make behavioral decisions, finally reaching a steady state. The solution of the game can be given by the Nash equilibrium equation regarding the location of the new facility. Based on the equalization analysis of all facilities in the quality decision stage, the optimal quality of new facilities is determined by maximizing their market shares or profits. In the stage of location decision, the optimal location is obtained by the interval based on the global optimization algorithm.Figure 1
Flowchart of game.In this study, the existence of Nash equilibrium is tested when there is already one or more facilities in the market. If there is only one facility in the market, the optimal-quality decision of all facilities can be obtained by Nash equilibrium analysis. When there are multiple existing facilities in the market, the best-quality decision of all facilities cannot be obtained directly. Therefore, the polynomial approximation method can be used to approximate the best-quality decision of all facilities. Tobin et al. [21] and Miller et al. [22] adopt this approximate approach and point out that a company seeking to establish new production facility on the network characterized by competition or oligopoly competition needs an economic equilibrium model to describe the existing competition on the network according to the equilibrium price, demand, production level, and shipment quantity.The two-stage approach [21, 22] consists of four steps: (1) find the equilibrium and solve the variational inequality; (2) apply the sensitivity analysis method of variational inequality to solve the economic equilibrium model; (3) use the partial derivative generated by sensitivity analysis to linearly approximate the competitor’s response function; and (4) the response function is incorporated into the profit function to solve the profit maximization problem and determine the optimal location of the new facility. This method is demonstrated by an example of Cournot–Nash oligopoly model.For any given feasible location of the new facility, each facility makes the best-quality decision to maximize its market share or profit by considering the quality choices of its competitors. At this stage, we model the competitive decision-making process of the facility as a noncooperative game, whose solution is given by Nash game equilibrium and can be used as the position function of the new facility, which is called the quality function of facility.


## 3.1.2. Position Decision Stage

The second stage of the two-stage approach is the location decision stage, which determines the best location for the new facility. The position decision problem can be obtained by changing the quality variable (α0 and αj) of the corresponding quality function of all facilities obtained in the quality decision stage. The problem obtained in this stage is a continuous nonlinear programming with two variables (x1 and x2). To solve this problem, we use the branch and bound algorithm based on interval analysis to solve the nonlinear facility location problem on the plane.


## 3.2. Equilibrium Analysis

The competitive decision-making process of the facility can be modeled as a noncooperative game (abbreviated as quality game hereafter), and the solution of the game can be obtained through the equilibrium analysis of the new facility’s position equation. First, we set the quality level range of each facility asαmin,αmax. In the competitive noncooperative game, existing facilities will minimize their loss of market share by changing their service quality, so the quality decision of each facility is the best response to the quality decision of all other facilities (competitors). For our problem, there is always a Nash equilibrium that can be expressed as a function of new facility’s position. In competitive environment, equilibrium accords with the best-quality decision of all facilities, and this function is then called the best-quality function of facilities, or simple quality function.In the competition process, the best-response method can be derived from Nash equilibrium. According to Nash equilibrium, the optimal value of facility equality satisfies the first-order conditions [23]: the first-order partial derivatives of the profit function with respect to the quality variable must be zero, so we have ∂πj/∂αj=0j=0,…,m. Debreu [24] proved that general equilibrium always exists in perfectly competitive markets. To ensure the existence of Nash equilibrium, we have the following two theorems.Theorem 1.
(see [24]). For each player in a game, if its strategy space is compact and convex, and its profit function is continuous and quasiconcave with respect to its own strategy. Then, there exists at least one pure strategy Nash equilibrium in the game.Since any closed interval in the one-dimensional Euclidean space is compact and quasiconcave, we consider the intervalαmin,αmax as the strategy space of each player. And the profit functions πjj=0,1,2,…,m are continuous and quasiconcave with respect to each player’s quality strategy.Theorem 2.
The profit function of each facility is concave with respect to its quality strategy; then it is quasiconcave.Proof.
To verify the concavity of the profit functions, we only need to prove that the second derivative of each profit function is negative. According to the profit function of the new facility, its second-order partial derivative with respect to quality variable can be calculated as follows:(7)∂2π0x,α0,α1,…,αm∂α02=−2c∑i=1nwi1/e2λidi0∑j=1mαj/eλidijα0/eλidi0+∑k=1mαk/eλidikα0/eλidi0+∑k=1mαk/eλidik4.
According to the profit functions of the existing facilities, their second-order partial derivatives with respect to their quality variables can be calculated as follows:(8)∂2πjx,α0,α1,…,αm∂αj2=−2c∑i=1nwi1/e2λidij∑k=1k≠jmαk/eλidikα0/eλidi0+∑l=1mαl/eλidilα0/eλidi0+∑l=1mαl/eλidil4,j=1,…,m.
The second-order partial derivatives of all profit functions are negative, because the incomec, the distances, the buying power, and the qualities α0,αj are all positive. Therefore, the profit functions of all facilities are concave with respect to its quality variable.
According to Theorems1 and 2, the equilibrium of competitive game process considered in this study always exists. In the case of multiple existing facilities in the market, it is difficult to obtain the best quality of the closed form (analytic expression) in the Nash equilibrium. To obtain the best quality of the facility, we need to solve the following equations:(9)∂π0∂α0=0,∂πj∂αj=0,j=1,…,m.
That is,(10)∂π0∂α0=c∑i=1nwie−λidi0∑j=1mαje−λidijα0e−λidi0+∑j=1mαje−λidij2−β0=0,∂πj∂αj=c∑i=1nwie−λidijα0e−λidi0+∑k=1,k≠jmαke−λidikα0e−λidi0+∑k=1mαke−λidik2−βj=0,j=1,…,m.
Since the above equations are highly nonlinear, it is difficult to solve the equation form≥2. Therefore, we use polynomial approximation to find an approximate expression of the quality function of all facilities, rather than solving the equations accurately.


## 3.3. Polynomial Approximation of Quality Function

To overcome the difficulty in solving the above equations, we choose a polynomial to approximate the quality function. Firstly, a large number of new facilities are generated randomly. According to the equation set (9), the equation set corresponding to the optimal facility quality can be obtained. Second, we consider polynomial interpolation, especially multivariate Lagrange polynomial interpolation [25, 26]. Finally, we choose polynomial approximation that uses the least square method to minimize the sum of squared residuals.Since the specific form of the equation is unknown, the polynomial has the characteristics of simple form and good approximation, and the order of the polynomial determines the form of the polynomial. Therefore, we choose the order of the polynomial to minimize the error. In addition, we assume that the data can be used as a typical sample of the entire data.To evaluate the correlation between the approximate polynomial and the quality function, we first randomly generate 100 points and then calculate the approximate error. This error is a function of the order of the approximate polynomial and can be used as an evaluation criterion for the approximate model. To improve the approximation effect, we study the choice of polynomial order. Figure2 shows the trend of maximum error varying with polynomial order under random experiment involving two existing competitive facilities and a new facility. As can be seen from Figure 2, the maximum error shows a trend of decreasing-stable-rising, so there may be an optimal order to minimize the maximum error. Therefore, this study proposes a heuristic algorithm (as shown in Figure 3) to determine the optimal order of polynomial, where err, ε,degP, and Nmax are the maximum approximate error, the maximum acceptable error, the actual polynomial order, and the maximum polynomial order allowed, respectively.Figure 2
Evolution of maximum error with polynomial order.Figure 3
Flowchart of heuristic algorithm.


## 3.4. Interval Branch and Bound Algorithm

We substitute the quality function obtained in the quality decision-making stage for the best quality of all facilities in the Nash equilibrium and then derive the profit function from model (6). However, the objective function of this model is neither convex nor concave and usually has multiple local optimal solutions. Therefore, an appropriate global optimization technique is needed to obtain the global optimal solution of the nonlinear programming. The interval analysis is usually used to solve such problems. Most of the interval methods of global optimization are based on the branch and bound principle. These methods divide the search interval into subintervals (i.e., branches) and eliminate the subintervals without global minimum by using the bound of the objective function.Interval analysis method can give the bound of the objective function in the subinterval, but it does not necessarily provide an exact range, and a subinterval is required to ensure that the range is included. It is a key problem in interval analysis to find a clearer bound of objective function with appropriate computation.The main steps of interval branch and bound method are as follows:Step 1. Set Y=Y0 and initialize the interval list LW=∅,LS=∅, where Y0,LW,LS are the optimal domain, interval list with subdivided spaces, and solution list that satisfy the termination criteria, respectively.Step 2. Choose a coordinate direction to split Y.Step 3. According to the number of subdivisions, divide Y in the chosen direction and get the subspace Y1,Y2,…,Ys.Step 4. Determine whether each subspace contains an optimal solution. For each Yi, perform the following steps.(4.1) RemoveYi if it does not contain the optimal solution or reduce Yi if a part of Yi contains the nonoptimal solution.(4.2) IfYi is not removed, then save it (whole or reduced) to the interval list LW.Step 5. Stop the loop if the interval list is empty (i.e., LW=∅).Step 6. Select a space from the interval list and remove it. Let Y represent the space that can be selected.Step 7. If Y satisfies any stopping conditions, add Y to the solution list LS and return to step 5. Otherwise return to step 2.The branch and bound algorithm adopted in this paper is detailed by Fernandez et al. [10]. However, it should be noted that their competitive facility location model does not take into account the responses of existing competitors in the market.


## 4. Computational Experiments

To evaluate the performance of our approach in multifacility competitive market, a random case with two existing facilities and ten demand points is generated. The data of random cases are shown in Tables2 and 3.Table 2
Coordinates and purchasing power of demand point.
pi1pi2wi7.365183.6054843.961172.0336754.0439377.8610777.6816042.2578017.8108352.4128016.6905719.6514896.1373359.5721286.1290313.4577184.3166516.4765557.2263188.0381424.285831.1722317.9818924.0919281.8078849.952416.3998921.9386452.1180445.730661Table 3
Information of existing facilities and new facility.
fj1fj2βjαj′β0c4.8496650.3825219.287451.13869414.073421.7947326.5565031.89922815.82983.643078——The new quality level of all facilities is solved by Nash equilibrium, and the approximate quality function of all facilities is calculated by polynomial approximation method. The best order of approximation polynomial for quality level of two existing facilities is 4 and 2, respectively. The sum of squared residuals (SSR) for two existing facilities is5.79e−7 and 0.04014, respectively. The approximate quality functions of two existing facilities can be expressed as follows:(11)α1x1,x2=−1.502+7.234x1+12.17x2−5.987x12−4.491x1x2−5.989x22+1.626x13+0.1119x12x2+2.39x1x22+0.6615x23−0.136x14+0.0498x13x2−0.2034x12x22−0.1619x1x23,α2x1,x2=0.6711+0.2241x1+0.2723x2−0.04434x12−0.01724x1x2−0.06469x22.The best order of approximation polynomial for quality level of the new facility is 3 and the sum of squared residuals (SSR) is 0.02389. The approximate quality function of the new facility can be expressed as follows:(12)α0x1,x2=0.2402+0.592x1−0.09393x2−0.01691x12−0.152x1x2−0.009308x22−0.2984x13+0.145x12x2−0.1387x1x22−0.1681x23.The best location of the new facility obtained by interval branch and bound algorithm is (2.3057, 7.8245) and its service quality level is 0.8562.To further analyze the performance of the proposed method, we consider the number of existing facilities in the market as 2, 5, and 10, respectively. We randomly generate competitive markets with demand points of 20, 50, and 100. Since there is no exact algorithm to solve the competitive market with many existing facilities, we use the proposed approach in this study and the partial enumeration method to solve these random cases. The basic idea of partial enumeration is to evenly select a large number of points within the area to which the new facility belongs and find the best location for the new facility among these points.In order to eliminate the randomness of the experiment, we performed a large number of repeated experiments in each case. Table4 gives the average and maximum value of the relative error of the new facilities obtained by our method and partial enumeration methods, where the relative error is the error between our method and partial enumeration method divided by the result of partial enumeration method. As can be seen from Table 4, the average and maximum relative error of our method to partial enumeration are all less than 8%, which shows that the approximate effect of our method is acceptable. Given the number of demand points (20, 50, and 100), when there are few existing facilities (m = 2), the calculation time of partial enumeration method is no more than 4 times that of our method. When the number of existing facilities is 10, the calculation time of partial enumeration method rapidly increases to 10, 50, and 60 times that of our method. This shows that the proposed method is much better than the partial enumeration method in computational efficiency and has practical application advantages.Table 4
Comparison of the two methods.
mnRelative error (%)Average time (second)AverageMaximumOur methodPartial enumeration2201.722.71221.34236.48501.53.32354.05895.11001.865.43631.582301.415202.913.96325.611504.2504.326.33497.045143.821005.17.23759.48954.7110204.126.32531.85481.04505.026.58804.3740592.571007.147.851058.0963851.6


## 5. Case Study

### 5.1. Study Area and Data Source

In this study, Putuo district of Shanghai in China is selected as the research area, which covers an area of 55.47 square kilometers. According to the sixth census bulletin of Putuo district, the resident population of Putuo district was 1288881 on November 1, 2010. We replaced residential areas with simplified 406 residential areas; that is, there were 406 demand points in Putuo district. We can obtain the location, longitude, and latitude of 22 existing large shopping malls (including shopping square and department stores) in Putuo district of Shanghai from Google Maps. The residential areas and existing shopping malls in this study area are shown in Figure4.Figure 4
Distribution of residential areas and existing shopping malls in Putuo district.In this study, the competitive facility location problem considers the response of existing facilities in the market to new facilities entering the market (that is, changing their service quality to reduce the loss of market share). Therefore, only the location information of shopping malls is not enough to use the model in this study, and the existing service quality and other data of shopping mall are also needed. As shopping mall refers to a group of buildings, which is a combination of commercial shopping facilities, rather than a single store or enterprise store, its quality level cannot be directly obtained. Shopping malls are service-oriented facilities, and their quality level can be measured by their service to customers, which is reflected in the actual number of customers served by shopping malls and the actual sales of shopping malls. Under the same conditions, customers tend to be closer to the shopping malls. Therefore, the quality level of shopping malls can be obtained by customers’ or residents’ consumption in these shopping malls.Assuming that the initial service quality of all facilities is equal, along with the lapse of operating time, residents will choose the nearest shopping mall according to the distance. The passenger flow of different shopping malls is different, and the shopping mall will also improve its service quality according to the passenger flow to meet the needs of all customers. Through the consumption choice of residents and the improvement of the service quality of shopping malls, the market can reach a relative steady state. Therefore, we can obtain the original service quality of existing shopping malls in the market according to the purchasing power of residential areas and the distance to shopping malls. The calculation formula is shown in equation (13), and the calculation result is shown in Figure 5:(13)αj′×c=β.∑i=1nwiexp−λidij,where λi is the facility distance weight of demand point i, which is called the spatial damping coefficient in Wilson’s model. Here, we set λi=0.05,∀i=1,…,n in this study. β is a constant, which can be calculated by the summation of purchasing power of demand points equal to summation of profits of the facilities and equation (13). The formula of β is as follows:(14)β=∑i=1nwi∑j=1m∑i=1nwiexp−λidij.Figure 5
Purchasing power and original service quality in Putuo district.In this study, we define the quality of service in a shopping mall as the total number of customers that a shopping mall can serve. The total purchasing power of 406 demand points in Putuo district is 201269.948 million. The average purchasing power of the 406 demand points in Putuo district is 1561.58, so we havec = 1561.58.After obtaining the data of all settlements and shopping malls, we need to set the parameters in the model. In real life, the distance between large shopping malls and residential buildings is usually no less than 100 m. Therefore, we set the minimum distance between the demand point and the facility to 100 m, so we havedmin=100. To maintain their market shares, the quality level of facilities cannot be infinitely improved or decreased. We take the minimum and maximum quality levels of all existing facilities as standards and define the minimum and maximum quality levels of all facilities as αmin=minαj′/2 and αmax=2⋅maxαj′. In addition, the maximum order of polynomial approximation and the maximum acceptable error are set as Nmax=10 and ε=0.05.


### 5.2. Results

After setting the parameters, the competitive facility location model of this study is used to solve the problem. The quality level of the new shopping mall is calculated to be 53451, and the location of the new shopping mall is shown in Figure6. Figure 6 also shows the new quality levels for all existing facilities.Figure 6
Location of new shopping mall and new quality of existing facilities.As can be seen from Figure6, the new shopping mall is located near the Hongji Plaza numbered 10. The new shopping mall is not located in the northeastern part of Putuo district, which has relatively little purchasing power. Because Hongji Plaza is adjacent to three bus stations and west railway station, this area has a large purchasing power, convenient transportation, and large population flow, which is very suitable for residents to go shopping. There is currently only one large shopping mall in this area; therefore, it makes sense for the new shopping mall to be located there.


## 5.1. Study Area and Data Source

In this study, Putuo district of Shanghai in China is selected as the research area, which covers an area of 55.47 square kilometers. According to the sixth census bulletin of Putuo district, the resident population of Putuo district was 1288881 on November 1, 2010. We replaced residential areas with simplified 406 residential areas; that is, there were 406 demand points in Putuo district. We can obtain the location, longitude, and latitude of 22 existing large shopping malls (including shopping square and department stores) in Putuo district of Shanghai from Google Maps. The residential areas and existing shopping malls in this study area are shown in Figure4.Figure 4
Distribution of residential areas and existing shopping malls in Putuo district.In this study, the competitive facility location problem considers the response of existing facilities in the market to new facilities entering the market (that is, changing their service quality to reduce the loss of market share). Therefore, only the location information of shopping malls is not enough to use the model in this study, and the existing service quality and other data of shopping mall are also needed. As shopping mall refers to a group of buildings, which is a combination of commercial shopping facilities, rather than a single store or enterprise store, its quality level cannot be directly obtained. Shopping malls are service-oriented facilities, and their quality level can be measured by their service to customers, which is reflected in the actual number of customers served by shopping malls and the actual sales of shopping malls. Under the same conditions, customers tend to be closer to the shopping malls. Therefore, the quality level of shopping malls can be obtained by customers’ or residents’ consumption in these shopping malls.Assuming that the initial service quality of all facilities is equal, along with the lapse of operating time, residents will choose the nearest shopping mall according to the distance. The passenger flow of different shopping malls is different, and the shopping mall will also improve its service quality according to the passenger flow to meet the needs of all customers. Through the consumption choice of residents and the improvement of the service quality of shopping malls, the market can reach a relative steady state. Therefore, we can obtain the original service quality of existing shopping malls in the market according to the purchasing power of residential areas and the distance to shopping malls. The calculation formula is shown in equation (13), and the calculation result is shown in Figure 5:(13)αj′×c=β.∑i=1nwiexp−λidij,where λi is the facility distance weight of demand point i, which is called the spatial damping coefficient in Wilson’s model. Here, we set λi=0.05,∀i=1,…,n in this study. β is a constant, which can be calculated by the summation of purchasing power of demand points equal to summation of profits of the facilities and equation (13). The formula of β is as follows:(14)β=∑i=1nwi∑j=1m∑i=1nwiexp−λidij.Figure 5
Purchasing power and original service quality in Putuo district.In this study, we define the quality of service in a shopping mall as the total number of customers that a shopping mall can serve. The total purchasing power of 406 demand points in Putuo district is 201269.948 million. The average purchasing power of the 406 demand points in Putuo district is 1561.58, so we havec = 1561.58.After obtaining the data of all settlements and shopping malls, we need to set the parameters in the model. In real life, the distance between large shopping malls and residential buildings is usually no less than 100 m. Therefore, we set the minimum distance between the demand point and the facility to 100 m, so we havedmin=100. To maintain their market shares, the quality level of facilities cannot be infinitely improved or decreased. We take the minimum and maximum quality levels of all existing facilities as standards and define the minimum and maximum quality levels of all facilities as αmin=minαj′/2 and αmax=2⋅maxαj′. In addition, the maximum order of polynomial approximation and the maximum acceptable error are set as Nmax=10 and ε=0.05.


## 5.2. Results

After setting the parameters, the competitive facility location model of this study is used to solve the problem. The quality level of the new shopping mall is calculated to be 53451, and the location of the new shopping mall is shown in Figure6. Figure 6 also shows the new quality levels for all existing facilities.Figure 6
Location of new shopping mall and new quality of existing facilities.As can be seen from Figure6, the new shopping mall is located near the Hongji Plaza numbered 10. The new shopping mall is not located in the northeastern part of Putuo district, which has relatively little purchasing power. Because Hongji Plaza is adjacent to three bus stations and west railway station, this area has a large purchasing power, convenient transportation, and large population flow, which is very suitable for residents to go shopping. There is currently only one large shopping mall in this area; therefore, it makes sense for the new shopping mall to be located there.


## 6. Conclusion and Discussion

Aiming at the competitive facility location problem in urban planning, the response of existing facilities to new entry facility is considered to improve the attractiveness of the facilities in the model. The Huff probability model is used to describe the market share of each facility in the market. In order to maximize the profit of the new facility, a two-stage approach (quality decision stage and location decision stage) is adopted, that takes into account the competitors’ response. As an application result, the model and algorithm in this study are applied to solve the location problem of a new large shopping mall in Putuo district of Shanghai. The results show that the model and algorithm have good practicability.There are also has some limitations in this study. When selecting the location of new facilities, it is assumed that only one new facility is set up without considering the simultaneous establishment of multiple new facilities. Allowing multiple new facilities to enter the market at the same time will make the problem of this study more complicated. This is also the direction of further research.



---

*Source: 6759520-2020-12-15.xml*