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

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

    Re: VRP model

    ‏2013-02-25T15:51:15Z  
    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

    Re: VRP model

    ‏2013-02-26T08:47:53Z  
    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
    ];
    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

    Re: VRP model

    ‏2013-02-26T19:23:09Z  
    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;
    }
    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

    Re: VRP model

    ‏2013-02-27T08:59:40Z  
    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?
    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

    Re: VRP model

    ‏2013-02-27T18:34:57Z  
    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.
    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

    Re: VRP model

    ‏2013-02-28T08:04:54Z  
    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!
    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

    Re: VRP model

    ‏2013-02-28T14:01:23Z  
    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
    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

    Re: VRP model

    ‏2013-02-28T14:14:06Z  
    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
    Oh, and the error was that it is a not matrix :)
  • SystemAdmin
    SystemAdmin
    1883 Posts

    Re: VRP model

    ‏2013-03-03T09:30:05Z  
    Oh, and the error was that it is a not matrix :)
    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

    Re: VRP model

    ‏2013-06-30T15:31:50Z  
    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.

    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

    Re: VRP model

    ‏2015-01-10T22:43:37Z  

    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.

  • AlexFleischer
    AlexFleischer
    1247 Posts

    Re: VRP model

    ‏2015-01-12T16:01:13Z  
    • nazkose
    • ‏2015-01-10T22:43:37Z

    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.

    Hi

    have you had a look at https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014931542

    ?