Originally posted by: SystemAdmin

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!
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

thanks
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Delpho

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!

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

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.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Delpho

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 :).

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

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.
 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: davidoff

The model is actually in OPL

Do you mean , in OPL using CPLEX (instead of CP) ?

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ueve.fr-P.hD-Tong

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

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Rafaf

Hi Delpho,
Could you end the code in OPL, could you share it? I'm working on something similar.

Thank you,

#DecisionOptimization
#OPLusingCPOptimizer

Hi,

in the meantime,

https://www.ibm.com/developerworks/community/forums/html/topic?id=381774eb-d9d1-4c4a-86d1-f28259173c29&ps=25

could help

regards

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Delpho

Hi Rafa,

 

sorry but I didn't work again with OLP (neither I completed the project).

 

Good luck!!

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

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.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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.

#DecisionOptimization
#OPLusingCPOptimizer

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

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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

#DecisionOptimization
#OPLusingCPOptimizer

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

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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 .

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Xifeng

Hi Chris,

The classic VRP often has one depot and a set of customers. If it is extended to a multi-depot version, whilst each depot has a capacity limit, how to solve it using CPLEX?

Regards,

Xifeng

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

multi-depot is of course more complicated. The capacity usage of a truck must be computed using cumulative expression (that is, we have to compute capacity usage over time, not just total capacity usage).

So instead of the constraint:

    sum(d in Demands) presenceOf(tvisit[d][t])*d.q <= K; // Truck capacity
there will be cumulative function that is composed from stepAtStart (or stepAtEnd) each time the truck visit a depot (then the function is increased) or a customer (then is dereased). The cumul function could be also constrained not to overflow the maximum capacity of the truck. For more information about cumul functions see topic "Cumul functions in CP Optimizer" in section "Concepts" in the manual: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.1/ilog.odms.ide.help/refcppopl/html/cumul_functions.html

Best regards, Petr Vilím

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Xifeng

Hello Petr,

Thank you very much! I will try it according to your guidance. If there is any problem, I will ask you.

Sincerely,

Xifeng

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: HongPhuc123

Hi Petr Vilim,

Currently, I am working with a thesis project related to multi depot VRP and intend to solve by CP optimizer. Can we model the problem of multi objectives ( distance and number of vehicles) in CP. In addition, I don't understand clearly the constraint of multi depot above, can you explain more detailed?

Thanks and best regards,

Phuc Nguyen. 

#DecisionOptimization
#OPLusingCPOptimizer

Hi,

for multi objective, you may use staticLex

For example, if you need to first minimize the number of trucks and then the travel time you could write

minimize staticLex(nbUsed,travelTime);

regards

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: HongPhuc123

I got it. Thank you so much. But I still have one concern about multi depot using CP optimizers. Could you please help me get out this. I really appriciate for help.

thanks and best regard

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: HongPhuc123

Hi Petr Vilim,

Currently, I am working with a thesis project related to multi-depot VRP and intend to solve by CP optimize. Can we model the problem of multi-objectives ( distance and number of vehicles) in CP. In addition, I don't understand clearly the constraint of multi-depot above, can you explain more detailed?

Thanks and best regards,

Phuc Nguyen. 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

CP Optimizer supports multiple objectives in lexicographic order (i.e. one objective is always more important then the second objective). See for example:

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.ide.help/OPL_Studio/opllang_quickref/topics/tlr_oplf_staticLex.html

Alternatively you can assign each objective a weight and combine them as a sum.

Regarding the cumulative function, you can also have a look on example sched_cumul that is part of CP Optimizer distribution (there are multiple versions of this example for different programming languages, e.g. sched_cumul.mod in OPL). In this example there is "cash" that changes over time. Certain actions increase cash, some decrease cash. The cash can never go below zero. It is similar to truck capacity in VRP: some actions increase the load of the truck, some decrease it. The load can never exceed the capacity of the truck.

 

Best regards, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Zefeng

Hello Chris

How can I get access to the id of each interval in the the sequence truck[t]?

I mean, truck[t] consists of the intervals tvisit[d][t], I want to get access to the d.id of each interval.

This is important if I want to output the solution to a file, the solution should be the routes, represented by the id of each customer in the routes. 

#DecisionOptimization
#OPLusingCPOptimizer

Hi,

could

using CP;

range R = 1..3;

dvar interval tia[i in R] size i;
dvar sequence seq in tia;

subject to {
  noOverlap(seq);

  before(seq, tia[2], tia[3]);
  prev(seq, tia[1], tia[3]);
}

execute {
  writeln(seq);
  writeln(seq.first() );
  writeln(seq.next(seq.first() ) );
  writeln(seq.last() );

  writeln("loop");
  var s=seq.first();
  for(var i in R)
  {
   writeln(s);
   s=seq.next(s) ;
  }
  writeln(s);
}

help ?

This shows you a way to iterate over a sequence

regards

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: imarkov

This is probably not the correct channel, given that the topic is OPL, but I am trying to model the VRP using the Java API. Can anyone help me with that? Thanks.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

Hello,

From one hand (modeling concepts), you have the OPL model sent by Chris, so it should be easy to understand its main principles. A similar formulation is explained in this recent article:  http://ibm.biz/Constraints2018. You can also have a look at the formal definition of the different concepts in the documentation: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cpo.help/refcppcpoptimizer/html/introduction.html

 

From the other hand (Java), if you need concrete examples of Java models, you can have a look at the ones distributed with CPO in CPLEX_StudioXXX/cpoptimizer/examples/src/java/ (for example SchedSetup.java but several others may be of interest too). Most of these examples are also available in an OPL version (CPLEX_StudioXXX/opl/examples/opl/) so you can compare the two formulations.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: imarkov

Thanks, I've been able to remodel it in Java.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

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:

http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cpo.help/refcppcpoptimizer/html/interval_sequence.html

Hope that helps

 

 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

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.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

THANK YOU this was very helpful it worked with me. :)

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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("    ") }
   
  
  }  

#DecisionOptimization
#OPLusingCPOptimizer

Hi,

you could have a look at https://www.ibm.com/developerworks/community/forums/html/threadTopic?id=77777777-0000-0000-0000-000014678056&ps=25

regards

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

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

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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 .

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

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.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AMM1

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++ 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Xifeng

Hi Chris,

If the VRP is with multi-depot and each of which has a capacity limit, how to solve it? I appreciate your time and look forward to your answer!

Best regard

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

Hello Xifeng,

Could you be more precise about what you want to model please?

Regards,

Chris.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Dear Chris,
I saw your posting just now. I know how to calculate the traveling distance ^^

dexpr float truckDistance[t in 1..m] =  sum(d in Demands) distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)];

 

I have a related question. Now, I need to keep track of the traveling distance by using the cumulFunction, something like below.
cumulFunction cumDistance[t in 1..m] = sum(d in Demands) stepAtStart (tvisit[d][t], distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)])
However, I got a syntax error. 
Would you please help me how to conform to OPL syntax in this situation?

Regards,
Andy

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

Hello Andy,

First question is if you really need such a cumul function measuring the travelled distance over time. What do you need it for?

Then if you really need that, there are two options:
- either you use a stepAtStart(tvisit[d][t], 0, M) with a range [0,M] and post a constraint stating that the height of this range is the traveled distance: something like heightAtStart(tvisit[d][t],cumDistance[t])==distMatrixById[d.id][typeOfNext(truck[t], tvisit[d][t], d.id, d.id)

- or you use additional integer variables to track the traveled distance before each visit, using similar ideas as for instance what is suggested in this post (in a slighty  different context): https://www.ibm.com/developerworks/community/forums/html/topic?id=fb1ed8ca-c263-46af-b589-133b6c68faff&ps=25

 

Philippe

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

The CP code would look like the following. However, there are several errors:
(1) we cannot use sizeOf(a) as h in stepAtEnd(a, h)

(2) heightAtEnd should be determined by collectively considering two different activities (itvJ2T and itvR2T: one for energy consumption and the other for recharging)

============================================

If you can suggest the solution for me, I will be very thankful ^^

Andy

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

As said, stepAtEnd only accepts a range, not a decision variable or an expression like sizeOf(interval). For size, you need to do exactely the same as for the traveled distance: use heightAtEnd. so it would give something like:
 

cumulFunction cumBattery[t in Trucks]=  step(0, 100)  // initial battery level
    - sum(j in Jobs) stepAtEnd (itvJ2T[j,t], 0,3600)  //energy consumption
    + sum(r in Jobs) stepAtEnd (itvR2T[r][t], 0,???); //energy recharging

forall(j in Jobs,t in Trucks)
  heightAtEnd(itvJ2T[j][t],cumBattery[t]) == ConsumptionRate* DistMatrixById[j.id][typeOfNext(seqTrk[t], itvJ2T[j][t], j.id, j.id)];

forall(...)
  heightAtEnd(itvR2T[r][t],cumBattery[t]) == ChargingRate*sizeOf(itvR2T[r][t]);
  
 

 

#DecisionOptimization
#OPLusingCPOptimizer