Ce projet a pour objectif d’automatiser la répartition logistique d’une CERP en optimisant les itinéraires de livraison des camions vers les pharmacies, à l’aide d’un algorithme génétique, afin de réaliser chaque tournée en moins de 3 heures tout en minimisant le nombre de camions utilisés et la distance parcourues. On genere un pdf contenant les chemins de chaque livreur.
Pour voir toute la documentation: https://esiee5100.atlassian.net/wiki/x/h4EB
Tout est automatisé via le script bash fourni.
1. Ouvrez un terminal et place-toi dans le dossier du projet :
cd /chemin/vers/ton/projet2. Lancez le script d’installation et de génération :
Sur Unix :
bash setup.sh
bash generate_dataset.sh /chemin/vers/le/csv
bash run_generation.sh Exemple:
bash setup.sh
bash generate_dataset.sh delivery/livraison85.csv
bash run_generation.sh Sur Windows : Utiliser le fichier run_generation.bat
Ce script :
- crée un environnement virtuel Python,
- installe toutes les dépendances nécessaires,
- lance le script Python qui génère les PDF.
3. Les rapports PDF sont générés dans le dossier rapport sous le nom :
- rapport_livraison.pdf
Pour récupérer les coordonnées des pharmacies
python3 data/getCoordinates.py chemin/fichier/base.csv Pour récupérer les matrices de distance et de temps
python3 data/getMatrix.pyPour executer le programme, on utilise la commande :
make
./exe data/distance_matrix.csv data/time_matrix.csvUn PDF est généré avec des pages récapitulatives des chemins de tous les livreurs, suivies de pages détaillées pour chacun d’eux. Example de page d'un livreur:
Example de solution:
livreur 1 : 0 → 2 → 5 → 7 → 0
livreur 2 : 0 → 3 → 6 → 9 → 0
livreur 3 : 0 → 1 → 4 → 8 → 10 → 0
Les contraintes à respecter:
Contraintes appliquées lors de la génération d'un chemin d'un livreur:
- Chaque chemin commence et se termine au dépôt (ville 0)
- Chaque ville est visitée une seule fois
- Chaque chemin commence et se termine au dépôt (ville 0)
- Aucun chemin ne dépasse 3 heures de livraison, en comptant les 3 minutes de pause dans chaque pharmacie
Contraintes appliquées lors de la génération d'un individu:
- les chemins de chaque livreur respecte les contraintes au dessus
- toutes les villes fournies sans parcourus par les livreurs
Démarche de l'algorithme génétique :
On utilise le concept de "Multiple Population Genetic Algorithm", où :
-
on génère plusieurs populations ;
-
on sélectionne 2 parents et on génère plusieurs enfants avec mutation ;
-
on compare la meilleure solution de cette population avec la meilleure solution globale, et on la remplace si elle est meilleure.
Pseudo Code:
while num_population < NB_POPULATIONS do do
population ← initialize_population() // Génération aléatoire de NB_POPULATION individus,
// où chaque individu représente une solution complète
// et respecte les contraintes au dessus
num_generation ← 0
while num_generation < NB_GENERATIONS do
cumulative_fitness ← evaluate_fitness(population)
// cumulative_fitness[i] = somme cumulative des fitness jusqu’à l’individu i
// fitness mise à jour à partir de la distance, du temps, et du nombre de livreurs
parents ← selection(cumulative_fitness)
// on choisit 2 parents avec la plus grande cumulative fitness
for i = 1 to NB_CHILDREN do
child ← crossover(parents)
// On obtient 1 enfant avec une probablité de CROSSOVER = 0.8 sinon
// il sera une copie d'un de ses deux parents
// on doit verifier que l'enfant respecte les contraintes au dessus
mutation(enfant)
// On effectue une mutation sur l' enfant avec une probablité de MUTATION = 0.2
// en verifiant les contraintes
update_population(population, enfant)
// On met à jour la population en ajoutant l'enfant
// à la population initiale, remplaçant ainsi un individu
//existant qui a la plus faible fitness
generation ← generation + 1
best_indiv_p ← best_fitness(population) // Meilleur individu de cette population
if best_indiv_p est meilleur que best_solution_global:
best_solution_global ← best_indiv_p
Ce projet permet de générer automatiquement un rapport PDF pour toutes les camionnettes à partir :
- d’un fichier CSV d’adresses et coordonnées GPS,
- d’un fichier texte de résultats (chemins, temps, distances).
Le PDF contient :
- Une page de synthese qui contient une carte de trajet de tous les livreurs
- Pour chaque livreur:
- Une carte du trajet (fond OpenStreetMap, tracé du parcours)
- Un tableau détaillant chaque étape (lieu, adresse, heure d’arrivée, heure de départ)
- Les données de synthèse : distance totale, consommation estimée, coût du carburant
-
data/pharmacies_geocodec.csv
CSV contenant les adresses et coordonnées[lat, long]de chaque point de livraison.ATTENTION, le Cerp donc le point de départ doit par logique être l'adresse no 1.
Exemple :
CERP, 1 rue du Départ, 75014 Paris, [48.8381, 2.3208] Pharmacie Alpha, 10 avenue de la République, 75011 Paris, [48.8655, 2.3702] Pharmacie Beta, 25 rue de Vaugirard, 75006 Paris, [48.8472, 2.3205] Pharmacie Gamma, 5 boulevard Voltaire, 75011 Paris, [48.8575, 2.3762] Pharmacie Delta, 12 rue de la Convention, 75015 Paris, [48.8417, 2.2822] -
text_result/resultats.txt
Fichier texte listant, pour chaque livreur, le chemin suivi, les temps de trajet, et la distance totale.
Exemple :livreur 1: 0 → 1 → 2 → 0 12 10 13 distance totale : 8.5 livreur 2: 0 → 3 → 4 → 0 9 11 14 distance totale : 7.8
- Les fichiers PDF sont générés dans le dossier rapport.
- Les images de carte sont supprimées automatiquement après génération du PDF.
- Si besoin, adaptez les chemins des fichiers dans le script Python.