All projects
Shipped

Data Science | School | 3 min read

EcoRoute.

Delivering faster and polluting less, without having to choose. A heuristic VRP solver with graph theory and statistics to plan delivery rounds that respect both the clock and the planet.

🌿 Projet EcoRoute - Optimisation des tournées de livraison durables

Introduction

Depuis les années 1990, la prise de conscience mondiale sur la nécessité de réduire les émissions de gaz à effet de serre a conduit à des engagements tels que le protocole de Kyoto et l'Accord de Paris. 🌍 Le projet EcoRoute s'inscrit dans cette démarche en proposant des solutions innovantes pour optimiser les tournées de livraison, réduisant ainsi leur impact environnemental.

🎓 Thèmes académiques

  • Algorithmique et optimisation combinatoire
  • Algorithmique et optimisation ETU
  • Graphes et modélisation
  • Problème NP complet
  • Méthodes exactes
  • Métaheuristiques

Objectifs d'apprentissage

Modélisation Graphe

  • [4] Identifier les concepts et usages de la théorie des graphes.
  • [5] Modéliser un problème concret à l’aide d’un graphe.
  • [3] Résoudre un problème concret à l’aide d’un graphe.

Analyse de complexité

  • [4] Analyser la complexité asymptotique d'un algorithme.
  • [3] Utiliser les notions théoriques de complexité algorithmique.
  • [4] Étudier la complexité d’un problème de décision.
  • [2] Estimer la difficulté d’un problème d’optimisation.
  • [2] Définir la bonne approche pour résoudre un problème d’optimisation.
  • [4] Identifier si le problème est NP-difficile.

Recherche Opérationnelle (RO)

  • [2] Distinguer les différentes classifications des problèmes d’optimisation.
  • [3] Décrire les modèles de calcul utilisés en recherche opérationnelle.
  • [4] Examiner la nature du problème d'après l'énoncé du besoin.

Programmation linéaire

  • [5] Modéliser et résoudre un problème d'optimisation à l'aide de la programmation linéaire.
  • [2] Définir mathématiquement le problème.

Métaheuristiques

  • [5] Modéliser un problème d'optimisation selon le formalisme d'une métaheuristique.
  • [3] Réaliser un programme implémentant une métaheuristique.
  • [4] Analyser le comportement expérimental d'une métaheuristique.

Contexte

L’ADEME (Agence de l’Environnement et de la Maîtrise de l’Énergie) a lancé un appel à projets pour promouvoir des solutions de mobilité durable. 🚛 En réponse, l’équipe CesiCDP a décidé de se concentrer sur l’optimisation des tournées de livraison. Ce projet vise à relever des défis logistiques majeurs tout en minimisant l’impact écologique.

Objectifs

  • 🌱 Réduction des distances parcourues : Minimiser les trajets pour diminuer les émissions de CO₂.
  • 📦 Respect des contraintes logistiques : Prendre en compte les fenêtres de livraison, les capacités des véhicules et le trafic.
  • ⚙️ Efficacité opérationnelle : Proposer un outil d’aide à la décision pour les gestionnaires de tournées.

Approche

Le projet repose sur des techniques avancées d’optimisation combinatoire et des algorithmes tels que :

  • 🔍 Méthodes exactes : Pour résoudre des problèmes de petite taille avec précision.
  • 🚀 Métaheuristiques : Pour traiter des instances plus grandes et complexes.

Étapes du projet

  1. 📝 Modélisation du problème : Formaliser les données, les contraintes et les objectifs.
  2. 💡 Conception algorithmique : Développer des solutions basées sur des algorithmes performants.
  3. 🔬 Étude expérimentale : Tester les algorithmes sur des cas réels et analyser les résultats.
  4. 📊 Livrables et présentation : Fournir un rapport détaillé et démontrer les performances du système.

Pourquoi ce projet est important ?

  • 🌍 Impact environnemental : Réduction des émissions de gaz à effet de serre grâce à des tournées optimisées.
  • 🚚 Innovation logistique : Intégration de contraintes réalistes comme le trafic dynamique et les flottes hétérogènes.
  • 📈 Applications variées : Livraison de colis, gestion des déchets, distribution de produits alimentaires, etc.

👥 Équipe du projet

Rejoignez-nous ! 🚀

Le projet EcoRoute est une opportunité de contribuer à un avenir plus durable tout en relevant des défis techniques passionnants. Si vous êtes intéressé(e) par la recherche opérationnelle, l’optimisation ou la logistique, n'hésitez pas à forker, proposer des PR ou à nous contacter pour en savoir plus !