Topic
• 42 replies
• Latest Post - ‏2018-06-14T06:26:41Z by HongPhuc123
623 Posts

# Pinned topic VRP using CP

‏2013-01-22T07:56:36Z |
Hi, I'm Solving the VRP with OPL and I'd like to know, how can I use CP for solve the Vehicle Routing Problem and where can I get an example of the VRP with CP?
Thanks!
Updated on 2013-03-13T16:56:14Z at 2013-03-13T16:56:14Z by SystemAdmin
623 Posts

#### Re: VRP using CP

‏2013-03-13T16:56:14Z
thanks
• Delpho
3 Posts

#### Re: VRP using CP

‏2013-04-24T17:37:35Z
thanks

I 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!

• ChrisBr
59 Posts

#### Re: VRP using CP

‏2013-04-26T15: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.x-p1.x,2)+pow(p2.y-p1.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.

• Delpho
3 Posts

#### Re: VRP using CP

‏2013-05-04T09:43:06Z
• ChrisBr
• ‏2013-04-26T15: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.x-p1.x,2)+pow(p2.y-p1.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 :).

• ChrisBr
59 Posts

#### Re: VRP using CP

‏2013-05-14T14:23:15Z
• Delpho
• ‏2013-05-04T09: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.

• davidoff
51 Posts

#### Re: VRP using CP

‏2015-01-13T13:01:26Z
• Delpho
• ‏2013-05-04T09: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) ?

• ueve.fr-P.hD-Tong
1 Post

#### Re: VRP using CP

‏2015-11-17T15:42:39Z
• davidoff
• ‏2015-01-13T13: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?

Best regards

Tong

• GGR
90 Posts

#### Re: VRP using CP

‏2015-11-24T13:16:29Z

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

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-02-07T15:50:21Z
• ChrisBr
• ‏2013-04-26T15: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.x-p1.x,2)+pow(p2.y-p1.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)

thank you alot

( last (truck[t],tvisit[<1>][t]); // Truck t ends at depot

• ChrisBr
59 Posts

#### Re: VRP using CP

‏2017-02-14T16:03:58Z
• AMM1
• ‏2017-02-07T15: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)

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 interval-variable 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.

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-02-18T22:19:02Z
• ChrisBr
• ‏2017-02-14T16: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 interval-variable 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.

• AlexFleischer
260 Posts

#### Re: VRP using CP

‏2017-02-19T19:14:52Z
• AMM1
• ‏2017-02-18T22: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/cos-12-7-ai/

regards

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-02-22T09:39:14Z

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/cos-12-7-ai/

regards

good morning sir
​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.x-p1.x,2)+pow(p2.y-p1.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.

• AlexFleischer
260 Posts

#### Re: VRP using CP

‏2017-02-22T21:42:11Z
• AMM1
• ‏2017-02-22T09:39:14Z

good morning sir
​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.x-p1.x,2)+pow(p2.y-p1.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=5efb1db1-c642-4877-af60-b330f959a534&ps=25

2) You do as in

{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))))> | p1, p2 in Positions };

you scale and then you round

regards

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-02-25T21:55:12Z

Hi

1) You have an example of travel distance minimization at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=5efb1db1-c642-4877-af60-b330f959a534&ps=25

2) You do as in

{triplet} Dist = {
<p1.id,p2.id,ftoi(round(1000000*sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.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.x-p1.x,2)+pow(p2.y-p1.y,2))))> | p1, p2 in Positions };

so how to minimize the total distances traveled in my case ?!

Thank You .

• ChrisBr
59 Posts

#### Re: VRP using CP

‏2017-02-28T14: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.x-p1.x,2)+pow(p2.y-p1.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 2017-02-28T14:44:08Z at 2017-02-28T14:44:08Z by ChrisBr
• AMM1
44 Posts

#### Re: VRP using CP

‏2017-02-28T15:59:50Z
• ChrisBr
• ‏2017-02-28T14: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.x-p1.x,2)+pow(p2.y-p1.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. :)

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-03-05T20:58:23Z
• ChrisBr
• ‏2017-02-28T14: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.x-p1.x,2)+pow(p2.y-p1.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("    ") }

}

• AlexFleischer
260 Posts

#### Re: VRP using CP

‏2017-03-06T07:08:29Z
• AMM1
• ‏2017-03-05T20: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,

regards

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-03-19T09:45:17Z

Hi,

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.

• PhilippeLaborie
145 Posts

#### Re: VRP using CP

‏2017-03-20T12:12:45Z
• AMM1
• ‏2017-03-19T09: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

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-03-23T07:59:19Z

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 .

• PhilippeLaborie
145 Posts

#### Re: VRP using CP

‏2017-03-23T08:23:57Z
• AMM1
• ‏2017-03-23T07: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 use-case, you can look at mulprod.cpp.

• AMM1
44 Posts

#### Re: VRP using CP

‏2017-03-27T10:41:57Z

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 use-case, you can look at mulprod.cpp.

good morning sir,

i tried to compile and execute, mulprod.cpp i got an error

1*that generic.h : no such file or directory , how to fix it?

when i tried to remove it another error appeared iostream.h no such file or directory

2*also all of the libraries are coming from cplex folder , how to change them to cp ?

3* where can i find simple example of calling cp model and data file from ibm ilog using c++