Topic
  • 2 replies
  • Latest Post - ‏2013-07-24T13:43:37Z by hennou1
RithulKrishnan
RithulKrishnan
1 Post

Pinned topic Traveling Salesman Problem

‏2013-06-04T05:15:51Z |

Hi,

 

I'm solving the TSP using the given example, but I also want to show the sequence or route of the selected tour (e.g. if there are 4 cities, then I want to show the route as 1-3-2-4-1 or 1-3-2-4). I have been trying to do so from the past 2 days but have been unable to figure out a way to do this. Any help will be greatly appreciated.

 

Thank You,

Rithul

  • AlexFleischer
    AlexFleischer
    1248 Posts

    Re: Traveling Salesman Problem

    ‏2013-06-11T11:10:06Z  

    Hi,

     

    have you tried to add after

     

    writeln("Found subtour of size : ", thisSubtourSize);
        if (thisSubtourSize < newSubtourSize) {
          for (i in Cities)
            newSubtour[i] = thisSubtour[i];
            newSubtourSize = thisSubtourSize;
        }

     

    the following

     for(i in Cities) if (newSubtour[i]!=0) break;
        if (newSubtour[i]!=0)
        {
            var initial=i;
            write(i, " -> ");
            while (newSubtour[i]!=initial)
            {
                  i=newSubtour[i];
                  write(i," -> ");
            }     
            writeln(newSubtour[i]);
     }   
      }

     

    regards

     

  • hennou1
    hennou1
    7 Posts

    Re: Traveling Salesman Problem

    ‏2013-07-24T13:43:37Z  

    Hi,

     

    have you tried to add after

     

    writeln("Found subtour of size : ", thisSubtourSize);
        if (thisSubtourSize < newSubtourSize) {
          for (i in Cities)
            newSubtour[i] = thisSubtour[i];
            newSubtourSize = thisSubtourSize;
        }

     

    the following

     for(i in Cities) if (newSubtour[i]!=0) break;
        if (newSubtour[i]!=0)
        {
            var initial=i;
            write(i, " -> ");
            while (newSubtour[i]!=initial)
            {
                  i=newSubtour[i];
                  write(i," -> ");
            }     
            writeln(newSubtour[i]);
     }   
      }

     

    regards

     

    hi, I have a problem with the execution it does not work.

    My problem consist to optimise the pickup and delivery problem with préemption. 

    please i need yours help 

     

    fichier.mod 

     

     
     
    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 Fiv[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,Js,Vs,Ks] in 0..1;
     
     
    dvar int+ Xijv[Is,Js,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, s in Is: s==j)
    sum (v in Vs, j in SEGPs[i][s])Xijv[i,j,v]==1;
       
    c2 = forall (i in ICFs, s in Is: s==j)
    sum (v in Vs, j in SEGMs[s][i])Xijv[i,j,v]==1;
     
     
     // contrainte des veh au depot
     
    c3 = forall (v in Vs, j in Js: i==0)
    sum(i in SEGPs [i][j])Xijv[i,j,v]==1;
       
    c4= forall (v in Vs, j in Js: j==0)
    sum (i in SEGMs[j][i])Xijv[j,i,v]==1;
     
     /// sommet visité doit imperativement etre quitté
       
    c5= forall (i in ICFs, v in Vs,s in Is: s==j)
       sum (j in SEGPs[i][s]) Xijv[i,j,v] - sum (j in SEGMs[s][i]) Xijv[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, s in Is: s==j)
    sum (v in Vs, j in SEGPs[i][s]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[s][i])Yijvk[i,j,v,k] ==0;
       
       
    c7= forall (k in Ks, i in OKs, s in Is: s==j) 
    sum (v in Vs, j in SEGPs[i][s]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[s][i])Yijvk[i,j,v,k] == 1;
       
    c8= forall (k in Ks, i in DKs, s in Is: s==j)
    sum (v in Vs, j in SEGPs[i][s]) Yijvk[i,j,v,k]-sum (v in Vs, j in SEGMs[s][i])Yijvk[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,j in Js:j==0, v in Vs, k in Ks)
    Yijvk[i,j,v,k] == Yijvk[i,j,v,k] ==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]*Xijv[i,j,v] + TIJs[i,j,v]*Xijv[i,j,v] <= Fjv[j,v]*Xijv[i,j,v];
      
    c13= forall (v in Vs, i in IFRs, j in ICLs)
    Fiv[i,v]*Xijv[i,j,v] <= Fjv[j,v]*Xijv[i,j,v];
      
    c14 = forall ( i in Is:i==0, v in Vs)
     Fiv[v]*Xijv[i,j,v] == 0; 
    }} 
    *************************************************************************************

     

    fichier.data

     

     
     DBconnection db("odbc","DRIVER={Microsoft Access Driver (*.mdb)};DBQ=C:\\cplex\\mars1\\testpbm1.mdb//");
      
     
     
    //lecture des différentes tables
     
    QV from DBread (db,"select v,capacite FROM capv");
     
    CV from DBread (db, "select v,coutvehicule from coutveh");
     
    DK from DBread(db, "SELECT k,i  FROM desddek "); 
     
    ICL from DBread (db,"select i from indclt");
     
    ICF from DBread(db, "SELECT i FROM indcltfrs");
     
    K from DBread(db, "SELECT k FROM inddek");
     
    ID from DBread(db, "SELECT i FROM inddepot");
     
    IFR from DBread(db, "SELECT i FROM indfrs");
     
    I from DBread (db, "select i from indnoeud");
     
    V from DBread (db, "select v from indveh");
     
    OK from DBread (db,"select k,i from oriddek");
     
    qK from DBread (db,"select k,quantite from qtiteddek");
     
    DIJ from DBread (db,"select i,j,valeur from distance");
    TIJ from DBread (db,"select i,j,temp from time");
     
     
    //TIJ from DBread (db,"select i,j,temp from time");
     
    SEGP from DBread (db,"select n,s from segplus");
     
    SEGM from DBread (db,"select n,e from segmoins");

    **********************************************************************

    and you can see my formulation in the attachment 

    Attachments