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) ?

Re: VRP using CP
20151117T15:42:39ZThis is the accepted answer. This is the accepted answer. davidoff
 20150113T13:01:26Z
The model is actually in OPL
Do you mean , in OPL using CPLEX (instead of CP) ?
HI dear all,
Does anyone has the code of VRP in OPL?
I encounter some difficulties in coding the constraints in the picture, I appreciated a lot that any one can give me some code example or suggestions on coding the vehicle routing subtour elimination constraints in OPL language?
thank you in advance!
Best regards
Tong
Attachments

 IMG_20151117_163538.jpg
 2.7 MB
 Download

Re: VRP using CP
20151124T13:16:29ZThis is the accepted answer. This is the accepted answer.Hi
You can find a vrp model using CP Optimizer interval variable algebra sooner in this thread (ChrisBr Apr 26, 2013).
There is no need to tell any other tour related constraints. In a solution each visit belongs to one non overlapping sequence and is so forth visited once and only once as it
Please refer to the concept pages of the documentation of CP Optimizer for any information:
Hope that helps