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

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.

Variables

x_ijk: Indique 1 si le vehicule k  visite la ville j depuis la ville i ou 0 sinon.

x_iik=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}

Les sous tours:

contrainte5: 

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

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

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

\begin{equation} z_{ijk} \geq 0 \qquad \forall _{i , j \in I}   \enspace \forall _{k \in K} \end{equation}

Code OPL Cplex MTZ:

//definire le nombre de nodes
int nbvilles=21;
int nbvehicles =5;
// définir les parametres
// définir index
range villes=1..nbvilles; //I l'ensemble des villes
range vehicles=1..nbvehicles; //I l'ensemble des vehicules

//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);
float d[i in villes]=rand(100);
float q[k in vehicles]=rand(1000);

//Variables de décision
dvar boolean x[villes][villes][vehicles]; //x est un variable boolean égale 1 si il visite de la ville i à j sinon 0
dvar int+ u[villes][vehicles]; // u est un variable pour éliminer les sous tours

minimize sum(i,j in villes , k in vehicles)  c[i][j]*x[i][j][k];
//objective function
subject
to{
//constraints
//chaque nœud est entré une fois par un vehicule.
c1:
forall (j in villes: j >1) sum(i in villes) sum(k in vehicles) x[i][j][k]==1;
//la sortie de chaque vehicule est le point depuis il entre.
c2:
forall (k in vehicles) forall (j in villes) sum(i in villes)  x[i][j][k] == sum(i in villes)  x[j][i][k];
//Chaque véhicule quitte le dépôt
c3:
forall(k in vehicles) sum (j in villes: j >1)  x[1][j][k]==1;
forall (i in villes) forall (k in vehicles) x[i][i][k]==0;
c4:
//Contrainte pour ne dépasser la capacité:
forall (k in vehicles) sum(i in villes) sum(j in villes : j >1 ) d[j] * x[i][j][k] <= q[k];
//Contraintes pour éliminer les sous tours
c5:
forall (i,j in villes:  j !=1 , k in vehicles) u[i][k] - u[j][k] + (nbvilles-nbvehicles) * x[i][j][k] <= (nbvilles-nbvehicles-1);
}

Vidéo explicative Cplex VRP MTZ: