On Location-Allocation Problems for Dimensional Facilities

Abstract

This paper deals with a bilevel approach of the location-allocation problem with dimensional facilities. We present a general model that allows us to consider very general shapes of domains for the dimensional facilities, and we prove the existence of optimal solutions under mild assumptions. To achieve these results, we borrow tools from optimal transport mass theory that allow us to give explicit solution structure of the considered lower level problem. We also provide a discretization approach that can approximate, up to any degree of accuracy, the optimal solution of the original problem. This discrete approximation can be optimally solved via a mixed-integer linear program. To address very large instance sizes, we also provide a GRASP heuristic that performs rather well according to our experimental results. The paper also reports some experiments run on test data.

1 Introduction

Location-allocation problems are very important problems nowadays in the area of Operation Research and Logistics: they consist of finding the placement of a number of servers and deciding the assignments of the existing demand in order to minimize some general objective function. See, for example, [1,2,3]. Depending on the framework, the problem can be cast within the family of continuous non-convex or mixed-integer programming problems and in some cases it is closely related with the design of Voronoi partitions [4] in computational geometry. These problems are important by themselves for their mathematical implications but also by their many applications to several important areas such as territorial design, market share, hub-and-spoke design, voting district and shape optimization [5,6,7,8,9,10].

Sometimes these servers can be identified with extended domains: in this case we will speak about dimensional facilities. Mathematically, a dimensional facility location problem corresponds to finding the best position of a fixed shape geometrical figure [11, 12]. The resolution of the problem in this case must take care of the optimizing aspect of a certain utility function and also of the geometry of the facility.

In spite of their importance, to the best of our knowledge, the consideration of location-allocation problems with respect to dimensional facilities has not been extensively considered in the literature. Some exception is the paper [13].

There is a number of papers in the literature dealing with the so-called location-allocation problem, i.e., a combination of the two tasks, where one asks for the best positions of the servers together with the best partition of the demand. The location-allocation approach gives rise to a natural bilevel optimization problem where in the first level the location decisions are made under the constraint that the allocation will be given as a best reply function. This bilevel problem is in general hard to solve. In the particular case where the facilities are dimensional it becomes harder. See for references Ch. 14 in [1], Ch. 5 in [2].

Situations like these appear very often in Game Theory when two players compete in a hierarchical scheme and the model is usually called Stackelberg game (or Leader/follower game). In these bilevel problems, we have almost never an explicit expression of the solution for the lower level problem to be considered and then included to help in solving the upper level one.

Sometimes and under some suitable assumptions, the solution of the lower level problem (the so-called best reply) is obtained explicitly and this helps in the resolution of the upper level problem. This happens, for example, when we use optimal transport tools as done in [14, 15].

This theory started with the problem of moving a pile of sand into a hole of the same volume minimizing the transportation cost, formulated by Monge. Then, Kantorovich relaxed the problem providing a dual formulation. Recently these classical results have been used in a large number of application contexts as Transportation, Logistics, Physics, et cetera [16,17,18,19].

By using optimal transport theory, it is possible to obtain a structure of the solution of the lower level problem and then to prove the existence of the solution of the bilevel model. Moreover, the obtained structure of the partition that optimizes the demand problem is fundamental in order to develop some approximation results and some computational algorithms.

This paper generalizes previous result in [13] since that paper only considered the lower level problem and with particular shapes for the dimensional facilities. Moreover, the contribution of this paper is threefold. First, we formulate the bilevel location-allocation problem for very general dimensional facilities and prove, under suitable conditions, the existence of optimal solutions (the reader is referred to [20, 21] for further details on bilevel optimization and many of its applications). Secondly, we give an approximation scheme to solve the problem, discretizing some of its elements, providing convergence results to the optimal solution of the original problem [22,23,24]. Finally, we also develop an exact solution algorithm applicable to the discrete approximation scheme that reduces the problem to solve a mixed-integer linear problem. In addition, we also propose a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic, see [25], that performs very well experimentally in large size instances. The reader is referred to [26] for a complete list of successful applications of GRASP to NP-hard problems. The paper also reports our computational experiments with different test cases. For the sake of readability, we restrict ourselves to the two-dimensional setting although most of the results in this paper extend further to finite dimension spaces.

The rest of the paper is organized as follows: in the second section the bilevel problem is presented and existence results of optimal solutions are obtained; in the third section a discretization scheme is defined and some convergence theorems are proved. In section four different solution approaches are presented: an exact mixed-integer linear programming model and a GRASP heuristic. We report computational results on these algorithms based on a testbed of examples. The paper finishes with some conclusions and an outline for future research.

2 A Bilevel Model and Existence of Optimal Solutions

2.1 Bilevel Approach

We are given $\varOmega$, a Borel, compact subset of $\mathbb {R}^2$ which is the closure of a nonempty open connected set that represents a demand region. We assume that customers in $\varOmega$ are distributed according to a demand density D that is an absolutely continuous probability measure with respect to the Lebesgue measure, where $D: \varOmega \rightarrow \mathbb {R}$ is a nonnegative function with unit integral $\int _\varOmega D(q) \mathrm{d}q=1$, being $q=(x,y)\in \varOmega$ and $\mathrm{d}q=\mathrm{d}x\mathrm{d}y$. The goal is to locate $\rho$ given compact sets $P_1,\ldots ,P_{\rho }$ ($\rho \in \mathbb {N}$) in $\varOmega$, assuming that all of them are the closure of nonempty open connected sets, representing some service centers with dimensional extension. From now on, any set with these properties will be called a dimensional facility. The reader can observe that, according to this definition, $\varOmega$ is also a dimensional facility.

For each $i\in \{1,\ldots ,\rho \}$, let $P_i^{\underline{0}}$ be $P_i$ located on the plane with its centroid $p_i$ placed at $\underline{0}=(0,0)\in \mathbb {R}^2$. Given $q_i\in \mathbb {R}^2$, we use the notation $P_i^{q_i}=q_i+P_i^{\underline{0}}$ to refer to the dimensional facility $P_i^{\underline{0}}$ displaced by the translation vector $\overrightarrow{q_i}$ (see Fig. 1). Observe that $q_i$ is the centroid of $P_i^{q_i}$. For $P_i^{q_i}$, we call to $q_i\in \mathbb {R}^2$ a location for $P_i$. Then, we use the notation $P_i$ to refer the dimensional facility without specifying its location and the same applies for $p_i$. Note that, for the sake of simplicity, we are characterizing the location of $P_i$ by its centroid. However, we could characterize the location of $P_i$ by any other point.

Fig. 1

Two possible locations in the plane for the dimensional facility $P_i$

The problem considered in this paper is to locate $\rho$ dimensional facilities $P_1,\ldots ,P_{\rho }$ in $\varOmega$ and also to find the partition (market share) $A_1,\ldots ,A_{\rho }$ satisfying that the dimensional facility $P_i$ serves the consumer demand in the region ${A}_i\subseteq \varOmega$ optimizing a suitable criterion: we will find a partition of the set $\varOmega {\setminus } \{\text {int}(P_1)\cup \cdots \cup \text {int}(P_{\rho })\}$, i.e., a finite family $(A_i)_{i=1}^{\rho }$ of pairwise disjoint Borel sets such that $\bigcup _{i=1}^{\rho } {A}_i= \varOmega {\setminus } \{\text {int}(P_1)\cup \cdots \cup \text {int}(P_{\rho })\}$ up to D-negligible sets.

We require that the location of the dimensional facilities $P_1,\ldots ,P_{\rho }$ in $\varOmega$ must satisfy that the interior do not intersect and obviously that $P_i\subseteq \varOmega$ for all $i\in \{1,\ldots ,\rho \}$. A family of $\rho$ dimensional facilities that satisfy the above conditions will be called a suitable solution. We also assume that there is a location of the dimensional facilities verifying the above conditions, i.e., the problem considered has at least one suitable solution.

In order to formally describe the set of suitable solutions for the dimensional facilities $P_1,\ldots ,P_{\rho }$, we introduce the following notation: let $\varOmega _i$ denote the region of $\mathbb {R}^2$ in which locating $P_i$ makes it to be contained in $\varOmega$, i.e.,

$$\begin{aligned} \varOmega _i = \left\{ q_i\in \mathbb {R}^2 : P_i^{q_i}\subseteq \varOmega \right\} , \end{aligned}$$

for each $i\in \{1,\ldots ,\rho \}$. Obviously, $\varOmega _i\subseteq \varOmega$, for all $i\in \{1,\ldots ,\rho \}$. Then, the set of suitable solutions is

$$\begin{aligned} \varGamma = \left\{ (q_1,\ldots ,q_{\rho })\in \varOmega _1\times \cdots \times \varOmega _{\rho } : \text {int}\left( P_i^{q_i}\right) \cap \text {int}\left( P_j^{q_j}\right) =\emptyset , \quad \forall i,j\in \{1,\ldots ,\rho \},i\not = j\right\} . \end{aligned}$$

Clearly, $\varGamma \subseteq \varOmega ^{\rho }\subseteq \mathbb {R}^{2\rho }$. Recall that we are assuming that $\varGamma \not = \emptyset$.

We consider that the service costs u paid from a point $q\in \mathbb {R}^2$ with respect to the dimensional facility $P_i$ is given by a continuous function $u_i:\mathbb {R}^2\times \mathbb {R}^2 \rightarrow \mathbb {R}$ that depends on the considered point q and the location $q_i\in \mathbb {R}^2$ of the dimensional facility $P_i$:

$$\begin{aligned} u \left( q, P_i^{q_i}\right) = u_i (q,q_i), \end{aligned}$$

for each $i\in \{1,\ldots ,\rho \}$. To clarify the meaning of choosing the cost u in this way, we indicate some interesting particular cases (among others) of u and their interpretations:

• Service point case: this is the most intuitive situation. Here, the customer point $q\in \varOmega$ has to reach the service point in $P_i$ (or vice versa) to satisfy its demand [11]. Assume that the role of the service point is played by the centroid $p_i$ of $P_i$. Then, u can be chosen as

  $$\begin{aligned} u \left( q, P_i^{q_i}\right) = f_i (\gamma _i (q-q_i)), \end{aligned}$$

  being $f_i:\mathbb {R} \rightarrow \mathbb {R}$ a continuous function and $\gamma _i: \mathbb {R}^2 \rightarrow \mathbb {R}$ a norm, and where we are considering a measure of the distance between q and $q_i$ according to the norm $\gamma _i$. Note that, although in this case the service cost does not depend on the shape of the dimensional facility $P_i$ but only on its location, the shape of the dimensional facilities still plays a role in the problem since it determines the set of suitable solutions $\varGamma$ and also some others aspects of the problem as we will see later.

• Service cost dependent on the shape of the facility: in this case the measure of the distance from the customer point $q\in \varOmega$ to the dimensional facility $P_i$ is related to its shape. In particular, we can consider the following cases:

  • Cost induced by the Minkowski functional (see [27]): assume that the dimensional facility $P_i$ is closed, convex, with non-empty interior, then $P_i$ induces a gauge $\gamma _{P_i}: \mathbb {R}^2\rightarrow \mathbb {R}$ defined by the Minkowski functional

    $$\begin{aligned} \gamma _{P_i}(q) = \inf \left\{ \lambda > 0 : q\in \lambda P_i^{\underline{0}}\right\} , \end{aligned}$$

    where $\lambda P_i^{\underline{0}}$ denotes the resulting set after applying the homothecy of center $\underline{0}$ and ratio $\lambda$ to the set $P_i^{\underline{0}}$. Observe that $\gamma _{P_i}(q)=1$ if $q\in \partial P_i^{\underline{0}}$ and that $\gamma _{P_i}(q)<1$ if $q\in \text {int}(P_i^{\underline{0}})$. Hence, a way to measure how far the customer point $q\in \varOmega$ is from the dimensional facility $P_i^{\underline{0}}$ is using the continuous functional

    $$\begin{aligned} \tilde{\gamma }_{P_i}(q) = {\left\{ \begin{array}{ll} \gamma _{P_i}(q)-1, &{} \hbox {if }q\notin P_i^{\underline{0}}, \\ 0, &{} \hbox {if } q\in P_i^{\underline{0}}, \end{array}\right. } \end{aligned}$$

    where only the points in the set $P_i^{\underline{0}}$ have assigned the value 0. Taking into account the above discussion, a natural way to define the cost in this context is

    $$\begin{aligned} u(q,P_i^{q_i}) = {\left\{ \begin{array}{ll} f_i(\gamma _{P_i}(q-q_i)-1), &{} \hbox {if }q\notin P_i^{q_i}, \\ f_i(0), &{} \hbox {if }q\in P_i^{q_i}, \end{array}\right. } \end{aligned}$$

    where $f_i:\mathbb {R} \rightarrow \mathbb {R}$ is a continuous function. Note that the cost $u(q,P_i^{q_i})$ depends on the location of the dimensional facility $P_i$ as well as of its shape.

  • Worst case cost: this is the case in which the cost u paid from a customer point $q\in \varOmega$ with respect to the dimensional facility $P_i^{q_i}$ is chosen as the maximum distance between q and $P_i^{q_i}$ (see [28]), i.e., $u(q,P_i^{q_i}) = \max _{\tilde{q}\in P_i^{q_i}} \gamma _i(q-\tilde{q}),$ being $\gamma _i$ a norm. Or more generally, $u(q,P_i^{q_i}) = f_i\left( \max _{\tilde{q}\in P_i^{q_i}} \gamma _i(q-\tilde{q})\right) ,$ where $f_i:\mathbb {R} \rightarrow \mathbb {R}$ is a continuous function. In the particular case in which $P_i$ is a polygon, we observe that the cost can be obtained as $u(q,P_i^{q_i}) = f_i\left( \max _{j=1,\ldots ,n_i} \gamma _i(q-[q_i+v_j^i]) \right) ,$ where $\{v_1^i,\ldots ,v_{n_i}^i\}$ are the vertices of $P_i^{\underline{0}}$. This last observation is interesting from a computational point of view.

Given a suitable solution $Q = (q_1,\ldots ,q_\rho )\in \varGamma$, we introduce the notation $\varOmega (Q)=\varOmega {\setminus } \{\text {int}(P_1^{q_1})\cup \cdots \cup \text {int}(P_{\rho }^{q_\rho })\}$ to indicate the region of $\varOmega$ to be partitioned as a function of the location of the dimensional facilities. In addition, we denote by $\mathcal {A}_{\rho }(Q)$ the set of all partitions, up to D-negligible sets, in $\rho$ sub-regions of the region $\varOmega (Q)$ and by $A(Q) = (A_1(Q),\ldots , A_{\rho }(Q))$ an element of $\mathcal {A}_{\rho }(Q)$.

We are interested in finding a partition $A(Q)=(A_1(Q),\ldots ,A_{\rho }(Q))$ of the customers in $\varOmega (Q)$ that solves the following problem:

where $a_i>0$ is the cost incurred by each customer to access dimensional facility $P_i$ per unit demand and the second term in each integral

$$\begin{aligned} U_i(A_i(Q))= \int _{{A}_i(Q)} u\left( q, P_i^{q_i}\right) D(q) \mathrm{d}q \end{aligned}$$

is the distribution cost in the service region ${A}_i(Q)$, for each $i\in \{1,\ldots ,\rho \}$.

Once, that partition is obtained we would like to get the best location of the $\rho$ facilities in such a way that some additional costs are minimized, knowing that, given a suitable solution Q, the best partition of the customers is given by solving the above problem LL(Q), usually called lower level problem. These additional costs are: (1) the installation cost of each facility; (2) a cost due to the waiting time to be served by each facility; (3) a cost induced by the demand that is lost. In the following, we describe in detail these costs. (The reader is referred to [1], for a detailed discussion of different objective functions and costs appearing in Location Analysis.) We note in passing that even to evaluate the objective function of the above location problem, it is previously required to find the optimal partition solving problem LL(Q).

• (1) Installation cost: suppose that in $\varOmega$, besides a demand density D, there exists another absolutely continuous measure with respect to the Lebesgue measure, called B, to model the base installation costs. We assume that $B: \varOmega \rightarrow \mathbb {R}$ is a nonnegative function with finite integral $\int _\varOmega B(q) \mathrm{d}q < \infty$. For a suitable solution $Q=(q_1,\ldots ,q_{\rho })\in \varGamma$, the installation cost of the dimensional facility $P_i$ is modeled by the non-decreasing continuous function $I_i: \omega ^I_i\in [0,+\infty ) \rightarrow I_i(\omega ^I_i)\in [0,+\infty )\subseteq \mathbb {R}$, being $\omega ^I_i= \int _{P_i^{q_i}} B(q) \mathrm{d}q$, for each $i\in \{1,\ldots ,\rho \}$. There are many realistic installation costs that fit within this framework: standard set up cost fits by taking $I_i(\omega ^I_i)=F_i\in \mathbb {R}$ for all $\omega ^I_i\in \mathbb {R}$; square meter cost is obtained assuming that B is the density of the square meter cost in $\varOmega$ and that $F_i\in \mathbb {R}$ is the fixed cost of building the dimensional facility $P_i$, then the installation cost of $P_i$ is $I_i(\omega ^I_i)=F_i+\int _{P_i^{q_i}} B(q) \mathrm{d}q$ for all $\omega ^I_i\in \mathbb {R}$, $i\in \{1,\ldots ,\rho \}$; square meter cost with economy of scale also fits taking $I_i(\omega ^I_i)=F_i+\tilde{I}_i(\int _{P_i^{q_i}} B(q) \mathrm{d}q )$, being $\tilde{I}_i: \omega ^I_i\in \mathbb {R} \rightarrow \tilde{I}_i(\omega ^I_i)\in [0,+\infty )\subseteq \mathbb {R}$ a non-decreasing, continuous and concave function, for all $\omega ^I_i\in \mathbb {R}$ and $i\in \{1,\ldots ,\rho \}$.

• (2) Congestion cost: if $A(Q)=(A_1(Q),\ldots ,A_{\rho }(Q))$ is a partition of the customers in $\varOmega (Q)$ for a suitable solution $Q\in \varGamma$, we consider the congestion cost $C_i: \omega ^C_i\in [0,1] \rightarrow C_i(\omega _i^C)\in [0,+\infty )\subseteq \mathbb {R}$ for facility $P_i$, where $\omega ^C_i= \int _{{A}_i(Q)} D(q) \mathrm{d}q$ and $C_i$ is non-decreasing and continuous, for any $i\in \{1,\ldots ,\rho \}$. Congestion cost is the most relevant of the above-mentioned additional costs, since as we will see, it induces in our problem a hierarchical structure of bilevel optimization.

• (3) Lost demand cost: a lost demand cost is computed over the lost demand in $\varOmega {\setminus } \varOmega (Q)=\{\text {int}(P_1^{q_1})\cup \cdots \cup \text {int}(P_{\rho }^{q_\rho })\}$. Lost demand cost is given by $L: \omega ^L\in [0,1] \rightarrow L(\omega ^L)\in [0,+\infty )\subseteq \mathbb {R}$, being L a non-decreasing and continuous function, and where $\omega ^L=\int _{P_1^{q_1}\cup \cdots \cup P_{\rho }^{q_{\rho }}} D(q)\mathrm{d}q = \sum _{i=1}^{\rho } \int _{P_i^{q_i}} D(q) \mathrm{d}q$. We are assuming that the demand in the region $P_i^{q_i}\subseteq \varOmega$ is incompatible with installation of $P_i$ within that region, for any $i\in \{1,\ldots ,\rho \}$, and therefore, lost demand has to be accounted for. This assumption can be dropped taking $L(\omega ^L)=0$ for all $\omega ^L\in [0,1]$.

The above costs induce the following constrained optimization problem. The optimal suitable solution of the dimensional facilities $Q^*=(q_1^*,\ldots ,q_{\rho }^*)\in \varGamma$ can be obtained solving the following bilevel problem:

being

$$\begin{aligned} \mathcal {F} (Q) := \displaystyle \sum _{i=1}^{\rho } \left[ I_i \biggl ( \int _{P_i^{q_i}} B(q) \mathrm{d}q \biggr ) + C_i \biggl ( \int _{\widehat{A}_i (Q)} D(q) \mathrm{d}q \biggr )\right] + L\biggl ( \int _{P_1^{q_1}\cup \cdots \cup P_{\rho }^{q_{\rho }}} D(q) \mathrm{d}q\biggr ). \end{aligned}$$

Observe that for a given suitable solution $Q\in \varGamma$, the partition $\widehat{A}(Q)$ of $\varOmega (Q)$ is given by a solution of problem LL(Q). The solution of the location-allocation problem will be the pair $(Q^*, \widehat{A}(Q^*))$ where $Q^*$ solves problem BL. Let us remark that if $Q^*=(q^*_1,\ldots ,q^*_{\rho })$ is an optimal suitable solution of the bilevel problem BL, then for any $i\in \{1,\ldots ,{\rho }\}$, the dimensional facility $P_i^{q_i^*}$ is uniquely determined by its location (centroid) $q_i^*$, since we are assuming that its shape is fixed.

Bilevel optimization requires to have a nested optimization problem as an explicit constraint in the model. Most classical location models include an allocation phase that requires to decide how the costumers will patronize the new facilities, which is actually a nested optimization problem. However, in the standard literature of location there exists an explicit form to impose that condition that reduces to closest assignment. Hence, bilevel optimization is not needed. This is not our case, since we do not have an explicit form of the optimal response function and therefore we need to resort to the bilevel approach (see [29]).

2.2 Resolution via Optimal Transport Mass

Consider problem LL(Q) for a given suitable solution $Q\in \varGamma$. We point out that for dimensional facilities, we cannot directly apply the optimal transport theory as done in [13,14,15], because the characterization of the optimal partition holds when the measure $\nu$ has a discrete support. However, we can prove the existence of solution for problem LL(Q) by identifying each dimensional facility with its centroid, giving to the measure a discrete support, as the proof of the following theorem shows. Thus, building upon the results that appear in the mentioned works, we can obtain a result similar to the one given in those papers but applicable in this more general framework.

Theorem 2.1

Let $Q=(q_1,\ldots ,q_{\rho })\in \varGamma$. Suppose that the set

$$\begin{aligned} \left\{ q\in \varOmega (Q): a_i + u\left( q,P_i^{q_i}\right) = a_j + u\left( q,P_j^{q_j}\right) \right\} \end{aligned}$$

(1)

is D-negligible, for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not = j$. Then problem LL(Q) admits a unique solution $A(Q)=(A_1(Q),\ldots ,A_{\rho }(Q))$ that verifies

$$\begin{aligned} A_i(Q) \!=\! \left\{ q\in \varOmega (Q): a_i \!+\! u\left( q,P_i^{q_i}\right) < a_j + u\left( q,P_j^{q_j}\right) , \,\, \forall j\in \{1,\ldots ,\rho \}, j\not =i\right\} \end{aligned}$$

(2)

for each $i\in \{1,\ldots ,\rho \}$, where the equalities are intended up to D-negligible sets.

Proof

To prove the existence of solution for problem LL(Q), we rewrite it as a Monge optimal transport problem (see Section 2.1 in [13]). In the proof, we use the absolutely continuous probability measure $\tilde{\mu }(q) = \tilde{D}(q) \mathrm{d}q$ being $\tilde{D}(q) = \dfrac{1}{\int _{\varOmega (Q)} D(q)\mathrm{d}q} D(q)$. Indeed, we prove the existence of solution for the auxiliary problem

$$\begin{aligned} \inf _{A(Q)\in \mathcal {A}_{\rho }(Q)} \sum _{i=1}^{\rho } \left\{ \int _{{A}_i(Q)} \left[ a_i + u(q, P_i^{q_i}) \right] \tilde{D}(q) \mathrm{d}q \right\} , \end{aligned}$$

(3)

which implies the existence of solution for problem LL(Q).

Let S be the unit simplex in $\mathbb {R}^{\rho }$ defined by $S=\left\{ \omega =(\omega _1,\ldots ,\omega _{\rho })\in \mathbb {R}^{\rho } : \omega _i\ge 0,\right. \left. \sum _{i=1}^{\rho } \omega _i = 1\right\}$. Then, we can rewrite problem (3) in the following form:

$$\begin{aligned} \inf _{\omega \in S} \left( \inf _{A(Q)\in \mathcal {A}_{\rho }(Q)} \left\{ \sum _{i=1}^{\rho } \left[ \int _{{A}_i(Q)} u_i(q, q_i) \tilde{D}(q)\mathrm{d}q \right] : \int _{{A}_i(Q)} \tilde{D}(q)\mathrm{d}q = \omega _i \right\} + \sum _{i=1}^{\rho } a_i \omega _i \right) . \end{aligned}$$

(4)

Let $\tilde{q}_1,\ldots ,\tilde{q}_{\rho }$ be any $\rho$ points in $\varOmega (Q)$ such that $\tilde{q}_i\not = \tilde{q}_j$, for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$. By Tietze’s extension theorem, there exists a continuous function $c: \varOmega (Q)\times \varOmega (Q) \rightarrow [0,+\infty ]$ such that $c(q,\tilde{q}_i) = u_i(q,q_i)$, for any $q\in \varOmega (Q)$ and $i\in \{1,\ldots ,\rho \}$. Given $\omega = (\omega _1,\ldots ,\omega _{\rho })\in S$, consider the Monge optimal transport problem

$$\begin{aligned} \inf _{T_\sharp \tilde{\mu } = \nu (\omega )} \int _{\varOmega (Q)} c(q,T(q))\mathrm{d}\tilde{\mu }(q) \end{aligned}$$

(5)

being $\nu (\omega ) = \sum _{i=1}^{\rho } \omega _i \delta _{\tilde{q}_i}$.

By Theorem 2.1 in [13] there exists a solution for problem (5) and it is equivalent to its corresponding Kantorovich relaxed Monge’s formulation:

$$\begin{aligned} \inf _{T_\sharp \tilde{\mu } = \nu (\omega )} \int _{\varOmega (Q)} c(q,T(q))\mathrm{d}\tilde{\mu }(q) = \mathcal {W}_c(\tilde{\mu },\nu (\omega )). \end{aligned}$$

(6)

By Remark 1 in [15], in the problem (5) any transport map T is associated to a partition $(A_i)_{i=1}^{\rho }$ of $\varOmega (Q)$ in such a way that

$$\begin{aligned} T(q)=\sum _{i=1}^{\rho } \tilde{q}_i {\varvec{1}}_{A_i}(q) \quad \text {and} \quad \tilde{\mu }(A_i) = \omega _i. \end{aligned}$$

Conversely, any partition $(A_i)_{i=1}^{\rho }$ of $\varOmega (Q)$ satisfying $\tilde{\mu }(A_i)=\omega _i$ corresponds to a transport map of the form above. Then, we have that

$$\begin{aligned}&\inf _{T_\sharp \tilde{\mu } = \nu (\omega )} \int _{\varOmega (Q)} c(q,T(q))\mathrm{d}\tilde{\mu }(q) \nonumber \\&\qquad = \inf _{A(Q)\in \mathcal {A}_{\rho }(Q)} \left\{ \int _{\varOmega (Q)} c\left( q,\sum _{i=1}^{\rho } \tilde{q}_i {\varvec{1}}_{A_i}(q)\right) d\tilde{\mu }(q) : \tilde{\mu }(A_i)=\omega _i \right\} \nonumber \\&\qquad = \inf _{A(Q)\in \mathcal {A}_{\rho }(Q)} \left\{ \sum _{i=1}^{\rho } \left[ \int _{{A}_i(Q)} u_i(q, q_i) \tilde{D}(q)\mathrm{d}q \right] : \int _{{A}_i(Q)} \tilde{D}(q)\mathrm{d}q = \omega _i \right\} . \qquad \end{aligned}$$

(7)

Using equalities (3) $=$ (4), (6) and (7), we rewrite problem (3) as:

$$\begin{aligned} \inf _{A(Q)\in \mathcal {A}_{\rho }(Q)} \sum _{i=1}^{\rho } \left\{ \int _{{A}_i(Q)} \left[ a_i \!+\! u(q, P_i^{q_i}) \right] \tilde{D}(q) \mathrm{d}q \right\} \! = \inf _{\omega \in S} \left\{ \mathcal {W}_c(\tilde{\mu },\nu (\omega )) \!+\! \sum _{i=1}^{\rho } a_i \omega _i \right\} . \end{aligned}$$

The function $\mathcal {W}_c(\tilde{\mu },\nu (\cdot )) : S \rightarrow \mathbb {R}$ is continuous since $\mathcal {W}_c$ is the Wasserstein distance on the set of Borel probability measures on $\varOmega (Q)$. As in addition S is compact, there exists a minimizer for problem (3).

The form and the uniqueness of the solution for problem LL(Q) are obtained adapting the proofs of Lemma 2 and Theorem 2 in [15], respectively. $\square$

Theorem 2.1 ensures problem LL(Q) is feasible and, moreover, explicitly gives the unique solution, up to D-negligible sets, of the problem. Note that the unique solution of problem LL(Q) given in Theorem 2.1 represents the natural choice of each customer point in $\varOmega (Q)$ given a prescribed service cost, i.e., each customer point decides to be served by the dimensional facility that charges him/her the lowest cost. So, the form of the solution (2) provides a realistic modeling of the customers’ behavior.

For each particular case of service cost and shape of the facilities, the condition that (1) is D-negligible for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not = j$, has to be guaranteed to ensure that Theorem 2.1 is applicable. For example, for the worst case cost situation and polygonal facilities, the condition is guaranteed for all $Q\in \varGamma$ whenever $a_i\not = a_j$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$. This is not a strong assumption since the case $a_i=a_j$ can be tackle by slightly perturbing the values: $a_i+\varepsilon =a_j$ or $a_i=a_j+\varepsilon$ with $\varepsilon > 0$ small enough. Onwards, we assume that the hypothesis of Theorem 2.1 is satisfied for all $Q\in \varGamma$.

As the solution of problem LL(Q) is unique for all $Q\in \varGamma$, we can define the best reply function$\widehat{A}: Q\in \varGamma \rightarrow \widehat{A}(Q)\in \mathcal {A}_{\rho }(Q)$, that maps to a given suitable solution, the optimal partition of the customers given in (2). In the same way, the function $\widehat{A}_i$ is the i-th projection of the function $\widehat{A}$, for each $i\in \{1,\ldots ,\rho \}$.

It is easy to verify that the set $\varGamma \in \mathbb {R}^{2\rho }$ is compact. Next, taking into account the above arguments, we can prove the existence of solution for problem BL.

Lemma 2.1

The application between topological spaces $\widehat{A}:\varGamma \rightarrow \widehat{A}(\varGamma )$, where $\varGamma$ is endowed with the relative topology of $\mathbb {R}^{2\rho }$ and $\widehat{A}(\varGamma )$ with the final topology, is a homeomorphism.

Proof

As $\widehat{A}(\varGamma )$ is endowed with the final topology, $\widehat{A}$ is continuous as application between topological spaces. Observe that $\widehat{A}(Q)$ is different for each $Q\in \varGamma$, since $\widehat{A}$ partitions a different set $\varOmega (Q)$ for each $Q\in \varGamma$. Then, $\widehat{A}$ is injective. Moreover, $\widehat{A}$ is bijective, since it is clearly surjective. Thus, given that the image space $\widehat{A}(\varGamma )$ is endowed with the final topology, $\widehat{A}$ is a homeomorphism. $\square$

Lemma 2.2

Let $i\in \{1,\ldots ,\rho \}$. The function $\mathscr {C}_i (Q)= C_i \biggl ( \int _{\widehat{A}_i (Q)} D(q) \mathrm{d}q \biggr )$ is continuous on $\varGamma$.

Proof

Let $\mu _i: \widehat{A}(Q)\in \widehat{A}(\varGamma ) \rightarrow \int _{\widehat{A}_i(Q)} D(q) \mathrm{d}q\in [0,1]\subseteq \mathbb {R}$, i.e., $\mu _i(\widehat{A}(Q))$ is the measure, with respect to the D density, of the i-th component of $\widehat{A}(Q)$. Note that $\mathscr {C}_i (Q) = C_i(\mu _i(\widehat{A}(Q)))$ for all $Q\in \varGamma$. The function $C_i$ is continuous as well as the application $\widehat{A}$ (moreover, by Lemma 2.1 it is a homeomorphism). Thus, if we prove that $\mu _i$ is continuous, then $\mathscr {C}_i$ will be continuous.

To prove that $\mu _i$ is continuous, we have to show that $\mu _i^{-1}(Z)$ is open in $\widehat{A}(\varGamma )$ for any open set Z in $\mathbb {R}$, where $\widehat{A}(\varGamma )$ is endowed with the final topology. Since the open Euclidean balls constitute a base of the usual topology, it is enough to consider open Euclidean balls, i.e., intervals $Z=(\alpha ,\beta )$ with $\alpha ,\beta \in \mathbb {R}$ and $\alpha < \beta$.

For any $Z=(\alpha ,\beta )$ as above, we have that

$$\begin{aligned} \mu _i^{-1} (Z) = \left\{ \widehat{A}(Q) \in \widehat{A}(\varGamma ) : \int _{\widehat{A}_i(Q)} D(q)\mathrm{d}q\in (\alpha ,\beta )\right\} . \end{aligned}$$

Let $\widehat{A}(\tilde{Q})\in \mu _i^{-1} (Z)$, where $\tilde{Q}=(\tilde{q}_1,\ldots ,\tilde{q}_{\rho })\in \varGamma$. Then, $\int _{\widehat{A}_i(\tilde{Q})} D(q)\mathrm{d}q=\varsigma \in (\alpha ,\beta )$. Next, we will prove that there exists $\epsilon >0$ such that $\widehat{A}(\tilde{Q}) \in \widehat{A}(\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )\cap \varGamma ) \subseteq \mu _i^{-1} (Z)$. That result implies that $\mu _i^{-1} (Z)$ is open, which will complete the proof. Note that $\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )\cap \varGamma$ is the relative open ball $\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )$ of $\mathbb {R}^{2\rho }$ in $\varGamma$, so it is open in $\varGamma$ endowed with the relative topology of $\mathbb {R}^{2\rho }$. Hence, $\widehat{A}(\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )\cap \varGamma )$ is also open in $\widehat{A}(\varGamma )$ endowed with the final topology, because $\widehat{A}$ is a homeomorphism. Therefore, $\widehat{A}(\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )\cap \varGamma )$ is an open neighborhood of $\widehat{A}(\tilde{Q})$ contained in $\mu _i^{-1} (Z)$, which means that $\mu _i^{-1} (Z)$ is open. $\square$

