Optimisation des Tournées de Livraison
Un projet de recherche opérationnelle pour l'ADEME
Un projet de recherche opérationnelle pour l'ADEME
Dans le cadre d'un appel à manifestation d'intérêt lancé par l'ADEME (Agence de l'Environnement et de la Maîtrise de l'Energie), notre structure CesiCDP propose une solution pour optimiser les déplacements lors de tournées de livraison.
Développer des algorithmes qui permettent de calculer sur un réseau routier une tournée optimale reliant un sous-ensemble de villes, puis revenir au point de départ, afin de minimiser la durée totale du parcours.
Modélisation du problème - Représentation formelle des données et objectifs à optimiser
Analyse de complexité - Étude théorique de la complexité du problème
Implémentation algorithmique - Développement en Python d'au moins deux méthodes de résolution
Étude statistique - Analyse du comportement expérimental des algorithmes développés
Contraintes supplémentaires - Intégration d'au moins deux contraintes additionnelles (fenêtres temporelles, restrictions de passage, etc.)
Nous sommes une équipe d'étudiants en 1ère année du cycle ingénieur en alternance (FISA A3) à CESI Nanterre.
FISA A3 - CESI Nanterre
FISA A3 - CESI Nanterre
FISA A3 - CESI Nanterre
FISA A3 - CESI Nanterre
Consultez notre code et les différentes méthodes de résolution sur notre dépôt GitHub.
Accéder au GitHubSuivez notre avancement et l'organisation des tâches sur notre tableau Trello.
Accéder au TrelloJeu de données utilisé pour tester nos algorithmes d'optimisation
Document détaillant notre approche de modélisation formelle du problème
Énoncé détaillé du projet fourni par l'ADEME
Consultez nos documents de recherche sur les différents aspects du problème d'optimisation des tournées.
Analyse des problèmes NP-complets dans le contexte de la théorie des graphes et leur application à l'optimisation des tournées
Démonstration de la NP-complétude du cycle hamiltonien et de ses variantes avec contraintes supplémentaires (contraintes de ressources énergétiques, pondération des arêtes) par réduction depuis le problème 3-SAT
Démonstration de la NP-complétude du cycle hamiltonien et de ses variantes avec contraintes supplémentaires (contraintes de ressources énergétiques, pondération des arêtes) par réduction depuis le problème du voyageur de commerce (TSP)
D'autres documents de recherche seront ajoutés au fur et à mesure de l'avancement de nos travaux.
Dans cette section, nous présentons notre première livraison concernant la modélisation du problème d'optimisation des tournées.
Afin de modéliser le problème, nous avons créé un outil en javascript qui permet de créer des graphes avec les contraintes telles que les bornes de recharge et les pondérations des arêtes
Compte rendu du premier livrable au format PDF
Version Jupyter Notebook du compte rendu (format zip)