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

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 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 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:

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}

Code python Cplex MTZ:

# ### Install

# In[1]:


#!pip install cplex
#!pip install docplex


# ## Import

# In[2]:


import numpy as np
from docplex.mp.model import Model 


# ## Constante parameters

# - $I$ :   L' ensemble de villes.
# - $c_{ij}$ :   Cout du trajet entre ville i et ville j.
# - $m$ :   nombre de trajet

# In[3]:


# Nombre de Nodes
nbVilles = 20
# Index: Range ville
villes=range(nbVilles)
# Cout entre node i et node  j.
cij=np.random.rand(nbVilles,nbVilles)
# Nombre de trajet
m=5


# In[4]:


#Définition du model
model=Model('mTSP')


# ## Variable de décision

# # Traveling Salesman Problem,
# 
# - $x_{ij}$ :   Indique 1 si on visite la ville j depuis la ville i ou 0 sinon.
# - $u_{i}$ :   Variable qui sert à éliminer les soustours.
# 
# $$\begin{align}
#   x_{ij} \in \{ 0,1 \}\\ 
#   u_{i} \ge  0 \\ 
# \end{align}$$
# 
# 

# In[5]:


## Variable xij
x=model.binary_var_matrix(keys1=villes,keys2=villes,name='x')
## Varible ui
u=model.integer_var_list(keys=villes, lb=0, ub=nbVilles,name='u')


# ## Fonction Objective

# $$\begin{align}
# \min \quad & \sum_{i,j \in I} c_{ij} x_{ij} \\ \\
# \end{align}$$

# In[6]:


model.minimize(model.sum(cij[i,j] * x[i,j] for i in villes for j in villes))


# ### Contraintes:

# #### Contrainte 1:
# Assure le départ de chaque vendeur de son point de départ.

# $$\begin{align}
#   \sum_{j \in I \setminus 1} x_{1j} = m  
# \end{align}$$

# In[7]:


model.add_constraint(model.sum(x[0 , j] for j in villes if j>0)==m)    


# #### 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}

# In[8]:


model.add_constraint(model.sum(x[i , 0] for i in villes if i>0)==m)    


# #### Contrainte 3:
# 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}

# In[9]:


for j in villes:
    if j > 0:
        model.add_constraint(model.sum(x[i , j] for i in villes )==1)   


# #### Contrainte 4:
# 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}

# In[10]:


for i in villes:
    if i > 0:
        model.add_constraint(model.sum(x[i , j] for j in villes )==1)   


# #### Contrainte 5:
# Eliminer 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}

# In[11]:


for i in villes:
    for j in villes:
        if j != 0:
            model.add_constraint(u[i]-u[j]+(nbVilles -m)* x[i,j]<=nbVilles - m -1)


# ## Solve

# In[12]:


solution = model.solve(log_output=True)


# ## Affichage

# In[13]:


solution.display()


# In[14]:


solution.get_objective_value()

Vidéo explicative Cplex avec Python: