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

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.

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}

# ### Install

# In[1]:


get_ipython().system('pip install cplex')
get_ipython().system('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.

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


# In[4]:


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


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

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

# $$\begin{align}
#   \sum_{i \in I} x_{ij} = 1  && \forall j \in I \\ 
#  \sum_{j \in I} x_{ij} = 1  && \forall i \in I \\  
# \end{align}$$

# In[7]:


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


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

# In[8]:


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


# ## Solve

# In[9]:


solution = model.solve(log_output=True)


# ## Affichage

# In[10]:


solution.display()


# In[11]:


solution.get_objective_value()


# In[21]:


a=0;
breaker = False
for  b in villes :
    for  c in villes : 
        if solution.get_value(x[a , c])>0  :
            print(" (order "+(str(u[a]))+ ": " + str(solution.get_value(u[a]))+ " node: x_"+str(a)+")", end="=>")
            a=c 
            if(a==0):
                b=nbVilles
                breaker = True
                break
    if breaker:
        break

Vidéo explicative Cplex avec Python: