Cplex, problème du voyageur de commerce TSP

Le problème du voyageur de commerce (The traveling salesman problem) (TSP) est l'un des problèmes d'optimisation combinatoire les plus connus étudiés dans la littérature de recherche opérationnelle.

Elle consiste à déterminer un tour qui commence et se termine à un nœud de base donné après avoir visité un ensemble de nœuds exactement une fois tout en minimisant la distance totale. Résoudre le problème TSP est crucial car il appartient à la classe des non-polynômes (NP)-complets.

Dans cette classe de problèmes, aucun algorithme en temps polynomial n'a été découvert. Si quelqu'un trouve un algorithme TSP efficace, il peut être étendu à d'autres problèmes de classe NP-complet. Malheureusement, à ce jour, personne n'a pu le faire. Le TSP est divisé en deux catégories, symétrique et asymétrique, en fonction de la distance entre deux nœuds. En TSP asymétrique (ATSP), la distance d'un nœud à un autre est différent de la distance inverse, et en TSP symétrique (STSP), cette distance est la même. Comme mentionné précédemment, la TSP consiste à déterminer un circuit de distance minimale passant par chaque sommet une et une seule fois. Un tel circuit est appelé tour ou circuit hamiltonien (ou cycle).

TSP, The traveling salesman problem, Le problème du voyageur de commerce

Modèle Mathématique

Indices

I : L'ensemble de villes.

Parameters

c_ij : Cout du trajet entre ville i et ville j.

Variables

x_ij: Indique 1 si on visite la ville j depuis la ville i ou 0 sinon.

Objective function

Minimize Z

\begin{equation}\begin{aligned} Z =\sum_{i \in I} \sum_{j \in I} c_{ij} * x_{ij} \end{aligned} \end{equation}

Contraintes:

contrainte1:

la contrainte d'affectation, qui garantit que chaque nœud est quitté en total exactement.

\begin{equation} \sum_{i \in I} x_{ij} = 1 \qquad \forall _{ j \in I } \end{equation}

contrainte2:

la contrainte d'affectation, qui garantit que chaque nœud est visité en total exactement une fois.

\begin{equation} \sum_{j \in I} x_{ij} = 1 \qquad \forall _{i \in I } \end{equation}

contrainte3:

indiquer que $x_{ij}$ est une variable binaire et égale à 1 ou 0.

\begin{equation} x_{ij} \in \left\{ 0,1 \right\} \qquad \forall _{i , j \in I } \end{equation}

Les sous tours:

Le modèle de base mentionné ci-dessus n'est pas complet car il ne prend pas en charge le circuit hamiltonien. Supposons qu'il y ait dix-huit nœuds et qu'un voyageur veuille tous les visiter, il peut le faire des deux manières illustrées dans les figures ci dessous.

TSP, The traveling salesman problem, Le problème du voyageur de commerce

TSP, The traveling salesman problem, Le problème du voyageur de commerce , soustours

contrainte4:

éliminer les sous tours à l'aide de la méthode Miller–Tucker–Zemlin (MTZ).

\begin{equation} u_{i} - u_{j} + I * x_{ij} \leq I-1 \qquad \forall _{i , j \in I, \ j \neq 1, \ i \neq j} \end{equation}

\begin{equation} u_{i} \geq 0 \qquad \forall _{i \in I} \end{equation}

contrainte4:

éliminer les sous tours à l'aide de la méthode Danzig–Fulkerson–Johnson (DFJ).

\begin{equation} \sum_{i \in S} \sum_{j \in S} x_{ij} \leq \mid S \mid - 1 \qquad \forall _{S \in I, \ 2 \leq S \leq I-1} \end{equation}

contrainte4:

éliminer les sous tours à l'aide de la méthode Gavish–Graves (GG).

\begin{equation} \sum_{j \in 1} z_{ij} - \sum_{j \in I \setminus \ \left\{1\right\}} z_{ij} = 1 \qquad \forall _{i \in I \setminus \ \left\{1\right\} } \end{equation}

\begin{equation} z_{ij} \leq ( I-1) * x_{ij} \qquad \forall _{i \in I \setminus \left\{1\right\}} \ \forall _{j \in I } \end{equation}

\begin{equation} z_{ij} \geq 0 \qquad \forall _{i , j \in I} \end{equation}

Code OPL Cplex MTZ:

//definire le nombre de nodes
int nbvilles=200;

// définir les parametres

// définir index
range villes=1..nbvilles; //I l'ensemble des villes

//c est le couts ou bien la distance entre deux villes; créer des nombres aléatoire
float c[i in villes][j in villes]=rand(210);


//Variables de décision
dvar boolean x[villes][villes]; //x est un variable boolean égale 1 si il visite de la ville i à j sinon 0


dvar int+ u[villes]; // u est un variable pour éliminer les sous tours

minimize sum(i,j in villes)c[i][j]*x[i][j];
//objective function
subject
to{
//constraints
forall (j in villes) sum(i in villes)x[i][j]==1;
forall (i in villes) sum(j in villes)x[i][j]==1;

//Contraintes pour éliminer les sous tours
forall (i,j in villes: j!=1) u[i]-u[j]+nbvilles*x[i][j]<=nbvilles-1;
}


//affichage
execute{  
  var a=1;
  for ( var b=1 ; b < nbvilles+1; b++ ) 
{
for ( var c=1 ; c < nbvilles+1; c++ ) 
{
  if(x[a][c]>0  ) {
    write(", "+a); 
    a=c ;
    if(a==1){
      b=nbvilles+1;
      break;
    }
    }
 }
} ;
}

Vidéo explicative Cplex MTZ:

Code OPL Cplex DFj:

//definire le nombre de nodes
int nbvilles=15;

// définir les parametres

// définir index
range villes=1..nbvilles; //I l'ensemble des villes

//c est le couts ou bien la distance entre deux villes; créer des nombres aléatoire
float c[i in villes][j in villes]=rand(210);

//in this section define set and subset
range ss = 1..ftoi(round(2^nbvilles));
{int} sub [s in ss] = {i | i in 1..nbvilles: (s div ftoi(2^(i-1))) mod 2 == 1};


//Variables de décision
dvar boolean x[villes][villes]; //x est un variable boolean égale 1 si il visite de la ville i à j sinon 0




minimize sum(i,j in villes)c[i][j]*x[i][j];
//objective function
subject
to{
//constraints
forall (j in villes) sum(i in villes)x[i][j]==1;
forall (i in villes) sum(j in villes)x[i][j]==1;

//Contraintes pour éliminer les sous tours
forall (s in ss: 2<card(sub[s])<nbvilles) sum(i, j in sub[s]) x[i][j] <= card(sub[s])-1;
}


//affichage
execute POSTPROCESS {  
  var a=1;
  for ( var b=1 ; b < nbvilles+1; b++ ) 
{
for ( var c=1 ; c < nbvilles+1; c++ ) 
{
  if(x[a][c]>0  ) {
    write(a); 
    a=c ;
    if(a==1){
      b=nbvilles+1;
      break;
    }
    else{
      write("->")
    }
    }
 }
} ;
}

Vidéo explicative Cplex DFJ:

Code OPL Cplex GG:

//definire le nombre de nodes
int nbvilles=200;

// définir les parametres

// définir index
range villes=1..nbvilles; //I l'ensemble des villes

//c est le couts ou bien la distance entre deux villes; créer des nombres aléatoire
float c[i in villes][j in villes]=rand(210);


//Variables de décision
dvar boolean x[villes][villes]; //x est un variable boolean égale 1 si il visite de la ville i à j sinon 0


dvar float+ z[villes][villes]; // z est un variable pour éliminer les sous tours

//objective function
minimize sum(i,j in villes)c[i][j]*x[i][j];

subject to{
//constraints
forall (j in villes) sum(i in villes)x[i][j]==1;
forall (i in villes) sum(j in villes)x[i][j]==1;
forall (i in villes: i>=2 ) sum(j in villes)z[i][j]-sum(j in villes: j!=1)z[j][i]==1;
forall (i,j in villes: i!=1) z[i][j]<=(nbvilles-1)*x[i][j];
}

//affichage
execute{  
  var a=1;
  for ( var b=1 ; b < nbvilles+1; b++ ) 
{
for ( var c=1 ; c < nbvilles+1; c++ ) 
{
  if(x[a][c]>0  ) {
    write(", "+a); 
    a=c ;
    if(a==1){
      b=nbvilles+1;
      break;
    }
    }
 }
} ;
}

SoutienIntelligence

problème du voyageur de commerce TSP

Modèle Mathématique

Objective function

Minimize Z

\begin{equation}\begin{aligned} Z =\sum_{i \in I} \sum_{j \in I} c_{ij} * x_{ij} \end{aligned} \end{equation}

Contraintes:

contrainte1:

\begin{equation} \sum_{i \in I} x_{ij} = 1 \qquad \forall _{ j \in I } \end{equation}

contrainte2:

\begin{equation} \sum_{j \in I} x_{ij} = 1 \qquad \forall _{i \in I } \end{equation}

contrainte3:

\begin{equation} x_{ij} \in \left\{ 0,1 \right\} \qquad \forall _{i , j \in I } \end{equation}

Les sous tours:

contrainte4:

\begin{equation} u_{i} - u_{j} + I * x_{ij} \leq I-1 \qquad \forall _{i , j \in I, \ j \neq 1, \ i \neq j} \end{equation}

\begin{equation} u_{i} \geq 0 \qquad \forall _{i \in I} \end{equation}

contrainte4:

\begin{equation} \sum_{i \in S} \sum_{j \in S} x_{ij} \leq \mid S \mid - 1 \qquad \forall _{S \in I, \ 2 \leq S \leq I-1} \end{equation}

contrainte4:

\begin{equation} \sum_{j \in 1} z_{ij} - \sum_{j \in I \setminus \ \left\{1\right\}} z_{ij} = 1 \qquad \forall _{i \in I \setminus \ \left\{1\right\} } \end{equation}

\begin{equation} z_{ij} \leq ( I-1) * x_{ij} \qquad \forall _{i \in I \setminus \left\{1\right\}} \ \forall _{j \in I } \end{equation}

\begin{equation} z_{ij} \geq 0 \qquad \forall _{i , j \in I} \end{equation}

Code OPL Cplex MTZ:

Vidéo explicative Cplex MTZ:

Code OPL Cplex DFj:

Vidéo explicative Cplex DFJ:

Code OPL Cplex GG:

Vidéo explicative Cplex GG: