Pinned topic VRP using CP
Thanks!

Re: VRP using CP
20130424T17:37:35ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130313T16:56:14Z
thanksI am trying that too, I think I am close to the solution, but I have problems with the load of the trucks. Does anyone have any example?
Thanks!

Re: VRP using CP
20130426T15:22:54ZThis is the accepted answer. This is the accepted answer.Hello Ivan,
Here is an example:
using CP;
tuple Position {
key int id;
int x;
int y;
};
tuple Demand {
key int id;
int q;
};
int n = ...;
int m = 4; // Number of trucks
int K = ...;
{Position} Positions = ...;
{Demand} Demands = ...;
{int} Customers = { p.id  p in Positions };
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions };
execute {
writeln(Dist);
};
dvar interval visit [d in Demands] size 1;
dvar interval tvisit[d in Demands][t in 1..m] optional(d.id>1) size 1;
dvar sequence truck[t in 1..m] in all(d in Demands) tvisit[d][t] types all(d in Demands) d.id;
execute {
cp.param.TimeMode = "ElapsedTime";
cp.param.TimeLimit = 60;
// On this type of problem, search phase on sequence variable may help
// var f = cp.factory;
// cp.setSearchPhases(f.searchPhase(truck));
}
minimize sum(t in 1..m) endOf(tvisit[<1>][t]);
constraints {
forall(t in 1..m) {
noOverlap(truck[t], Dist); // Travel time
first(truck[t],tvisit[<0>][t]); // Truck t starts at depot
last (truck[t],tvisit[<1>][t]); // Truck t ends at depot
sum(d in Demands) presenceOf(tvisit[d][t])*d.q <= K; // Truck capacity
}
forall(d in Demands: d.id>1) {
alternative(visit[d], all(t in 1..m) tvisit[d][t]); // Truck selection
}
}
I hope this helps,
Chris.

Re: VRP using CP
20130504T09:43:06ZThis is the accepted answer. This is the accepted answer. ChrisBr
 20130426T15:22:54Z
Hello Ivan,
Here is an example:
using CP;
tuple Position {
key int id;
int x;
int y;
};
tuple Demand {
key int id;
int q;
};
int n = ...;
int m = 4; // Number of trucks
int K = ...;
{Position} Positions = ...;
{Demand} Demands = ...;
{int} Customers = { p.id  p in Positions };
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions };
execute {
writeln(Dist);
};
dvar interval visit [d in Demands] size 1;
dvar interval tvisit[d in Demands][t in 1..m] optional(d.id>1) size 1;
dvar sequence truck[t in 1..m] in all(d in Demands) tvisit[d][t] types all(d in Demands) d.id;
execute {
cp.param.TimeMode = "ElapsedTime";
cp.param.TimeLimit = 60;
// On this type of problem, search phase on sequence variable may help
// var f = cp.factory;
// cp.setSearchPhases(f.searchPhase(truck));
}
minimize sum(t in 1..m) endOf(tvisit[<1>][t]);
constraints {
forall(t in 1..m) {
noOverlap(truck[t], Dist); // Travel time
first(truck[t],tvisit[<0>][t]); // Truck t starts at depot
last (truck[t],tvisit[<1>][t]); // Truck t ends at depot
sum(d in Demands) presenceOf(tvisit[d][t])*d.q <= K; // Truck capacity
}
forall(d in Demands: d.id>1) {
alternative(visit[d], all(t in 1..m) tvisit[d][t]); // Truck selection
}
}
I hope this helps,
Chris.
Hello Chris,
This is great and helps a lot.
I am trying to do the VRP model with OPL, but I think I can borrow good ideas from this.
In my model I use distance, instead of coordenates, I think is faster in that way. Have you got a VRP model in OPL? I will post mine when it finally runs ok, but is always good to have a lot of different models for testing which is better :).

Re: VRP using CP
20130514T14:23:15ZThis is the accepted answer. This is the accepted answer. Delpho
 20130504T09:43:06Z
Hello Chris,
This is great and helps a lot.
I am trying to do the VRP model with OPL, but I think I can borrow good ideas from this.
In my model I use distance, instead of coordenates, I think is faster in that way. Have you got a VRP model in OPL? I will post mine when it finally runs ok, but is always good to have a lot of different models for testing which is better :).
Hi Ivan,
For sure using a true distance matrix is more accurate.
In this simple VRP model, the distance matrix is computed with the aim of keeping the OPL code easily understanding.
Regards,
Chris.

Re: VRP using CP
20150113T13:01:26ZThis is the accepted answer. This is the accepted answer. Delpho
 20130504T09:43:06Z
Hello Chris,
This is great and helps a lot.
I am trying to do the VRP model with OPL, but I think I can borrow good ideas from this.
In my model I use distance, instead of coordenates, I think is faster in that way. Have you got a VRP model in OPL? I will post mine when it finally runs ok, but is always good to have a lot of different models for testing which is better :).
The model is actually in OPL
Do you mean , in OPL using CPLEX (instead of CP) ?