Optimisation Discrète VRPTW
Liens
Objectifs
Le Problème de VRP (Vehicle Routing Problem) est un défi complexe qui se pose dans de nombreux domaines nécessitant une gestion optimale des ressources logistiques et du transport. Il s’agit d’un problème d’optimisation visant à déterminer les itinéraires les plus efficaces pour un ensemble de véhicules afin de desservir un ensemble de clients avec des contraintes spécifiques.
Le but de ce projet était donc de résoudre ce problème en utilisant différentes métaheuristiques afin d’obtenir les meilleurs résultats.
Technologies Utilisées
- Langages de Programmation : Java
- Algorithmes Métaheuristiques :
- Recherche Tabou
- Recuit Simulé
- Descente de Gradient
Travail Réalisé
Pour résoudre ce problème, un code a donc été développé. Le code permet dans un premier temps de créer des routes de livraisons aléatoires puis de les afficher via une interface graphique.
Ensuite, différentes classes avec différentes stratégies et métaheuristiques ont été implémentées afin de pouvoir les analyser.
Finalement, un grand nombre de tests ont été réalisés dans différentes conditions et avec différentes métaheuristiques afin de déterminer la meilleure (voir le rapport pour plus de détails).
Conclusion
Ce projet m’a permis d’en apprendre plus sur la manière de résoudre des problèmes complexes d’optimisation. On peut penser au problème du sac à dos ou encore au voyageur de commerce.
J’ai pu voir qu’il n’était pas possible de trouver la solution optimale de ce genre de problème au vu du nombre important de solutions et du temps que cela prendrait. Ainsi, le but était d’appliquer des méthodes pour trouver des solutions assez bonnes et proches de la solution optimale.
J’ai trouvé cela captivant de résoudre un problème de cette façon et de penser au fait que dans les situations du quotidien ou pour des problèmes d’entreprise il faut faire des concessions. En effet, parfois trouver la solution optimale d’un problème n’est pas forcément nécessaire si on a déjà une bonne solution.
Ce projet fut ainsi très enrichissant. C’était une première d’avoir un projet de ce type où nous avons une certaine liberté sur l’implémentation et sur la résolution du problème. Pouvoir appliquer les concepts vus en cours et les tester sur un problème lié au contexte d’entreprise était vraiment motivant, cela m’a beaucoup plu et intéressé.