Optimisation de Tournées de Véhicules
Résolution d'un problème TSP/VRP avec contraintes personnalisées en appliquant méthodes exactes et métaheuristiques.
Contexte du projet
Ce projet a été réalisé dans le cadre de mon cursus à CESI école d'ingénieurs. L'objectif était de résoudre un problème pratique d'optimisation de tournées de véhicules, combinant les fondamentaux de la recherche opérationnelle avec des techniques algorithmiques avancées.
Le défi majeur consistait à minimiser les coûts de livraison, la distance dans notre cas, tout en satisfaisant des contraintes métier complexes : restrictions de routes, dépendances entre livraisons/collectes, et propriétés mathématiques du cycle hamiltonien.
Ce projet a demandé une approche rigoureuse : formulation mathématique, implémentation algorithmique, et validation expérimentale complète.
Approche et méthodologie
Le projet a suivi une démarche scientifique structurée, du problème mathématique à la validation expérimentale :
1. Formulation mathématique
- Définition rigoureuse du problème (TSP/VRP avec contraintes)
- Modélisation en programmation linéaire (PL)
- Fonction objectif et contraintes mathématiques explicites
2. Résolution exacte
- Solveur PL pour trouver la solution optimale (petites instances)
- Évaluation de la complexité (NP-difficile)
- Benchmark sur instances de référence
3. Résolution approchée - Métaheuristique
- Colonie de fourmis (ACO) : Algorithme inspiré du comportement collectif des fourmis
- Phéromones virtuelles pour explorer et exploiter l'espace des solutions
- Tunage des paramètres (évaporation, intensité, visibilité)
4. Étude paramétrique et expérimentation
- Plan d'expérience
- Analyse de sensibilité des paramètres de l'ACO
- Visualisations graphiques et statistiques des résultats
- Comparaison approches exacte vs approchée
Contraintes et spécificités du problème
Le projet intégrait deux contraintes métier sélectionnées parmi une liste disponible :
Restrictions d'arêtes
Certaines routes peuvent être coûteuses ou interdites (terrains difficiles d'accès, routes fermées, péages). Cette contrainte rend l'espace de recherche non-euclidien et complexifie l'optimisation.
Dépendances de visite
Une livraison doit obligatoirement précéder une collecte (ex : livrer de la marchandise avant de la reprendre). Cette contrainte crée des ordres partiels sur les nœuds et limite drastiquement l'ensemble des solutions valides.
Ces deux contraintes, au-delà des classiques (cycle hamiltonien, inégalité triangulaire), reflètent des situations réalistes en logistique.
Livrables et résultats
L'entièreté du projet a été implémentée dans un notebook Jupyter intégrant :
Code et algorithmes
- Implémentation des solveurs (PL et ACO)
- Génération d'instances test et instances de référence
- Mécanismes de validation et vérification des contraintes
Résultats et visualisations
- Graphiques de convergence de l'ACO
- Heatmaps d'analyse paramétrique
- Comparaisons coûts exact vs approché
- Visualisations des tournées optimales (représentation graphique)
- Tableaux de synthèse et statistiques détaillées
Documentation
- Explications détaillées de chaque étape
- Conclusions et recommandations
- Perspectives d'amélioration et extensions possibles
Résultats
