Projet de stage de Master 2 sur l'optimisation des tournées de véhicules appliquées à la collecte de bouteilles en verre consignées
Dernière mise-à-jour le : [2023-10-04]
Statut : en pause
Les librairies nécessaires à l'exécution du code sont :
- pandas
- geopy
- folium
- matplotlib
L'algorithme ALNS, contenu dans le module alns, résout un problème de tournée multi-route avec les points dans le fichier "points.csv", le véhicule contenu dans le fichier "vehicule.json" et les éléments extérieur dans le fichier "contexte.json". Ces fichiers doivent être dans un même dossier passé en argument {filePath}. Par défaut ce dossier est "dataBase".
La solution retournée est un ensemble de périodes (timeslot) contenant des routes qui elles-même sont une liste ordonnées de points définissant le chemin à prendre.
L'objectif est par défaut le calcul initial du travail précédent. Il peut être remplacé par la minimisation de la distance ou de la durée en changeant l'argument correspondant par le mot clé souhaité parmi "cost", "distance" et "duration".
python3 runBase.py {filePath} {objectif}
Le paramétrage des paramètres de l'ALNS permet de fixer les 4 paramètres non fixés par la littérature. L'algorithme génétique situé dans le module algoGeneticAlns est utilise les données du dossier "dataBase" et produit un fichier "gene.csv" contenant le meilleur gene de chaque génération.
Par défaut, nous avons 200 générations et une population de taille 10.
python3 runParametrage.py {nbGeneration} {nbPopulation}
Le module plne contient l'implémentation d'un programme linéaire en nombre entier d'un VRPTW qui utilise la bibliothèque Python-MIP. Le temps limite d'exécution est posé à 3600s.
Le module algoGeneticTournee contient les fichiers de code d'un algorithme génétique pour optimiser une tournée de véhicules. Par défaut, l'algorithme utilise 10 générations, une population de 1000 et un taux de mutation de 0,1. Vous pouvez ajuster ces paramètres selon vos besoins. De plus, le chemin d'accès du fichier de sortie graphique est à modifier dans le fichier "algo.py", en suivant l'exemple 'file:///home/chloe/PycharmProjects/optimisationTournee/view.html'.
Le module apiRO est conçu pour utiliser l'API d'optimisation de tournée de GraphHopper. GraphHopper est un service qui fournit des API pour le routage, l'optimisation de tournée, la géocodage, et d'autres fonctionnalités liées à la géolocalisation. Pour utiliser ce module, vous aurez besoin d'une clé API de GraphHopper, car elle est nécessaire pour effectuer des requêtes à l'API d'optimisation de tournée. Assurez-vous d'obtenir une clé API valide de GraphHopper et de la configurer correctement dans le fichier "routOptimization.py" et "methodes.py" afin d'utiliser les services de GraphHopper.
L'exécutable "runComparaison.py" permet de comparer quatre méthodes d'optimisation de tournée : le programme linéaire, l'algorithme ALNS, l'algorithme génétique et l'API de GraphHopper. Chaque méthode prend en paramètre la liste des points à visiter et le collecteur qui effectue la tournée. Les résultats de la comparaison sont enregistrés dans le fichier "comparaison.csv", ce qui facilite l'analyse des performances de chaque méthode et aide à choisir la plus appropriée pour votre application.
python3 runComparaison.py
Chaque méthode peut également être exécutée individuellement dans l'exécutable "main.py".
Une instance de la classe Solver à besoin d'une méthode parmi les suivantes :
- alnsConvertisseur : ALNS
- algoGenConvertisseur : Algorithme génétique
- routeOptimization : API d'optimisation de route
- VRPTWmip : programme linéaire en nombre entier
La fonction preprocess prend en paramètre la liste des clients et la liste des collecteurs disponibles. Elle retourne la ou les meilleurs routes trouvées par collecteur.
La fonction solve prend la liste des clients à visiter et le collecteur pour effectuer la tournée. Elle retourne le meilleur chemin trouvé en utilisant la méthode choisie précédemment.
preview() : affichage d'une solution sous forme de liste
previewSolution() : affichage d'une instance de la classe Solution
previewConvexHull() : affichage de l'étape intermédiaire metant en avant les points sélectionnés, l'enveloppe convexe et les points internes sur l'ensemble des points
previewSelection() : affichage d'une sélection de points sous forme de dictionnaire