# Modeling: How to force customers visit their NEAREST facility

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?

• Are you assuming that facilities have unlimited capacity (so that a customer can be assigned to the nearest open facility regardless of how many other customers are assigned to that facility)?
– prubin
Aug 16 at 3:08

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}.$$

• It seems that this has resolved my concerns, and I will carefully consider the principles behind it. Thank you for your assistance, it has been really helpful. I am amazed by the clever modeling technique, particularly the indexing of $i$ in the summation symbol. It's truly fantastic. By the way, could you please advise me on how to systematically improve my modeling skills? Aug 16 at 2:26
• Glad to help. A good resource is Model Building in Mathematical Programming by H. Paul Williams. Aug 16 at 3:28

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$$

• This is not sufficient. For example, taking $v_i=1$ for all $i$ would satisfy these constraints, but the customer assignments $y_{ni}$ could then be arbitrary. Aug 15 at 22:29
• Dear @RobPratt, thanks. This constraint is only to deploy a facility based on the nearest distance and w.r.t the predefined covering radius. The rest can still be added based on the whole problem definition. Aug 16 at 4:49

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$$

• True, updated it Aug 18 at 1:59