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? Like I am sure there is some trick
Thanks !
$\begingroup$
$\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$– SuneNov 18 at 11:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.