Claim

There exists $\epsilon >0$ such that $\widehat{A}(\tilde{Q}) \in \widehat{A}(\mathcal {B}_{\infty }(\tilde{Q}, \epsilon )\cap \varGamma ) \subseteq \mu _i^{-1} (Z)$.

Proof of the Claim

Let $\varepsilon > 0$ be small enough. For each $\varepsilon _n = \varepsilon /n$ with $n\in \mathbb {N}$, we define the following sets: $\varOmega ^-(\tilde{Q},\varepsilon _n) = \{q\in \varOmega : q\notin \text {int}(P_1^{\breve{q}_1})\cup \cdots \cup \text {int}(P_{\rho }^{\breve{q}_{\rho }}) \text { for all } \breve{Q}=(\breve{q}_1,\ldots ,\breve{q}_{\rho })\in \mathcal {B}_{\infty }(\tilde{Q},\varepsilon _n)\}$ and $\varOmega ^+(\tilde{Q},\varepsilon _n) = \{q\in \varOmega : q\in \varOmega {\setminus }\{\text {int}(P_1^{\breve{q}_1})\cup \cdots \cup \text {int}(P_{\rho }^{\breve{q}_{\rho }}) \} \text { for some } \breve{Q}=(\breve{q}_1,\ldots ,\breve{q}_{\rho })\in \mathcal {B}_{\infty }(\tilde{Q},\varepsilon _n)\}.$ It is not difficult to see that the sets $\varOmega ^-(\tilde{Q},\varepsilon _n)$ and $\varOmega ^+(\tilde{Q},\varepsilon _n)$ are measurable with respect to the Lebesgue measure m. Now, consider the sets $\widehat{A}_i^-(\tilde{Q},\varepsilon _n) = \{q\in \varOmega ^-(\tilde{Q},\varepsilon _n) : a_i + u(q,P_i^{\tilde{q}_i}) + 3\xi _n < a_j + u(u,P_j^{\tilde{q}_j}) \text { for all } j\in \{1,\ldots ,\rho \} \text { with } j\not = i\}$ and $\widehat{A}_i^+(\tilde{Q},\varepsilon _n) = \{q\in \varOmega ^+(\tilde{Q},\varepsilon _n) : a_i + u(q,P_i^{\tilde{q}_i}) < a_j + u(q,P_j^{\tilde{q}_j}) + 3\xi _n \text { for all } j\in \{1,\ldots ,\rho \} \text { with } j\not = i\}$, being $\xi _n = \max \left\{ \left| u(q,P_j^{\tilde{q}_j})-u(q,P_j^{\breve{q}_j})\right| : q\in \varOmega , j\in \{1,\ldots ,\rho \}, \breve{q}_j\in \text {cl}(\mathcal {B}_{\infty }(\tilde{q}_j,\varepsilon _n))\right\}$, which are also Lebesgue measurable sets.

Note that $\widehat{A}_i^-(\tilde{Q},\varepsilon _n) \subseteq \widehat{A}_i^-(\tilde{Q},\varepsilon _{n+1}) \subseteq \widehat{A}_i(\tilde{Q})$ since $\varOmega ^-(\tilde{Q},\varepsilon _n) \subseteq \varOmega ^-(\tilde{Q},\varepsilon _{n+1}) \subseteq \varOmega (\tilde{Q})$. Analogously, $\widehat{A}_i(\tilde{Q}) \subseteq \widehat{A}_i^+(\tilde{Q},\varepsilon _{n+1}) \subseteq \widehat{A}_i^+(\tilde{Q},\varepsilon _n)$ since $\varOmega (\tilde{Q}) \subseteq \varOmega ^+(\tilde{Q},\varepsilon _{n+1}) \subseteq \varOmega ^+(\tilde{Q},\varepsilon _{n})$. Indeed,

$$\begin{aligned} \bigcup _{n=1}^{\infty } \widehat{A}_i^-(\tilde{Q},\varepsilon _n) = \widehat{A}_i(\tilde{Q}) = \bigcap _{n=1}^{\infty } \widehat{A}_i^+(\tilde{Q},\varepsilon _n) \end{aligned}$$

up to m-negligible sets. Thus, applying the continuity properties of the Lebesgue measure, it follows that

$$\begin{aligned} \lim _{n\rightarrow \infty }m\left( \widehat{A}_i^-(\tilde{Q},\varepsilon _n)\right)= & {} m\left( \bigcup _{n=1}^{\infty } \widehat{A}_i^-(\tilde{Q},\varepsilon _n)\right) = m\left( \widehat{A}_i(\tilde{Q}) \right) = m\left( \bigcap _{n=1}^{\infty } \widehat{A}_i^+(\tilde{Q},\varepsilon _n)\right) \nonumber \\= & {} \lim _{n\rightarrow \infty } m\left( \widehat{A}_i^+(\tilde{Q},\varepsilon _n)\right) . \end{aligned}$$

(8)

Let $\eta = \sup _{q \in \varOmega } D(q)$ and let $\phi >0$ be such that $(\varsigma -\phi ,\varsigma +\phi )\subseteq (\alpha ,\beta )$. Due to (8), there exists $n_0\in \mathbb {N}$ such that $m\left( \widehat{A}_i(\tilde{Q}) {\setminus } \widehat{A}_i^-(\tilde{Q},\varepsilon _{n_0})\right) < \phi /\eta$ and $m\left( \widehat{A}_i^+(\tilde{Q},\varepsilon _{n_0}){\setminus } \widehat{A}_i(\tilde{Q}) \right) < \phi /\eta$. Therefore, $\int _{\widehat{A}_i(\tilde{Q}) {\setminus } \widehat{A}_i^-(\tilde{Q},\varepsilon _{n_0})} D(q)\mathrm{d}q \le \eta \int _{\widehat{A}_i(\tilde{Q}) {\setminus } \widehat{A}_i^-(\tilde{Q},\varepsilon _{n_0})} \mathrm{d}q < \phi$ and $\int _{\widehat{A}_i^+(\tilde{Q},\varepsilon _{n_0}){\setminus } \widehat{A}_i(\tilde{Q})} D(q)\mathrm{d}q \le \eta \int _{\widehat{A}_i^+(\tilde{Q},\varepsilon _{n_0}){\setminus } \widehat{A}_i(\tilde{Q})} \mathrm{d}q < \phi$. Or equivalently, $\int _{\widehat{A}_i^-(\tilde{Q},\varepsilon _{n_0})} D(q)\mathrm{d}q > \varsigma - \phi$ and $\int _{\widehat{A}_i^+(\tilde{Q},\varepsilon _{n_0})} D(q)\mathrm{d}q < \varsigma + \phi$.

Now, let $\breve{Q}=(\breve{q}_1,\ldots ,\breve{q}_{\rho })\in \mathcal {B}_{\infty }(\tilde{Q},\varepsilon _{n_0})\cap \varGamma$. Then, $\left| u(q,P_j^{\tilde{q}_j}) - u(q,P_j^{\breve{q}_j})\right| \le \xi _{n_0}$ for all $q\in \varOmega$ and $j\in \{1,\ldots ,\rho \}$. Therefore, $\left| \left( u(q,P_i^{\tilde{q}_i})\right. \right. \left. \left. -u(q,P_j^{\tilde{q}_j}) \right) - \left( u(q,P_i^{\breve{q}_i})-u(q,P_j^{\breve{q}_j})\right) \right| \le 2\xi _{n_0} < 3\xi _{n_0}$ for all $q\in \varOmega$ and $j\in \{1,\ldots ,\rho \}$. Note that the above inequality together with the fact that $\varOmega ^-(\tilde{Q},\varepsilon _{n_0}) \subseteq \varOmega (\breve{Q}) \subseteq \varOmega ^+(\tilde{Q},\varepsilon _{n_0})$ imply that:

$$\begin{aligned} \widehat{A}_i^-(\tilde{Q},\varepsilon _{n_0}) \subseteq \widehat{A}_i(\breve{Q}) \subseteq \widehat{A}_i^+(\tilde{Q},\varepsilon _{n_0}) . \end{aligned}$$

Thus,

$$\begin{aligned} \int _{ \widehat{A}_i(\breve{Q})} D(q)\mathrm{d}q \in (\varsigma - \phi , \varsigma + \phi )\subseteq (\alpha ,\beta ). \end{aligned}$$

Hence, it is enough to take $\epsilon = \varepsilon _{n_0}$ to complete the proof of the Claim. $\square$

Lemma 2.3

Let $i\in \{1,\ldots ,\rho \}$. The function $\mathscr {I}_i (Q)=I_i \biggl ( \int _{P_i^{q_i}} B(q) \mathrm{d}q \biggr )$ is continuous on $\varGamma$.

Proof

The proof is similar to the one of Lemma 2.2 but using the sets $P_i^-(\tilde{Q},\varepsilon _n) = \{q\in \varOmega : q\in P_i^{\breve{q}_i} \text { for all } \breve{Q}=(\breve{q}_1,\ldots ,\breve{q}_{\rho })\in \mathcal {B}_{\infty }(\tilde{Q},\varepsilon _n)\}$ and $P_i^+(\tilde{Q},\varepsilon _n) = \{q\in \varOmega : q\in P_i^{\breve{q}_i} \text { for some } \breve{Q}=(\breve{q}_1,\ldots ,\breve{q}_{\rho })\in \mathcal {B}_{\infty }(\tilde{Q},\varepsilon _n)\}$. $\square$

Lemma 2.4

The function $\mathscr {L} (Q)=L\biggl ( \int _{P_1^{q_1}\cup \cdots \cup P_{\rho }^{q_{\rho }}} D(q) \mathrm{d}q\biggr )$ is continuous on $\varGamma$.

Proof

The proof is similar to the one of Lemma 2.3 but using the sets $\bigcup _{i=1}^{\rho } P_i^-(\tilde{Q},\varepsilon _n)$ and $\bigcup _{i=1}^{\rho } P_i^+(\tilde{Q},\varepsilon _n)$. $\square$

Theorem 2.2

There exists an optimal solution for problem BL.

Proof

Problem BL consists in minimizing the function $\mathcal {F}(Q)=\sum _{i=1}^{\rho } \mathscr {I}_i (Q) + \sum _{i=1}^{\rho } \mathscr {C}_i (Q) +\mathscr {L} (Q)$ on $\varGamma$. The function $\mathcal {F}$ is continuous by Lemmas 2.2, 2.3 and 2.4, and the set $\varGamma$ is compact, so the result follows using Weierstrass theorem. $\square$

Theorem 2.2 finally proves that problem BL is well defined and gives sufficient conditions for the existence of optimal solutions.

3 A Convergent Discrete Approximation Scheme

The previous section states that problem BL is well defined. However, in spite of being well defined, optimizing the problem BL is a very difficult task since it amounts to minimize with a best reply function over the partitions of $\varOmega$ as a constraint defining the feasible domain. To overcome that inconvenience we propose a discrete approximation of problem BL. This approximation provides good solutions for the original problem. Since $\varOmega$ is bounded by hypothesis, we can easily find a rectangle of $\mathbb {R}^2$ containing $\varOmega$. Consider a grid G over that rectangle, and thus over $\varOmega$. Let ${\varvec{G}}$ be the set of cells of the grid G. We denote by (k, l) a cell of ${\varvec{G}}$, where k indexes the horizontal position of the cell in the grid and l the vertical one. Now, consider the sets

$$\begin{aligned} {\varvec{\varOmega }} = \{(k,l)\in {\varvec{G}} : \text {int}((k,l))\cap \varOmega \not = \emptyset \} \end{aligned}$$

and

Clearly, and we want to be as similar to $\varOmega$ as possible. Indeed, is the outer approximation of $\varOmega$ given by the cells of the grid G (see Fig. 2). The finer the grid, the better the approximation. Note that, for an element of the problem denoted by a letter, we use that letter in bold to represent the discrete counterpart of the element. Moreover, with the hollow fonts we represent the approximation of that element induced by its discrete counterpart, e.g., is the approximation of $\varOmega$ induced by ${\varvec{\varOmega }}$. Onwards, we keep this meaning for the notation in bold and hollow fonts.

Fig. 2

Sets ${\varvec{\varOmega }}$ and for an example of a Borel set $\varOmega$ and a regular grid G

Before to describe the discretization of problem BL, we introduce the following notation and define some elements involved in the discretization for each $(k,l)\in {\varvec{\varOmega }}$ and $i\in \{1,\ldots ,\rho \}$:

• $q_{(k,l)}$: is the center of the cell (k, l) (if $\{(x^-,y^-),(x^+,y^-),(x^-,y^+),(x^+,y^+)\}\subseteq \mathbb {R}^2$ are the extreme points of the cell (k, l), then the center of (k, l) is $((x^-+x^+)/2,(y^-+y^+)/2)\in \mathbb {R}^2$).

• ${\varvec{P}}_i^{(k,l)}$: is the subset of cells of ${\varvec{\varOmega }}$ defined by

  $$\begin{aligned} {\varvec{P}}_i^{(k,l)} = \left\{ (r,s)\in {\varvec{\varOmega }} : \text {int}((r,s))\cap \text {int}\left( P_i^{q_{(k,l)}}\right) \not = \emptyset \right\} . \end{aligned}$$

• $\mathbb {P}_i^{(k,l)}$: is the set defined by

  $$\begin{aligned} \mathbb {P}_i^{(k,l)} = \bigcup _{(r,s)\in {\varvec{P}}_i^{(k,l)}} (r,s). \end{aligned}$$

  The set $\mathbb {P}_i^{(k,l)}$ is the approximation of the facility $P_i^{q_{(k,l)}}$ induced by the cells of ${\varvec{P}}_i^{(k,l)}$ (the discretization scheme is the same that the one shown in Fig. 2). We refer to $\mathbb {P}_i^{(k,l)}$ as cell facility. The finer the grid, the better the approximation.

• ${\varvec{\varOmega }}_i$: is the subset of cells of ${\varvec{\varOmega }}$ defined by

  $$\begin{aligned} {\varvec{\varOmega }}_i = \left\{ (k,l)\in {\varvec{\varOmega }} : P_i^{q_{(k,l)}} \subseteq \varOmega \right\} . \end{aligned}$$

• : is the set defined by

  

  The set is the approximation of $\varOmega _i$ induced by ${\varvec{\varOmega }}_i$.

The discretized version of problem BL (DBL) is to locate $\rho$ facilities $P_1,\ldots ,P_{\rho }$ in and to find their demand regions $A_1,\ldots ,A_{\rho }$ optimizing the costs as in the original continuous problem BL. To address this discretized problem, we need to transform the original one making the following natural and simplifying assumptions:

• Assumption 1 The dimensional facilities $P_1,\ldots ,P_{\rho }$ can only be located at the centers of the cells in ${\varvec{\varOmega }}$.

  This is a simplifying choice that reduces the location problem to a finite number of positions. Then, a suitable solution of problem DBL is determined by a $\rho$-tuple ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\subseteq {\varvec{\varOmega }}^{\rho }$ where $(k_i,l_i)$ is the cell in whose center $q_{(k_i,l_i)}$ is located the dimensional facility $P_i$, for each $i\in \{1,\ldots ,\rho \}$.

• Assumption 2 We impose on the cell facilities some conditions induced by the corresponding ones applicable to the sets $P_1,\ldots ,P_{\rho }$ in problem BL.

  • Assumption 2.1 The interior of the cell facilities cannot intersect between them.

    This is a modeling assumption because we want that our facilities are placed in a physical framework and overlapping of facilities is not allowed. So, if we denote by ${\varvec{\varGamma }}\subseteq {\varvec{\varOmega }}^{\rho }$ the set of suitable solutions of problem DBL, ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ iff $P_i^{q_{(k_i,l_i)}} \subseteq \varOmega$ for all $i\in \{1,\ldots ,\rho \}$ and $\text {int}(\mathbb {P}_i^{(k_i,l_i)})\cap \text {int}(\mathbb {P}_j^{(k_j,l_j)}) = \emptyset$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not = j$. Equivalently, using the sets defined above:

    $$\begin{aligned} \begin{array}{rl} {\varvec{\varGamma }}=\bigg \{((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varOmega }}_1\times \cdots \times {\varvec{\varOmega }}_{\rho } : &{} {\varvec{P}}_i^{(k_i,l_i)}\cap {\varvec{P}}_j^{(k_j,l_j)} = \emptyset , \\ &{}\forall i,j\in \{1,\ldots ,\rho \},i\not = j\bigg \}. \end{array} \end{aligned}$$

  • Assumption 2.2 Partitions are computed on the set of cells.

    Given a suitable solution ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$, we have to find the optimal partition of . The reader should observe that this is the natural approach when one considers the discrete approximation of the dimensional facilities by the cell facilities. Note that is, up to D-negligible sets, the union of the cells of the set ${\varvec{\varOmega }}({\varvec{Q}})$ defined as

    $$\begin{aligned} {\varvec{\varOmega }}({\varvec{Q}})=\{(r,s)\in {\varvec{\varOmega }} : (r,s)\notin {\varvec{P}}^{(k_i,l_i)}_i, \forall i\in \{1,\ldots ,\rho \}\}. \end{aligned}$$

  • Assumption 2.3 The installation and lost demand costs are computed now over the region occupied by the cell facilities.

• Assumption 3 Each element of a partition must be composed by a finite number of cells.

  Given a suitable solution ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$, any partition $A({\varvec{Q}})=(A_1({\varvec{Q}}),\ldots ,A_{\rho }({\varvec{Q}}))$ of the set must satisfy that each region $A_i({\varvec{Q}})$ is the union of a finite number of cells of ${\varvec{\varOmega }}({\varvec{Q}})$, for all $i\in \{1,\ldots ,\rho \}$. Once again, this assumption is the natural consequence of the discretization of the feasible region $\varOmega$ into cells.

  Formally speaking, we denote by ${\varvec{A}}_i({\varvec{Q}})$ the subset of ${\varvec{\varOmega }}({\varvec{Q}})$ such that

  $$\begin{aligned} A_i({\varvec{Q}}) = \bigcup _{(r,s)\in {\varvec{A}}_i({\varvec{Q}})} (r,s), \end{aligned}$$

  for each $i\in \{1,\ldots ,\rho \}$. The partition ${\varvec{A}}({\varvec{Q}})=({\varvec{A}}_1({\varvec{Q}}),\ldots ,{\varvec{A}}_{\rho }({\varvec{Q}}))$ of ${\varvec{\varOmega }}({\varvec{Q}})$ assigns the demand cells in ${\varvec{\varOmega }}({\varvec{Q}})$ among the facilities. Note that, for this element of the problem, $A({\varvec{Q}})=\mathbb {A}({\varvec{Q}})$.

• Assumption 4 Costs are computed with respect to centers of cells.

  Specifically, suppose that the dimensional facilities $P_1,\ldots ,P_{\rho }$ are located at ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$. The cost $u_G$ paid from a point with respect to the dimensional facility $P^{q_{(k_i,l_i)}}_i$ is now induced by the grid G as:

  $$\begin{aligned} u_{G} \left( q, P_i^{q_{(k_i,l_i)}}\right) = u \left( q_{(r,s)}, P_i^{q_{(k_i,l_i)}}\right) , \end{aligned}$$

  being $q_{(r,s)}$ the center of the cell $(r,s)\in {\varvec{\varOmega }}({\varvec{Q}})$ to which the point q belongs to, for each $i\in \{1,\ldots ,\rho \}$. Thus, in the discretized problem, all the points in a cell have the same cost, namely the cost of the center of that cell in the non-discretized problem. To ensure $u_G$ is well defined, if $\{(x^-,y^-),(x^+,y^-),(x^-,y^+),(x^+,y^+)\}\subseteq \mathbb {R}^2$ are the extreme points of the cell (r, s), in terms of membershipness, we consider (r, s) as $[x^-,x^+)\times [y^-,y^+)\subseteq \mathbb {R}^2$ (this avoid that q may belong to more than one cell). Note that if the grid G is fine enough, $u_G(q, P_i^{q_{(k_i,l_i)}})$ gives a good approximation of $u(q,P_i^{q_{(k_i,l_i)}})$.

• Assumption 5 The cost functions $I_1,\ldots ,I_{\rho },C_1,\ldots ,C_{\rho },L$ are non-decreasing, piecewise linear, continuous and nonnegative.

  We denote by $I_1^{\mathrm{PL}},\ldots ,I_{\rho }^{\mathrm{PL}},C_1^{\mathrm{PL}},\ldots , C_{\rho }^{\mathrm{PL}},L^{\mathrm{PL}}$ these cost functions in problem DBL to emphasize that they are piecewise linear. Note that the piecewise linearity assumption is not a big loss of generality. Indeed, taking a partition of the interval [0, 1] and evaluating the congestion cost function $C_i$ of problem BL at the points of the partition, we can build, by linear interpolation, a piecewise linear congestion cost function $C_i^{\mathrm{PL}}$ that approximates $C_i$, for any $i\in \{1,\ldots ,\rho \}$. The finer the partition, the better the approximation. The same applies for $I_1,\ldots ,I_{\rho }$ and L.

Figure 3 shows, as an illustrative example, the discretized version of the Example 4.1 from [13] considering a regular grid G over $\varOmega$ with $25\times 25$ cells (note that, as $\varOmega$ is the unit square, ${\varvec{G}} = {\varvec{\varOmega }}$).

Fig. 3

Example 4.1 from [13] in the discrete scheme

Consider a suitable solution ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ of problem DBL and let $\widehat{A}({\varvec{Q}})=(\widehat{A}_1({\varvec{Q}}),\ldots ,\widehat{A}_{\rho }({\varvec{Q}}))$ be the optimal partition of the customers in under the assumptions above. Under those assumptions, for each $i\in \{1,\ldots ,\rho \}$, the access cost incurred by all customers assigned to the dimensional facility $P_i$ can be expressed as

$$\begin{aligned} \int _{\widehat{A}_i({\varvec{Q}})} a_i D(q)\mathrm{d}q = \sum _{(r,s)\in {\varvec{\widehat{A}}}_i({\varvec{Q}})} \int _{(r,s)} a_i D(q)\mathrm{d}q= \sum _{(r,s)\in {\varvec{\widehat{A}}}_i({\varvec{Q}})} a_i w^D_{rs}, \end{aligned}$$

where we are using the notation $w^D_{rs} = \int _{(r,s)} D(q) \mathrm{d}q$ for any $(r,s)\in {\varvec{\varOmega }}$. Moreover, the distribution cost in the service region $\widehat{A}_i({\varvec{Q}})$ is

$$\begin{aligned} U_i(\widehat{A}_i({\varvec{Q}})) = \int _{\widehat{A}_i({\varvec{Q}})} u_G\left( q,P_i^{q_{(k_i,l_i)}}\right) D(q)\mathrm{d}q = \sum _{(r,s)\in {\varvec{\widehat{A}}}_i({\varvec{Q}})} w^D_{rs} u\left( q_{(r,s)},P_i^{q_{(k_i,l_i)}}\right) , \end{aligned}$$

for each $i\in \{1,\ldots ,\rho \}$. Thus, the partition $\widehat{A}({\varvec{Q}})=(\widehat{A}_1({\varvec{Q}}),\ldots ,\widehat{A}_{\rho }({\varvec{Q}}))$ is given by the solution $\widehat{{\varvec{A}}}({\varvec{Q}})=(\widehat{{\varvec{A}}}_1({\varvec{Q}}),\ldots ,\widehat{{\varvec{A}}}_{\rho }({\varvec{Q}}))$ of the discretized lower level problem

being ${\varvec{\mathcal {A}}}_{\rho }({\varvec{Q}})$ the set of all partitions in $\rho$ subsets (where the empty set is a valid subset) of the set ${\varvec{\varOmega }}({\varvec{Q}})$.

The assignment cost of a cell $(r,s)\in {\varvec{\varOmega }}({\varvec{Q}})$ to a dimensional facility $P_i$ in $\{P_1,\ldots ,P_{\rho }\}$ is $a_i w^D_{rs} + w^D_{rs} u(q_{(r,s)},P^{q_{(k_i,l_i)}})$. Then, note that in problem DLL$({\varvec{Q}})$ we are minimizing the sum of the assignment costs of the cells in ${\varvec{\varOmega }}({\varvec{Q}})$. Thus, the optimal partition $\widehat{{\varvec{A}}}({\varvec{Q}})$ is the one that allocates each cell $(r,s)\in {\varvec{\varOmega }}({\varvec{Q}})$ to the dimensional facility in $\{P_1,\ldots ,P_{\rho }\}$ that provides the minimum assignment cost, i.e., if $(r,s)\in \widehat{{\varvec{A}}}_i({\varvec{Q}})$ for some $i\in \{1,\ldots ,\rho \}$, then

$$\begin{aligned} a_i w^D_{rs} + w^D_{rs} u\left( q_{(r,s)},P_i^{q_{(k_i,l_i)}}\right) \le a_j w^D_{rs} + w^D_{rs} u\left( q_{(r,s)},P_j^{q_{(k_j,l_j)}}\right) , \end{aligned}$$

for all $j\in \{1,\ldots ,\rho \}$. Note that there may exist cells $(r,s)\in {\varvec{\varOmega }}({\varvec{Q}})$ for which

$$\begin{aligned} a_i w^D_{rs} + w^D_{rs} u\left( q_{(r,s)},P_i^{q_{(k_i,l_i)}}\right) = a_j w^D_{rs} + w^D_{rs} u\left( q_{(r,s)},P_j^{q_{(k_j,l_j)}}\right) \end{aligned}$$

for some $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$, such that they have a non-D-negligible demand density $w^D_{rs}$. Therefore, in the discrete scheme, we cannot define the best reply function $\widehat{{\varvec{A}}}: {\varvec{Q}}\in {\varvec{\varGamma }}\rightarrow \widehat{{\varvec{A}}}({\varvec{Q}})\in {\varvec{\mathcal {A}}}_{\rho }({\varvec{Q}})$ as we have done in the non-discretized problem, since it could be not injective. In this case, the application is not injective when two or more dimensional facilities give the same minimum assignment cost to a cell (r, s).

Reasoning in the same way as above, problem DBL can be expressed as:

being

$$\begin{aligned} {\varvec{\mathcal {F}}}({\varvec{Q}}):= & {} \displaystyle \sum _{i=1}^{\rho } \left[ I_i^{\mathrm{PL}}\left( \sum _{(r,s)\in {\varvec{P}}_i^{(k_i,l_i)}} w_{rs}^B\right) + C_i^{\mathrm{PL}}\left( \sum _{(r,s)\in \widehat{{\varvec{A}}}_i({\varvec{Q}})} w^D_{rs}\right) \right] \\&+ \,L^{\mathrm{PL}}\left( \sum _{i=1}^{\rho } \sum _{(r,s)\in {\varvec{P}}_i^{(k_i,l_i)}} w_{rs}^D\right) , \end{aligned}$$

where we are using the notation $w^B_{rs} = \int _{(r,s)} B(q) \mathrm{d}q$ for any $(r,s)\in {\varvec{\varOmega }}$. Problem DBL is again a bilevel problem since to evaluate a suitable solution ${\varvec{Q}}\in {\varvec{\varGamma }}$ in the objective function ${\varvec{\mathcal {F}}}$ one needs to solve before the problem DLL$({\varvec{Q}})$, to have an expression of $\widehat{{\varvec{A}}}({\varvec{Q}})$. Note that $Q=(q_{(k_1,l_1)},\ldots ,q_{(k_{\rho },l_{\rho })})\in \varGamma$ for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$, i.e., every suitable solution of problem DBL codifies a suitable solution of problem BL.

It is easy to prove that problem DBL is NP-hard with a reduction from the $\rho$-median problem, where $\rho$ is the number of facilities to be located in our problem.

In the following, we suppose that there exists a suitable solution $\mathring{Q}=(\mathring{q}_1,\ldots ,\mathring{q}_{\rho })\in \varGamma$ for problem BL such that $P_i^{\mathring{q}_i}\cap \partial \varOmega = \emptyset$ for all $i\in \{1,\ldots ,\rho \}$ and $P_i^{\mathring{q}_i}\cap P_j^{\mathring{q}_j} = \emptyset$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$. This ensures the existence of a grid G, fine enough, for which problem DBL has at least one suitable solution: take a grid G in which the point $\mathring{q}_i$ is the center of one of the cells in ${\varvec{G}}$, say $(\mathring{k}_i,\mathring{l}_i)$, for each $i\in \{1,\ldots ,\rho \}$, and fine enough to guarantee ${\varvec{P}}_i^{(\mathring{k}_i,\mathring{l}_i)}\cap {\varvec{P}}_j^{(\mathring{k}_j,\mathring{l}_j)} = \emptyset$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$; then, $\mathring{{\varvec{Q}}}=((\mathring{k}_1,\mathring{l}_1),\ldots ,(\mathring{k}_{\rho },\mathring{l}_{\rho }))\in {\varvec{\varGamma }}$.

Next, we show our convergence results.

Let us consider a sequence of successively refined grids $\{ G(n) \}_{n\in \mathbb {N}}$ satisfying that G(1) is a grid for which problem DBL has at least one suitable solution. The sequence of grids $\{ G(n) \}_{n\in \mathbb {N}}$ is a sequence of successively refined grids if given a grid $G(\tilde{n})$ and any of its cell $(\tilde{k},\tilde{l})$, there exists $\breve{n}\in \mathbb {N}$ with $\breve{n} > \tilde{n}$ such that $(\tilde{k},\tilde{l})$ is the union of a set of cells of the grid $G(\breve{n})$ with strictly less width and height than $(\tilde{k},\tilde{l})$. We add an additional index n to the notation introduced in the section to indicate the grid of the sequence which is being considered in each case. For example, DLL$({\varvec{Q}},n)$ is the discretized lower level problem for a suitable solution ${\varvec{Q}}\in {\varvec{\varGamma }}(n)$ when we consider the grid G(n), $n\in \mathbb {N}$. Finally, we denote by $\kappa (n)$ the maximum length of the cell sides in ${\varvec{G}}(n)$, $n\in \mathbb {N}$.

In the following results, we assume that the functions $I_1^{\mathrm{PL}}(\cdot , n),\ldots ,I_{\rho }^{\mathrm{PL}}(\cdot , n),C_1^{\mathrm{PL}}(\cdot , n),\ldots ,C_{\rho }^{\mathrm{PL}}(\cdot , n),L^{\mathrm{PL}}(\cdot , n)$ of problem DBL(n) are obtained from the functions $I_1(\cdot ),\ldots ,I_{\rho }(\cdot ),C_1(\cdot ),\ldots ,C_{\rho }(\cdot ),L(\cdot )$ of problem BL by linear interpolation over a partition of the corresponding domains, in such a way that the larger the n, the finer the partition. Moreover, we suppose that the partition is such that, for any $\varepsilon > 0$, there exists $\tilde{n}\in \mathbb {N}$ such that $\left| I_1(\omega _1^B)-I_1^{\mathrm{PL}}(\omega _1^B,n)\right| < \varepsilon$, for all $\omega _1^B \in \mathbb {R}$ and all $n\in \mathbb {N}$ with $n\ge \tilde{n}$. The same assumption is done for the remaining mentioned functions. Note that this assumptions can be done due to the properties assumed for the functions $I_1,\ldots ,I_{\rho },C_1,\ldots ,C_{\rho },L$.

Lemma 3.1

Let $i\in \{1,\ldots ,\rho \}$. For any $\varepsilon > 0$, there exists $n(\varepsilon )\in \mathbb {N}$ such that

$$\begin{aligned} \left| C_i\left( \int _{\widehat{A}_i(Q)} D(q) \mathrm{d}q \right) - C_i^{\mathrm{PL}}\left( \int _{\widehat{A}_i({\varvec{Q}},n)} D(q) \mathrm{d}q,n \right) \right| < \varepsilon , \end{aligned}$$

for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$, being $Q=(q_{(k_1,l_1)},\ldots ,q_{(k_{\rho },l_{\rho })})$, and all $n\in \mathbb {N}$ with $n\ge n(\varepsilon )$.

Proof

First, take $\tilde{n}\in \mathbb {N}$ such that $\left| C_i(\omega _i^D)-C_i^{\mathrm{PL}}(\omega _i^D,n)\right| < \varepsilon / 2$, for all $\omega _i^D \in [0,1]$ and all $n\in \mathbb {N}$ with $n\ge \tilde{n}$. Since $C_i$ is continuous, it is uniformly continuous on [0, 1], therefore, for $\varepsilon / 2$ there exists $\xi > 0$ such that, when $|\omega _i^D - \tilde{\omega }_i^D| < \xi$, then $|C_i(\omega _i^D) - C_i(\tilde{\omega }_i^D)| < \varepsilon / 2$, for all $\omega _i^D, \tilde{\omega }_i^D \in [0,1]$.

For each $q_i\in \mathbb {R}^2$ and each $n\in \mathbb {N}$, let $\mathbb {P}^+_i(q_i,n)=\{q\in \mathbb {R}^2 : q\in P_i^{\tilde{q}_i} \text { for some } \tilde{q}_i\in \mathcal {B}_{\infty }(q_i,\kappa (n))\}$. For all $Q=(q_1,\ldots ,q_{\rho })\in \varGamma$ and all $n\in \mathbb {N}$, we define the set $\widehat{\mathbb {A}}_i^-(Q,n) = \{q\in \varOmega : q\in (\widehat{A}_i(Q))^{\tilde{q}_i} \text { for all }$$\tilde{q}_i\in \mathcal {B}_{\infty }(\widehat{q}_i(Q,n),\kappa (n))\}{\setminus } \mathbb {P}_i^+(q_i,n)$, being $\widehat{q}_i(Q,n)$ any point in $\widehat{A}_i(Q,n)$ and $(\widehat{A}_i(Q,n))^{\tilde{q}_i}$ the set $\widehat{A}_i(Q,n)$ when we apply to it the translation induced by the vector $\overrightarrow{\widehat{q}_i(Q,n) \tilde{q}_i}\in \mathbb {R}^2$, for any $\tilde{q}_i\in \mathcal {B}_{\infty }(\widehat{q}_i(Q,n),\kappa (n))$. In the same way, we define $\widehat{\mathbb {A}}^+_i(Q,n) = \{q\in \varOmega : q\in (\widehat{A}_i(Q))^{\tilde{q}_i} \text { for some }$$\tilde{q}_i\in \mathcal {B}_{\infty }(\widehat{q}_i(Q,n),\kappa (n))\}$. Note that the definition of the sets above does not depend on the point $\widehat{q}_i(Q,n)$ chosen and induces two applications $\widehat{\mathbb {A}}_i^-$ and $\widehat{\mathbb {A}}_i^+$ with domain on $\varGamma \times \mathbb {N}$.

Let $Q\in \varGamma$. Note that $\widehat{\mathbb {A}}_i^-(Q,n)\subseteq \widehat{\mathbb {A}}_i^-(Q,n+1) \subseteq \widehat{A}_i(Q)$, and that $\bigcup _{n=1}^{\infty } \widehat{\mathbb {A}}_i^-(Q,n) = \widehat{A}_i(Q)$ up to m-negligible sets. In the same way, $\widehat{A}_i(Q) \subseteq \widehat{\mathbb {A}}_i^+(Q,n+1)\subseteq \widehat{\mathbb {A}}_i^+(Q,n)$ and $\bigcap _{n=1}^{\infty } \widehat{\mathbb {A}}_i^+(Q,n) = \widehat{A}_i(Q)$ up to m-negligible sets. Then, reasoning in the same way that in the proof of Lemma 2.2, it can be shown that, given $\xi > 0$, there exists $\breve{n}\in \mathbb {N}$ such that $\int _{\widehat{A}_i(Q) {\setminus } \widehat{\mathbb {A}}^-_i(Q,n)} D(q)\mathrm{d}q < \xi$ and $\int _{\widehat{\mathbb {A}}^+_i(Q,n) {\setminus } \widehat{A}_i(Q)} D(q)\mathrm{d}q < \xi$ for all $n\in \mathbb {N}$ with $n\ge \breve{n}$. Moreover, as the statement above is true for all $Q\in \varGamma$, there exists $\bar{n}\in \mathbb {N}$ such that $\int _{\widehat{A}_i(Q) {\setminus } \widehat{\mathbb {A}}^-_i(Q,n)} D(q)\mathrm{d}q < \xi$ and $\int _{\widehat{\mathbb {A}}^+_i(Q,n) {\setminus } \widehat{A}_i(Q)} D(q)\mathrm{d}q < \xi$ for all $Q\in \varGamma$ and all $n\in \mathbb {N}$ with $n\ge \bar{n}$.

It is not difficult to see that $\widehat{\mathbb {A}}^-_i(Q,n)\subseteq \widehat{A}_i({\varvec{Q}},n)\subseteq \widehat{\mathbb {A}}^+_i(Q,n)$, for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$, being $Q=(q_{(k_1,l_1)},\ldots ,q_{(k_{\rho },l_{\rho })})$, and all $n\in \mathbb {N}$. Therefore, $\left| \int _{\widehat{A}_i(Q)} D(q) \mathrm{d}q - \int _{\widehat{A}_i({\varvec{Q}},n)} D(q) \mathrm{d}q \right| < \xi$ for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$, being $Q=(q_{(k_1,l_1)},\ldots ,q_{(k_{\rho },l_{\rho })})$, and all $n\in \mathbb {N}$ with $n\ge \bar{n}$.

The proof is completed taking $n(\varepsilon ) = \max \{\tilde{n}, \bar{n}\}$. $\square$

Lemma 3.2

Let $i\in \{1,\ldots ,\rho \}$. For any $\varepsilon > 0$, there exists $n(\varepsilon )\in \mathbb {N}$ such that

$$\begin{aligned} \left| I_i\left( \int _{P_i^{q_{(k_i,l_i)}}} B(q) \mathrm{d}q \right) - I_i^{\mathrm{PL}}\left( \int _{\mathbb {P}_i^{(k_i,l_i)}(n)} B(q) \mathrm{d}q,n \right) \right| < \varepsilon , \end{aligned}$$

for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$ and all $n\in \mathbb {N}$ with $n\ge n(\varepsilon )$.

Proof

The proof is similar to the one of Lemma 3.1 but using the set $\mathbb {P}^+_i(q_i,n)$ defined as above and the set $\mathbb {P}^-_i(q_i,n)=\{q\in \mathbb {R}^2 : q\in P_i^{\tilde{q}_i} \text { for all } \tilde{q}_i\in \mathcal {B}_{\infty }(q_i,\kappa (n))\}$. $\square$

Lemma 3.3

For any $\varepsilon > 0$, there exists $n(\varepsilon )\in \mathbb {N}$ such that

$$\begin{aligned} \left| L\left( \int _{\bigcup _{i=1}^{\rho }P_i^{q_{(k_i,l_i)}}} D(q) \mathrm{d}q \right) - L^{\mathrm{PL}}\left( \int _{\bigcup _{i=1}^{\rho } \mathbb {P}_i^{(k_i,l_i)}(n)} D(q) \mathrm{d}q,n \right) \right| < \varepsilon , \end{aligned}$$

for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$ and all $n\in \mathbb {N}$ with $n\ge n(\varepsilon )$.

Proof

The proof is similar to the one of Lemma 3.2 but using the sets $\bigcup _{i=1}^{\rho }\mathbb {P}^-_i(q_i,n)$ and $\bigcup _{i=1}^{\rho }\mathbb {P}^+_i(q_i,n)$. $\square$

From these lemmas, one can obtain the final convergence result.

Theorem 3.1

Suppose that, for any suitable solution $Q\in \varGamma$ of problem BL and for any $\epsilon >0$, there exists $\tilde{Q}=(\tilde{q}_1,\ldots ,\tilde{q}_{\rho })\in \mathcal {B}_{\infty }(Q,\epsilon )\cap \varGamma$ such that $P_i^{\tilde{q}_i}\cap \partial \varOmega = \emptyset$ for all $i\in \{1,\ldots ,\rho \}$ and $P_i^{\tilde{q}_i}\cap P_j^{\tilde{q}_j} = \emptyset$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$. Then, for any $\varepsilon > 0$, there exists $n(\varepsilon )\in \mathbb {N}$ such that:

• 1. $\left| \mathcal {F}(Q^*) - {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n)\right| < \varepsilon$,

• 2. $\left| \mathcal {F}(Q^*) - \mathcal {F}(\bar{Q})\right| < \varepsilon ,$

for all $n\in \mathbb {N}$ with $n\ge n(\varepsilon )$, being $Q^*$ an optimal suitable solution of problem BL, ${\varvec{Q}}^*=((k_1^*,l_1^*),\ldots ,(k_{\rho }^*,l_{\rho }^*))$ an optimal suitable solutions of problem DBL(n), and $\bar{Q}=(q_{(k_1^*,l_1^*)},\ldots ,q_{(k_{\rho }^*,l_{\rho }^*)})$ the suitable solution of problem BL codified by ${\varvec{Q}}^*$.

Proof

From Lemmas 3.1, 3.2 and 3.3 is derived that there exists $\tilde{n}\in \mathbb {N}$ such that $\left| \mathcal {F}(Q) - {\varvec{\mathcal {F}}}({\varvec{Q}},n)\right| < \varepsilon / 4$, for all ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$, being $Q=(q_{(k_1,l_1)},\ldots ,q_{(k_{\rho },l_{\rho })})$, and all $n\in \mathbb {N}$ with $n\ge \tilde{n}$.

Since $\mathcal {F}$ is continuous on $\varGamma$ as it was been shown in the proof of Theorem 2.2, there exists $\epsilon > 0$ such that, if $Q\in \mathcal {B}_{\infty }(Q^*,\epsilon ) \cap \varGamma$, then $\left| \mathcal {F}(Q^*) - \mathcal {F}(Q)\right| < \varepsilon / 4$. Moreover, by hypothesis, there exists $\tilde{Q}=(\tilde{q}_1,\ldots ,\tilde{q}_{\rho })\in \mathcal {B}_{\infty }(Q^*,\epsilon )\cap \varGamma$ such that $P_i^{\tilde{q}_i}\cap \partial \varOmega = \emptyset$ for all $i\in \{1,\ldots ,\rho \}$ and $P_i^{\tilde{q}_i}\cap P_j^{\tilde{q}_j} = \emptyset$ for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$. It is not difficult to see that there exists $\breve{n}\in \mathbb {N}$ for which $\tilde{q}_i\in (k_i,l_i)$, for each $i\in \{1,\ldots ,\rho \}$, for some ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(\breve{n})$. Moreover, note that, for all $n\in \mathbb {N}$ with $n\ge \breve{n}$, there always exists ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}(n)$ such that $\tilde{q}_i\in (k_i,l_i)$ for each $i\in \{1,\ldots ,\rho \}$. Using the continuity of $\mathcal {F}$ on $\varGamma$ and taking into account that $\{ G(n) \}_{n\in \mathbb {N}}$ is a sequence of successively refined grids, it can be proven that there exists $\bar{n}\in \mathbb {N}$ with $\bar{n}\ge \breve{n}$ such that $\left| \mathcal {F}(\tilde{Q}) - \mathcal {F}(\breve{Q})\right| < \varepsilon / 4$, being $\breve{Q}=(q_{(\tilde{k}_1,\tilde{l}_1)},\ldots ,q_{(\tilde{k}_{\rho },\tilde{l}_{\rho })})\in \varGamma$ the suitable solution of problem BL codified by the suitable solution $\tilde{{\varvec{Q}}}=((\tilde{k}_1,\tilde{l}_1),\ldots ,(\tilde{k}_{\rho },\tilde{l}_{\rho }))\in {\varvec{\varGamma }}(n)$ of problem DBL(n) verifying $\tilde{q}_i\in (\tilde{k}_i,\tilde{l}_i)$ for each $i\in \{1,\ldots ,\rho \}$, for all $n\ge \bar{n}$.

Let $n(\varepsilon ) = \max \{ \tilde{n}, \bar{n}\}$. Take $n\in \mathbb {N}$ with $n\ge n(\varepsilon )$ and let $\breve{Q}=(q_{(\tilde{k}_1,\tilde{l}_1)},\ldots ,q_{(\tilde{k}_{\rho },\tilde{l}_{\rho })})\in \varGamma$ the suitable solution of problem BL codified by the suitable solution $\tilde{{\varvec{Q}}}=((\tilde{k}_1,\tilde{l}_1),\ldots ,(\tilde{k}_{\rho },\tilde{l}_{\rho }))\in {\varvec{\varGamma }}(n)$ of problem DBL(n) verifying $\tilde{q}_i\in (\tilde{k}_i,\tilde{l}_i)$ for each $i\in \{1,\ldots ,\rho \}$. From the reasoning above, $\left| \mathcal {F}(Q^*) - {\varvec{\mathcal {F}}}(\tilde{{\varvec{Q}}},n)\right| < \dfrac{3 \varepsilon }{4}$. If ${\varvec{Q}}^*=((k_1^*,l_1^*),\ldots ,(k_{\rho }^*,l_{\rho }^*))\in {\varvec{\varGamma }}(n)$ is the optimal suitable solution of problem DBL(n), then $\left| {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n) - \mathcal {F}(\bar{Q}) \right| < \varepsilon / 4$, being $\bar{Q}=(q_{(k_1^*,l_1^*)},\ldots ,q_{(k_{\rho }^*,l_{\rho }^*)})$. Now, observe that, if ${\varvec{\mathcal {F}}}({\varvec{Q}}^*,n) \le \mathcal {F}(Q^*)$, then ${\varvec{\mathcal {F}}}({\varvec{Q}}^*,n) \le \mathcal {F}(Q^*) \le \mathcal {F}(\bar{Q})$, which implies $\left| \mathcal {F}(Q^*) - {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n)\right|< \varepsilon / 4 < \varepsilon$. On the other hand, if $\mathcal {F}(Q^*) \le {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n)$, then $\mathcal {F}(Q^*)< {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n) < {\varvec{\mathcal {F}}}(\tilde{{\varvec{Q}}},n)$, which implies $\left| \mathcal {F}(Q^*) - {\varvec{\mathcal {F}}}({\varvec{Q}}^*,n)\right|< \dfrac{3 \varepsilon }{4}< \varepsilon$. Finally, taking into account the above, it is not difficult to see that $\left| \mathcal {F}(Q^*) - \mathcal {F}(\bar{Q})\right| < \varepsilon$. $\square$

The theorem above proves the convergence of the sequence of solutions for the discrete approximation to the optimal objective value of problem BL.

4 Solution Approaches

Section 3 provides a methodology to solve problem BL by sequences of discrete problems DBL that converge to the optimal objective value. However, solving each one of those discrete approximations is an issue by itself, but, as we will see in the following, we propose two methods to solve the problem DBL: one of them is exact and it consists of a mixed-integer linear programming (MILP) model and the other one is a GRASP heuristic (see [25]).

4.1 A Mathematical Programming Formulation

This section provides a valid MILP formulation for problem DBL for a fixed grid G.

In order to give a valid formulation for problem DBL, we need to determine the sets and parameters that charge the model with the necessary information of the problem. At this point we remark that the overall global computation time to get an optimal solution of problem DBL is the computing time to obtain the input sets and parameters of the model plus the computing time required to reach the optimal solution. Our goal is to get a computational time as small as possible, so that we have to properly balance both components. On the one hand, if we do not preprocess adequately the information from the elements of the problem, then the model will have to work too much to obtain that information and, as it is known, this is not desirable since MILP models can be really hard to solve. On the other hand, if we want to fully preprocess the elements of the problem to do the model to work less, we will have to do different operations over the set of cells of ${\varvec{\varOmega }}$. Since we are interesting in $|{\varvec{\varOmega }}|$ (number of cells of ${\varvec{\varOmega }}$) to be large (to better approximate problem BL by problem DBL), the time to obtain the initial information sets and CPU memory consumption can increase dramatically.

