Minimizing maximum distance for integer case

35 Views Asked by At

I am working with different facility location models giving its single (only one center help a demand zone) and multi-source models (multiple centers can help a demand zone).

My decision variables are $$ x_j = \begin{cases} 1 & \text{if a center is located in } j \in J \\ 0 & \text{otherwise} \end{cases} $$ and $$ y_{ij} = \begin{cases} 1 & \text{if demand zone } i \in I \text{ is assisted by center } j \in J \\ 0 & \text{otherwise} \end{cases} $$ for the single-source model.

For the multi-source one we have $y_{ij} \geq 0$ taking integer values and representing the number of people sent to demand zone $i\in I$ from center $j\in J$.

The single-source model is given by \begin{align} \min_{x,y} \quad & \max_{i,j} \{ d_{ij}y_{ij} \} \\ \text{s.a.: } \quad & \sum_j x_j = N \\ & \sum_j y_{ij} = 1, \: \forall i \\ & y_{ij} \leq x_j , \: \forall i, j \\ & x_j \in \{0,1\}, \: \forall i, j \\ & y_{ij} \in \{0,1\}, \: \forall i, j \end{align} So far I have been able to change all the restrictions for the multi-source model. \begin{align} \sum_j x_j = N \\ \sum_j y_{ij} = w_i, \quad \forall i \\ y_{ij} \leq q_jx_j , \quad \forall i, j \\ x_j \in \{0,1\}, \quad \forall i, j \\ y_{ij} \geq 0, \quad \forall i, j \end{align} where $w_i$ is the demand associated to each zone and $q_j$ is the capacity of each center.

However, I am stuck on modifying the objective function so that the distance is not counted several times when sending more than one person.

Could anyone help me? Thank you!

1

There are 1 best solutions below

0
On

First note that your capacity constraint $y_{ij}\le q_j x_j$ should instead be $\sum_i y_{ij}\le q_j x_j$ for all $j$.

Now to minimize the maximum distance, introduce constant $M_{ij}=\min(w_i,q_j)$ and binary variable $z_{ij}$, impose constraint $y_{ij}\le M_{ij} z_{ij}$, and minimize $\max_{i,j} \{d_{ij}z_{ij}\}$.