Pinned topic VRP using CP
Thanks!


ACCEPTED ANSWER
Re: VRP using CP
20130424T17:37:35Z in response to SystemAdminI 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!


ACCEPTED ANSWER
Re: VRP using CP
20130426T15:22:54Z in response to SystemAdminHello 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.

ACCEPTED ANSWER
Re: VRP using CP
20130504T09:43:06Z in response to ChrisBrHello 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 :).

ACCEPTED ANSWER
Re: VRP using CP
20130514T14:23:15Z in response to DelphoHi 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.

ACCEPTED ANSWER
Re: VRP using CP
20150113T13:01:26Z in response to DelphoThe model is actually in OPL
Do you mean , in OPL using CPLEX (instead of CP) ?