We use the following sets and parameters to build our MILP model:

• ${\varvec{\varOmega }}_i$: set of candidates for feasible location of dimensional facility $P_i$ in problem DBL, i.e., the set of cells $(k,l)\in {\varvec{\varOmega }}$ such that $P_i^{q_{(k,l)}}\subseteq \varOmega$. This set is defined for each $i\in \{1,\ldots ,\rho \}$.

• ${\varvec{E}}_{rs}^i$: set of cells (k, l) in ${\varvec{\varOmega }}_i$ verifying $(r,s)\in {\varvec{P}}_i^{(k,l)}$. We define this set for each $(r,s)\in {\varvec{\varOmega }}$ and $i\in \{1,\ldots ,\rho \}$.

• $w^D_{rs}$: the demand density in the cell (r, s). This parameter is defined for each $(r,s)\in {\varvec{\varOmega }}$.

• $w^B_{rs}$: the base installation cost density in the cell (r, s). This parameter is defined for each $(r,s)\in {\varvec{\varOmega }}$.

• $u_{rs,kl}^{i}$: $u(q_{(r,s)},P_i^{q_{(k,l)}})$, i.e., the cost in problem DBL paid from any point in (r, s) with respect to the dimensional facility $P_i$ when it is located at the center of the cell (k, l). If $(r,s)\in {\varvec{P}}^{(k,l)}_i$ we take $u_{rs,kl}^{i}=-a_i$ (the reason of this choice will be easily understood when the model is presented). We define this parameter for each $(r,s)\in {\varvec{\varOmega }}$, $i\in \{1,\ldots ,\rho \}$ and $(k,l)\in {\varvec{\varOmega }}_i$.

We now analyze the asymptotic computational complexity for obtaining these sets and parameters assuming ${\varvec{\varOmega }}$ has already been determined. For each $i\in \{1,\ldots ,\rho \}$, suppose that $\mathcal {O}(f_1(P_i,\varOmega ))$ is the asymptotic computational complexity bound for testing if the dimensional facility $P_i$ satisfies $P_i^{q_i}\subseteq \varOmega$ for the location $q_i\in \mathbb {R}^2$. Then, obtaining ${\varvec{\varOmega }}_i$ can be done in $\mathcal {O}(|{\varvec{\varOmega }}|f_1(P_i,\varOmega ))$ (one check for each point $q_{(r,s)}$ with $(r,s)\in {\varvec{\varOmega }}$). Thus, the complexity to get all the sets $\{{\varvec{\varOmega }}_1,\ldots ,{\varvec{\varOmega }}_{\rho }\}$ is bounded by $\mathcal {O}(|{\varvec{\varOmega }}|\sum _{i=1}^{\rho }f_1(P_i,\varOmega ))$.

For each $i\in \{1,\ldots ,\rho \}$, once ${\varvec{\varOmega }}_i$ is computed, take $(k,l)\in {\varvec{\varOmega }}_i$. For each $(r,s)\in {\varvec{\varOmega }}$ check if it occurs that $\text {int}((r,s))\cap \text {int}(P_i^{q_{(k,l)}})\not = \emptyset$ and let $\mathcal {O}(f_2(P_i))$ be the time required to do that test for the cell. If it occurs, add (k, l) to ${\varvec{E}}^i_{rs}$ and take $u^i_{rs,kl}=-a_i$. Otherwise, compute $u(q_{(r,s)},P_i^{q_{(k,l)}})$ and take $u^i_{rs,kl}=u(q_{(r,s)},P_i^{q_{(k,l)}})$. Let $\mathcal {O}(f_3(P_i))$ be the complexity for computing the cost $u(q,P_i^{q_i})$ for any $q,q_i\in \mathbb {R}^2$. Hence, the asymptotic computational complexity of obtaining all the sets ${\varvec{E}}^i_{rs}$ and all the parameters $u^i_{rs,kl}$ can be bounded by $\mathcal {O}(|{\varvec{\varOmega }}|^2\sum _{i=1}^{\rho } [f_2(P_i) + f_3(P_i)])$ ($|{\varvec{\varOmega }}_i|$ is at most $|{\varvec{\varOmega }}|$).

As for the parameters $w^D_{rs}$, to obtain all of them it is necessary to compute $|{\varvec{\varOmega }}|$ integrals. The same can be said for parameters $w^B_{rs}$.

The above analysis shows that all the sets and parameters which we use to define the MILP model can be obtained in a “reasonable” computation time. The space requirements are also efficient and can be bounded above by: $\sum _{i=1}^{\rho } |{\varvec{\varOmega }}_i|\le \rho |{\varvec{\varOmega }}|$, $\sum _{i=1}^{\rho } \sum _{(r,s)\in {\varvec{\varOmega }}}|{\varvec{E}}_{rs}^i|\le \rho |{\varvec{\varOmega }}|^2$, there are $|{\varvec{\varOmega }}|$ constants $w^D_{rs}$, the same number of parameters $w^B_{rs}$, and the cardinality of $u^i_{rs,kl}$ is at most $\rho |{\varvec{\varOmega }}|^2$.

Next, we describe the MILP model. Recall that any non-decreasing, bounded, continuous, piecewise linear function can be modeled with a MILP formulation, see, for example, [30]. Below we represent by $\overline{I_1^{\mathrm{PL}}}(\omega _1^I),\ldots ,\overline{I_{\rho }^{\mathrm{PL}}}(\omega _{\rho }^I),\overline{C_1^{\mathrm{PL}}}(\omega _1^C),\ldots ,\overline{C_{\rho }^{\mathrm{PL}}}(\omega _{\rho }^C),\overline{L^{\mathrm{PL}}}(\omega ^L)$ the linearization of the functions $I_1^{\mathrm{PL}}(\omega _1^I),\ldots ,I_{\rho }^{\mathrm{PL}}(\omega _{\rho }^I),C_1^{\mathrm{PL}}(\omega _{1}^C),\ldots ,C_{\rho }^{\mathrm{PL}}(\omega _{\rho }^C),L^{\mathrm{PL}}(\omega ^L)$ in the objective function of a suitable MILP formulation, and by SCDVPL the Set of Constraints and the Domain declaration of the decision Variables involved in the model that together makes the representation of the Piecewise Linear functions to be correct.

In order to understand the model, we define the following families of decision variables. Binary variable $\theta ^i_{kl}$ is a location variable: it takes the value 1 if the dimensional facility $P_i$ is located at the center of the cell $(k,l)\in {\varvec{\varOmega }}_i$, and 0 otherwise, for each $i\in \{1,\ldots ,\rho \}$. Binary variable $\tau ^i_{rs}$ is an allocation variable, and it takes the value 1 if customers in the cell $(r,s)\in {\varvec{\varOmega }}$ are served by the dimensional facility $P_i$, and 0 otherwise, for each $i\in \{1,\ldots ,\rho \}$. Variable $\varphi _{rs}$ will assume the value of the cost $u_G$ paid from the cell $(r,s) \in {\varvec{\varOmega }}$ when it is assigned to its dimensional facility in a solution of problem DBL. We point out that the facility assigned to a cell must be the one given by a solution of the corresponding discretized lower level problem. Variable $\varphi _{rs}$ will be 0 if (r, s) is contained in a cell facility, for each $(r,s)\in {\varvec{\varOmega }}$.

Theorem 4.1

Problem DBL is equivalent to the following MILP problem:

$$\begin{aligned} \min&\,\,\,\,\, \displaystyle \sum _{i=1}^{\rho } \overline{I_i^{\mathrm{PL}}}\left( \sum _{(r,s)\in {\varvec{\varOmega }}} \sum _{(k,l)\in {\varvec{E}}^i_{rs}} w^B_{rs} \theta ^i_{kl} \right) + \sum _{i=1}^{\rho } \overline{C_i^{\mathrm{PL}}}\left( \sum _{(r,s)\in {\varvec{\varOmega }}} w^D_{rs} \tau ^i_{rs} \right) \\&\,\,\,\,\, \displaystyle +\, \overline{L^{\mathrm{PL}}}\left( \sum _{(r,s)\in {\varvec{\varOmega }}} w^D_{rs} \left[ 1- \sum _{i=1}^{\rho }\tau ^i_{rs}\right] \right) \nonumber \end{aligned}$$

(9)

$$\begin{aligned} \mathrm{s.t.}&\,\,\,\,\, {\mathcal {SCDVPL}}, \end{aligned}$$

(10)

$$\begin{aligned}&\,\,\,\,\, \sum _{(k,l)\in {\varvec{\varOmega }}_i} \theta ^i_{kl} = 1,&\forall i\in \{1,\ldots ,\rho \}, \end{aligned}$$

(11)

$$\begin{aligned}&\,\,\,\,\, \sum _{i=1}^{\rho } \tau ^i_{rs} + \sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl}=1,&\forall (r,s)\in {\varvec{\varOmega }}, \end{aligned}$$

(12)

$$\begin{aligned}&\,\,\,\,\, \sum _{j=1}^{\rho } a_j w^D_{rs} \tau _{rs}^j + w^D_{rs} \varphi _{rs} \le a_i w^D_{rs} + \sum _{(k,l)\in {\varvec{\varOmega }}_i} w^D_{rs} u^i_{rs,kl} \theta ^i_{kl},&\forall (r,s)\in {\varvec{\varOmega }},i\in \{1,\ldots ,\rho \}, \end{aligned}$$

(13)

$$\begin{aligned}&\,\,\,\,\, \sum _{(k,l)\in {\varvec{\varOmega }}_i} u^i_{rs,kl} \theta ^i_{kl}-M(1-\tau ^i_{rs})&\nonumber \\&\,\,\,\,\, \qquad \le \varphi _{rs} \le \sum _{(k,l)\in {\varvec{\varOmega }}_i} u^i_{rs,kl} \theta ^i_{kl}+M(1-\tau ^i_{rs}),&\forall (r,s)\in {\varvec{\varOmega }},i\in \{1,\ldots ,\rho \}, \end{aligned}$$

(14)

$$\begin{aligned}&\,\,\,\,\, \theta ^i_{kl}\in \{0,1\},&\forall i\in \{1,\ldots ,\rho \},(k,l)\in {\varvec{\varOmega }}_i, \end{aligned}$$

(15)

$$\begin{aligned}&\,\,\,\,\, \tau ^i_{rs}\in \{0,1\},&\forall (r,s)\in {\varvec{\varOmega }},i\in \{1,\ldots ,\rho \}, \end{aligned}$$

(16)

$$\begin{aligned}&\,\,\,\,\, \varphi _{rs}\ge 0,&\forall (r,s)\in {\varvec{\varOmega }}, \end{aligned}$$

(17)

where $M=\max \{u^i_{rs,kl} : (r,s)\in {\varvec{\varOmega }},i\in \{1,\ldots ,\rho \},(k,l)\in {\varvec{\varOmega }}_i\}$.

Proof

The domain of the decision variables is stated in (15)–(17).

Suppose that ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ is the suitable solution of problem DBL given by the formulation (9)–(17). Then, for each $i\in \{1,\ldots ,\rho \}$, $\theta _{k_il_i}^i=1$ and $\theta _{kl}^i=0$ for all $(k,l)\in {\varvec{\varOmega }}_i$ other than $(k_i,l_i)$, so

$$\begin{aligned} \sum _{(r,s)\in {\varvec{\varOmega }}} \sum _{(k,l)\in {\varvec{E}}^i_{rs}} w^B_{rs} \theta ^i_{kl} = \sum _{(r,s)\in {\varvec{P}}_i^{(k_i,l_i)}} w_{rs}^B. \end{aligned}$$

Moreover, if partition of ${\varvec{\varOmega }}({\varvec{Q}})$ in problem (9)–(17) is done according to ${\varvec{A}}({\varvec{Q}})\in {\varvec{\mathcal {A}}}_{\rho }({\varvec{Q}})$, it follows that

$$\begin{aligned} \sum _{(r,s)\in {\varvec{\varOmega }}} w^D_{rs} \tau ^i_{rs} = \sum _{(r,s)\in {\varvec{A}}_i({\varvec{Q}})} w^D_{rs}, \end{aligned}$$

since $\tau ^i_{rs}$ will be 1 iff $(r,s)\in {\varvec{A}}_i({\varvec{Q}})$ for each $(r,s)\in {\varvec{\varOmega }}$. This last condition also implies that, for each $(r,s)\in {\varvec{\varOmega }}$, $\tau ^i_{rs}=0$ for all $i\in \{1,\ldots ,\rho \}$ iff $(r,s)\in {\varvec{\varOmega }} {\setminus } {\varvec{\varOmega }}({\varvec{Q}})=\{{\varvec{P}}_1^{(k_1,l_1)}\cup \cdots \cup {\varvec{P}}_{\rho }^{(k_{\rho },l_{\rho })}\}$, therefore

$$\begin{aligned} \displaystyle \sum _{(r,s)\in {\varvec{\varOmega }}} w^D_{rs} \left[ 1- \sum _{i=1}^{\rho }\tau ^i_{rs}\right] = \sum _{(r,s)\in \bigcup _{i=1}^{\rho } {\varvec{P}}_i^{(k_i,l_i)} } w^D_{rs} = \sum _{i=1}^{\rho } \sum _{(r,s)\in {\varvec{P}}_i^{(k_i,l_i)}} w_{rs}^D. \end{aligned}$$

The objective function (9) of the problem (9)–(17) minimizes the same function as in problem DBL, given that $\overline{I_1^{\mathrm{PL}}},\ldots ,\overline{I_{\rho }^{\mathrm{PL}}},\overline{C_1^{\mathrm{PL}}},\ldots ,\overline{C_{\rho }^{\mathrm{PL}}},\overline{L^{\mathrm{PL}}}$ and SCDVPL in (10) are a correct representation, respectively, of $I_1^{\mathrm{PL}},\ldots ,I_{\rho }^{\mathrm{PL}},C_1^{\mathrm{PL}},\ldots ,C_{\rho }^{\mathrm{PL}},L^{\mathrm{PL}}$. It remains to see that the solution given by the formulation (9)–(17) is a suitable solution ${\varvec{Q}}\in {\varvec{\varGamma }}$ of problem DBL and that it provides an optimal partition ${\varvec{A}}({\varvec{Q}})$ of ${\varvec{\varOmega }}({\varvec{Q}})$ in the corresponding discretized lower level problem.

Constraints (11) state that the dimensional facility $P_i$ has to be set in one of the cells of its set ${\varvec{\varOmega }}_i$ of candidates for feasible location, for each $i\in \{1,\ldots ,\rho \}$.

With constraints (12), several conditions are imposed. On the one hand, (12) implies $\sum _{i=1}^{\rho } \tau ^i_{rs} \le 1$, so the demand of the cell $(r,s)\in {\varvec{\varOmega }}$ cannot be satisfied by more than one dimensional facility. On the other hand, implication $\sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl}\le 1$ of (12) avoids intersections among the interiors of the cell facilities located according to the variables $\theta ^i_{kl}$. Suppose that the dimensional facilities $P_i$ and $P_j$ have been located at the centers of the cells $(k_i,l_i)\in {\varvec{\varOmega }}_i$ and $(k_j,l_j)\in {\varvec{\varOmega }}_j$, respectively, so $\theta ^i_{k_il_i}=1$ and $\theta ^j_{k_jl_j}=1$, $i,j\in \{1,\ldots ,\rho \}$, $i\not =j$. If ${\varvec{P}}^{(k_i,l_i)}_i\cap {\varvec{P}}^{(k_j,l_j)}_j\not = \emptyset$, then there exists $(r,s)\in {\varvec{\varOmega }}$ such that $(r,s)\in {\varvec{P}}^{(k_i,l_i)}_i$ and $(r,s)\in {\varvec{P}}^{(k_j,l_j)}_j$, and therefore $(k_i,l_i)\in {\varvec{E}}^i_{rs}$ and $(k_j,l_j)\in {\varvec{E}}^j_{rs}$. This implies $\sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl}\ge 2$ which contradicts implication $\sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl}\le 1$ of (12). Also, constraints (12) force demand of cell $(r,s)\in {\varvec{\varOmega }}$ to be satisfied by one dimensional facility if (r, s) does not belong to any cell facility ($\sum _{i=1}^{\rho } \tau ^i_{rs} = 1$ and $\sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl} = 0$), and to belong to a cell facility if its demand is not satisfied by any dimensional facility ($\sum _{i=1}^{\rho } \tau ^i_{rs} = 0$ and $\sum _{i=1}^{\rho }\sum _{(k,l)\in {\varvec{E}}^i_{rs}} \theta ^i_{kl} = 1$). So, constraints (13)–(14) ensure the feasible location of the dimensional facilities and makes a distinction between demand cells and cells contained in the cell facilities.

The correct allocation of demand cells to dimensional facilities according to the corresponding discretized lower level problem is achieved with constraints (13) and (14). Indeed, suppose that, for $(\tilde{r},\tilde{s})\in {\varvec{\varOmega }}$, $\tau ^{\tilde{i}}_{\tilde{r}\tilde{s}}=1$ for some $\tilde{i}\in \{1,\ldots ,\rho \}$. Hence, by constraints (12), $\tau ^{j}_{\tilde{r}\tilde{s}}=0$ for all $j\in \{1,\ldots ,\rho \}$ with $j\not = \tilde{i}$, and thus constraints (13) state that $a_{\tilde{i}} w^D_{\tilde{r}\tilde{s}} + w^D_{\tilde{r}\tilde{s}}\varphi _{\tilde{r}\tilde{s}} \le a_i w^D_{\tilde{r}\tilde{s}} + \sum _{(k,l)\in {\varvec{\varOmega }}_i} w^D_{\tilde{r}\tilde{s}} u^i_{\tilde{r}\tilde{s},kl} \theta ^i_{kl}$ for all $i\in \{1,\ldots ,\rho \}$. Note that, as $\sum _{(k,l)\in {\varvec{\varOmega }}_i} \theta ^i_{kl} = 1$ by constraints (11), hence $\sum _{(k,l)\in {\varvec{\varOmega }}_i} \theta ^i_{kl} =\theta _{k_i,l_i}^i=1$, and we know $(\tilde{r},\tilde{s})\notin {\varvec{P}}_i^{(k_i,l_i)}$ due to constraints (12), then $\sum _{(k,l)\in {\varvec{\varOmega }}_i} w^D_{\tilde{r}\tilde{s}} u^i_{\tilde{r}\tilde{s},kl} \theta ^i_{kl} = u^i_{\tilde{r}\tilde{s},k_il_i}= u(q_{(\tilde{r},\tilde{s})}, P_i^{q_{(k_i,l_i)}})$, for each $i\in \{1,\ldots ,\rho \}$. So, if $\varphi _{\tilde{r}\tilde{s}}$ takes the value $u(q_{(\tilde{r},\tilde{s})},P_{\tilde{i}}^{q_{(k_{\tilde{i}},l_{\tilde{i}})}})$, constraints (13) impose that cell $(\tilde{r},\tilde{s})$ is assigned to the dimensional facility that provides the smallest cost in the discretized lower level problem. By the constraint of type (14) for $(\tilde{r},\tilde{s})$ and $i= \tilde{i}$, $\varphi _{\tilde{r}\tilde{s}} = \sum _{(k,l)\in {\varvec{\varOmega }}_{\tilde{i}}} w^D_{\tilde{r}\tilde{s}} u^{\tilde{i}}_{\tilde{r}\tilde{s},kl} \theta ^{\tilde{i}}_{kl} = u^{\tilde{i}}_{\tilde{r}\tilde{s},k_{\tilde{i}} l_{\tilde{i}}}= u(q_{(\tilde{r},\tilde{s})},P_{\tilde{i}}^{q_{(k_{\tilde{i}},l_{\tilde{i}})}})$ as $M(1-\tau ^{\tilde{i}}_{\tilde{r}\tilde{s}}) = 0$. When $i\not = \tilde{i}$, constraints of type (14) for $(\tilde{r},\tilde{s})$ are not violated given that $\sum _{(k,l)\in {\varvec{\varOmega }}_i} u^i_{\tilde{r}\tilde{s},kl} \theta ^i_{kl}=u^i_{\tilde{r}\tilde{s},k_il_i} \le M$ and $\varphi _{rs}= u^{\tilde{i}}_{\tilde{r}\tilde{s},k_{\tilde{i}} l_{\tilde{i}}}\le M$, for $M= \max \{u^j_{rs,kl} : (r,s)\in {\varvec{\varOmega }},j\in \{1,\ldots ,\rho \},(k,l)\in {\varvec{\varOmega }}_j\}$.

Now, suppose that for $(\tilde{r},\tilde{s})\in {\varvec{\varOmega }}$, $\tau ^{i}_{\tilde{r}\tilde{s}}=0$ for all $i\in \{1,\ldots ,\rho \}$. As $\tau ^{i}_{\tilde{r}\tilde{s}}=0$ for all $i\in \{1,\ldots ,\rho \}$, by constraints (12), we know $\theta _{k_{\tilde{i}}l_{\tilde{i}}}^{\tilde{i}}=1$ for one $\tilde{i}\in \{1,\ldots ,\rho \}$ and one $(k_{\tilde{i}},l_{\tilde{i}})\in {\varvec{\varOmega }}_{\tilde{i}}$, i.e., $(\tilde{r},\tilde{s})\in {\varvec{P}}_{\tilde{i}}^{(k_{\tilde{i}},l_{\tilde{i}})}$. So, constraint of type (13) for $(\tilde{r},\tilde{s})$ and $i= \tilde{i}$ imposes $\sum _{j=1}^{\rho } a_j w^D_{\tilde{r}\tilde{s}} \tau _{\tilde{r}\tilde{s}}^j + w^D_{\tilde{r}\tilde{s}}\varphi _{\tilde{r}\tilde{s}} \le a_{\tilde{i}} w^D_{\tilde{r}\tilde{s}} + \sum _{(k,l)\in {\varvec{\varOmega }}_{\tilde{i}}} w^D_{\tilde{r}\tilde{s}} u^{\tilde{i}}_{\tilde{r}\tilde{s},kl} \theta ^{\tilde{i}}_{kl}$. But $\sum _{j=1}^{\rho } a_j w^D_{\tilde{r}\tilde{s}} \tau _{\tilde{r}\tilde{s}}^j = 0$ and $\sum _{(k,l)\in {\varvec{\varOmega }}_{\tilde{i}}} w^D_{\tilde{r}\tilde{s}} u^{\tilde{i}}_{\tilde{r}\tilde{s},kl} \theta ^{\tilde{i}}_{kl} = w^D_{\tilde{r}\tilde{s}} u^{\tilde{i}}_{\tilde{r}\tilde{s},k_{\tilde{i}}l_{\tilde{i}}} = -w^D_{\tilde{r}\tilde{s}} a_{\tilde{i}}$, according to the definition of parameters $u^i_{\tilde{r}\tilde{s},kl}$, therefore, $\varphi _{\tilde{r}\tilde{s}}$ has to be 0. Constraints of type (13) for $(\tilde{r},\tilde{s})$ when $i\not = \tilde{i}$ are satisfied trivially as $\sum _{j=1}^{\rho } a_j w^D_{\tilde{r}\tilde{s}} \tau _{\tilde{r}\tilde{s}}^j + w^D_{\tilde{r}\tilde{s}}\varphi _{\tilde{r}\tilde{s}}=0$. In this case, constraints (14) for (r, s) are not violated since, by constraints (11), $\sum _{(k,l)\in {\varvec{\varOmega }}_i} u^i_{\tilde{r}\tilde{s},kl} \theta ^i_{kl} = u^i_{\tilde{r}\tilde{s},k_il_i}$ for some $(k_i,l_i)\in {\varvec{\varOmega }}_i$, and $u^i_{\tilde{r}\tilde{s},k_il_i}-M\le 0 = \varphi _{\tilde{r}\tilde{s}} \le u^i_{\tilde{r}\tilde{s},k_il_i} + M$ given that $M=\max \{u^j_{rs,kl} : (r,s)\in {\varvec{\varOmega }},j\in \{1,\ldots ,\rho \},(k,l)\in {\varvec{\varOmega }}_j\}$. Here, note that $M=\max \{u^j_{rs,kl} : (r,s)\in {\varvec{\varOmega }},j\in \{1,\ldots ,\rho \},(k,l)\in {\varvec{\varOmega }}_j\}$ is the minimum value of M that makes the model (9)–(17) to be correct.

From the above discussion, constraints (13)–(14) force the minimum cost assignment of cell $(\tilde{r},\tilde{s})$ to a dimensional facility in $\{P_1,\ldots ,P_{\rho }\}$ for each cell $(\tilde{r},\tilde{s})\in {\varvec{\varOmega }}$ that is not contained in any cell facility. Hence, the constrains imposed by the discretized lower level problem, in the constrained optimization problem DBL, are satisfied for any feasible solution of the problem (9)–(17). So we conclude that problem (9)–(17) is equivalent to problem DBL. $\square$

4.2 Heuristic Method

As mentioned above, problem DBL is NP-hard, therefore one cannot expect to solve large instances with the MILP formulation (9)–(17) which has $2\rho |{\varvec{\varOmega }}|$ binary variables defined in (15)–(16) plus the number of binary variables in (10) required to modeling the piecewise linear cost functions in (9). This makes the model difficult to solve, especially when the considered number of cells $|{\varvec{\varOmega }}|$ is large to better approximate problem BL. For this reason, we introduce an alternative heuristic algorithm to get “good/reasonable” feasible solutions of problem DBL for larger size instances.

