2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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)? $\endgroup$
    – prubin
    Aug 16, 2023 at 3:08

3 Answers 3

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Runfeng Yu
    Aug 16, 2023 at 2:26
  • $\begingroup$ Glad to help. A good resource is Model Building in Mathematical Programming by H. Paul Williams. $\endgroup$
    – RobPratt
    Aug 16, 2023 at 3:28
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Aug 15, 2023 at 22:29
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Aug 16, 2023 at 4:49
1
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ True, updated it $\endgroup$ Aug 18, 2023 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.