Ce projet a été réalisé en binôme dans le cadre d'un cours, lors de ma dernière année à l'Université de Technologie de Troyes.

Il traite une problématique de logistique urbaine, à l'aide d'une méthode exacte (mais limitée) et d'une méthode approchée (fournissant de bons résultats). Il a été mené avec le langage python, en utilisant également le logiciel Microsoft Excel.

Le problème du voyageur de commerce (TSP – Traveling-Sales Problem) recherche un itinéraire de voyage optimal, partant d'un point initial, passant par un ensemble de points une et une seule fois et revenant au point initial.

Voici un exemple de données avec 40 points, le point 0 étant le point initial duquel partir :

Les points peuvent représenter des clients qu'un camion partant d'un dépôt doit livrer, avant de revenir au dépôt.

La fonction-objectif, à minimiser, peut être : la distance, le coût de transport... Ici nous avons étudié un cas particulier : celui où les clients ont une fenêtre de temps dans laquelle ils souhaitent être livrés. Cela complexifie le problème. Il a été choisi de rendre cette contrainte "souple", c'est-à-dire de permettre au voyageur d'arriver chez un client après la fin de sa fenêtre de temps. Toutefois, cela engendre une pénalité, qui est un coût proportionnel au temps de retard . De plus, si le voyageur arrive chez un client avant le début de sa fenêtre de temps, il doit attendre avant de le livrer.

La fonction-objectif définissant notre problème est la somme des coûts de trajet d'une tournée auquel on y ajoute le coût de pénalité de retard si le client n’est pas visité à temps. L'itinéraire optimal est celui qui minimise cette fonction.

Pour simplifier la résolution du problème, deux hypothèses sont émises :

1. Distance entre les points = Temps de trajet = Coût du trajet.
2. Le temps de service chez un client est nul.

Voici comment sont formalisées les données que récupèrent les algorithmes :

Comme nous pouvons le voir, il y a une autre contrainte : les clients demandent chacun une certain quantité de produit et le camion a une capacité limitée. Il s'agit d'un problème plus général que le TSP : le problème de tournées de véhicules (VRP – Vehicules Routing Problem). Le camion ne peut généralement pas livrer tous les clients en une seule tournée et il doit effectuer des retours au dépôt.

Nous avons d'abord résolu le cas particulier du TSP (pas de contrainte de capacité, une seule route optimale). Puis nous avons transformé l'algorithme pour le généraliser en VRP (capacité du véhicule limitée, plusieurs tournées).

Nous avons d'abord construit une modélisation mathématique linéaire du problème :

Nous avons ensuite codé cette modélisation en python en utilisant le solveur pyscipopt. Le code se trouve dans le fichier "TSPTW_Solveur.py".

Ce solveur trouve rapidement la solution optimale pour des problèmes à 15 clients ou moins. Au-delà, la résolution nécéssite davantage de temps. Avec une limite de temps de quelques minutes, la meilleure solution du solveur est relativement mauvaise.

Il est donc nécessaire, pour des problèmes complexes, d'avoir recours à des méthodes approchées. Ici nous avons reproduit et adapté une métaheuristique répandue : l'algorithme génétique.

L'algorithme génétique est inspiré des sciences biologiques et de l'évolution. Une population d'individus (= des routes ici) de taille fixe évolue sur un certain nombre de générations. Plus un individu a de "bons gênes" (= plus le coût de la route est faible), plus il a de chances de survivre et de se reproduire, c'est la sélection naturelle. De nouveaux individus sont créés par croisement (cross-over) entre des couples individus de la population. Enfin, un processus de mutation des gênes permet de diversifier la population et de découvrir de nouvelles zones de recherche. À la fin de l'algorithme, on s'intéresse au meilleur individu qui a existé dans la population.

Différentes variantes et valeurs de paramètres de l'algorithme génétique sont possibles.

Notre code se trouve dans le fichier "TSPTW_GA.py".

Nous avons testé notre algorithme sur des instances de 3 dimensions : 20 sommets, 40 sommets et 100 sommets. Avec 3 instances par dimension, cela faisait 9 instances en tout.

Notre algorithme génétique comporte 4 paramètres (taille de population, nombre de générations, probabilité de mutation, part de la population initiale provenant d'une heuristique). Nous avons réalisé un nombre important d'exécutions avec différentes configurations de paramètres. À l'aide des résultats moyens, nous avons choisi le meilleur paramétrage.

Nous avons confirmé que l'algorithme converge vers des bonnes solutions, bien meilleures que celles du solveur avec une limite de temps du même ordre de grandeur.

Ci-dessous deux exemples d'exécutions pour l'instance présentée au début (Dimension 40) :

1. Meilleure solution : 6827,78 - Temps d'exécution : 89,73s

Bleu : Meilleure solution trouvée, par génération

Orange : Valeur moyenne des solutions de la population, par génération

2. Meilleure solution : 6764,32 - Temps d'exécution : 124,00s

Il est possible de modifier ces derniers algorithmes pour les transformer en problèmes de tournées de véhicules.

Pour la partie méthode exacte (solveur), il faudrait ajouter quelques contraintes de capacité ou encore ajouter une dimension à la variable de décision x. Il n'était pas pertinent pour nous de coder à nouveau une méthode exacte.

Nous avons codé une nouvelle méthode approchée. Un algorithme similaire au précédent est utilisé, avec quelques changements : notamment le découpage en tournée et le calcul de la fonction-objectif qui s'aident de l'algorithme SPLIT.

Le code se trouve dans le fichier "VRPTW_GA.py".

Voici une exécution de cet algorithme : Meilleure solution : 9924,57 - Temps d'exécution : 494,03s

Il est nécessaire que la route soit suivie dans cet ordre : [[0, 2, 15, 21, 0], [0, 27, 18, 8, 5, 17, 16, 37, 0], [0, 28, 26, 12, 3, 34, 9, 33, 0], [0, 13, 6, 0], [0, 31, 10, 11, 19, 36, 7, 0], [0, 1, 30, 32, 20, 35, 29, 24, 0], [0, 22, 23, 39, 25, 4, 14, 38, 0]]