5
$\begingroup$

I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable:

dvar float+ w[N][D]; // violation time for late arrivals for every node and every day

These dvars are working, but now I want to make a link with the violation costs decision variables, which are:

dvar boolean a1[N][D];// no violation 
dvar boolean a2[N][D];// soft violation of 0-5 minutes
dvar boolean a3[N][D];// soft violation of 6-10 minutes
dvar boolean a4[N][D];// soft violation of 11 -15 minutes 
dvar boolean a5[N][D];// soft violation of 15+ minutes

I want to force:

a1[N][D] to be 1, when w[N][D] <=0, 0 otherwise
a2[N][D] to be 1, when w[N][D] >0 & <=5, 0 otherwise
a3[N][D] to be 1, when w[N][D] >5 & <=10, 0 otherwise
a4[N][D] to be 1, when w[N][D] >10 & <=15, 0 otherwise
a5[N][D] to be 1, when w[N][D] >=16, 0 otherwise

Then I have:

  forall(i in N, d in D)
  (a1[i][d] + a2[i][d] + a3[i][d] + a4[i][d] + a5[i][d]) == 1;

There is still something wrong with these constraints though.

forall(i in N, d in D)
  (a1[i][d] + a2[i][d] + a3[i][d] + a4[i][d] + a5[i][d]) == 1; //sum of all a's = 1

forall(i in N, d in D)
  w[n][d]<= (5*a2[i][d]) + 1000*(1-a2[i][d]); // a2 == 1 when w[n][d]>0 & <=5

forall(i in N, d in D)
  (6*a3[i][d] - 1000*(a3[i][d]-1))<= w[i][d]; // a3

forall(i in N, d in D)
   w[i][d] <= (10*a3[i][d]) + 1000*(1-a3[i][d]); // a3

forall(i in N, d in D)
  (11*a4[i][d] - 1000*(a4[i][d]-1))<= w[i][d]; //a4

forall(i in N, d in D)
   w[i][d] <= (15*a4[i][d]) + 1000*(1-a4[i][d]); // a4

forall(i in N, d in D)
  (16*a5[i][d] - 1000*(a5[i][d]-1))<= w[i][d]; //a5

it sets a5==1 for all constraints.

Furthermore, w is used in the model as:

forall (i in N, d in D:q[i][d]>=1)
y[i][d] - w[i][d] <= sl[i][d]; // late arrival time soft

where y[i][d] is the arrival time variable and sl the soft time window

$\endgroup$
6
$\begingroup$

Here's a stronger formulation that uses the same variables and fewer constraints, assuming $L \le w_{i,d} \le U$: \begin{align} \sum_{k=1}^5 a_{k,i,d} &= 1 &&\text{for all $i$ and $d$}\\ L a_{1,i,d} + 1 a_{2,i,d} + 6 a_{3,i,d} + 11 a_{4,i,d} + 16 a_{5,i,d} &\le w_{i,d} &&\text{for all $i$ and $d$}\\ 0 a_{1,i,d} + 5 a_{2,i,d} + 10 a_{3,i,d} + 15 a_{4,i,d} + U a_{5,i,d} &\ge w_{i,d} &&\text{for all $i$ and $d$} \end{align}

$\endgroup$
3
$\begingroup$

You can impose $$ a_{nd} + b_{nd} + f_{nd} + g_{nd} =1 $$ And link these variables with $\omega_{nd}$ as follows :

\begin{align*} &\omega_{nd} \le 5 a_{nd} +M(1-a_{nd})\\ 6 b_{nd} - M(1-b_{nd}) \le & \; \omega_{nd} \le 10 b_{nd} +M(1-b_{nd})\\ 11 f_{nd} - M(1-f_{nd}) \le & \; \omega_{nd} \le 15 f_{nd} +M(1-f_{nd}) \\ 16 g_{nd} - M(1-g_{nd}) \le & \; \omega_{nd} \\ \end{align*}

For example, if $\omega_{nd}=1$, only the first constraint will be active with $a_{nd} = 1$.

If $\omega_{nd}=7$, only the second one will be active with $b_{nd} = 1$, and so forth.

$\endgroup$
  • $\begingroup$ Thanks for your help! I added an extra boolean for the case of w[i][d] == 0. Then I imposed: a1 + a2 + a3 + a4 + a5 == 1 (see changed question). $\endgroup$ – Jeroen May 8 '20 at 11:21
  • $\begingroup$ It is still not working, I wonder what is wrong with the code posted above. $\endgroup$ – Jeroen May 8 '20 at 11:36
  • $\begingroup$ Can you show what is not working ? (what constraint/cost is not properly enforced for example) $\endgroup$ – Kuifje May 8 '20 at 11:37
  • $\begingroup$ It sets a1 == 1 for all nodes and all days and it changes my w[i][d] to my big M value (1000) $\endgroup$ – Jeroen May 8 '20 at 11:39
  • $\begingroup$ Are you sure you have constraints that activate the violation time correctly ? if the violation time takes value $1000$ maybe it is not well defined. $\endgroup$ – Kuifje May 8 '20 at 11:55
1
$\begingroup$

You could use logical constraints instead of big M with hard coded 1000

range N=1..2;
range D=1..3;

dvar boolean a1[N][D];
dvar int w[N][D] in -10..10;

subject to
{
// a1[N][D] to be 1, when w[N][D] <=0, 0 otherwise
forall(n in N,d in D) a1[n][d]==(w[n][n] <=0);
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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