Problème de tournées de véhicules (VRP) avec cplex et python
Le problème de construction de tournées de véhicules connu sous le nom de Vehicle Routing Problem (VRP) est une extension du problème du voyageur de commerce, connu également sous le nom de Travelling Salesman Problem (TSP). Nous allons donc dans un premier temps définir le problème du voyageur de commerce, puis nous verrons ses extensions, enfin nous verrons le cross docking et son fonctionnement et les chemins qu’on peut conquérir dans notre thèse.
Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales, etc.). Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet.
CVRP
L’objectif du CVRP est de minimiser le coût total, c-à-d la somme des distances ou des temps de parcours des tournées, tout en respectant la contrainte de capacité des véhicules : la quantité de marchandises livrées sur une tournée ne doit pas dépasser la capacité du véhicule qui l’assure. La figure au dessous, représente un exemple de problème 1 de VRP avec 20 clients, résolu avec 4 véhicules.
Modèle Mathématique
Indices
I : L'ensemble de villes.
K: L'ensemble de vehicules.
Parameters
cij : Cout du trajet entre ville i et ville j.
di: la demande du client i.
qk: la capacité du vehicule k.
Variables
xijk: Indique 1 si le vehicule k visite la ville j depuis la ville i ou 0 sinon.
xiik=0
Objective function
Minimize Z
\begin{equation}\begin{aligned} Z =\sum_{i \in I} \sum_{j \in I} \sum_{k \in K} c_{ij} * x_{ijk} \end{aligned} \end{equation}
Contraintes:
contrainte1:
la contrainte 1, assure que chaque nœud est entré une fois par un vehicule.
\begin{equation} \sum_{i \in I } \enspace \sum_{k \in K } x_{ijk} = 1 \qquad \forall _{j \in I \setminus 1} \end{equation}
contrainte2:
la contrainte 2 , assure la sortie de chaque vehicule est le point depuis il entre..
\begin{equation} \sum_{i \in I } x_{ijk} = \sum_{i \in I } x_{jik} \qquad \forall _{j \in I } \quad \forall _{k \in K} \end{equation}
contrainte3:
la contrainte 3 Chaque véhicule quitte le dépôt
\begin{equation} \sum_{j \in I \setminus 1} x_{1jk} = 1 \qquad \forall _{k \in K} \end{equation}
contrainte4:
la contrainte 4 , assure que la somme de livraison par vehicule, ne depasse pas la capacité du vehicule .
\begin{equation} \sum_{i \in I } \sum_{j \in I \setminus 1} d_{i} x_{jik} \leq q_{k} \qquad \forall _{k \in K} \end{equation}
Les sous tours:
contrainte5:
éliminer les sous tours à l'aide de la méthode Miller–Tucker–Zemlin (MTZ).
\begin{equation} u_{ik} - u_{jk} + \left( I - K \right) * x_{ij} \leq I-K-1 \qquad \forall _{i , j \in I, \ j \neq 1} \enspace \forall _{k \in K} \end{equation}
\begin{equation} u_{ik} \geq 0 \qquad \forall _{i \in I} \enspace \forall _{k \in K} \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
# ## Indices
# - $I$ : L' ensemble de villes.
# - $K$ : L'ensemble de vehicules.
# ## Constante parameters
# - $c_{ij}$ : Cout du trajet entre ville i et ville j.
# - $d_{i}$ : La demande du client i.
# - $q_{k}$ : La capacité du vehicule k.
# In[3]:
# Nombre de Nodes
nbVilles = 20
# Index: Range ville
villes=range(nbVilles)
# Nombre de vehicules
nbVehicles=3
vehicles=range(nbVehicles)
# Cout entre node i et node j.
cij=np.random.rand(nbVilles,nbVilles)
#print(cij)
#demande de chaque client i.
di=np.random.random(nbVilles)*10
#print(di)
#quapacité du vehicule k.
qk = np.random.rand(nbVehicles)*200
#print(qk)
# In[4]:
#Définition du model
model=Model('CVRP')
# ## Variable de décision
# # Traveling Salesman Problem,
#
# - $x_{ijk}$ : Indique 1 si on visite la ville j depuis la ville i à travers le vehicule k ou 0 sinon.
# - $u_{i}$ : Variable qui sert à éliminer les soustours.
#
# $$\begin{align}
# x_{ijk} \in \{ 0,1 \}\\
# u_{ik} \ge 0 \\
# \end{align}$$
#
#
# In[5]:
## Variable xij
x=model.binary_var_cube(keys1=villes,keys2=villes,keys3=vehicles,name='x')
## Varible ui
u=model.integer_var_matrix(keys1=villes, keys2=vehicles,lb=0, ub=nbVilles,name='u')
# ## Fonction Objective
# \begin{equation}
# \begin{aligned}
# \sum_{i \in I} \sum_{j \in I} \sum_{k \in K} c_{ij} * x_{ijk}
# \end{aligned}
# \end{equation}
# In[6]:
model.minimize(model.sum(cij[i,j] * x[i,j,k] for i in villes for j in villes for k in vehicles))
# ### Contraintes:
# #### Contrainte 1:
# Assure que chaque nœud est entré une fois par un vehicule.
# \begin{equation}
# \sum_{i \in I } \sum_{k \in K } x_{ijk} = 1 \qquad \forall _{j \in I \setminus 1}
# \end{equation}
# In[7]:
for j in villes:
if j > 0 :
model.add_constraint(model.sum( x[i , j , k] for i in villes for k in vehicles )==1 , ctname="cst1")
# #### Contrainte 2:
# Assure la sortie de chaque vehicule est le point depuis il entre.
# \begin{equation}
# \sum_{i \in I } x_{ijk} = \sum_{i \in I } x_{jik} \qquad \forall _{j \in I }
# \quad \forall _{k \in K}
# \end{equation}
# In[8]:
for j in villes:
for k in vehicles:
model.add_constraint(model.sum(x[i , j , k] for i in villes )==model.sum(x[j , i , k] for i in villes) , ctname="c2")
# #### Contrainte 3:
# Chaque véhicule quitte le dépôt.
# \begin{equation} \sum_{j \in I \setminus 1} x_{1jk} = 1 \qquad \forall _{k \in K} \end{equation}
# In[9]:
for k in vehicles:
model.add_constraint(model.sum(x[0 , j , k] for j in villes if j>0)==1, ctname="c3")
# #### Contrainte 4:
# assure que la somme de livraison par vehicule, ne depasse pas la capacité du vehicule.
# \begin{equation} \sum_{i \in I } \sum_{j \in I \setminus 1} d_{i} x_{jik} \leq q_{k} \qquad \forall _{k \in K} \end{equation}
# In[10]:
for k in vehicles:
model.add_constraint( model.sum(di[j] * x[i , j,k] for i in villes for j in villes if j>0)<=qk[k], ctname="c4")
# #### Contrainte 5:
# Eliminer les sous tours à l'aide de la méthode Miller–Tucker–Zemlin (MTZ).
# \begin{equation} u_{ik} - u_{jk} + \left( I - K \right) * x_{ijk} \leq I-K-1 \qquad \forall _{i , j \in I, \ j \neq 1} \enspace \forall _{k \in K} \end{equation}
# In[11]:
for i in villes:
for j in villes:
if j > 0:
for k in vehicles:
model.add_constraint(u[i,k]-u[j,k]+(nbVilles -nbVehicles)* x[i,j , k]<=(nbVilles - nbVehicles -1), ctname="c5")
# ## 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: