Location and quality selection for new facilities on a network market

Abstract

In this paper, the problem of determining the location and quality of new facilities in a network market is analyzed. Customers make their choice according to an attraction function, which is directly proportional to the facility quality level and decreasing with respect to the distance between customers and facilities. In order to solve the location problem, both an integer linear program and an exact algorithm are proposed. These algorithms are embedded into a branch and bound-based algorithm for solving the joint location–quality problem. An illustrative example where customers present different distance perception is presented.

1 Introduction

The problem of locating $r$ facilities in a network where other competing facilities already exist was formalized by Hakimi (1983) who used the denomination $(r|X_{p})$ -medianoid to call the optimal set of $r$ points when the competitor has $p$ facilities located at $X_p$. The demand was assumed to be concentrated in the set of nodes, and the objective was to maximize the demand captured. Some node optimality results guarantee the existence of an optimal solution in the set of nodes for different customer choice rules. The simplest choice rule is the binary one according to which customers patronize the closest facility. Depending on whether goods are essential or not (inelastic or elastic demand), consumers use all their buying power or they may not satisfy all their demand if the conditions in which the service is provided are considered not good enough. Static maximum capture location models have been studied by ReVelle (1986), Benati and Laporte (1994), Dasci et al. (2002), Eiselt and Laporte (1989, 1996), Redondo et al. (2009), Serra et al. (1992), Serra and Colomé (2001), Serra and ReVelle (1995), and Suárez-Vega et al. (2004a, b), among others.

In this paper, we study a competitive location model where demand is inelastic and customers make a decision taking into account travel distances and certain attributes of the facilities. The attraction felt by a customer toward a facility depends on the distance between the customer and the facility and on the quality level of the facility. We formulate the attraction as a function directly proportional to the quality of the facility and inversely proportional to an increasing function of the distance between customers and facilities. This formulation derives from the gravity model suggested by Reilly (1929) and from the model proposed by Huff (1964) who considered the travel distance and the facility size as the relevant elements in the decision making. Other competitive location models using distance and facility attributes (or value position, besides the geographic location) can be found in Drezner (1994a, b), Eiselt and Laporte (1988a, b), Eiselt et al. (1989), Ghosh and Craig (1983), Peeters and Plastria (1998), Plastria (1997), and Thill (1992, 1997, 2000).

The entry firm wants to find both the locations and the quality levels of the new facilities in order to maximize profits (revenue minus costs). To solve the location problem, we propose both an integer linear program and an exact algorithm, and their capabilities are then analyzed. The joint location–quality problem with a binary choice rule has been solved in the discrete space by Eiselt and Laporte (1989) and Suárez-Vega et al. (2004b), and in the plane by Plastria and Carrizosa (2001), but to our knowledge, the network case has not yet been solved.

The rest of the paper is organized as follows. The model is presented in Sect. 2. Section 3 includes the solution notion and some optimality results. Some algorithms are proposed for solving both the location and the location–quality problems. In Sect. 4, an application of the global search algorithm for solving a hypermarket location–size problem in Gran Canaria (Spain) is presented. Finally, Sect. 5 contains some concluding remarks.

2 The model

