Topic
  • 8 replies
  • Latest Post - ‏2015-11-24T13:16:29Z by GGR
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
    48 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
    48 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
    82 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