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

Re: VRP using CP
20170207T15:50:21ZThis 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.
good evening sir
iam trying to solve VRPMTW using cp optimizer , i have problem in starting and ending each route on the depot,
here in this example code , tvisit [<1>],[t] it ensures that it will end at costumer 1 not the depot
when i put it , tvisit [<0>],[t] the code doesn't work at all
also what is the objective function for VRPMTW (vehicle routing problem with multiple time windows)
please help me in solving this issue.
thank you alot
( last (truck[t],tvisit[<1>][t]); // Truck t ends at depot

Re: VRP using CP
20170214T16:03:58ZThis is the accepted answer. This is the accepted answer. AMM1
 20170207T15:50:21Z
good evening sir
iam trying to solve VRPMTW using cp optimizer , i have problem in starting and ending each route on the depot,
here in this example code , tvisit [<1>],[t] it ensures that it will end at costumer 1 not the depot
when i put it , tvisit [<0>],[t] the code doesn't work at all
also what is the objective function for VRPMTW (vehicle routing problem with multiple time windows)
please help me in solving this issue.
thank you alot
( last (truck[t],tvisit[<1>][t]); // Truck t ends at depot
Hello Amal,
In this example, tvisit[...] doesn't represent a "visit' in a place, but an activity. And the sequence doesn't represent a "route" but an "ordered list of activities".
From this point of view, "starts at depot" and "ends at depot" are 2 different activities. And "last(truck[t],tvisit[<1>][t])" really means "ends at depot".
It is not possible to constrain an intervalvariable to be both first and last in a sequence except if it is the only one in this sequence (useless case actually).I hope this clarifies,
Chris.

Re: VRP using CP
20170218T22:19:02ZThis is the accepted answer. This is the accepted answer. ChrisBr
 20170214T16:03:58Z
Hello Amal,
In this example, tvisit[...] doesn't represent a "visit' in a place, but an activity. And the sequence doesn't represent a "route" but an "ordered list of activities".
From this point of view, "starts at depot" and "ends at depot" are 2 different activities. And "last(truck[t],tvisit[<1>][t])" really means "ends at depot".
It is not possible to constrain an intervalvariable to be both first and last in a sequence except if it is the only one in this sequence (useless case actually).I hope this clarifies,
Chris.
hi,
thank you for replying really appreciate it ,
i need your help in making my code.
i am try to model VRPMTW , the code is working for only 20 clients , if i put 100 clients i get an error :CP Optimizer solves problems with a search space up to 2^1000
i have licensed version of IBM ILOG 12.7 community version
should i simplify the code ? or the problem in the program it self.

Re: VRP using CP
20170219T19:14:52ZThis is the accepted answer. This is the accepted answer. AMM1
 20170218T22:19:02Z
hi,
thank you for replying really appreciate it ,
i need your help in making my code.
i am try to model VRPMTW , the code is working for only 20 clients , if i put 100 clients i get an error :CP Optimizer solves problems with a search space up to 2^1000
i have licensed version of IBM ILOG 12.7 community version
should i simplify the code ? or the problem in the program it self.
Hi,
you get this error because the community edition is limited.
You should try to get a full version at https://developer.ibm.com/docloud/blog/2016/11/24/cos127ai/
regards

Re: VRP using CP
20170222T09:39:14ZThis is the accepted answer. This is the accepted answer. AlexFleischer
 20170219T19:14:52Z
Hi,
you get this error because the community edition is limited.
You should try to get a full version at https://developer.ibm.com/docloud/blog/2016/11/24/cos127ai/
regards
good morning sir
Thank you for replying, the problem is solved i downloaded new version of IBM ILOG.
I HAVE question regarding :
i used :
tuple distance { int c1; int c2; int dista; }; {distance} Dist = { <p1.id,p2.id,ftoi(round(sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions } to calculate the distances between clients .
1: my objective is to minimize the total traveled distances how to write it?
2: also i need these distances to be float , if i do that the noOverlap constraint shows an error , how to solve this issue.?
thank you. 
Re: VRP using CP
20170222T21:42:11ZThis is the accepted answer. This is the accepted answer. AMM1
 20170222T09:39:14Z
good morning sir
Thank you for replying, the problem is solved i downloaded new version of IBM ILOG.
I HAVE question regarding :
i used :
tuple distance { int c1; int c2; int dista; }; {distance} Dist = { <p1.id,p2.id,ftoi(round(sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions } to calculate the distances between clients .
1: my objective is to minimize the total traveled distances how to write it?
2: also i need these distances to be float , if i do that the noOverlap constraint shows an error , how to solve this issue.?
thank you.Hi
1) You have an example of travel distance minimization at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=5efb1db1c6424877af60b330f959a534&ps=25
2) You do as in
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions };you scale and then you round
regards

Re: VRP using CP
20170225T21:55:12ZThis is the accepted answer. This is the accepted answer. AlexFleischer
 20170222T21:42:11Z
Hi
1) You have an example of travel distance minimization at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=5efb1db1c6424877af60b330f959a534&ps=25
2) You do as in
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions };you scale and then you round
regards
THANK you Alix for helping me,
but i still have problem in writing the objective function
how to minimize total distance traveled while distances between clients are not given direct in the data file like the example you mentioned to me .
In my case , Distances are calculated by the code it self using this :
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))))>  p1, p2 in Positions };so how to minimize the total distances traveled in my case ?!
Thank You .

Re: VRP using CP
20170228T14:20:48ZThis is the accepted answer. This is the accepted answer.Hello Amal,
The general way to model such distance minimization is to use typeOfNext feature.
We can start from the above model with few changes.First, in addition of a set of tuples (needed for the noOverlap constraint), we need a distance matrix:
int distMatrix[p1 in Positions][p2 in Positions] = ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))));and this matrix must be indexed by the types used in the sequence variable:
int distMatrixById[p1 in Customers][p2 in Customers] = distMatrix[<p1>][<p2>];
Then we can define the expression of the travel distance of a truck:
dexpr float truckDistance[t in 1..m] =
sum(d in Demands) distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)];
note that if tvisit[d][t] is absent  the delivery d is not performed by the truck t  the expression will return d.id, then the distance will be null (distMatrixById[k][k]==0).and the total distances traveled:
dexpr float totalDistance = sum(t in 1..m) truckDistance[t];Then you can define your objective as:
minimize totalDistance;I hope this helps,
Chris.
Updated on 20170228T14:44:08Z at 20170228T14:44:08Z by ChrisBr 
Re: VRP using CP
20170228T15:59:50ZThis is the accepted answer. This is the accepted answer. ChrisBr
 20170228T14:20:48Z
Hello Amal,
The general way to model such distance minimization is to use typeOfNext feature.
We can start from the above model with few changes.First, in addition of a set of tuples (needed for the noOverlap constraint), we need a distance matrix:
int distMatrix[p1 in Positions][p2 in Positions] = ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))));and this matrix must be indexed by the types used in the sequence variable:
int distMatrixById[p1 in Customers][p2 in Customers] = distMatrix[<p1>][<p2>];
Then we can define the expression of the travel distance of a truck:
dexpr float truckDistance[t in 1..m] =
sum(d in Demands) distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)];
note that if tvisit[d][t] is absent  the delivery d is not performed by the truck t  the expression will return d.id, then the distance will be null (distMatrixById[k][k]==0).and the total distances traveled:
dexpr float totalDistance = sum(t in 1..m) truckDistance[t];Then you can define your objective as:
minimize totalDistance;I hope this helps,
Chris.
THANK YOU this was very helpful it worked with me. :)

Re: VRP using CP
20170305T20:58:23ZThis is the accepted answer. This is the accepted answer. ChrisBr
 20170228T14:20:48Z
Hello Amal,
The general way to model such distance minimization is to use typeOfNext feature.
We can start from the above model with few changes.First, in addition of a set of tuples (needed for the noOverlap constraint), we need a distance matrix:
int distMatrix[p1 in Positions][p2 in Positions] = ftoi(round(1000000*sqrt(pow(p2.xp1.x,2)+pow(p2.yp1.y,2))));and this matrix must be indexed by the types used in the sequence variable:
int distMatrixById[p1 in Customers][p2 in Customers] = distMatrix[<p1>][<p2>];
Then we can define the expression of the travel distance of a truck:
dexpr float truckDistance[t in 1..m] =
sum(d in Demands) distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)];
note that if tvisit[d][t] is absent  the delivery d is not performed by the truck t  the expression will return d.id, then the distance will be null (distMatrixById[k][k]==0).and the total distances traveled:
dexpr float totalDistance = sum(t in 1..m) truckDistance[t];Then you can define your objective as:
minimize totalDistance;I hope this helps,
Chris.
good morning
i want to ask you how can i run more than one .dat file at the same time
i am using cp to solve vrpmtw and i have 48 problems to solve within 1 hr. (time limit ) so how can i run all of them at the same time and get solution for them separately.
my execute is
execute {
for (var o = 1; o <= m; o++) {
write("vehicle"+ " "+ o+ truck[o]);
write(" ") }
} 
Re: VRP using CP
20170306T07:08:29ZThis is the accepted answer. This is the accepted answer. AMM1
 20170305T20:58:23Z
good morning
i want to ask you how can i run more than one .dat file at the same time
i am using cp to solve vrpmtw and i have 48 problems to solve within 1 hr. (time limit ) so how can i run all of them at the same time and get solution for them separately.
my execute is
execute {
for (var o = 1; o <= m; o++) {
write("vehicle"+ " "+ o+ truck[o]);
write(" ") }
}Hi,
you could have a look at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=77777777000000000000000014678056&ps=25
regards

Re: VRP using CP
20170319T09:45:17ZThis is the accepted answer. This is the accepted answer. AlexFleischer
 20170306T07:08:29Z
Hi,
you could have a look at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=77777777000000000000000014678056&ps=25
regards
hi alix,
i want to call my( ibm ilog using cp) model and data file using c++ code in order to run it as a part of my FORTRAN code.
how can i do this?
regards.

Re: VRP using CP
20170320T12:12:45ZThis is the accepted answer. This is the accepted answer. AMM1
 20170319T09:45:17Z
hi alix,
i want to call my( ibm ilog using cp) model and data file using c++ code in order to run it as a part of my FORTRAN code.
how can i do this?
regards.
Hello,
For using the C++ interface of OPL, you can have a look at the carseq.cpp example in your delivery of CPLEX Optimization Studio, you will find it in:
CPLEX_STUDIO_DIR/opl/examples/opl_interfaces/cpp/src/carseq.cpp
Philippe

Re: VRP using CP
20170323T07:59:19ZThis is the accepted answer. This is the accepted answer. PhilippeLaborie
 20170320T12:12:45Z
Hello,
For using the C++ interface of OPL, you can have a look at the carseq.cpp example in your delivery of CPLEX Optimization Studio, you will find it in:
CPLEX_STUDIO_DIR/opl/examples/opl_interfaces/cpp/src/carseq.cpp
Philippe
Thank you for helping me , i checked the example you mentioned
the example is modeling the cp model using c++
but i just want a c++ code that calls the cp model and data file and just run them in IBM ILOG it self .

Re: VRP using CP
20170323T08:23:57ZThis is the accepted answer. This is the accepted answer. AMM1
 20170323T07:59:19Z
Thank you for helping me , i checked the example you mentioned
the example is modeling the cp model using c++
but i just want a c++ code that calls the cp model and data file and just run them in IBM ILOG it self .
In the same directory, you have other examples of using OPL models and data files in C++. Well, it is mostly for CPLEX but you can mostly replace IloCplex by IloCP. For a simple usecase, you can look at mulprod.cpp.