problème du multiple voyageurs de commerce mTSP
Le problème du multiple voyageurs de commerce (mTSP) est une généralisation du problème bien connu du voyageur de commerce (TSP), où plus d'un vendeur (voyageur) est autorisé à être utilisé dans la solution. De plus, les caractéristiques du mTSP semblent plus appropriées pour des applications réelles, et il est également possible d'étendre le problème à une grande variété de problèmes de routage de véhicules (VRP) en incorporant certaines contraintes supplémentaires.
Le mTSP est une relaxation du problème d'acheminement de véhicules (VRP); si la capacité du véhicule dans le VRP est une valeur suffisamment grande pour ne pas restreindre la capacité du véhicule, alors le problème est le même que le mTSP.
Modèle Mathématique
Indices
I : L'ensemble de villes.
Parameters
cij : Cout du trajet entre ville i et ville j.
Variables
xij: 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 1, assure le départ de chaque vendeur de son point de départ.
\begin{equation} \sum_{j \in I \setminus 1} x_{1j} = m \end{equation}
contrainte2:
la contrainte 2 , assure le retour de chaque vendeur à son point de départ.
\begin{equation} \sum_{i \in I \setminus 1} x_{i1} = m \end{equation}
contrainte3:
la contrainte d'affectation, qui garantit que chaque nœud est quitté en total exactement une fois.
\begin{equation} \sum_{i \in I} x_{ij} = 1 \qquad \forall _{ j \in I \setminus \ \left\{1\right\}} \end{equation}
contrainte4:
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 \setminus \ \left\{1\right\}} \end{equation}
contrainte5:
indiquer que xij 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:
contrainte6:
éliminer les sous tours à l'aide de la méthode Miller–Tucker–Zemlin (MTZ).
\begin{equation} u_{i} - u_{j} + \left( I -m \right) * x_{ij} \leq I-m-1 \qquad \forall _{i , j \in I, \ i \neq 1, \ i \neq j} \end{equation}
\begin{equation} u_{i} \geq 0 \qquad \forall _{i \in I} \end{equation}
contrainte6:
é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}
contrainte6:
éliminer les sous tours à l'aide de la méthode Gavish–Graves (GG).
\begin{equation} \sum_{j \in I} 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=20;
int m =5;
// 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
sum(j in villes: j>1)x[1][j]==m;
sum(i in villes: i>1)x[i][1]==m;
forall (i in villes) x[i][i]==0;
forall (j in villes:j>1) sum(i in villes)x[i][j]==1;
forall (i in villes:i>1) sum(j in villes)x[i][j]==1;
//Contraintes pour éliminer les sous tours
forall (i,j in villes: i>1 && j !=i ) u[i]-u[j]+(nbvilles-m)*x[i][j]<=nbvilles-m-1;
}
Vidéo explicative Cplex mTSP MTZ:
Code OPL Cplex DFj:
//definire le nombre de nodes
int nbvilles=15;
int m =2;
// 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
//in this section define set and subset
range ss = 1..ftoi(round(2^nbvilles));
{int} sub [s in ss] = {i | i in 2..nbvilles: (s div ftoi(2^(i-1))) mod 2 == 1};
//objective function
minimize sum(i,j in villes)c[i][j]*x[i][j];
subject to{
//constraints
sum(j in villes: j>1)x[1][j]==m;
sum(i in villes: i>1)x[i][1]==m;
forall (i in villes) x[i][i]==0;
forall (j in villes:j>1) sum(i in villes)x[i][j]==1;
forall (i in villes:i>1) sum(j in villes)x[i][j]==1;
//Contraintes pour éliminer les sous tours
forall (s in ss: 2<=card(sub[s])) sum(i, j in sub[s]) x[i][j] <= card(sub[s])-1;
}
Vidéo explicative Cplex mTSP DFJ:
Code OPL Cplex GG:
//definire le nombre de nodes
int nbvilles=40;
int m =5;
// 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
sum(j in villes: j>1)x[1][j]==m;
sum(i in villes: i>1)x[i][1]==m;
forall (i in villes) x[i][i]==0;
forall (j in villes:j>1) sum(i in villes)x[i][j]==1;
forall (i in villes:i>1) sum(j in villes)x[i][j]==1;
//Contraintes pour éliminer les sous tours
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];
}