Informatica

We consider a certain geographical area in which customers are supposed to be concentrated in demand points (see Francis et al., 2002). The demand of these customers is fixed and currently satisfied by a set of facilities already established in that area belonging to one or several firms. When a new firm wants to enter this market with the idea of capturing as much demand as possible, the company is facing a problem of Competitive Location. The entering firm must decide where to locate its own facilities in order to maximize its total profit, which will depend on the total captured demand. This decision implies the study of the conditions that surround the distribution of a specific product, such as the location space, the characteristics of the facilities (quality), the customer choice rule, and additional constraints imposed by the firm, or by the local administration. The combination of all these factors will give rise to different competitive location models that will need a different study and the use of different techniques to solve them (see Eiselt et al., 1993, 2015; Friesz et al., 1988; Plastria, 2001; Revelle and Eiselt, 2005; Al-Yakoob and Sherali, 2018).

A crucial issue in this type of models is to study the customers behaviour when choosing the facility or facilities that will satisfy their demand. In the literature, it has been usual to consider the distance to the facility as the first criterion used by the customer, so that the demand is served by the closest facility (see Drezner, 1995; Hotelling, 1929). Distance gives a first measure of attraction that each customer feels for each facility. Subsequently, the way of evaluating the attraction of customers by the facilities was modified, considering that facilities at the same distance did not have to be equally attractive for a customer if those facilities had different qualities (their size, number of parking spaces, leisure areas, etc). Different techniques emerge to measure the attraction between customers and facilities, but all of them have in common that this attraction is directly proportional to the quality of the facility, and inversely proportional to some function of the distance between them (Hodgson, 1978; Wilson, 1976). In this way, now the customer will be served by the most attractive facility, which would coincide with the closest one if all the facilities have the same quality. It was Huff (1964) who proposed for the first time a location model in which customers satisfied their demand according to a rule of proportional behaviour: customer demand will be split between all the facilities proportionally to the attraction it feels for each one.

The most common customer choice rules are then the binary or deterministic rule (the full demand of a customer is satisfied by only one facility, the one to which he is attracted most – binary attraction), and the Huff, probabilistic or proportional rule (a customer splits his demand over all facilities in the market proportionally with his attraction to each facility – additive attraction), see Drezner and Drezner (2004), Serra et al. (1999b). Although in many cases customers patronize facilities according to these two rules, there are others in which these rules do not represent customer behaviour properly. In this paper we are going to consider that customers follow the partially binary or multideterministic rule, where it is supposed that several firms are present in the market with some pre-existing facilities, and the full demand of a customer is served by all the firms but patronizing only one facility from each firm, the facility with the maximum attraction, then its demand is split between those facilities proportionally with their attraction (see Fernández et al., 2017; Hakimi, 1990; Suárez-Vega et al., 2004).

This unusual rule explains the customers behaviour in some everyday cases better. For example, suppose that to do his weekly shopping, a customer has several supermarkets around his home belonging to two different firms. Most likely, the customer does not do all the weekly shopping in a single supermarket, because there may be products that are not available in the supermarkets of one of the firms, or that their prices are higher than its competitor’s. Nor the customer will go to all supermarkets of the same firm, since it is assumed that all of them offer the same products at the same prices. Then, the customer will go to one of the supermarkets of each firm, the one with maximum attraction, and will buy more or less products in each supermarket depending of its attraction.