The algorithm proposed is a GRASP (see [26] for details) in which we can distinguish three modules. The first module GRASP_DIMFAC is actually the GRASP, which uses the next two modules to build the final solution. From a location of the dimensional facilities $P_1,\ldots ,P_{\rho }$ (not necessarily feasible), the second module WAVE_DIMFAC, which is a continuous wavefront algorithm, generates a random feasible solution $((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ of problem DBL. Recall that wavefront algorithms are a standard technique in computational geometry to deal with continuous deformations of geometrical elements usually using breadth-first search (see, for example, [31]). Finally, the third module GREEDY_DIMFAC is a greedy algorithm, i.e., a local optimal search improvement at each step [32], that given a feasible solution $((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ of problem DBL, locally searches for another feasible solution improving the objective value of the first one.

In what follows, and for the sake of simplicity, we consider that $\varOmega$, the sets $P_1,\ldots ,P_{\rho }$ and the grid G are fixed. This implies that all the elements that are derived from them are also fixed.

4.2.1 GRASP Algorithm

Before describing the GRASP, we observe the following. Given a suitable solution ${\varvec{Q}}=((k_1,l_1),\ldots ,(k_{\rho },l_{\rho }))\in {\varvec{\varGamma }}$ for problem DBL, computing its objective value can be done easily. This is due to the fact that for each cell $(r,s)\in {\varvec{\varOmega }}$, we can know if it is contained in a cell facility and in which, or if it is a demand cell. If (r, s) is a demand cell we also know to which dimensional facility it is assigned: the one with minimum assignment cost. In other words, ${\varvec{P}}_1^{(k_1,l_1)}, \ldots ,{\varvec{P}}_{\rho }^{(k_{\rho },l_{\rho })}$ and ${\varvec{A}}({\varvec{Q}})=({\varvec{A}}_1({\varvec{Q}}),\ldots ,{\varvec{A}}_\rho ({\varvec{Q}}))$ can be easily obtained processing sequentially all the cells of ${\varvec{\varOmega }}$. So, obtained the above sets, we can compute ${\varvec{\mathcal {F}}}({\varvec{Q}})$.

The above is correct except for the case in which two or more dimensional facilities provide equal minimum assignment cost for a cell $(r,s)\in {\varvec{\varOmega }}$. In that case, as we are looking for a heuristic solution for problem DBL and we want to do this as fast as possible, we assign the cell (r, s) to any of that dimensional facilities with minimum assignment cost.

A formal pseudocode of our GRASP is given in Algorithm 1.

Our GRASP algorithm for problem DBL takes advantage of the fact that we have a tool to generate and evaluate suitable solutions. Initially, in STEP 1, GRASP_DIMFAC generates a list $\varPsi$ of $\psi$ random suitable solutions with procedure WAVE_DIMFAC and improves them with procedure GREEDY_DIMFAC. These suitable solutions are ordered in the list $\varPsi$ according with their objective values, being the best suitable solution the first in the list.

The randomization part of the GRASP in STEP 2 tries to obtain new suitable solutions from some already available solutions. It performs permutations among the centroids of some dimensional facilities ($\varpi$ dimensional facilities, being $\varpi$ a parameter). Given a suitable solution in the list we obtain another one using WAVE_DIMFAC. This suitable solution may not have the resulting permuted centroids since permuting the positions of the dimensional facilities $P_1,\ldots ,P_{\rho }$ in a suitable solution of problem DBL may not provide another suitable solution, as the interior of the dimensional facilities could intersect or they could not be contained in $\varOmega$. Next, we improve that suitable solution with GREEDY_DIMFAC. If the resulting suitable solution is better than any in the list, we replace the worst suitable solution by the new one, reorder the suitable solutions in the list, and continue the process with the following not yet processed solution in the list. The process is repeated, starting the list by the beginning again if it is necessary, a predefined number of times: termination criterion. The algorithm returns the first element in $\varPsi$, i.e., the best suitable solution found for problem DBL and its objective value.

4.2.2 Wavefront Algorithm

The main idea of the wavefront algorithm to generate random suitable solutions for problem DBL is the following: since directly locating dimensional facilities $P_1,\ldots ,P_{\rho }$ in the demand region in a valid way (i.e., in a way such that their interiors do not intersect) could not be an easy task, we begin by locating in a valid way a shrunken version of them, which is easier, and then we make these shrunken dimensional facilities to grow. The wavefront is shown in Algorithm 2. If $\mathscr {P}_i^{q_i}$ is the homothecy of center $q_i$ and ratio $\lambda \ge 0$ applied to the set $P_i^{q_i}$, in the algorithm, we characterize the location of the set $\mathscr {P}_i^{q_i}$ by its centroid $q_i$, for each $i\in \{1,\ldots ,\rho \}$. In addition, we use the following notation in the algorithm: $\ell _1(\mathscr {P}_i^{q_i},\mathscr {P}_j^{q_j})$ is the minimum $\ell _1$-distance between a point in $\mathscr {P}_i^{q_i}$ and a point in $\mathscr {P}_j^{q_j}$; $\kappa x$ and $\kappa y$ denote the maximum width and the maximum height of a cell in ${\varvec{\varOmega }}$, respectively.

The wavefront algorithm begins in STEP 1 with a shrunken version $\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_\rho ^{q_\rho }$ (determined by parameter $\lambda$) of the sets $P_1^{q_1},\ldots ,P_{\rho }^{q_{\rho }}$. In STEP 2, if condition $\ell _1(\mathscr {P}_i^{q_i},\mathscr {P}_j^{q_j})\ge 3(\kappa x + \kappa y)$ is satisfied for all $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$, we can continue making to grow $\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_\rho ^{q_\rho }$ applying them a homothecy of ratio $\lambda$. The meaning of the condition above (onwards, the minimum $\ell _1$-separation-condition) is the following: the algorithm WAVE_DIMFAC is able to find a suitable solution for problem BL from an initial location (not necessarily feasible) of the dimensional facilities $P_1,\ldots ,P_\rho$; from this suitable solution of problem BL we will obtain a suitable solution of problem DBL moving each dimensional facility from the location $q_i$ to the center of the cell of ${\varvec{\varOmega }}$ to which $q_i$ belongs to (STEP 7 of the algorithm); however, this movement may lead to some cases where the interior of the cell facilities intersect, producing a non-suitable location of the facilities in problem DBL; it is easy to see that the minimum $\ell _1$-separation-condition avoids this undesirable situation in STEP 7. Since $1/\lambda \in \mathbb {N}$, it holds that $\{\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_{\rho }^{q_{\rho }}\} = \{P_1^{q_1},\ldots ,P_{\rho }^{q_{\rho }}\}$ after a finite number of homothecies of ratio $\lambda$ applied to sets $\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_{\rho }^{q_{\rho }}$ in STEP 2. If the minimum $\ell _1$-separation-condition is not satisfied for some $i,j\in \{1,\ldots ,\rho \}$ with $i\not =j$ in STEP 2, we have to separate the pairs of problematic shrunken dimensional facilities.

The separation of the dimensional facilities $\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_\rho ^{q_\rho }$ in STEP 3 and STEP 4 is done with the separator vectors $\overrightarrow{\upsilon }$. The separator vector $\overrightarrow{\upsilon _{ij}}$ gives the direction that moves away the centroid $q_j$ of the dimensional facility $\mathscr {P}_j^{q_j}$ from the centroid $q_i$ of the dimensional facility $\mathscr {P}_i^{q_i}$ such that does not verify the minimum $\ell _1$-separation-condition with respect to $\mathscr {P}_j^{q_j}$ (if the minimum $\ell _1$-separation-condition is verified then $\overrightarrow{\upsilon _{ij}}=\underline{0}$). Thus, $(\sum _{j=1}^{\rho } \overrightarrow{\upsilon _{ij}})/\Vert \sum _{j=1}^\rho \overrightarrow{\upsilon _{ij}} \Vert _2$ can be used as a direction to separate $\mathscr {P}_j^{q_j}$ from the other sets which are too close to it. Parameter $\vartheta$ controls the distance of the separations. Separation steps are applied $\varUpsilon _2\in \mathbb {N}$ times if all the pairs of dimensional facilities satisfy the minimum $\ell _1$-separation-condition in each iteration, otherwise, $\overrightarrow{\upsilon }$ has to be updated and the separation process has to begin again. So, the separation process ends when $\varUpsilon _2$ iterations are done fixed $\upsilon$ or when an overall number $\varUpsilon _1\in \mathbb {N}$ of iterations is reached.

If the maximum number of iterations is reached (the third line of STEP 4 has been revisited a number $\varUpsilon _1\in \mathbb {N}$ of consecutive times without pass by a step different from STEP 3 and STEP 4), we have to relocate in STEP 5 the dimensional facilities $\mathscr {P}_1^{q_1},\ldots ,\mathscr {P}_\rho ^{q_\rho }$ which do not satisfy the minimum $\ell _1$-separation-condition and begin the growing process again (from STEP 1). The point $q_i$ is relocated maximizing the minimum Euclidean distance from the centroid $q_j$ of the dimensional facility $\mathscr {P}_j^{q_j}$ violating the minimum $\ell _1$-separation-condition with respect to $\mathscr {P}_i^{q_i}$: found the solution $q^*$ of the problem , we relocate the point $q_i$ at a point randomly selected in a neighborhood of $q^*$ (we use the ball $\mathcal {B}_{\ell _1}(q^*,\varepsilon )$ as that neighborhood). Actually, in STEP 5 of our algorithm, instead of solving a global maximin problem, we solve a local maximin problem which needs a random point to start, making the process more random. As relocation of points $q_i$ done in STEP 5 depends on the order of the dimensional facilities, we then permute the order of the dimensional facilities to get more randomness in the algorithm. That permutations has to be undone (STEP 6) before to determine the suitable solution of dimensional facilities $P_1,\ldots ,P_{\rho }$ found (STEP 7) and to return it.

4.2.3 Greedy Algorithm

Consider now that we are given a suitable solution ${\varvec{Q}}\in {\varvec{\varGamma }}$ for problem DBL. The greedy algorithm shown in Algorithm 3 performs a local search to improve the objective value given by the current suitable solution ${\varvec{Q}}$. Specifically, if $(k_i,l_i)\in {\varvec{\varOmega }}$ is the cell in whose center is located the dimensional facility $P_i$, the greedy algorithm evaluates the objective function of problem DBL if we move $P_i$ to the centers of the cells in a neighborhood of $(k_i,l_i)$ (determined by parameters $\varDelta _k,\varDelta _l \in \mathbb {N}$) keeping the position of the remaining dimensional facilities, provided that the movement produces a suitable solution. This is done for each $i\in \{1,\ldots ,\rho \}$. Then, we relocate the dimensional facilities whose movement to a neighbor cell provides the best improvement of the objective value. This process is repeated until no improvement is obtained.

Note that Algorithm 3 is presented for a grid G where the neighbors of a cell $(r,s)\in {\varvec{G}}$ are determined by the adjacent horizontal and vertical cells in ${\varvec{G}}$. This is done for the sake of simplicity. However, it is easy to extend the Algorithm 3 to more general grids if the neighborhood of a cell is well defined in the considered grid.

4.3 Computational Experiments

This section reports some computational experiments performed to show the usefulness of the proposed methodologies to solve problem BL. Our code is implemented in MATLAB R2017A and it makes calls to the XPRESS solver version 8.0 to solve the MILP programs. All experiments were run in a computer DellT5500 with a processor Intel(R) Xeon(R) with a CPU X5690 at 3.75 GHz and 48 GB of RAM memory.

We have included several test examples. Some of them were already proposed in [13] and some others are new. Including the new examples we want to compare the diversity of the solutions when different service costs, distance measures, shapes of the dimensional facilities, cost functions and densities are combined. In addition, we also show how the solutions of the examples are affected when they are included in the bilevel approach combining the different elements of the problem.

In all cases, we use regular grids to approximate the exact solution of the bilevel problem BL. We always begin by solving the problem by means of our heuristic algorithm (Algorithm 1) with the following parameters. Algorithm 1 runs with a list of solutions of length $\psi =50$, $\varpi =2$ centroids to be permuted and the stopping criterion, in STEP 2, consists of processing the list without improvement. Algorithm 2 is executed with a homothecy ratio $\lambda =0.05$ (which results in applying the homothecy transformation, at least, $1/\lambda =20$ times), a separation parameter $\vartheta =0.05$ and stopping separation criterion $\varUpsilon _1=9$ and $\varUpsilon _2=3$. Finally, Algorithm 3 is applied with $\varDelta _k=\varDelta _l=5$. Once the heuristic solution is found, we next improve that solution adding it as an initial feasible solutions to the exact MILP formulation and then we let it run for 4 h (14,400 s) of CPU time. The performance of the GRASP heuristic and the MILP formulation is reported in Table 1. This table shows, for both methods, the time required for the preprocessing of the information (PT), the execution time once the information has been preprocessed (ET), the best objective value found (BOVF) and the gap obtained for the solution provided by the MILP formulation (GAP).

Example 4.1

Our first test illustrates how the approach in this paper applies to one example borrowed from the literature [13]. First, we consider that the demand region $\varOmega$, the dimensional facilities $P_1,P_2,P_3$ and all the elements of the lower level problem are the ones given in Example 4.1 in [13]. In addition, we will assume that there also exists an installation cost described by the base installation cost density $B(q) = 6(x-y)$ if $x\ge y$ and $B(q) = 0$ otherwise, and the installation cost functions $I_i(\omega _i^I) = \omega _i^I$ for all $\omega _i^I\in [0,1]$.

To better illustrate the performance of our methodology, we distinguish two different situations.

Example 4.1.1

The first situation includes non-uniform demand density D on $\varOmega$, given by $D(q) = 8 (x-0.5)$ if $x\ge 0.5$ and $D(q)=0$ otherwise. In addition, we also consider the following non-zero lost demand cost $L(\omega ^L)=\omega ^L$ for all $\omega ^L\in [0,1]$ and zero congestion costs $C_i(\omega _i^C) = 0$ for all $\omega _i^C\in [0,1]$, for each $i\in \{1,\ldots ,3\}$. Note that, in this example, the problem does not explicitly depend on the partition of the demand region.

Example 4.1.2

The second example considers uniform demand density $D(q)=1$, as in the original example in [13], it does not apply any lost demand cost (i.e., $L(\omega ^L)=0$ for all $\omega ^L\in [0,1]$) but it includes the following congestion costs: $C_i(\omega _i^C) = \omega _i^C$ if $\omega _i^C< \tilde{\omega }_i^C/3$ and $C_i(\omega _i^C)=\omega _i^C + 100(\omega _i^C-\tilde{\omega }_i^C/3)$ otherwise, for all $\omega _i^C\in [0,1]$ and each $i\in \{1,\ldots ,3\}$, being $\tilde{\omega }_i^C=1-\int _{\bigcup _{i=1}^3 P_i} D(q)\mathrm{d}q$. The inclusion of this congestion cost term makes the problem to depend on the partition of the demand region. The choice of this particular expression forces a fairly equal splitting of the demand among the three facilities.

We have solved the location-allocation problems defined by these situations, and the results can be seen in Fig. 4 and Table 1.

Fig. 4

Graphical output of the solutions for Example 4.1

Table 1 GRASP heuristic and MILP formulation performance

The graphical output of our algorithms reports the results that could have been anticipated. In the Example 4.1.1 (Fig. 4a, b), since the base installation cost density is null in the upper triangle and the demand is also null in the left half of the region $\varOmega$, the dimensional facilities tend to be located, as much as possible, in the upper triangle and in the left half of the square region. However, their measure does not allow them to be completely included in that region. This is the reason why two of them have a portion on the higher installation cost (lower triangle) and higher lost demand (right half square) parts of the diagram. The MILP formulation provides a solution (Fig. 4b) slightly better than the one obtained by the GRASP heuristic (Fig. 4a). The reader should observe that the solution provided by the MILP formulation is optimal (it has zero GAP) as it can be seen in Table 1.

The solution of the location-allocation problem of Example 4.1.2 is shown in Fig. 4c, d. The result shown in these figures is consistent and it shows that the installation cost does not fully determine the final location of the dimensional facilities. This can be explain because, a non-approximate equal splitting of the demand among the facilities, is highly penalized by the installation cost functions $I_1,I_2,I_3$. Even so, the solution attempts to place the facilities in the upper triangle to also reduce the installation cost, actually, the biggest facility is completely contained in the upper triangle. The solution obtained by the MILP formulation (Fig. 4d) is the same that the one provided by the GRASP heuristic (Fig. 4c). This means that, in this case, the MILP formulation is not able to find a better solution than the GRASP heuristic within the CPU time limit. However, the use of the MILP approach provides the GAP of the solution obtained (see Table 1). Finally, in Fig. 4c, d, it seems that the demand region $A_2$, assigned to the second facility $P_2$, has two connected components. This fact is not strange if one has in mind the properties of bisectors for different distance measures, as it is our case, see [3, 33] for more details.

Example 4.2

This situation is included to illustrate the use of different service costs in the model. We consider that the demand region $\varOmega$ is the unit square and there are three dimensional facilities. The first one, $P_1$, is a non-convex polygon with cost based on the worst case situation given by $u_1(q,q_1) = 0.8 \max _{\tilde{q}\in P_1^{q_1}} \ell _2(q-\tilde{q})$. The second facility, $P_2$, is a regular pentagon and its cost, is given by $u_2(q,q_2) = \ell _2(q-q_2)$, where $q_2$ is the centroid of $P_2$. Finally, the last facility, $P_3$, is the unit ball of a weighted Euclidean norm, namely $P_3:=\{(x,y): \sqrt{75 x^2 + 150 y^2}\le 1\}$; and its cost $u_3(q,q_3) = 0.2\gamma _{P_3}(q-q_3)$. This is the case where the cost is induced by a Minkowski functional.

The remaining parameters of this example are the following: $a_1=a_2=a_3=1$ and the demand density is uniform, namely $D(q) = 1$. The congestion costs, $C_i$ are: $C_i(\omega ^C)=\omega ^C$ if $\omega ^C\le 0.25$ and $C_i(\omega ^C)=\omega ^C+\aleph _i\omega ^C$ if $\omega ^C\ge 0.25$, where $\aleph _1=\aleph _2=0.5$ and $\aleph _3=0.25$; and the lost demand cost is $L(\omega ^L)=\omega ^L$.

Finally, the base installation cost density is defined by the expression

$$\begin{aligned} B(q) = {\left\{ \begin{array}{ll} 2(x+y), &{} \hbox {if }x\le 0.5\hbox { and }y\le 0.5, \\ 2(x+1-y), &{} \hbox {if }x\le 0.5\hbox { and }y> 0.5, \\ 2(1-x+y), &{} \hbox {if }x> 0.5\hbox { and }y\le 0.5, \\ 2(1-x+1-y), &{} \hbox {if }x> 0.5\hbox { and }y> 0.5. \end{array}\right. } \end{aligned}$$

This function accumulates the density in the center of the square since the bivariate density function increases from the vertices of the unit square to its center. We take as base installation costs $I_1(\omega ^I) = I_2(\omega ^I) = I_3(\omega ^I) = 5\omega ^I$.

We solve this configuration for grids with different sizes to illustrate the convergence of our discretization approach. We have chosen grids of $20\times 20$ (see Fig. 5a, b), $30\times 30$ (see Fig. 5c, d), $40\times 40$ (see Fig. 5e, f), $50\times 50$ (see Fig. 5g, h) and $60\times 60$ (see Fig. 5i, j).

Fig. 5

Graphical output of the solutions for Example 4.2

From our results we report that in all cases (i.e., for the different grid sizes) the exact MILP approach could not improve the solution found by our heuristic algorithm. In the $20\times 20$ grid case the solution found is optimal, as certified by the MILP problem (see Table 1). The configuration of the solutions found can be explained by the shapes of the densities and costs functions. Since the base installation density is lower in the vicinity of the vertices of $\varOmega$ and the demand is uniform, the facilities try to locate the closer to the vertices the better. Nevertheless, the congestion cost makes that one of the facilities that is less congested, $P_3$, moves closer to $P_1$ to cannibalize part of its demand. The two connected components in the partition allocated to $P_1$ in Fig. 5i, j can be explained, as before, by the properties of bisectors with different norms. Finally, one observes some stability in the solutions whenever the grids are denser.

Fig. 6

Graphical output of the solutions for Example 4.3

Example 4.3

This situation is included to illustrate our methodology with a larger number of facilities, 10, and also with different congestion costs associated to each of them. We assume a cost $u_i(q,q_i)=\ell _ 2(q-q_i)$, for all $i=1,\ldots ,10$. Once again, we consider that the demand region $\varOmega$ is the unit square and there are ten tetrominoes as dimensional facilities. $\varOmega$ is discretized in a $60\times 60$ grid. Since, our tetrominoes have small measure with respect to $\varOmega$, this example considers that the installation and lost demand costs are negligible and thus we take them as null.

We report two examples that depend on different demand density functions and in both cases the congestion costs for the tetrominoes are the same. These congestion costs are: $C_i(\omega ^C)=\omega ^C$ if $\omega ^C\le \aleph _i$ and $C_i(\omega ^C)=\aleph _i+100(\omega ^C-\aleph _i)$ if $\omega ^C\ge \aleph _i$ where $\aleph =1/30(5,5,3,3,3,3,3,3,1,1)$.

Example 4.3.1

In this case, we have chosen a uniform demand density $D(q)=1$.

Example 4.3.2

This second case considers as demand density for each $q=(x,y)\in \varOmega$, $D(q) = 3(x-y)$ if $x\ge y$, and $D(q) =3(y-x)$, if $x<y$. Observe that this density is null on the diagonal of $\varOmega$ and is maximal at the points (1, 0) and (0, 1).

As it can be seen in Fig. 6, the results provided by the two methods, in the two cases (Examples 4.3.1 and 4.3.2), are consistent. As it occurs in Example 4.2, the exact MILP approach could not improve the solution found by our GRASP algorithm in both cases. Analyzing the results in each case, we observe that in Example 4.3.1 (Fig. 6a, b) the facilities are spread more or less “uniformly” on the unit square. This is due to the considered uniform demand density. On the other hand, in Example 4.3.2 (Fig. 6c, d) the facilities are mainly concentrated close to the points (1, 0) and (0, 1), where the demand density is much higher. It is also interesting to remark the excellent behavior of our MILP formulation in Example 4.3.1. We observe in Table 1 that, given the structure of the problem defined in Example 4.3.1 (there is no installation cost, no lost demand cost, and all the cells have the same demand density), the MILP formulation is able to prove optimality [GAP (%) is zero] of the solution found by the GRASP heuristic in a rather short computing time.

5 Conclusions

This paper gives a first complete proof of existence of optimal solutions of a general location-allocation problem with dimensional facilities. This result includes as particular instances previously published results in the field with dimensionless facilities (point facilities). It also provides two methods to solve this problem using sequences of solutions for a discrete approximation of the problem. One is exact and it is based on a new mixed-integer linear programming formulation and the other one is a GRASP heuristic that results in very good solutions.

This paper has a number of possible extensions that may open some interesting research lines. Among them, we would like to mention relaxing some conditions ensuring existence of optimal solutions, as for instance the continuity of the utilities in the objective function of the lower level problem, although this is beyond the scope of this paper. In addition, these results can be extended to the case where the facilities are allowed to be rotated: existence of solutions can be proved similarly but the discretization scheme would need to consider also a finite number of rotation angles which would make the algorithms more complicated. Moreover, although we have restricted ourselves to consider problems on the plane most of our results extend to any finite dimension space assuming that facilities are full dimension compact sets. In that case, one can adapt the existence of solutions and convergence proofs, redefining the grid to be a generic subdivision of the feasible domain. The discretization results can be also adapted although at the price of increasing the complexity of the models that then become exponential in the dimension of the space.