Développement d'une méthode pour le problème de tournées de véhicules multi-dépôts

Abstract

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).