In our model, we will suppose that there exists a finite set of possible locations for the new facilities (discrete location space), and that customers follow a partially binary choice rule to serve their demand. So, the entering firm will serve a part of customers demand proportionally to the maximum attraction between each customer and the new facilities. It may happen that there are several new facilities with the maximum attraction for a customer, so it must decide if its demand is served by one or more of those facilities. But is this a real possible scenario? Can there be several facilities with the same maximum attraction for a customer? As the attraction depends on the characteristics of the facility (quality) and the distance to the customer, and it is feasible that the facilities belonging to the same firm have the same characteristics, the answer depends on whether it is usual for a customer to have several facilities of the same firm at the same distance. Although this situation is possible, this is unlikely to happen if real distances between facilities and consumers are considered. In fact, the customer does not use real distances to determine their attraction to a centre, but an approximation, which will depend on their accuracy when calculating distances between two points in a network, how often they use that route or the traffic in the area. In this way, a customer can consider that all facilities with the same characteristics whose real distances belong to an interval have the same attraction to him. This would justify that there may be several facilities with the same maximum attraction for a customer, being able to be equally chosen to serve their demand. To have a better estimation of the market share captured by each new facility, we suppose that in case of ties in the maximum attraction, customer’s demand is equally split among all these facilities (equity-based rule, see Pelegrín et al., 2015).

As location decisions are long-term, the firm wants not only to maximize its total market share, but also to ensure the viability of these facilities in the future, although the customers demand will be unknown and its preferences could change. In this way, the firm imposes the condition that a new facility will be opened only if it captures at least a fixed minimal demand in the short-term, trying to guarantee a future satisfactory captured demand. This will be introduced into the model as new constraints for candidate locations. So, it is necessary to know the exact captured demand by each new facility when locations must be decided. The equity-based ties breaking rule involves that both the objective function and the minimal market share constraints are nonlinear, so we will deal with a nonlinear constrained discrete competitive facility location model (see Balakrishnan and Storbeck, 1991; Benati and Hansen, 2002; Colomé et al., 2003; Ljubić and Moreno, 2018; Serra et al., 1999a for minimum capture constrained models and Drezner et al., 2002; McGarvey and Cavalier, 2005; Plastria and Vanhaverbeke, 2008 for other constrained models).

This paper could be considered as an extension of Fernández et al. (2017), where unconstrained discrete competitive facility location models were analysed under binary and partially binary customer choice rules. There are some highlight differences between the previous paper and this new one that justify its relevance. In the previous one, none ties breaking rule was used if ties in maximum attraction occur for the new facilities, since this was irrelevant for the entering firm when its market share was going to be maximized. In this new one, we deal with a nonlinear constrained problem due to the use of the equity-based ties breaking rule when there are several new facilities with maximal attraction for a customer. In addition, and for each customer, it has been considered that a new facility will capture part of the consumer’s demand if the attraction between them exceeds a certain fixed threshold, so it may happen that there are customers with no captured demand by the new facilities.

In summary, the contribution of the paper is as follows. A new discrete location model is proposed where i) partially binary choice rule is applied to customers, ii) real distances are approximated by intervals of different ranges, iii) minimum attraction conditions have been considered for each customer, iv) an equity-based rule has been used in case of ties in maximum attraction between facilities, and v) minimal market share constraints are introduced to the new facilities unsure of a future captured demand.

The model is formulated as a binary nonlinear programming problem for which an equivalent formulation as a binary linear programming problem is proposed. This allows to solve small size problems using a standard optimizer (Xpress), and for more complex problems a heuristic algorithm based on ranking of the search space elements with constraints handling is proposed, which could also be used to solve other constrained problems. This algorithm extends the one proposed in Fernández et al. (2017).

The rest of the paper is organized as follows. In Section 2 the unconstrained model without ties breaking rule is described and an initial formulation is presented. In Section 3 the constrained model with equity-based ties breaking rule is introduced, the first nonlinear formulation is obtained, and then a linearization of the model is proposed. The proposed resolution method based on ranking of the search space elements is presented in Section 4, which could also be used to solve other constrained facility location problems. To justify the merit of the proposed algorithm, some computational experiments are shown in Section 5. Finally, conclusions are listed in the last section.

