Modeling: How to force customers visit their NEAREST facility

Question

Let set $I$ denote the facility location set, $N$ denote the customer set, and $d_{ni}, \forall n\in N, i \in I $ is the distance between customer $n$ and facility $i$. The problem is to locate facilities in $I$ with binary decision variable $v_i$, and assign customer $n$ to the opened $i$ with binary variable $y_{ni}$.

Note that there are many other constraints that I had omitted, and the problem is much difficult than the classic facility location problem. The most tricky part is how to build an equation which forces customer to visit their nearest and opened facility. Without this constraint, customer may visit farther facility, which is not what I want.

Now, I provide a equation as follows, which is nonlinear but can be linearized.

$$ \sum_{i\in I} d_{ni} y_{ni} = \min \{ M(1-v_i) + d_{ni}v_i,\forall i \in I\} \quad \forall n \in N $$

where $M$ is a sufficient large constant.

My problem is: Could anyone suggest a better way to force customers visit their nearest opened facility? I think the above relationship is complex. How to simplify this or provide another method?

Answer 1

If the objective is to minimize total distance, this will happen naturally. But if you want to explicitly enforce it, you can impose a rule like $$\lnot(y_{ni} \land v_j) \quad \text{for all $n,i,j$ such that $d_{ni} > d_{nj}$}.$$ Rewriting in conjunctive normal form yields a conflict constraint: \begin{align} \lnot y_{ni} \lor \lnot v_j & &&\text{for all $n,i,j$ such that $d_{ni} > d_{nj}$}\\ (1-y_{ni})+(1-v_j) &\ge 1 &&\text{for all $n,i,j$ such that $d_{ni} > d_{nj}$}\\ y_{ni} + v_j &\le 1 &&\text{for all $n,i,j$ such that $d_{ni} > d_{nj}$}\tag1\label1 \end{align} Because $\sum_i y_{ni}\le 1$ for all $n$, you can then strengthen \eqref{1} by using the idea described in How can I strengthen a family of constraints in the presence of a clique constraint?: $$ \sum_{i: d_{ni} > d_{nj}} y_{ni} + v_j \le 1 \quad \text{for all $n$ and $j$}.$$

Answer 2

If you would like to assign the customers to the nearest facility, one way would be by adding a set-covering constraint to ensure the customers with the minimum distance from a facility are assigned to that.

Suppose $S$ is either the maximal acceptable service distance or time or covering radius, and the set $N_n \small = \{i | d_{ij} < S\}$ is to control the distance in contrast to the $S$. The following constraint should impose what you want:

$$ \sum_{i \in N_n} v_{i} \geq 1 \quad \forall \ n \in N$$

Answer 3

Another way is for all customers $n$ sort the distance in ascending order into a set $S_n =\{d_{ni}: d_{n,i} \le d_{n,i+1}\}$ basically indexed by the facility.
Then for each customer loop the below constraints through the set
$v_i \le \sum_{j \in S_n}^{i}y_{n,j} \ \ \forall i \in S_n \ \ \forall n$
with another constraint which may be there already
$ \sum_n y_{n,i} \le Mv_i \quad \forall i $
where $M$ is big number like capacity of the facility and
$\sum_i y_{n,i} = 1 \ \ \forall n$