Un projet académique d'optimisation des tournées de distribution de produits pétroliers (essence et gasoil).
Titre : Optimisation des tournées de distribution de produits pétroliers
| Élément | Détail |
|---|---|
| Université | Université d'Abomey-Calavi (UAC) |
| Établissement | Institut de Formation et de Recherche en Informatique (IFRI) |
| Niveau | Licence IA |
| Enseignement | Outils de résolution de problèmes d'optimisation |
| Année académique | 2025-2026 |
| Équipe pédagogique | Dr Ing. (MC) HOUNDJI V. Ratheil, Ing. TIKPON Linuse, Ing. TONOU Mélène |
| Groupe | N°3 — Merveille, Sobour et Rosas |
Une entreprise de distribution de produits pétroliers planifie les tournées quotidiennes de ses camions-citernes pour approvisionner un réseau de stations-service à partir de plusieurs dépôts pétroliers.
Tournée des camions — Chaque camion, géré par un prestataire externe, commence sa tournée à un garage et doit y retourner à la fin (pas nécessairement le même garage de départ).
Capacité et produit — Chaque camion a une capacité limitée et ne peut transporter qu'un seul type de produit (essence ou gasoil) par tournée.
Dépôts et stations — Chaque dépôt dispose d'un stock pour chaque produit. Chaque station-service exprime une demande pour un ou plusieurs produits.
Satisfaction de la demande — Les demandes des clients doivent être satisfaites intégralement.
Chargement — Chaque camion visite au plus un dépôt pour se charger.
- Les stocks disponibles dans l'ensemble des dépôts sont suffisants pour satisfaire la demande totale.
- Les distances entre tous les sites (garages, dépôts, stations) sont connues.
- Les temps de chargement et déchargement sont considérés comme négligeables.
- Tous les sites sont accessibles à tout moment.
Minimiser la distance totale parcourue par l'ensemble de la flotte tout en respectant toutes les contraintes opérationnelles.
La structure ci-dessous reflète l'état actuel du code.
.
├── benchmark.py # Génère les graphiques et le CSV de benchmark à partir de results/*
├── execute_all.sh # Exécute toutes les méthodes sur toutes les instances
├── main.py # Point d'entrée pour résoudre une instance donnée
├── code/
│ ├── models/
│ │ ├── exact.py # Solveur exact
│ │ ├── h_alns.py # Heuristique ALNS (Adaptive Large Neighborhood Search)
│ │ ├── pso.py # Solveur PSO (Particle Swarm Optimization)
│ │ └── sa.py # Solveur SA (Recuit simulé)
│ └── tools/
│ ├── generate_levels.py # Génération d'instances (niveaux)
│ ├── generateur.py # Générateur utilitaire
│ ├── utils.py # I/O des instances/solutions, helpers
│ ├── validation.py # Validation des solutions et rapports
│ └── visualisation.py # Visualisation des instances et solutions
├── docs/
│ ├── exact.pdf
│ ├── sa.pdf
│ ├── PSO_README.md
│ └── Projet_Optimisation-2025-26.pdf
├── instances/ # Fichiers JSON des instances (level01..level07)
├── results/ # Sorties par méthode (exact/alns/pso/sa)
├── plots/ # Figures de benchmark générées
├── tests/
│ ├── test_models.py
│ └── test_tools.py
├── pyproject.toml
├── requirements.txt
├── README.md
└── uv.lock
- Python 3.12 ou supérieur
- git
- pip (ou
uv)
git clone https://github.com/rosasbehoundja/vrp_problem.git
cd vrp_problempython3 -m venv .venv
source .venv/bin/activate
pip install -r requirements.txtpython -m venv .venv
.\.venv\Scripts\Activate
pip install -r requirements.txt# Installer uv si nécessaire
pip install uv
# Synchroniser les dépendances
uv installpip install -e .Le script main.py charge une instance JSON et exécute la méthode choisie.
- Méthodes disponibles:
exact,alns,pso,sa - Arguments communs:
instance(obligatoire): chemin vers le fichier JSON (ex:instances/level01.json)-m, --method: méthode de résolution (défaut:alns)-t, --time-limit(int): temps limite pourexactetalns(défaut: 30s)-i, --iterations(int): nombre d'itérations pouralns,pso,sa(défaut: 1500)-p, --particles(int): nombre de particules pourpso(défaut: 50)--no-plot: désactive l'affichage du graphe--save-dir: dossier de sortie (défaut:results)
Exemples:
# ALNS sur level01
python main.py instances/level01.json -m alns -t 60 -i 2000
# PSO sur level03 avec 100 particules
python main.py instances/level03.json -m pso -p 100 -i 1500 --no-plot
# Recuit simulé (SA) sur level02
python main.py instances/level02.json -m sa -i 10000
# Solveur exact avec temps limite
python main.py instances/level04.json -m exact -t 600 --no-plotSorties:
- La solution est sauvegardée dans
results/<method>/solXX.json(XX = numéro du niveau). - Un rapport de validité peut être inclus dans
solution["report"]. - Si
--no-plotn'est pas fourni, une visualisation est affichée.
Le script bash execute_all.sh parcourt les niveaux 01..07 et exécute chaque méthode avec des paramètres par défaut raisonnables.
bash execute_all.sh- Un fichier de log
execution_log_YYYYMMDD_HHMMSS.txtest créé. - Les résultats sont stockés sous
results/alns,results/sa,results/pso,results/exact.
Le script benchmark.py agrège les résultats et produit des figures publication-ready ainsi qu'un CSV de synthèse.
Options principales:
--results-dir(défaut:results)--save-dir(défaut:plots)--methods(liste; défaut:exact alns pso sa)--levels(liste; défaut:01 02 03 04 05 06 07)--no-show(désactive l'affichage interactif)--log-objective(axe Y en log pour les objectifs)--style(standardouacademic; défaut:academic)--combined(génère la figure combinée)
Exemples:
# Benchmark complet avec style académique
python benchmark.py --results-dir results --save-dir plots --no-show --style academic
# Limité aux méthodes heuristiques
python benchmark.py --methods alns pso sa --no-show
# Avec échelle log pour l'objectif
python benchmark.py --log-objective --no-showSorties:
plots/benchmark_objectives.png|pdfplots/benchmark_times.png|pdfplots/benchmark_quality_gap.png|pdfplots/benchmark_statistics.png|pdfplots/benchmark_combined.png|pdf(si--combined)plots/benchmark_summary.csv
python -m pytest -qPour toute question ou contribution, ouvrez une issue ou effectuez une pull request.