Tous les projets
CESI · 3e année
OptiMap
Calculer une tournée de livraison quasi optimale sur une carte donnée.
Terminémai 2024 – juin 2024

Développer une application qui détermine l'une des meilleures tournées de livraison sur une carte donnée. Le problème étant très proche de celui du voyageur de commerce, nous sommes partis de ses méthodes de résolution.
Démarche
- 1Modélisation mathématique : un graphe dont les sommets sont les villes et les arêtes les routes
- 2Étude de la complexité du problème et des algorithmes pour le résoudre
- 3Implémentation de six approches : colonie de fourmis, génétique, recuit simulé, recherche tabou, essaims particulaires, heuristique TSP
- 4Mesure des performances (temps de calcul et longueur trouvée) et comparaison

Conclusion : aucun algorithme ne gagne partout. L'application choisit donc le plus adapté selon la taille de la carte et les préférences de l'utilisateur. Devant le jury, nous avons proposé des évolutions : plusieurs véhicules sur une même tournée, itinéraire simple d'un point A à un point B, historique des tournées.