Topic
  • 6 replies
  • Latest Post - ‏2015-01-13T13:01:26Z by davidoff
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
    41 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
    41 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) ?