Topic
  • 24 replies
  • Latest Post - ‏2017-03-27T10:41:57Z by AMM1
SystemAdmin
SystemAdmin
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
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: VRP using CP

    ‏2013-03-13T16:56:14Z  
    thanks
  • Delpho
    Delpho
    2 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
    ChrisBr
    51 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
    Delpho
    2 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
    ChrisBr
    51 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
    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
    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?

    thank you in advance!

     

    Best regards

    Tong

  • GGR
    GGR
    83 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:

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

    Hope that helps

     

     

     

  • AMM1
    AMM1
    14 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)

    please help me in solving this issue. 

    thank you alot 

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

     

  • ChrisBr
    ChrisBr
    51 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)

    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 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
    AMM1
    14 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
    AlexFleischer
    149 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
    AMM1
    14 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
    ​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.

  • AlexFleischer
    AlexFleischer
    149 Posts

    Re: VRP using CP

    ‏2017-02-22T21:42:11Z  
    • AMM1
    • ‏2017-02-22T09: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.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
    AMM1
    14 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
    ChrisBr
    51 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
    AMM1
    14 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
    AMM1
    14 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
    AlexFleischer
    149 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,

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

    regards

  • AMM1
    AMM1
    14 Posts

    Re: VRP using CP

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

     

  • PhilippeLaborie
    PhilippeLaborie
    87 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
    AMM1
    14 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
    PhilippeLaborie
    87 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
    AMM1
    14 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++