0
$\begingroup$

enter image description here

This is a CVRP problem and I have difficulty understanding the constraints in the red box.

For the sub-eliminator constraint (MTZ), my question is how can we make it on our own? I am sure there is some trick.

$\endgroup$
1
  • 2
    $\begingroup$ What do you mean by “ how can we make it on our own”? Do you mean “how do we implement them in a modelling language” or what is meant by the statement? $\endgroup$
    – Sune
    Nov 18, 2023 at 11:26

1 Answer 1

2
$\begingroup$

The MTZ constraints are big-M constraints that enforce the logical implication $$x_{ij}=1\implies u_j\ge u_i+d_j.$$ That is, if you traverse arc $(i,j)$, the cumulative demand at $j$ is at least the cumulative demand at $i$ plus the demand at $j$. The basic form is $$u_i+d_j-u_j\le M_{ij}(1-x_{ij}).$$ To find a good value for $M_{ij} $, you want an upper bound on the LHS when $x_{ij}=0$. Adding the bounds $u_i\le C$ and $-u_j\le -d_j$ yields $$u_i+d_j-u_j\le C+d_j-d_j=C,$$ so take $M_{ij}=C$.

$\endgroup$

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.