Consider a market represented by a network $N=N(V,E)$ with node set $V=\{v_{i}\}_{i=1}^{n}$ and edge set $E$. The demand is concentrated in the set of nodes, being $w(v)\ge 0$ the demand (or buying power) at node $v$. For any $x,y \in N(V,E),\,d(x,y)$ is the distance between $x$ and $y$ on the network. Given two points $x$ and $y$ on the edge $[v_{i},v_{j}]$, the closed segment $[x,y]$ is the subset of points of $[v_{i},v_{j}]$ between $x$ and $y,$ including $x$ and $y$. Denote $]x,y[=[x,y]\setminus \{x,y\}$, $]x,y]=[x,y]\setminus \{x\}$ and $[x,y[=[x,y]\setminus \{y\}$.

Each facility $j$ is characterized by its location $x_{j}$ and its quality level $a_{j}$ with $a_{j}\in [L,U]$ where $0<L<U<+\infty$. When we say that a firm has $k$ facilities located at $X=(x_{1},\ldots ,x_{k})$ with quality levels $A_{X}=(a_{1},\ldots ,a_{k})$, we mean that the $j$th facility has quality level $a_j$ and is located at point $x_j$, for $j=1,\ldots ,k$. There exists a cost function of the quality level (independent of the location), $C:[L,U]\rightarrow \mathfrak {R}_{0}^{+}$, which is continuous and increasing.

The attraction felt by customers at node $v$ toward facility $j$ at $x_j$ is given by

$$\begin{aligned} a_{vj}=\frac{a_{j}}{f_{v}(d(v,x_{j}))} \end{aligned}$$

(1)

where $f_{v}:\mathbb {R}_0^+ \longrightarrow \mathbb {R}_0^+$ is a continuous, strictly increasing and nonnegative function, with $f(d)=0$ if and only if $d=0$. If $d(v,x_{j})=0$ we set $a_{vj}= +\infty$.

Expression (1) is an extended version of the one involved in the model proposed by Huff (1964). In the original Huff model, the quality is represented by the size of the facility and $f_v$ is a power function of the travel time. The attraction function defined by (1) corresponds to a gravity model. Gravity models have been used often to formulate probabilistic choice functions in a spatial interaction context, for representing the probability of each destination $j$ conditioned to each origin $i$. A view of gravity models and other formulations utilized in spatial interaction modelling can be found in Fotheringhan and O’Kelly (1989), Roy and Thill (2004), and Sen and Smith (1995), among others.

There are already $p$ facilities operating at points $X_{p}=(x_{1},x_{2},\ldots ,x_{p})$ with quality levels $A_{X_{p}}=(a_{1},a_{2},\ldots ,a_{p})$. A competitor firm $A$ plans to enter the market with $r$ facilities and wants to determine the locations and quality levels that maximize the profit. Any point on the network is a candidate facility location. Firms provide essential goods or services to customers who patronize the most attractive facility. Ties in attraction between existing and new facilities are broken in favor of the existing ones. If an existing facility is open at $v$, customers at $v$ patronize this facility independently of what the competitor may decide.

Suppose that firm $A$ opens $r$ facilities at $Y_{r}=(x_{p+1},x_{p+2},\ldots ,x_{p+r})$ with quality levels $A_{Y_{r}}=(a_{p+1},a_{p+2},\ldots ,a_{p+r})$. For any $v \in V$ let $G(v,X_{p},A_{X_{p}})=\max \{a_{vj}:j=1,\ldots ,p\}$ and $G(v,Y_{r},A_{Y_{r}})=\max \{a_{vj}:j=p+1,\ldots ,p+r\}$. Then, firm $A$ captures the demand of nodes $v$ in the set

$$\begin{aligned} V(Y_{r},A_{Y_{r}})=\left\{ v\in V\;:\; G(v,Y_{r},A_{Y_{r}})>G(v,X_{p},A_{X_{p}}) \right\} . \end{aligned}$$

(2)

Assuming that the net profit margin per unit of revenue (captured demand) is equal to 1 for any facility, the profit obtained by firm $A$ is

$$\begin{aligned} \varPi (Y_{r},A_{Y_{r}})=W(Y_{r},A_{Y_{r}})\;-C(A_{Y_r}) \end{aligned}$$

(3)

where $W(Y_{r},A_{Y_{r}})=\sum _{v\in V(Y_{r},A_{Y_{r}})}w(v)$ is the total demand captured by firm $A$ and $C(A_{Y_r})=\sum _{j=p+1} ^{p+r}C(a_{j})$ is the total cost due to the quality levels.

Firm $A$ wants to find the locations $Y_{r}^*=(x_{p+1}^*,x_{p+2}^*,\ldots ,x_{p+r}^*)$ and quality levels $A_{Y_{r}}^*=(a_{p+1}^*,a_{p+2}^*,\ldots ,a_{p+r}^*)$ (if they exist) such that

$$\begin{aligned} \varPi (Y_{r}^*,A_{Y_{r}}^*)=\max \limits _{Y_r \in N^r(V,E),\; A_{Y_r} \in [L,U]^r} \varPi \left( Y_{r},A_{Y_{r}}\right) . \end{aligned}$$

(4)

We study the problem of firm $A$ assuming that $X_p$ and $A_p$ are given, so that possible reactions of the firms already operating in the market or preemptive strategies are not considered in this paper. Hereafter, $G_v=G(v,X_{p},A_{X_{p}})$.

3 Solution notion

In this section, the resolution of the joint location–quality problem is analyzed. First, the quality and the location problems are separately studied, and then a branch and bound algorithm combining the results obtained for these situations is proposed to solve the joint location–quality problem.

3.1 The quality problem

Given the locations $Y_{r}$ for the new facilities, the quality problem consists of finding the best quality levels for those stores in order to maximize the new firm profits. As Suárez-Vega et al. (2004b) proved, only an $\varepsilon$-optimal solution to the quality problem is guaranteed to exist. This is a consequence of the discontinuity of the market share function in the set of points $Q=\{a_{v}^{p+j}=G_{v}f_{v}(d(v,x_{p+j})):L\le a_{v}^{p+j} \le U,v\in V, \; j=1,\ldots ,r\}$. Then, given $Y_r$, the quality problem is to find an $\varepsilon -$optimal solution $A_{Y_r}^* \in [L,U]^r$ to the problem $\max \nolimits _{A_{Y_r} \in [L,U]^r} \varPi (Y_r,A_{Y_r})$, that is, a vector $A_{Y_r}^* \in [L,U]^r$ such that a value $\delta =\delta (\varepsilon ) > 0$ exists and if $\Vert A_{Y_r}-A_{Y_r}^*\Vert < \delta$, then $\varPi (Y_r,A_{Y_r}) - \varPi (Y_r,A_{Y_r}^*) < \varepsilon$. The next example illustrates this result.

Example 1

Consider the network of Fig. 1 where $X_{1}=v_{1}$ with $a_1=0.5$. Let $f_{v}(x)=x,\,\forall v\in V$, and suppose that $Y_{1}=v_{2}$ with quality level $a_{2}\in [0.1,1]$. Firm $A$ wants to obtain the quality level $a_{2}^{*}$, which maximizes profits.

The attraction felt by the nodes toward the existing facility is $G_{v_{1}}=+\infty ,\,G_{v_{2}}=G_{v_{3}}=0.5$. A facility at $Y_{1}$ with quality level $a_{2}$ captures all the demand of node $v$ if $a_{v2}>G_{v}$. Then, node $v_1$ and $v_2$ are captured by $X_1$ and firm $A$, respectively. Firm $A$ captures $v_3$ if $a_2>0.5$. Figure 2 shows the profit function for firm $A$ when $C(a_{2})=0.5a_{2}$. Since the supremum is not achieved, the profit function does not have a maximum on $[0.1,1]$. In this case, an $\varepsilon$-optimal solution exists, i.e., a value $a_{\varepsilon }$ close to $a_{2}=0.5$, such that $1.75-\varPi (a_{\varepsilon }) < \varepsilon$.

Fig. 1

Three nodes network

Fig. 2

Profit function of firm A

3.2 The location problem

A finite dominating set (FDS) for a network location problem is a finite set of points, which contains an optimal solution (Hooker et al. 1991), and this set allows us to find an optimal solution by solving a discrete problem. If we fix the quality levels of the new facilities in (4), we obtain a location problem for which we can construct a FDS.

Consider $A_{Y_{r}}=(a_{p+1},a_{p+2},\ldots ,a_{p+r})$ given. For any $v \in V$ and $a \in [L,U]$, let

$$\begin{aligned} ISOA(v,a)&= \left\{ x\in N(V,E):f_{v}(d(v,x))=\frac{a}{G_{v}} \right\} \\ ISOA(a)&= \bigcup \limits _{v\in V}ISOA(v,a)\\ ISOA(A_{Y_r})&= \bigcup \limits _{j=1}^r ISOA(a_{p+j}). \end{aligned}$$

A point $x \in ISOA(v,a)$ is named a $(v,a)$-isoattractive point. The notion of an isoattractive point in our location–quality problem is analogous to the concept of an isodistant point used by Peeters and Plastria (1998).

Then, given $X_{p},\,A_{X_{p}}$, and $A_{Y_{r}}$, if $[s,t]\cap ISOA(a_{p+j})=\emptyset$, from the continuity of $f$, it follows that $V(( x_{p+1},\ldots ,x_{p+j},\ldots ,x_{p+r}),A_{Y_r})$ is constant when $x_{p+j}$ varies along the segment $[s,t]$. That is to say, the market share of firm $A$ is constant along any edge segment without isoattractive points.

In order to construct a FDS for our location problem, we define the sets $P(a_{p+k}),\,k=1,2,\ldots ,r$, as follows.

For each $a_{p+k},\,k\in \left\{ 1,\ldots ,r\right\}$, and each edge $[v_{i},v_{j}]\in E$, consider the points in $ISOA(a_{p+k})\cap [v_{i},v_{j}]$ $=\{x_{ijk}^{1},x_{ijk}^{2},\ldots ,x_{ijk}^{q_{ijk}}\}$ enumerated by increasing order of the value of the distance to node $v_{i}$. The market share of firm $A$ in each of the open intervals $]v_{i},x_{ijk}^{1}[,\,]x_{ijk}^{l},x_{ijk}^{l+1}[,\, l=1,\ldots ,q_{ijk}-1,\,]x_{ijk}^{q_{ijk}},v_{j}[$, is constant. For each nonempty interval $]x_{ijk}^{l},x_{ijk}^{l+1}[$, we can choose an arbitrary point (e.g., its midpoint) $y_{ijk}^{l}\in ]x_{ijk} ^{l},x_{ijk}^{l+1}[,$ with $l=0,\ldots ,q_{ijk},$ where $x_{ijk}^{0}=v_{i}$ and $x_{ijk}^{q_{ijk}+1}=v_{j}$. If $v_{i}\notin ISOA(a_{p+k}),$ set $y_{ijk} ^{0}=v_{i}$. Analogously, if $v_{j}\notin ISOA(a_{p+k}),$ let $y_{ijk} ^{q_{ijk}}=v_{j}.$ If $ISOA(a_{p+k})\cap [v_{i},v_{j}]\,=$ $\emptyset$ set $q_{ijk}=0,$ and $y_{ij}^{0}=v_{i}$ or $y_{ij}^{0}=v_{j}.$ Let $P_{ij}(a_{p+k})=\{y_{ijk}^{l}\}_{l=0}^{q_{ijk}}.$ Clearly, the set $P_{ij}(a_{p+k})$ is not necessarily unique. Then, $P(a_{p+k})=\bigcup \nolimits _{i,j}P_{ij}(a_{p+k})$ is a set of candidate points to locate a facility with quality level $a_{p+k}$.

Proposition 1

If $X_{p},\,A_{X_{p}},$ and $A_{Y_{r}}$ are given, then there exists an optimal solution to problem (4), $Y_{r}^{*}\left( A_{Y_{r}}\right) =\,(x_{p+1}^*,x_{p+2}^*,\ldots ,x_{p+r}^*)$, where $x_{p+k}^*\in P(a_{p+k}),\,k=1,2,\ldots r$.

Proof

See Suárez-Vega et al. (2004b).

Proposition 1 is proved taking into account that the demand captured by the firm is constant when one facility location varies on any open segment $]x_{ijk} ^{l},x_{ijk}^{l+1}[$, being the rest of the facility locations fixed, and that the demand captured by any isoattractive point $x$ is not greater than the demand captured by points on open segments incident at $x$ without isoattractive points.

From Proposition 1, it follows that a FDS for our location problem is $B=\prod \nolimits _{i=1}^{r} P(a_{p+i})$. As Pelegrín et al. (2012) proved, the number of isoattractive points, given a quality level, is upper bounded by $nm$, where $n$ and $m$ are the network number of nodes and edges, respectively. Then, given $A_{Y_{r}}$, a vector of optimal locations can be found in the set $P\left( A_{Y_{r}}\right) =\{(x_{p+1},x_{p+2},\ldots ,x_{p+r} ):x_{p+k}\in P(a_{p+k})\}$, which has, at most, $(nm)^{r}$ points.

Consider the network of Fig. 1. Let $r=p=1,\,X_{1}=v_{1},\,a_{1}=1$, and $f_{v}(x)=x,\,\forall v\in V$. Assume that the quality level of a new facility is $a_{2}=1$. Then, $ISOA(v_1,a_2)=\{v_1\},\,ISOA(v_2,a_2)=\{v_1,v_3\}$, and $ISOA(v_3,a_2)=\{v_1,v_2\}$. Therefore, a FDS is $P\left( a_{2}\right) =\left\{ y_{12},y_{13},y_{23}\right\}$ where $y_{ij}$ is the midpoint of edge $\left[ v_{i},v_{j}\right]$. In this case, point $y_{23}$ is an optimal solution. In fact, every point on $]v_{2},v_{3}[$ is an optimal solution to the location problem.

Next, we will define different sets and variables in order to formulate an integer linear program for solving the location problem:

• $P(a_{p+i})=\{x_{1}^{i},x_{2}^{i},\ldots ,x_{q_i}^{i}\}$ is the set of potential locations for a new facility with quality level $a_{p+i}$.

• $N_{t}^{i}=\{j : d(v_t,x_{j}^{i})=0 \quad or \quad \frac{a_{p+i}}{f(d(v_t,x_{j}^{i}))}> G_{v_t},j=1,2,\ldots ,q_i \}$ is the set of potential locations for a new facility with quality level $a_{p+i}$ that are more attractive than the existing stores for node $v_t$.

• $y_{j}^{i}=1$ if a new facility with quality level $a_{p+i}$ is located at $x_{j}^{i}$, and zero otherwise.

• $s_t=1$ if the demand node $v_t$ is captured by the new firm, and zero otherwise.

Then, the location problem can be solved using the following model:

$$\begin{aligned}&\hbox {Max} \sum _{t=1}^{n}w(v_t)s_t \nonumber \\&st: \sum _{j=1}^{q_i} y_{j}^{i}=1 \quad \quad \forall i=1,2,\ldots ,r \end{aligned}$$

(5)

$$\begin{aligned}&\quad s_t \le \sum _{i=1}^{r}\sum _{j\in N_{t}^{i}}y_{j}^{i} \quad \quad \forall t=1,2,\ldots ,n \end{aligned}$$

(6)

$$\begin{aligned}&\quad s_t=0 \quad \quad \forall v_t \in X_p \end{aligned}$$

(7)

$$\begin{aligned}&\quad y_{j}^{i} \in \{0,1\} \quad \quad \forall j=1,2,\ldots ,q_i, \forall i=1,2,...,r \nonumber \\&\quad s_{t} \in \{0,1\} \quad \quad \forall t=1,2,\ldots ,n \end{aligned}$$

(8)

The objective function represents the market captured by the new firm. Restrictions (5) impose that only one new facility with quality level $a_{p+i}$ can be opened. Restrictions (6) imply that node $v_t$ is served by the new firm $(s_t=1)$ only if at least one new facility is more attractive than the existing stores. With (7), we impose that customers at nodes in $X_p$ purchase from the existing facilities. In fact, the problem structure allows relaxing restrictions (8) to $s_{t} \in [0,1]$ and therefore reducing the number of binary variables in the model.

The rest of this section includes several useful results for solving the location problem. These results allow a reduction in the computations in the search for an optimal location set. Two exact algorithms in order to find an optimal solution to the location problem for given quality levels are proposed.

Proposition 2

If $X_{p},\,A_{X_{p}}$, and $A_{Y_{1}}=a$ are given, and functions $f_{v},\,v \in V$, are strictly increasing, then any point $x \in [v_{i},v_{j}]$ satisfies the relation $V\left( x,a\right) \subseteq V\left( v_{i},a \right) \cup V\left( v_{j},a \right)$.

Proof

If $x=v_{i}$ or $x=v_{j}$, the result is trivial. Suppose $x\in ]v_{i},v_{j}[$ and $v\in V\left( x,a\right)$. Since $f_{v}$ is strictly increasing, it follows that $f_{v}$ is invertible. If $v \in V(x,a)$, then $\frac{a}{f_{v}\left( d\left( v,x\right) \right) }>G_{v}$, which implies $f_{v}^{-1}\left( \frac{a}{G_{v}}\right) >d\left( v,x\right) =\min \{d\left( v,v_{i}\right) +d\left( v_{i},x\right) ,d\left( v,v_{j}\right) +d\left( v_{j},x\right) \}.$ Then, as $d\left( v,x\right) > d\left( v,v_{i}\right)$ or $d\left( v,x\right) > d\left( v,v_{j}\right)$, it follows that $\frac{a}{f_{v}\left( d\left( v,v_{i}\right) \right) }>G_{v}$ or $\frac{a}{f_{v}\left( d\left( v,v_{j}\right) \right) }>G_{v}$. Therefore, $v\in V\left( v_{i},a \right) \cup V\left( v_{j},a \right)$.

Corollary 1

If $X_{p},\,A_{X_{p}}$, and $A_{Y_{1}}=a$ are given, and functions $f_{v}$ are strictly increasing, then the total demand captured by a facility at $x \in [v_{i},v_{j}],\,W( x,a) =\sum \nolimits _{v\in V (x,a) } w( v)$ is upper bounded by $\overline{W} = \sum \nolimits _{v\in V ( v_{i},a ) \cup V\left( v_{j},a \right) }w\left( v\right)$, that is,

$$\begin{aligned} W\left( x,a\right) \le \sum _{v\in V\left( v_{i},a\right) \cup V\left( v_{j},a\right) }w\left( v\right) . \end{aligned}$$

Proof

It carries from Proposition 2.

The algorithm described in Fig. 3 uses Corollary 1 to find the optimal location for a new facility with a given quality level. Note that, if quality levels are fixed, the problem of maximizing profits is equivalent to maximizing the demand captured or market share. The optimization approach proposed uses the FDS mentioned in Proposition 1, denoted by $P(a)=\{y^{1},y^{2},\ldots ,y^{s}\}$, where $y^{k}$ is represented by the vector $( u^{k},v^{k},d_{u}^{k} )$, which indicates that $y^{k}$ is the point on edge $[ u^{k},v^{k}]$ such that $d_{u}^{k}=d(y^k,u^k)$.

Fig. 3

Algorithm to find the optimal location ($r=1$ and the quality level is given)

Note that in Step 2, only the edges for which the upper bound for the demand captured, $\overline{W}$, is greater than the maximum value found until that moment are considered. The use of this bound in the algorithm allows many edges to be discarded and consequently a reduction in the computational effort required to find the optimal location.

Some computational experiments have been done to analyze the performance of the proposed resolution methods. The networks on which the experiments have been done were taken from Pelegrín et al. (2012) and were randomly generated taking the following combinations for the number or nodes ($n$) and edges ($m$):

• $n=50,100,150,200$.

• $m=n+\frac{n}{2},2n,2n+\frac{n}{2},3n,$ for each $n$.

The length of each edge was randomly chosen within the interval $[5,188]$. If an edge was not used in any shortest path linking any pair of nodes of a network, then the edge was removed from the network. For each combination of $n$ and $m$, the location for the existing facilities and their size (between 2,500 and 10,000 m$^2$) were randomly obtained and the number of existing facilities considered was $p=n/10.$ Finally, for each network, fifty different demand distributions, taking random demands between 5,000 to 10,000 were generated.

Table 1 presents a comparison between the performance of both Algorithm 1 and the resolution of the ILP (5)–(8) using the LINGO software. For each scenario, the location problem average times (in seconds) employed by LINGO (column three) and Algorithm 1 (column five) are presented. Column seven shows the average of candidates for optimal location for each scenario. As this table shows, times employed by Algorithm 1 are, on average, 1.29 % of LINGO’s times. Only in the largest case, with an average of 11,070.32 candidates, time employed by Algorithm 1 is over 1 s (1.089 s) while LINGO needs an average of 141.96 s to find the solution for these cases. The eighth column shows the percentage of edges that Algorithm 1 discarded using the bound proposed in Corollary 1. On average, 64.59 % of the edges were discarded using this bound, which means a significant improvement with respect to searching for the best location for the new facility.

Table 1 Results for Algorithm 1 and LINGO in solving the location problem (average time and standard deviation)

Consider now $r \ge 1$. Suppose that $X_{p}$ and $A_{X_{p}}$ are given, and assume that functions $f_{v}$ are strictly increasing for any node $v$. For any $(v,x,a) \in V \times N \times [L,U]$ define the covering function $\mu (v,x,a)$ as follows,

$$\begin{aligned} \mu (v,x,a)=\left\{ \begin{array}{l@{\quad }l} 1, &{}\hbox {if} \frac{a}{f_{v}(d( v,x) ) }>G_{v} \\ 0,&{}\hbox {otherwise,} \\ \end{array}\right. \end{aligned}$$

that is, $\mu (v,x,a)=1$ if a facility at location $x$ with quality $a$ covers node $v$, and $\mu (v,x,a)=0$ otherwise. Since

$$\begin{aligned} V(Y_{r},A_{Y_{r}})=\bigcup \limits _{k=p+1}^{p+r} V(x_{k},a_{k}), \end{aligned}$$

it follows that

$$\begin{aligned} W(Y_{r},A_{Y_{r}})\!=\! \sum \limits _{k=p+1}^{p+r} W( x_{k},a_{k}) -\; \sum \limits _{v\in \bigcup \limits _{k=p+1}^{p+r} \; V( x_{k},a_{k} ) } \; w(v) \Big (\!\Big (\!\sum \limits _{j=p+1}^{p+r} \mu (v,x_{j},a_{j})\Big )\!-\!1 \Big ). \end{aligned}$$

The value $\sum \nolimits _{k=p+1}^{p+r} W(x_{k},a_{k} )$ is an upper bound of $W(Y_{r},A_{Y_{r}})$, which is used to solve the location problem in Algorithm 2 described in Fig. 4. Note that in Step 2.3, the market share for a potential candidate $Y_{r}^{j}$ is only calculated if its upper bound is higher than the current upper bound.

Fig. 4

Algorithm to find the optimal locations ($r>1$ and given quality levels)

A comparison between the performance of both Algorithm 2 and the resolution of the ILP using LINGO when two or three new facilities are located is presented in Table 2. Computational times are presented in seconds (forth and sixth columns). The last column presents the average number of candidates to be the solution to the problem.

Table 2 Results for Algorithm 2 and LINGO in solving the location problem

When two new facilities are located, times for Algorithm 2 are significantly less than for LINGO. This advantage decreases when the number of candidates increases. Computational times for LINGO vary from 36.148 to 4.881 times the computational effort needed by Algorithm 2. Moreover, LINGO could not solve the two largest problems with 200 nodes (500 and 600 edges), which were solved using Algorithm 2. In these cases, the average number of candidates was 2.66E$+$07 and 1.13E$+$08, respectively.

In the cases where three new facilities are located, LINGO presents a clear advantage over Algorithm 2 whose computational times experimented a significant increase, especially when the number of candidates increase. For this situation, LINGO employed between 0.5 and 40.5 % of the computational time required by Algorithm 2. Moreover, Algorithm 2’s times for networks with more or equal to 150 nodes were too large to take into account. Note that, LINGO also could not solve some large problems with 150 nodes and 450 edges (10 out of 50), and with 200 nodes and 400 edges (27 out of 50). Finally, the cases with 200 nodes, and 500 and 600 edges, where the number of potential solutions was around $10^9$ and $10^{10}$, could not be solved either by LINGO nor Algorithm 2.

When computational times for Algorithm 2 do not appear in Table 2, it is because the times employed were too large. However, when times for LINGO do not appear, it was due to technical software problems.

3.3 The location–quality problem

When the problem consists of finding both locations and quality levels for the new facilities, due to the discontinuities of the capture function $W(y,a)$, the maximum of the profit function is not always attained. In this case, for problem (4), only an $\varepsilon$-optimal solution (see Definition 1) can be guaranteed.

Definition 1

An $\varepsilon$-optimal solution to problem (4) is a pair $(Y^*_r,A^*_{Y_r}) \in N^r \times [L,U]^r$, which satisfies that for any $\varepsilon >0$ there exists $\delta =\delta (\varepsilon )>0$ such that if $(Y_r,A_{Y_r}) \in N^r \times [L,U]^r$ verifies $\Vert A_{Y_r}-A_{Y^*_r}\Vert <\delta$, then $\varPi (Y_r,A_{Y_r})-\varPi (Y^*_r,A^*_{Y_r}) < \varepsilon$.

If $(Y_r^*, A_{Y_r}^*)$ is an $\varepsilon$-optimal solution to the location–quality problem, then $(Y_r(A_{Y_r}^*), A_{Y_r}^*)$, where $Y_r(A_{Y_r}^*)$ is an optimal solution to the location problem when $A_{Y_r}=A_{Y_r}^*$ is also an $\varepsilon$-optimal solution to the location–quality problem. For any $A_{Y_r} \in [L,U]^r$, consider the function

$$\begin{aligned} \varPi \left( A_{Y_{r}}\right) =\varPi \left( Y_{r}(A_{Y_{r}}),A_{Y_{r}}\right) =\max \limits _{Y_{r}\in N^{r}}\varPi \left( Y_{r},A_{Y_{r}}\right) . \end{aligned}$$

Function $\varPi \left( A_{Y_{r}}\right)$ is well defined, and an $\varepsilon$-optimal solution to the problem

$$\begin{aligned} \max _{A_{Y_{r}}\in [L,U]^{r}}\varPi ( A_{Y_{r}}) \end{aligned}$$

is an $\varepsilon$-optimal solution to the location–quality problem.

For any quality vector $A_{Y_r}$, the location vector $Y_r(A_{Y_r})$ can be obtained by using some of the procedures proposed in the previous section. In order to solve the location–quality problem, we apply a branch and bound algorithm on function $\varPi ( A_{Y_{r}})$, which generates a sequence of partitions of $D=[L,U]^{r}$ until an $\varepsilon$-optimal solution is found. The proposed algorithm (Algorithm 3), described in Fig. 5, utilizes the following results.

Fig. 5

Algorithm to solve the location–quality problem

Proposition 3

If $X_{p},\,A_{X_{p}}$, and $Y_{r}$ are given, and functions $f_{v},\,v \in V$ are strictly increasing, then market share function $W(A_{Y_r})=W(Y_r,A_{Y_r})$ is increasing with respect to the quality levels, that is, if $A_{Y_r}^1=( a_{p+1}^1, \ldots ,a_{p+r}^1)$ and $A_{Y_r}^2=( a_{p+1}^2, \ldots ,a_{p+r}^2))$ and $A_{Y_r}^1 < A_{Y_r}^2$, then $W(A_{Y_r}^1) \le W(A_{Y_r}^2)$. Here, $A_{Y_r}^1 < A_{Y_r}^2$ means $a_j^1 \le a_j^2$ for any $j,\,j=p+1,\ldots ,p+r$, and there exists $j$ with $a_j^1 < a_j^2$.

Proof

If $A_{Y_r}^1 < A_{Y_r}^2$, then $\max \{ \frac{a_{p+j}^1}{f_{v} ( d ( v,x_{p+j}) )} :j=1,2,\ldots ,r \} \le \,\max \{ \frac{a_{p+j}^2}{f_{v} ( d ( v,x_{p+j}) )} :j=1,2,\ldots ,r \}$ and, consequently, $V( Y_{r},A_{Y_{r}}^1 )\subseteq V( Y_{r},A_{Y_{r}}^2 )$. Therefore, $W(A_{Y_r}^1) \le W(A_{Y_r}^2)$.

Let $D=D(\underline{A},\overline{A})$ denote the $r$-rectangle whose lower left vertex and upper right vertex are the vectors $\underline{A}=(\underline{a}_1,\ldots ,\underline{a}_r)$ and $\overline{A}=(\overline{a}_1,\ldots ,\overline{a}_r)$, respectively. Proposition 4 provides an upper bound of $\varPi (A_{Y_r})=\varPi (Y_r(A_{Y_r}),A_{Y_r})$ for $A_{Y_{r}} \in D$.

Proposition 4

If $X_{p},\,A_{X_{p}},$ are given, functions $f_{v},\,v \in V$ are strictly increasing, and the cost function $C$ is increasing, then $\forall A_{Y_{r}}\in D=D(\underline{A},\overline{A})$ the following relation holds:

$$\begin{aligned} \varPi (A_{Y_{r}}) \le W(Y_{r}(\overline{A}),\overline{A})-C(\underline{A}). \end{aligned}$$

Proof

Since $C$ is increasing, from Proposition 4, and taking into account that $Y_r(\overline{A})$ is the optimal location when $A_{Y_r}=\overline{A}$, it follows that

$$\begin{aligned} \varPi ( Y_{r}(A_{Y_{r}}),A_{Y_{r}})&= W( Y_{r}(A_{Y_{r}}),A_{Y_{r}}) -C( A_{Y_{r}}) \le W( Y_{r}(A_{Y_{r}}),A_{Y_{r}}) -C( \underline{A}) \\&\quad \le W( Y_{r}(\overline{A}),\overline{A}) -C( \underline{A}). \end{aligned}$$

Next, Algorithm 3 is described. At Step 1, the list of sets to be partitioned, $\mathcal {L}$, is initialized to the total feasible region, $\mathcal {L}=\{D_{1}\}$, with $D_{1}=[L,U]^{r}$. The global lower bound is set to $\beta _{0}^{*}=-\infty$.

At Step 2, a set $D_{k}\in \mathcal {L}$ is partitioned, and lower and upper bounds of $sup\;\varPi$ for every set $D_{ik}$ in the partition are calculated. As the feasible set in the quality problem is an $r$-rectangle, a partition of sets $D_{k}$ into $2$ $r$-intervals has been applied. These new subsets are obtained by splitting each rectangle through the midpoint of the largest sized axis. This partitioning procedure allows us to obtain some bounds of $sup\;\varPi$ in the regions $D_{ik}$ from the bounds calculated for the parent $D_{k}$. Since the demand captured and the cost $C$ are increasing functions of the quality levels, if $D_{ik}=D(\underline{A}_{ik},\overline{A}_{ik})$, from Proposition 4, a local upper bound of $\varPi$ in $D_{ik}$ is

$$\begin{aligned} \alpha (D_{ik})=W(Y_{r}(\overline{A}_{ik}),\overline{A}_{ik})-C\left( \underline{A}_{ik}\right) . \end{aligned}$$

To obtain the local lower bound of $\sup \varPi$ in $D_{ik}$, the highest objective value either in vertex $\underline{A}_{ik}$ or $\overline{A}_{ik}$ is selected, i.e., $\beta (D_{ik})=\max \{\varPi (\underline{A}_{ik}),\varPi (\overline{A}_{ik})\}=\varPi (A_{ik},Y_{r}(A_{ik})),$ where $\varPi (\underline{A}_{ik})$ and $\varPi (\overline{A}_{ik})$ are calculated using some of the procedures proposed in Sect. 3.2. At Step 3, the global lower bound is updated.

At Step 4, sets that do not need to be partitioned in the future are eliminated from the list $\mathcal {L}$. At Step 4(i), the $r$-intervals $D_{ik}$ verifying $\alpha (D_{ik})=\beta (D_{ik})$ are eliminated because this equality implies that $\beta (D_{ik})$ is the maximum profit in $D_{ik}$ and $(Y_{r}(A_{ik}),A_{ik})$ is an optimal solution of $\varPi$ in this rectangle. Sets satisfying condition 4(ii) are not partitioned because an $\varepsilon$-optimal solution in $D_{ik},\,(A_{ik},Y(A_{ik}))$ has been found. At Step 4(iii), all sets with the local upper bound less than the global lower bound are discarded because they do not contain an $\varepsilon$-optimal solution.

At Step 5, the most “promising” rectangle is chosen. We select the set $D_{k}\in \mathcal {L}$ with the highest local lower bound.

The maximum error committed by the algorithm in obtaining the optimum value of $\varPi$ in $D_{ik}$ may be bounded as follows:

$$\begin{aligned}&error(D_{ik})\le \alpha (D_{ik})-\beta (D_{ik}) \\&\quad =W(\overline{A}_{ik})-C(\underline{A}_{ik})-\max \{\varPi (\underline{A}_{ik} ),\varPi (\overline{A}_{ik})\}\le W(\overline{A}_{ik})-C(\underline{A}_{ik} )-\varPi (\overline{A}_{ik}) \\&\quad = W(\overline{A}_{ik})-C(\underline{A}_{ik})-W(\overline{A}_{ik})+C(\overline{A}_{ik})=C(\overline{A}_{ik})-C(\underline{A}_{ik}), \end{aligned}$$

being $W(A)=W(Y_{r}(A),A)$ for $A\in [L,U]^{r}$. Since the cost function $C$ is continuous and the bipartition is an exhaustive subdivision procedure, the above result guarantees the finiteness of the algorithm (see Horst and Tuy 1993). Then, for every prefixed $\varepsilon >0$ (the maximum error allowed) and for each set $D_{k}$, there is a descendant $D_{ik}=D(\underline{A}_{ik},\overline{A}_{ik})$ obtained by successive splits, such that $\varepsilon \le C\left( \overline{A}_{ik}\right) -C(\underline{A}_{ik})$.

These techniques have also been applied to solve location problems by Suárez-Vega et al. (2004b), Hansen et al. (1995, 1997), Redondo et al. (2009), and Plastria (1992), among others.

Example 2

Consider the market represented in Fig. 6, where an existing facility exists at $X_1=x_1$, with quality level $a_1=1$. If firm $A$ wants to open two facilities and the unique choice criterion is the travel distance, disregarding the quality level, an optimal solution is $Y_{2}=( v_{2},v_{4})$. In fact, every pair of locations $(x_2,x_3)$ with $x_2 \in [v_{2},v_{3}[$ and $x_3 \in ]v_{3},v_{4}]$ is an optimal solution to this location problem. The solution is quite different if not only facility locations, but also quality levels have to be determined. In this case, in order to reduce the cost due to the quality level, the facilities must be opened close to demand points, moving away from $X_{1}.$ An $\varepsilon -$optimal solution to the location–quality problem, considering that the quality levels for the new facilities must belong to interval $[0.1,1]$ and taking $\varepsilon =0.001$, is $\big ( Y_{2}^{*},A_{Y_{2}^{*}}\big )=( x_2,x_3; 0.167,0.351)$, which is represented in Fig. 6.

Fig. 6

Network used in Example 2

4 Locating new stores in Gran Canaria

In this section, we apply Algorithm 3 to solve the problem of determining both the location and the size (sales area) of new hypermarkets in the Spanish island of Gran Canaria (Canarian Archipelago). Gran Canaria is 200 km from the western African coast and 1,200 km from the Spanish mainland. The island has a surface area equal to 1,560 $\hbox {km}^{2}$ and a population of 836,092 inhabitants (2008 Census).

In this application, the network $N=N(V,E)$ represents the main roads of the island. The length of the edges corresponds to the travel time, and the demand was aggregated into the 52 districts that form the island. To determine the demand nodes, the gravity center of the individual house locations in each district was calculated and then it was allocated to the closest network node.

According to the Law of Regulation of Commercial Activity in the Canaries (B.O.C. 1994), a hypermarket is a large store with a minimum sales area of 2,500 $\hbox {m}^{2}$. In 2008, eleven hypermarkets already existed in Gran Canaria. These facilities were allocated to the closest network vertex, which resulted in a set with seven nodes. The quality level associated with each of these nodes was the sum of the sales areas of the hypermarkets allocated to it. The distribution of both the demand and the existing hypermarkets is shown in Fig. 7. Note that 59.88 % of the total population and 45.60 % of the hypermarkets sales area are concentrated in the capital, in the northwestern part of the island. The rest of the hypermarkets, and an important part of the demand, is distributed on the eastern and southern areas of the island. The central and western parts of the island are mountainous with low population densities.

Fig. 7

The market

We solved the location–quality problem for $r$ varying from 1 to 3. For each facility, the quality level, $a$, is given by the hypermarkets’ sales area measured in thousands of $m^{2}$ with $a\in [L,U]=[2.5,10]$.

In order to analyze the effect in the model on different customer behavior with respect to the travel distance, for every node $v$, we have considered $f_{v}(d)=d^{\lambda }$, with $\lambda =0.5,\; 1,\; 2$. Of course, the higher the value of $\lambda ,$ the higher customers’ resistance to making long trips to make purchases. Function $f_{v}(d)=d^{\lambda }$ with $\lambda > 0$ is one of the possible distance decay functions used in the class of gravity models defined by $T_{ij} = F(i)G(j)H(d_{ij})$, which represents the interaction between population centers $i$ and $j$ separated by a distance equal to $d_{ij}$, and characterized by values $F(i)$ and $G(j)$, respectively (Sen and Smith 1995). This decay function has been utilized often to formulate the behavior of the customer in competitive location models (see Berman and Krass 2002; Drezner 1994a; Drezner et al. 2002; Plastria 1997, among others). Figure 8 shows the market allocated to each existing hypermarket for the cases with the lowest ($\lambda =0.5$) and the highest ($\lambda =2$) distance penalization. When customers present high predisposition to travel to purchase, the size of the hypermarket is the most important factor. In this case, the two largest hypermarkets (#2 and #7) capture 74.66 % of the total market. In particular, store #2 captures demand in all the island, including areas around other existing hypermarkets. The rest of the stores capture only the demand of the districts where they are located because they are too small or they are too close to the largest existing facility. When $\lambda =2$, each facility captures the demand around it and the larger the size, the larger the capture. If the results for $\lambda =0.5$ and $\lambda =2$ are compared, the main difference occurs for the largest store that loses 24.33 points of market share when the predisposition to travel decreases.

Fig. 8

Market for the existing hypermarkets for different distance decay parameters

The variable cost associated with the quality level has been modelled taking into account the suggestions of a consultant of an important chain of supermarkets that operates in the Island. This cost is represented by a nonnegative and continuous function $C(a)$ verifying $C(0)=0$, with decreasing marginal cost for $0 \le a \le a^*$ and increasing marginal cost if $a^* < a$. So, to represent this behavior, we have considered a three-order polynomial cost function, concave for $a \in [0,a^*]$ and convex for $a \in [a^*, +\infty )$. Point $a^*$ is the inflexion point of function $C$, where the marginal costs change from decreasing to increasing. The cost function considered was

$$\begin{aligned} C(a)=\frac{1{,}500}{43}a^{3}-\frac{28{,}125}{43}a^{2}+8{,}000a, \end{aligned}$$

where $a^*=6.250$. This function is shown in Fig. 9. Functions with this shape are often utilized in economic contexts (Chiang 2006).

Fig. 9

Size cost functions considered

The location–size problem was solved using Algorithm 3. To obtain the lower bounds (in Step 2.1), Algorithm 1, Algorithm 2, or ILP can be used for solving the corresponding location problems. We applied the branch and bound algorithm with $\varepsilon =0.001$, which guarantees a maximum error of 0.1 %, using a computer working at 3.2 GHz. In order to obtain a more clear geographical representation for the best locations found for each scenario, the neighboring locations have been aggregated and represented in Fig. 10.

Fig. 10

Best locations for the new hypermarkets

Table 3 shows the results obtained for the different scenarios, considering the different values of the distance decay parameter, when the number of new stores varies from one to three. For each case, the profits and market share obtained for the new firm, and the locations and sizes for the new facilities are presented. The results show how the behavior of the customers respect to the travel distance influence on the solution. When the willingness of customers to move to buy decreases, that is, when $\lambda$ increases, bigger hypermarkets are opened, varying sometimes the locations, leading to an increase in market share and profit. This increase in market share is a consequence not only of the bigger size of the new facility but also of the travel distance effect on the demand captured by the existing and new stores.

Table 3 Results for the different values of $r$

For $r=1$, in all cases, the best locations for the new hypermarket were sited in the capital of the island (see Fig. 10), with a maximum distance of 1.1 km between them, where both demand and rival stores are mostly concentrated. When customers present the highest predisposition to travel ($\lambda =0.5$), the new hypermarket is set at the demand node with the highest population and where no hypermarkets exist. This new store is set with the minimum size allowed which is sufficient to capture the demand allocated at this node. When the predisposition to travel decreases, the new hypermarket is located in an edge joining two demand nodes and close to an existing store. In these cases, the new facility had to have a greater size in order to be more competitive than the existing one and capture the demand of these two demand nodes. The average time needed to solve these problems, using Algorithm 1 for the location problems, was 0.39 s.

The location solution for the problem when two new stores are opened consists of adding a new store to the one obtained for the case with $r=1$ (see Table 3; Fig. 10). When $\lambda =0.5$, the second store is located in the second highest populated demand node with the minimum size allowed. When customers’ predisposition to travel to buy decreases, the second hypermarket moves away more, the greater the lambda, from the area where the existing hypermarkets are concentrated. As for one new store, the market share of the new firm increases when customers’ willingness to travel to buy decreases, such that the market captured when $\lambda =2$ is higher than double that obtained when $\lambda =0.5$. The average time needed to solve these problems, using Algorithm 2 for the location problems, was 17.32 s.

The solution (size and location) to the problem of locating three new hypermarkets coincides with the result of a sequential selection procedure where a new location is chosen in each stage (see Table 3; Fig. 10). When $\lambda =0.5$, a third store with the minimum size is also located in the capital but far away from the existing hypermarkets. When the predisposition to travel decreases, the new facility is located in the most populated area of the southeastern part of the island. As in the two previous cases, the market share increases when the willingness to travel to buy decreases (market share for $\lambda =2$ is around double that for $\lambda =0.5$). In this case, using Algorithm 2 for solving the location problem, an average of 140.5 min was needed to obtain these results.

Observe that, in a general scenario, when $\lambda$ increases, the opening of a facility closer to the customers may be desirable or not. If the aversion to the distance increases moderately, a facility belonging to firm $A$ might obtain at less the same profit without changing its location if its quality increases and the associated increase in cost is low enough. If the aversion to the distance is too high and the quality level required to compensate the effect of the distance is not reachable or it is too costly, the best strategy might be to locate the facilities very close to demand points, avoiding locations with existing facilities, thus emerging local spatial monopolies.

Table 4 shows a comparison between the market shares of the different facilities before (Market 1) and after (Market 2) the entry of three new competing facilities. Existing facilities are denoted as E1–E7 and the new ones are N1, N2, and N3. When $\lambda =0.5$, all the capture for the new facilities (18.75 % of market share) is obtained from E2’s market, from districts pertaining to the capital, whereas the capture for the rest of existing facilities remain equal. The new facilities are located in the most populated districts of the capital and set the minimum possible size for a hypermarket in the Canaries. Their market share is exclusively taken from the demand points in the district where they are located. If $\lambda =2$, i.e., when customers present a high aversion to travel to buy, the losses are shared among facilities E2 and E4 (principally), which are in the capital and, E3 and E7 (for a less degree) located in the southern part of the island. The last is a consequence of the location of the two new facilities outside the capital, in the North (N2) and in the East (N3).

Table 4 Size and market share for the facilities before and after the entry of the new firm

As Table 3 shows, the new firm’s profits have a high variability depending on the parameter value that identifies customers reaction to the increase in travel distance. So the error made when we choose a solution obtained under a certain customer behavior hypothesis and the patronizing is made according to a different behavior, has been calculated. For every pair of scenarios $(i,j)$, corresponding to the solution obtained for scenario $i$ when customer behavior is reflected by scenario $j$, we obtain the value $e_{ij}$ given by

$$\begin{aligned} e_{ij}=100\cdot \frac{\varPi _{j}(S_{j})-\varPi _{j}(S_{i})}{\varPi _{j}(S_{j})} \end{aligned}$$

where $S_{i}$ and $S_{j}$ are the solutions for scenarios $i$ and $j$, respectively, and $\varPi _{j}$ represents the objective value for the scenario $j$. Table 5 shows the summary of the percentages of error for the different scenarios. The first column identifies the scenario whose solution has been chosen. The following columns describe, for each scenario $i,$ how $e_{ij},$ with $j=1,\ldots ,3$, behaves.

Table 5 Percentage error for the different scenarios

From the results presented in Table 5, we can conclude that, if the decision maker has no idea about the true value of the parameter that reflects the customers behavior, the best option is to take the solution, which considers that customers have a high predisposition to travel to buy ($\lambda =0.5$) because it is the one that minimizes the average error in the three scenarios ($r=1,2,3$). The worst cases occur when customers’ have high predisposition to travel but the solution is obtained supposing the opposite. In those cases, the percentage error varies from 182.35 to 205.45 %.

5 Concluding remarks

In this paper, we study a location–quality problem on networks where two firms compete in order to maximize profits; both location and quality level are decision variables. Customers behave according to a binary choice rule and demand is assumed to be inelastic. In this case, an optimal solution may not exist and only an $\varepsilon$-optimal solution is guaranteed (Suárez-Vega et al. 2004b). Although many authors have studied either the location or quality problem, to the authors’ knowledge, the joint location–quality problem on networks with a binary choice rule has never been solved.

For solving the location problem, an integer linear program was proposed. As alternative to the ILP, two exact algorithms for solving the problem were presented. For $r=1$, we propose an upper bound for the total capture in an edge and it was introduced in Algorithm 1 to discard edges where the optimal solution is not possible. The use of this algorithm for solving the location problems presented in this paper has meant an average reduction of 64.59 % of the edges investigated in the search for the best solution. For a general value of $r$, an upper bound and an alternative expression for the new firm capture are proposed. These results have been introduced in Algorithm 2 allowing for a significant improvement with respect to an exhaustive-based method. A comparison between the performance of both Algorithm 1 and Algorithm 2 and the resolution of the ILP using LINGO is presented. We conclude that for the problems solved in this paper, Algorithm 1 is always faster than LINGO and for $r=2$, Algorithm 2 improves LINGO, but for $r=3$, LINGO goes faster than Algorithm 2.

Using either the ILP program, Algorithm 1 (for $r=1$) or Algorithm 2 (for $r>1$), we have designed a branch and bound-based algorithm, which allows us to find an $\varepsilon$-optimal solution to the joint location–quality problem. Defining the quality as the facility size, the algorithm proposed is employed to find the best locations and the sizes for the hypermarkets belonging to a firm that wants to enter the retail market in Gran Canaria (Spain).

The problem has been solved in several scenarios, changing the decay distance parameter reflecting the customers willingness to travel for shopping. When customers present hight predisposition to travel, the best locations for the new facilities are in the capital, where 59.88 % of the total population and 45.60 % of hypermarkets sales area are concentrated. When customers present low predisposition to travel to make purchases, the first hypermarket is located in the capital but the others are sited far away, in the North (where no hypermarkets exist) or in the East (in a populated area between two hypermarkets).

The study of the error produced when the chosen solution does not coincide with the customers’ behavior suggests that the most favorable choice in this case is to apply the model assuming the lowest value for the decay parameter. The worst case occurs when the customers have high predisposition to travel but the solution is obtained supposing the opposite, with errors that varied from 182.35 to 205.45 %.

The work presented in this paper can be extended in several directions. One of this possible extensions is the study of the quality–location problem for nonbinary choice rules. We can consider that the behavior of the customer is modelled by a nonnegative, continuous decreasing function of the travel distance, which represents the part of demand captured by each facility (some results about the use of these decay functions in covering location problems can be found in Berman et al. 2003, 2010). For each firm, the closest facility to the customer could capture part of the demand, the demand captured by each of these facilities would depend on the difference in travel distance from the customer to the closest facility of the competing firms. A customer would use firm $A$ exclusively if the distance from this customer to the competitors exceeds the distance to firm $A$ in an amount greater than or equal to a threshold. Other models to be considered are those where the customer choice rule is probabilistic or proportional; in this case, the demand of a customer is distributed among the facilities operating in the market, and not only among the closest ones, according to the travel distance between the consumers and the stores. On the other hand, we could study the location problem for unessential demands; in this situation, the customer may no to use all its buying power if the facilities are considered not attractive enough. Moreover, if more than one firm plans enter the market, several scenarios may arise depending on the manner in which the competence is carried out (for example, firms may act individually or according to collusion agreements). Finally, location problems with preemptive strategies, anticipating the actions of future competitors, and dynamic location models, considering the opening of several facilities in different periods of time, could be analyzed.