In this section we are going to present the basic model (unconstrained and without ties breaking rule), but introducing all the special characteristics of the model, and in the next section we will add additional constraints that ensure that a new facility will be opened only if it captures a minimal amount of customers demand. We will suppose that customers are concentrated in demand points, and that their demand is known and fixed. As it is very difficult for a customer to evaluate real distances to the facilities, we will consider distances by intervals, that is, taking integer values as the intervals centres, all distances within a fixed range interval will be approximated to its central value. Thus, for example, if we take a range of 10 km, all distances on the interval $(x-5,x+5]$ will be approximated to x, x being an integer value.

A new firm wants to compete for the market share by opening some new facilities in order to maximize the total captured demand. There are some pre-existing facilities belonging to other firms, and the partially binary customer choice rule is considered. With this customer behaviour, the full demand of each customer is served by all the firms but patronizing only one facility from each one, the facility with the maximum attraction, then the demand is split between those facilities proportionally with their attraction. But there could be customers whose demand was not served by any of the new facilities because they were not attractive enough. To better adjust the problem to customer behaviour, we will assume that a customer will be served by a given facility if its attraction is greater than or equal to a fixed threshold value. For this, the attraction between each customer and its possible facilities will be defined as the ratio between the quality of the facility and a function of the distance between them, if this value is at least the threshold value set for the customer, and zero otherwise. For each customer, its threshold value will be between the minimum and the maximum attraction values of the most attractive facilities of the firms already operating in the market.

In order to introduce the constrained model, suppose that the entering firm imposes the condition that a new facility will be opened only if it captures at least a fixed amount of customers demand in the short-term denoted by α. With this new constraint, it is necessary to know what demand points are allocated to each new facility, and what part of the demand is captured by the entering firm. Given $i\in I$, it is known what proportion of its demand will be captured by the entering firm, the proportion corresponding to its maximum attraction (this could be zero), but it is possible that there exist several new facilities with non zero maximum attraction. Since the minimal market share constraints refer to the new facilities, not to the entering firm, it is very important to know exactly the captured demand by each new facility, and then it is crucial to know what breaking rule is going to be used in case of ties in the maximum attraction. In this paper, instead of selecting only one of them to serve the full demand, we assume a more realistic situation, so, if ties occur, the demand of each customer captured by the entering firm will be equally split among its open facilities with maximum attraction. Then, we consider the following new variables:

So the objective function becomes: where it must be verified that:

The necessary condition in (6) is verified by any optimal solution, since the objective function is increasing with respect to the numerator. To guarantee the sufficient condition in (6), besides that a demand point can only be allocated to open facilities, the following set of constraints is necessary: where ϵ is small enough and ${a_{\max }}=\operatorname{Max}\{{a_{ij}}:\forall i\in I,\hspace{0.1667em}\forall j\in L\}$.

Note that if ${a_{ij}}=\max \{{a_{ir}}:{x_{r}}=1,r\in L\}$ and ${z_{ij}}=0$, then the left side of (7) becomes ${\textstyle\sum _{h\in L}}{z_{ih}}{a_{ih}}-({\textstyle\sum _{h\in L}}{z_{ih}}){a_{ij}}\leqslant 0$ and then (7) doesn’t hold. On the other hand, if ${a_{ij}}<\max \{{a_{ir}}:{x_{r}}=1,\hspace{0.1667em}r\in L\}={a_{ik}}$ and ${z_{ij}}=1$, then for $j=k$ the left side of (7) becomes ${\textstyle\sum _{h\in L}}{z_{ih}}{a_{ih}}-({\textstyle\sum _{h\in L}}{z_{ih}}){a_{ij}}<0$ and (7) doesn’t hold.

Moreover, from (7) it follows that ${\textstyle\sum _{j\in L}}{z_{ij}}\geqslant 1$, $\forall i\in I$, even if $\max \{{a_{ir}}:{x_{r}}=1,r\in L\}=0$, so the objective function is well defined.

On the other hand, the minimal market share constraint for each new facility, when the previously introduced ties breaking rule is considered, is expressed as: that is a similar expression than the objective function, so it is also well defined.

