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

# Pinned topic Traveling Salesman Problem

‏2013-06-04T05:15:51Z | salesman sequence traveling tsp

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
3152 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
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.

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