Topic
12 replies Latest Post - ‏2015-01-12T16:01:13Z by AlexFleischer
SystemAdmin
SystemAdmin
1883 Posts
ACCEPTED ANSWER

Pinned topic VRP model

‏2013-02-25T14:57:04Z |
Hello everyone,

I am trying to model a VRP for solving the e-n13 instance. I am new in this, so sorry if the question is BASIC.

I wanna to create the constraint for maximum load.
cap = 600000;
demand = 0, 1200, 1700, 1500, 1400, 1700, 1400, 1200, 1900, 1800, 1600, 1700, 1100;

With this data I wanna do something like that:

// Cities
int n = ...;
range Cities = 1..n;

int demandCities= ...;

// Edges -- sparse set
tuple edge {int i; int j;}
{edge} Edges = {<i,j> | ordered i,j in Cities};
int distEdges = ...;

// Vehicles
int cap = ...;

// Decision variables
dvar boolean xEdges;

forall (j in Cities)
total_load = sum (<i,j> in Edges) x<i,j>*d[i] <= cap;
// The vehicle is not overload
total_load <= cap;
But I am really lost with the last part, I want to have an int which sum every demand of each city I use for the route, and then compare this with the maximum load.
Thank you!
Updated on 2013-03-03T09:30:05Z at 2013-03-03T09:30:05Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    1883 Posts
    ACCEPTED ANSWER

    Re: VRP model

    ‏2013-02-25T15:51:15Z  in response to SystemAdmin
    I think I have almost the model, but I don't know how to do the max.capacity constraint and if the k vehicles will run ok with this model, if someone could give me someadvice for that it would be great!

    This is the data:
    /*********************************************
    * OPL 12.4 Data
    * Author: Iván
    * Creation Date: 25/02/2013 at 14:16:04
    *********************************************/
    n = 13;
    v = 5;
    cap = 6000;
    demand = 0, 1200, 1700, 1500, 1400, 1700, 1400, 1200, 1900, 1800, 1600, 1700, 1100;

    dist =[

    9 14 21 23 22 25 32 36 38 42 50 52
    5 12 22 21 24 31 35 37 41 49 51
    7 17 16 23 26 30 36 36 44 46
    10 21 30 27 37 43 31 37 39
    19 28 25 35 51 29 31 29
    9 10 16 22 20 28 30
    7 11 13 17 25 27
    10 16 10 18 20
    6 6 14 16
    12 12 20
    8 10
    10
    ];

    Attachments

    • SystemAdmin
      SystemAdmin
      1883 Posts
      ACCEPTED ANSWER

      Re: VRP model

      ‏2013-02-26T08:47:53Z  in response to SystemAdmin
      Not sure I understand exactly what you are trying to model... may be try in this direction

      subject to {
      forall (j in Cities)
      sum (e in Edges : e.j == j) x[e]*d[e] <= cap;
      }
      • SystemAdmin
        SystemAdmin
        1883 Posts
        ACCEPTED ANSWER

        Re: VRP model

        ‏2013-02-26T19:23:09Z  in response to SystemAdmin
        Thank you for your answer.

        I am trying to modelize a CVRP. 5 (as maximum) vehicles with 6000 of capacity. Each vehicle travels nodes til you have to avoid exceeding its capacity, then they return to the depot and starts the next.

        Clarify this the model I am trying?

        Your sugestion gives me an error. What is e.j==j exactly meaning?
        • SystemAdmin
          SystemAdmin
          1883 Posts
          ACCEPTED ANSWER

          Re: VRP model

          ‏2013-02-27T08:59:40Z  in response to SystemAdmin
          Check that your variables names are the same. e.g. "d" against "dist". Expression e.j == j means that the sum is only by e which fits that criterion.
          • SystemAdmin
            SystemAdmin
            1883 Posts
            ACCEPTED ANSWER

            Re: VRP model

            ‏2013-02-27T18:34:57Z  in response to SystemAdmin
            Ok, I understand.

            I fix that, but I get an error CPLEX status = 5002.

            I think my main problem is model the utilitation of vehicles, as a vehicle return tu depot when it is plenty and then k=k++.

            Noone has an example of VRP with cplex? http://en.wikipedia.org/wiki/Vehicle_routing_problem . I just wanna the simple one, with capacity constraint, and I see people asking about problems with VRP more complex than this.

            Thank you!
            • SystemAdmin
              SystemAdmin
              1883 Posts
              ACCEPTED ANSWER

              Re: VRP model

              ‏2013-02-28T08:04:54Z  in response to SystemAdmin
              I have a TSP model, it is related. You may start from it and make the necessary changes.
              http://en.wikipedia.org/wiki/Travelling_salesman_problem

              int NCity = ...;
              range RCity = 1..NCity;
              int MAX_LOOPS = ...;

              tuple Edge {key int src; key int tgt; int weight;}
              {Edge} raw_edges = ...;

              int edges src in RCitytgt in RCity;

              execute {
              for (var e in raw_edges) {
              edgeshttp://e.srchttp://e.tgt = e.weight;
              }
              }

              assert
              forall (t in RCity)
              forall (s in 1..t)
              edges[t][s] == edges[s][t];

              dvar int uhttp://2..NCity in 2..NCity;
              dvar boolean actRCityRCity;

              minimize sum(t in RCity, s in RCity) edges[t][s] * act[t][s];

              subject to {
              forall (t in RCity) {
              sum (s in RCity) act[t][s] == 1;
              sum (s in RCity) act[s][t] == 1;
              act[t][t] == 0;
              }

              forall (t in 2..NCity) {
              forall (s in 2..NCity) {
              u[t] - u[s] + 1 <= (NCity - 1) * (1 - act[t][s]);
              }
              }
              }
              Regards,
              Zahar
              • SystemAdmin
                SystemAdmin
                1883 Posts
                ACCEPTED ANSWER

                Re: VRP model

                ‏2013-02-28T14:01:23Z  in response to SystemAdmin
                Hi zahar,

                Thank you for your answer and model.

                I have already a TSP model working, and with good optimal results with instances, but I still don't know how to obtain a basic CVRP. The main problem, I think, is make an if, or something similar, that allow the model to use a vehicle til is is plenty, and then add 1 to the counter and start again from depot, but remembering the nodes already visited, of course. If someone has one of this or anyone wanna try to modelize one with me would be great!!

                I like your model for tsp but I get an error in your subtour elimination ecuation :

                u[t] - u[s] + 1 <= (NCity - 1) * (1 - act[t][s]);

                maybe because the writing fails os this forum and miss-translate something bad.

                Have you got some data for lunch it and see if it faster than mine? Thank you :D
                • SystemAdmin
                  SystemAdmin
                  1883 Posts
                  ACCEPTED ANSWER

                  Re: VRP model

                  ‏2013-02-28T14:14:06Z  in response to SystemAdmin
                  Oh, and the error was that it is a not matrix :)
                  • SystemAdmin
                    SystemAdmin
                    1883 Posts
                    ACCEPTED ANSWER

                    Re: VRP model

                    ‏2013-03-03T09:30:05Z  in response to SystemAdmin
                    This constraint in TSP is called MTZ constraint (initials of the people who first found it). I think it is the fastest model for TSP, you can check on your data.
                    • hennou1
                      hennou1
                      7 Posts
                      ACCEPTED ANSWER

                      Re: VRP model

                      ‏2013-06-30T15:31:50Z  in response to SystemAdmin

                      please i need your help, i am trying to resolve pickup and delivery problem with preemption and i can't do it 

                       

                       

                      /*********************************************
                       * OPL 12.3 Model
                       * Author: HENI
                       * Creation Date: 13 juin 2013 at 12:01:47
                       *********************************************/
                       
                       
                      int M=30000;
                       
                      //tuples
                            
                      tuple indnoeud{
                       
                          float i;
                      }
                         
                        tuple inddepot{
                       
                          float i;
                      }        
                              
                      tuple indcltfrs{
                       
                          float i;
                      }
                      tuple indfrs{
                          
                          float i;
                          }
                          
                      tuple indclt{
                          
                          float i;
                      }
                      tuple indveh{
                         float v;
                      }
                       
                       
                      tuple inddek{
                         float   k;
                      }
                       
                       
                      tuple oriddek{
                        float k;
                         float  i;
                      }
                       
                      tuple desddek{
                        float k;
                         float  i;
                      }
                       
                      tuple qtiteddek{
                        float k;
                         float  quantite;
                      }
                       
                      tuple coutveh{
                        float v;
                         float  coutvehicule;
                      }
                       
                       
                      tuple capv{
                        float v;
                         float  capacite;
                      }
                       
                      tuple distance{
                       float i; 
                       float j; 
                       float valeur;
                       
                       
                      tuple time{
                       float i; 
                       float j; 
                       float temp;
                       
                      tuple segplus{
                       
                       float n; 
                       float s;
                      tuple segmoins{
                       
                       float n; 
                       float e;
                      }  
                       
                       
                      {indnoeud}I=...;
                      //{indnoeud2}J=...;
                      {inddepot}ID=...;
                      {indcltfrs}ICF=...;
                      {indfrs}IFR=...; 
                      {indclt}ICL=...;
                      {indveh}V=...;
                      {inddek}K=...;
                      {oriddek}OK=...;
                      {desddek}DK=...;
                      {qtiteddek}qK=...;
                      {coutveh}CV=...;
                      {capv}QV=...;
                      {distance}DIJ=...;
                      {time}TIJ=...;
                      {segplus}SEGP=...;
                      {segmoins}SEGM=...;
                       
                       
                       
                       
                      //définition des indices
                       
                       
                      {float} Is={i|<i> in I};
                      {float} Js={j|<j> in I};
                      {float} Ss={s|<s> in I};
                      {float} IDs={i|<i> in ID};
                      {float} Ks={k|<k> in K};
                      {float} Vs={v|<v> in V};
                      {float} ICFs={i|<i> in ICF};
                      {float} IFRs={i|<i> in IFR};
                      {float} ICLs={i|<i> in ICL};
                      //{string} OKs={i|<i> in OK};
                      //{string} DKs={i|<i> in DK};
                       
                       
                       
                       
                       
                       
                      //définition des paramètres
                       
                      float qKs[Ks];
                       
                      float QVs[Vs]; 
                       
                      float SEGPs[Is]; 
                       
                      float SEGMs[Is];
                       
                      float F0v[Vs]=0;
                       
                      float CVs [Vs];
                       
                      float OKs [Ks];
                       
                      float DKs [Ks];
                       
                      float DIJs [Is][Js];  
                       
                      float TIJs [Is][Js];
                       
                      //float TPs[Ps];
                       //float QVs[Vs];
                      // float CTkpjs[Js][Kps];
                       
                      //lire les paramètres
                       
                       
                      execute { 
                      for (var ook in OK){
                      OKs[ook.k]=ook.i;
                      }}
                       
                      execute { 
                      for (var ddk in DK){
                      DKs[ddk.k]=ddk.i;
                      }}
                       
                      execute { 
                      for (var nnn in SEGP){ 
                      SEGPs[nnn.n]=nnn.s;
                      }
                      }
                       
                      //execute { 
                      //for (var mmm in SEGM){
                      //SEGMs[mmm.n]=mmm.e;
                      //}
                      //}
                       
                       
                       
                      execute {
                       for (var jjj in TIJ)
                       {
                       
                       TIJs[jjj.i][jjj.j]=jjj.temp; 
                       
                      }
                      }
                       
                      execute {
                       for (var iii in DIJ)
                       {
                       
                       DIJs[iii.i][iii.j]=iii.valeur; 
                       
                      }
                      }
                       
                      execute {
                        for (var Ks in qK){
                            qKs[Ks.k]=Ks.quantite;
                        }}
                          
                      execute {
                          for (var Vs in QV){
                            QVs[Vs.v]=Vs.capacite;
                          }}
                          
                          
                      execute {
                          for (var Vs in CV){
                            CVs[Vs.v]=Vs.coutvehicule;
                          }}
                       
                       
                      //*************************************decision variables*********************************************************
                       
                       
                      dvar int+ Yijvk[Is,Vs,Ks] in 0..1;
                       
                       
                      dvar int+ Xijv[Is,Vs] in 0..1;
                       
                       //*****************************************constraint naming**************************************. 
                      constraint c1;
                      constraint c2;
                      constraint c3;
                      constraint c4;
                      constraint c5;
                      constraint c6;
                      constraint c7;
                      constraint c8;
                      constraint c9;
                      constraint c10;
                      constraint c11;
                      constraint c12;
                      constraint c13;
                      constraint c14;
                       
                      //*******************************MODEL*********************************************************
                       
                      dexpr float Cobj= sum (v in Vs, i in Is, j in Js)(CVs[v]*DIJs[i,j]*Xijv[i,j,v]);
                       
                       
                      //fonction objectif : min coût de transport
                       
                       
                      minimize sum (v in Vs, i in Is, j in Js)(CVs[v]*DIJs[i,j]*Xijv[i,j,v]);
                       
                      subject to
                      {
                         
                      // contraintes de gestion de stocks
                       
                      c1= forall (i in ICFs)
                      sum (v in Vs, j in SEGPs[i][2])Xijv[i,j,v]==1;
                         
                      c2 = forall (i in ICFs)
                      sum (v in Vs, j in SEGMs[i][2])Xjiv[i,j,v]==1;
                       
                       // contrainte des veh au depot
                       
                      c3 = forall (v in Vs)
                      sum(i in SEGPs [0][2])Xi0v[i,0,v]==1;
                         
                      c4= forall (v in Vs)
                      sum (i in SEGMs[0][2])X0iv[o,i,v]==1;
                         
                         
                         /// sommet visité doit imperativement etre quitté
                         
                      c5= forall (i in ICFs, v in Vs)
                         sum (j in SEGPs[i][2]) Xijv[i,j,v] - sum (j in SEGMs[i][2]) Xjiv[i,j,v] ==0;
                         
                         
                         // conservation des flot: permet transbordement 
                         
                       //c6= forall ((k in Ks ,i in ICFs: i!= OKs) AND (i!= DKs)) 
                       
                      c6= forall (k in Ks ,i in ICFs: i!= OKs, i in ICFs:i!= DKs)
                      sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] ==0;
                         
                         
                      c7= forall (k in Ks, i in OKs) 
                      sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] == 1;
                         
                      c8= forall (k in Ks, i in DKs)
                      sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] == -1;
                         
                         /// respect capacite 
                         
                      c9= forall (i in Is, j in Js, v in Vs)
                      sum (k in Ks) Yijvk[i,j,v,k]*qKs[k] <= QVs[v]*Xijv[i,j,v];
                         
                      c10= forall (i in ICFs, v in Vs, k in Ks)
                      Y0iv[i,j,v] == Yi0v[i,j,v] ==0;
                         
                      // passage sur un arc sans transporter une demande
                         
                      c11= forall (i in Is, j in Js, v in Vs, k in Ks)
                      Yijvk[i,j,v,k]<= Xijv[i,j,v];
                         
                         
                      // contrainte elemination des sous tours
                        
                      c12 = forall (i in Is, j in Js, v in Vs)
                      Xijv[i,j,v] == 1 => Fiv[i,v] + TIJs[i,j,v] <= Fjv[j,v];
                        
                      c13= forall (v in Vs, i in IFRs, j in ICLs)
                      Fiv[i,v] <= Fjv[j,v];
                        
                      c14 = forall ( v in Vs)
                       F0v[v] == 0;
                      }  
                      }
                      execute {
                       
                       writeln ("objectif=", Cobj)
                       
                      }
  • nazkose
    nazkose
    1 Post
    ACCEPTED ANSWER

    Re: VRP model

    ‏2015-01-10T22:43:37Z  in response to SystemAdmin

    Hello,

    I am trying to model capacitated vehicle routing problem like you did, I stuck at the same part, did you find any solution for it ?

    Thank you.