So, the final formulation of the model as a binary nonlinear programming problem is:

The Ranking-based Discrete Optimization Algorithm (RDOA) has been applied to solve facility location problems in Fernández et al. (2017). The RDOA is specially adopted to discrete facility location and is based on ranking of candidate locations. The algorithm demonstrated good efficiency when solving different instances of unconstrained discrete facility location problems and outperformed well-known algorithms suitable to solve similar problems.

However, the RDOA does not have any strategy for constraint handling and, therefore, cannot be directly applied to solve our constrained facility location model. In this section we propose a modified RDOA, which includes constraints for the solutions (RCDOA).

The $({\operatorname{LPBCM}_{\alpha }})$ described in Section 3 has been solved by the deterministic optimization algorithm using Xpress (FICO Xpress Mosel, 2014) and the RCDOA, described in Section 4.

The database with real geographical data of coordinates of 1624 municipalities in Spain with population greater or equal to 2500 inhabitants has been considered as demand points. The set of 247 most populated demand points (municipalities with a population greater or equal to 25000 inhabitants) was used as the set of location candidates L (see Fig. 1).

For distances between demand points and facilities, two different ranges have been used on computational experiments, 10 and 20 km, and for the attraction function, it has been supposed that ${q_{j}}=1$, $\forall j\in L$, and $f({d_{ij}})=1+{d_{ij}}$, $\forall i\in I$, $j\in L$.

It was considered that there are 3 preexisting firms with 3 or 5 facilities per firm already located in the most populated demand points. Distribution of candidate locations among the firms is presented in Table 1.

The minimal market share for a new facility is expressed as percent of estimated average market share per existing facility after location. The average market share per facility can be expressed by where is the total demand of all customers in I. Then the minimal market share is considered as 0% to 80% of $\tilde{m}$, depending on the problem instance, but only the results for some of them will be shown, the ones with significative information for the model. For small α values, Xpress is able to find the optimal solutions, which do not usually change, and only when α values increase, the optimal solutions can change, if any, and it is even possible that Xpress can not find them because of the time limit. The values of minimal market share α are presented in Table 2, knowing that the total demand W of I is 35462869.

To define ${A_{i}}$, the minimum attraction level for customer i, we consider ${A_{i}^{\max }}=\max \{{a_{i}}({J_{k}}):k\in K\}$ and ${A_{i}^{\min }}=\min \{{a_{i}}({J_{k}}):k\in K\}$, then ${A_{i}}={A_{i}^{\min }}+\delta ({A_{i}^{\max }}-{A_{i}^{\min }})$ with $0\leqslant \delta \leqslant 1$. Four δ values have been selected for the result tables, $\delta =0,0.2,0.6,1$, in order to reduce the table size.

In this paper a new constrained discrete competitive facility location model has been analysed in which, besides assuming that customers follow a partially binary choice rule for selecting the facility or facilities that will serve their demand, equity-based ties breaking rule is proposed and minimal market share constraints have been incorporated to ensure the viability of the new facilities (a new facility will be opened if it captures a minimal amount of customer demand in that area). A formulation as a nonlinear binary programming problem has been proposed, and after defining new sets of variables, it has been possible to present a linearization of the proposed constrained model $({\operatorname{LPBCM}_{\alpha }})$, which allows to obtain optimal solutions for small size problems using a standard optimizer.

Due to the complexity of the $({\operatorname{LPBCM}_{\alpha }})$ model, a heuristic algorithm for random search based on ranking of location candidates and geographical distance has been applied for the resolution of more complex problems. This procedure uses two labels for each location candidate point: the ranking label and the violation label of the minimal market share constraint. The viability of the proposed algorithm has been investigated for different problem instances and compared with the standard optimizer Xpress, showing that RCDOA always obtains the same solutions as Xpress. For more complex instances, only RCDOA has been used, and the results show that in all cases, the algorithm either obtains the best possible solution, or converges to its approximation if a feasible solution is available.