Optimisation de tournées sous contraintes — PLNE & colonie de fourmis

CESI École d'Ingénieurs · 2025

Projet de recherche opérationnelle (contexte ADEME, mobilité durable) : modélisation d'un problème de tournées de livraison avec routes pénalisées et contraintes d'ordre entre visites, résolution exacte en programmation linéaire en nombres entiers (PuLP), métaheuristique par colonie de fourmis et étude expérimentale comparée, le tout en Python.

Projet de recherche opérationnelle réalisé au CESI, sur un cas inspiré des appels à projets de l'ADEME en faveur d'une mobilité plus sobre : optimiser les tournées de livraison d'un véhicule lorsque certaines routes sont coûteuses ou bloquées et que certaines visites doivent obligatoirement en précéder d'autres.

Le problème a d'abord été formalisé comme une extension du voyageur de commerce (graphe orienté pondéré, variables binaires de passage, variables d'ordre, contraintes de précédence) — un problème NP-difficile. Nous l'avons résolu de manière exacte par programmation linéaire en nombres entiers avec PuLP sur des instances générées aléatoirement avec NetworkX, puis de manière approchée avec une métaheuristique de colonie de fourmis (phéromones, évaporation, paramètres alpha/bêta) pour passer à l'échelle.

Une étude expérimentale (pandas, seaborn) compare coût des solutions et temps de calcul selon le nombre de villes, le nombre de fourmis, le nombre d'itérations et le taux d'évaporation. Un bon exercice pour relier modélisation mathématique, implémentation et analyse de résultats.

• Python
• Recherche opérationnelle
• PLNE
• PuLP
• NetworkX
• Métaheuristiques