Ordered p-median problems with neighbourhoods

Abstract

In this paper, we introduce a new variant of the p-median facility location problem in which it is assumed that the exact location of the potential facilities is unknown. Instead, each of the facilities must be located in a region around their initially assigned location (the neighborhood). In this problem, two main decisions have to be made simultaneously: the determination of the potential facilities that must be open to serve the customers’ demand and the location of the open facilities in their neighborhoods, at global minimum cost. We present several mixed integer non-linear programming formulations for a wide family of objective functions which are common in Location Analysis: ordered median functions. We also develop two math-heuristic approaches for solving the problem. We report the results of extensive computational experiments.

A Appendix: Proof of Proposition 3.1

Denote by $F_{3I}$, $F_{2I}$, $F_{OT}$ and $F_{BEP}$ the feasible regions of ($\mathrm{OMPN}_{3I}$), ($\mathrm{OMPN}_{2I}$), ($\mathrm{OMPN}_{OT}$) and ($\mathrm{OMPN}_{BEP}$) obtained when relaxing the integrality conditions of the models.

• 1. Consider the map** $\pi : \mathbb {R}^n_+\times \mathbb {R}^{n \times n}_+ \times [0,1]^{n\times n} \times \mathcal {X}_R \times \mathcal {D}\rightarrow \mathbb {R}^{n^3}_+ \times [0,1]^3 \times [0,1]^n \times \mathcal {D}$ defined as:

  $$\begin{aligned} \pi (\xi , \theta , s, x, (d, {\bar{a}})) = ((\xi _k s_{ik} x_{ij})_{i,j,k=1}^n, (s_{ik}x_{ij})_{i,j,k=1}^n, (x_{jj})_{j=1}^n, (d, {\bar{a}})) \end{aligned}$$

  First, let us check that $\pi (F_{2I}) \subseteq F_{3I}$, which would prove the first inequality. Let $(\theta , \xi , s, x, (d, {\bar{a}})) \in F_{2I}$, and define $({\bar{\theta }}, {\bar{x}}, (d,{\bar{a}}))=\pi (\theta , \xi , s, x, (d, {\bar{a}}))$, i.e.:

  $$\begin{aligned} {\bar{\theta }}_{ij}^k = \xi _k s_{ik} x_{ij}, \; {\bar{w}}_{ij}^k = s_{ik}x_{ij}, \; {\bar{x}}_{jj}= x_{jj}, \; \forall i,j,k=1, \ldots , n. \end{aligned}$$

  By construction, the constraints (3.1)–(3.4) are verified:

  • $\displaystyle \sum _{j, k=1}^n {\bar{w}}_{ij}^k =\displaystyle \sum _{j, k=1}^n s_{ik} x_{ij} = \displaystyle \sum _{j=1}^n x_{ij} \displaystyle \sum _{k=1}^n s_{ik} {\mathop {=}\limits ^{(3.10)}} \displaystyle \sum _{j=1}^n x_{ij} {\mathop {=}\limits ^{x\in \mathcal {X}_R}} 1$.

  • $\displaystyle \sum _{i, j=1}^n {\bar{w}}_{ij}^k =\displaystyle \sum _{i, j=1}^n s_{ik} x_{ij} = \displaystyle \sum _{i=1}^n s_{ik} \displaystyle \sum _{j=1}^n x_{ij} {\mathop {=}\limits ^{x\in \mathcal {X}_R}} \displaystyle \sum _{i=1}^n s_{ik} {\mathop {=}\limits ^{(3.9)}} 1$.

  • $\displaystyle \sum _{k=1}^n {\bar{w}}_{ij}^k = \displaystyle \sum _{k=1}^n s_{ik}x_{ij} = x_{ij} \displaystyle \sum _{k=1}^n s_{ik} {\mathop {=}\limits ^{(3.10)}} x_{ij} {\mathop {\le }\limits ^{x\in \mathcal {X}_R}} x_{jj}$.

  • $\displaystyle \sum _{j=1}^n {\bar{x}}_{jj} = \displaystyle \sum _{j=1}^n x_{jj} = {\mathop {=}\limits ^{x\in \mathcal {X}_R}} p$.

  • ${\bar{\theta }}_{ij}^k = \xi _k s_{ik} x_{ij} {\mathop {\ge }\limits ^{(3.12), (3.13)}} (d_{ij}- \widehat{D}_{ij}(2-s_{ik}-x_{ij})) \, s_{ik}x_{ij} = d_{ij}- \widehat{D}_{ij}(1- s_{ik}x_{ij}) + (\widehat{D}_{ij} - d_{ij})(1-s_{ik}x_{ij}) + \widehat{D}_{ij}s_{ik} x_{ij} (s_{ik}+x_{ij}) {\mathop {\ge }\limits ^{{\bar{w}}_{ij}^k = s_{ik}x_{ij}, s_{ik}, x_{ij}\le 1, d_{ij}\le \widehat{D}_{ij}}} d_{ij}- \widehat{D}_{ij}(1-{\bar{w}}_{ij}^k)$.

  • $\displaystyle \sum _{i, j=1}^n {\bar{\theta }}_{ij}^k = \displaystyle \sum _{i,j=1}^n \xi _k s_{ik} x_{ij} = \xi _k \displaystyle \sum _{i=1}^n s_{ik} \displaystyle \sum _{j=1}^n x_{ij} {\mathop {=}\limits ^{x \in \mathcal {X}_R}} \xi _{k} \displaystyle \sum _{i=1}^n s_{ik} {\mathop {=}\limits ^{(3.9)}} \xi _k {\mathop {\ge }\limits ^{(3.6)}} \xi _{k+1} = \displaystyle \sum _{i, j=1}^n {\bar{\theta }}_{ij}^{k+1}$.

  Then, $\pi (\theta , \xi , s, x, (d, {\bar{a}})) \in F_{3I}$, so $\pi (F_{2I}) \subset F_{3I}$, i.e. any solution of the convex relaxation of ($\mathrm{OMPN}_{2I}$) induces a solution of the convex relaxation of ($\mathrm{OMPN}_{3I}$). Furthermore, the objective values for $(\theta , \xi , s, x, (d, {\bar{a}}))$ in ($\mathrm{OMPN}_{2I}$) and $\pi (\theta , \xi , s, x, (d, {\bar{a}}))$ in ($\mathrm{OMPN}_{3I}$) coincides:

  $$\begin{aligned} \displaystyle \sum _{i,j,k=1}^n \lambda _k {\bar{\theta }}_{ij}^k + \displaystyle \sum _{j=1}^n f_j{\bar{x}}_{jj}&= \displaystyle \sum _{i,j,k=1}^n \lambda _k \xi _k s_{ik} x_{ij} + \displaystyle \sum _{j=1}^n f_j x_{jj} \\&= \displaystyle \sum _{k=1}^n \lambda \xi _k \displaystyle \sum _{i=1}^n s_{ik} \displaystyle \sum _{j=1}^n x_{ij} + \displaystyle \sum _{j=1}^n f_j x_{jj} \\&{\mathop {=}\limits ^{x \in \mathcal {X}_R}} \displaystyle \sum _{k=1}\lambda _k \xi _k \displaystyle \sum _{i=1}^n s_{ik} + \displaystyle \sum _{j=1}^n f_j x_{jj} \\&{\mathop {=}\limits ^{(3.9)}} \displaystyle \sum _{k=1}^n \lambda _k \xi _k + \displaystyle \sum _{j=1}^n f_j x_{jj} \end{aligned}$$

  Thus, $z_{2I}^R \ge z_{3I}^R$.

