Résumé:
Le domaine de l’optimisat ion combinatoire est fortement présent dans de nombreux secteurs de
recherche et d’industrie. Parmi les secteurs, où on trouve plus de problèmes d’optimisat ion : les
secteurs de transport et planification de production. En effet, plusieurs problèmes sont issus de
ces deux secteurs comme le problème de localisation des usines, le problème de tournées de
véhicules…etc.
Le problème de tournées de véhicules (VRP) est l’un des problèmes les plus connus dans la
recherche opérationnelle. Dans le cadre de ce travail de recherche, nous sommes intéressés
d’étudier le problème de tournées de véhicules multi-dépôts (Multi-Depots Vehicule Routing
Problem MDVRP) qui est une extension de VRP classique. Ce problème est NP-difficiles
permettant de déterminer les tournées de véhicules associées à chaque dépôt pour satisfaire un
ensemble de clients, tout en minimisant le coût total de la livraison.
La motivation de ce travail est d'aborder un problème difficile et dans une version encore peu
étudiée dans la littérature, comportant des capacités limitées à la fois pour les dépôts et les
véhicules réalisant les tournées. De plus, des problèmes de taille réaliste sont visés.
L’object if de ce mémoire est de développer une méthode efficace, simple et robuste pour la
résolution de MDVRP. Dans le but de réaliser notre objectif, nous avons proposé une adaptation
de l’algorithme inspiré des réact ions chimiques (CRO) pour ce problème.
Afin de tester la performance de l’approche que nous avons proposée, nous l’avons testée et
validée sur un ensemble de tests provenant de la littérature. Les études expérimentales faites
ont montré l’efficacité de la méthode proposée de trouver des solutions de bonne qualité pour
le problème étudiée dans ce mémoire.
Mots-clés : Méthodes d’optimisation combinatoire, Problème de tournées de véhicules, Problème de tournées de véhicules multi-dépôts Méta-heuristiques, Algorithme inspiré des réactions chimiques (CRO).
