Originally posted by: AMM1

good morning 
i need your help in this issue 
i am solving vrpmtw using cp optimizer 
in my data set , i have the x and y coordinates for each client 
i have problem regarding Transition matrix used in NoOverlap function 
i calculate the distances using 
tuple triplet { int c1; int c2; int d; }; 
{triplet} Dist = { 
< p1.id,p2.id,ftoi(round(sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))))>; | p1, p2 in Positions }; 

i need to make Dist in real values not integers( double precision) and then use it in noOverlap(truck[t],Dist); 
how can convert it? 
tried to do some scaling but this scaling  slowed up The model, it  was solving problems within 1 hour and now itis not giving any solutions 
Is there another way to use double precision distances matrix with? 
or any alternatives of noOoverlap to use it in model (noOverlap(truck[t],Dist)) 
in order to use real distances matrix and get real not integer objective value

Originally posted by: Petr Vilím

Hello,

unfortunately scaling is the only possible option. Floating-point values are not supported in transition matrix (and start times of interval variables are also integers).

The model without scaling could be simpler than with scaling. E.g. distance 1.4 is truncated to 1 and that makes the problem simpler than scaling to 14. That could explain why there is suddenly no solution.

I would recommend to start with some small instances, ideally when you can find a solution by hand. And verify that the model can find that solution (or a better one).

It may also help to temporarily ignore deadlines in your time windows. You can change the objective to minimize violation of deadlines. Once you have a solution that satisfies all deadlines you can use it as starting point for your original problem (you can give CP Optimizer a known solution as starting point to start the search).

Another option is to make all interval variables optional and maximize the number of present intervals. Again, once all of them are present you have a valid solution that could be used as a starting point.

Good luck, Petr

Originally posted by: AMM1

good morning sir

thank you for your reply

actually, am solving a set of real benchmark instances  so the size of the problems for me is fixed I cant reduce it also the number of time windows are big

I am now searching for an alternative for the function  (noOverlap(truck[t],Dist)) 

how to model VRPMTW using another function that we can use real distances with ?

Hi,

if you are not ok with scaling then what you could do is use a MIP approach or if you stay with CPO you could mix noOverlap (and then you take floor of distance which is optimistic) and real distance.

Let me show you an example starting with https://www.ibm.com/developerworks/community/forums/html/topic?id=5efb1db1-c642-4877-af60-b330f959a534

.mod

using CP;
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;

 

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);

float dist3[i in 1..n+1][j in 1..n+1]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);

dvar interval itvs[1..n+1] size 1;

dvar sequence seq in all(i in 1..n+1) itvs[i];

dvar int s[1..n];
dvar int rank[1..n] in 1..n;

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
      <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};
           
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    allDifferent(rank);
    forall(i in 1..n) s[i]==startOf(itvs[i]);
    forall(i in 1..n-2) s[rank[i]]<=s[rank[i+1]];
    
    forall(i in 1..n-2) s[rank[i+1]]-s[rank[i]]>=dist3[rank[i],rank[i+1]];

    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);    // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
}
          
          
 int  x[<i,j> in Edges]=prev(seq,itvs[i],itvs[j])+prev(seq,itvs[j],itvs[i]);
 int  isPrevFromNPlus1[i in 1..n]=prev(seq,itvs[i],itvs[n+1]);
 int l=first({i | i in 1..n : isPrevFromNPlus1[i]==1});
 edge el=<1,l>;
 
 execute
 {
 isPrevFromNPlus1;
 x;
 x[el]=1;
 }
 
 // Let us check here that the constraints of the IP model are ok
 assert forall (j in Cities)
        as:sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
        
// Let us compute here the objective the IP way
int cost=sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];

execute
{
writeln(cost);
}    

.dat

n = 17;
dist = [
633
257
91
412
150
80
134
259
505
353
324
70
211
268
246
121
390
661
227
488
572
530
555
289
282
638
567
466
420
745
518
228
169
112
196
154
372
262
110
437
191
74
53
472
142
383
120
77
105
175
476
324
240
27
182
239
237
84
267
351
309
338
196
61
421
346
243
199
528
297
63
34
264
360
208
329
83
105
123
364
35
29
232
444
292
297
47
150
207
332
29
249
402
250
314
68
108
165
349
36
495
352
95
189
326
383
202
236
154
578
439
336
240
685
390
435
287
184
140
542
238
254
391
448
157
301
145
202
289
55
57
426
96
483
153
336
];

dist3 is the distance that could be float

regards

Originally posted by: AMM1

good morning mr alex

Thank you for your help

but I still couldn't apply it 

whats the need for dist2 and dist3 in this model since dist is given in the data set ( .dat) ?

how to apply this idea if the distances are calculated in the .mod file not given in the .dat?

Hi,

I tried to show you how to manage if the distances were float instead of int.

At

https://www.ibm.com/developerworks/community/forums/html/topic?id=a03f60c3-0b5b-48f8-b622-c44944028363&ps=25

I wrote an example on how scaling can help TSP work with float distances

regards