• 2. Let us check now that $z^R_{3I} \le z^R_{BEP}$.

  Let $(u, v, D, x, (d,{\bar{a}})) \in \mathbb {R}^n \times \mathbb {R}^n \times \mathbb {R}^n_+ \times \mathcal {X}_R \times \mathcal {D}$ be the optimal solution of the continuous relaxation of ($\mathrm{OMPN}_{BEP}$). Let $p_{ik}$ be the optimal dual variables associated to constraint (3.21). By optimality conditions they must verify:

  $$\begin{aligned} \displaystyle \sum _{i=1}^n p_{ik}=1, \forall k=1, \ldots , n,\\ \displaystyle \sum _{k=1}^n p_{ik}=1, \forall i=1, \ldots , n. \end{aligned}$$

  Let us construct the following vector in $\mathbb {R}^n_+ \times \mathbb {R}^{n\times n}_+ \times [0,1]^{n\times n} \times \mathcal {X}_R \times \mathcal {D}$:

  $$\begin{aligned} \left( {\bar{\theta }}, {\bar{w}}, x, (d,{\bar{a}})\right) := \left( \left\{ d_{ij}p_{ik} x_{ij}\right\} , \left\{ p_{ik}x_{ij}\right\} , x, (d,{\bar{x}})\right) . \end{aligned}$$

  By the construction of the $p_{ik}$-values, it is straightforward to proof that the projected values verify the constraints of ($\mathrm{OMPN}_{2I}$) and that the objective values of both solutions coincide. Thus, $z^R_{BEP} \ge z^R_{3I}$

• 3. Finally, we prove that $z^R_{BEP} =z^R_{OT}$.

  Let us consider $x \in \mathcal {X}_R$, $(d,a) \in \mathcal {D}$. Observe that the difference between ($\mathrm{OMPN}_{OT}$) and ($\mathrm{OMPN}_{BEP}$) is the way of evaluating the ordered median cost, $\mathrm{om}(x,d,a)$. In the first case:

  $$\begin{aligned} \mathrm {om}(x,d,a) = \min&\displaystyle \sum _{k=1}^{n-1} \varDelta _k (kt_k + \displaystyle \sum _{i=1}^n z_{ik})\\ s.t.&z_{ik} \ge D_i - t_k, \forall i, k=1, \ldots , n,\\&D_i \ge d_{ij} - \widehat{D}_{ij} (1-x_{ij}), \forall i,j=1, \ldots , n, i\ne j,\\&z_{ik}, D_i \ge 0, \forall i, k=1, \ldots , n,\\&t_k \in \mathbb {R}, \forall k=1, \ldots , n. \end{aligned}$$

  while in the BEP formulation is via:

  $$\begin{aligned} \mathrm {om}(x,d,a) = \min&\displaystyle \sum _{k=1}^n u_k + \displaystyle \sum _{i=1}^n v_i\\ \text{ s.t. }&u_i + v_k \ge \lambda _k D_i, \forall i,k=1, \ldots , n,\\&D_i \ge d_{ij} - \widehat{D}_{ij}(1-x_{ij}), \forall i, j=1, \ldots , n (i\ne j), \end{aligned}$$

  but the values coincides with the ordered median function of the (relaxed) travel costs. Thus, $z^R_{BEP} =z^R_{OT}$.