Algorithme inspiré des réactions chimiques amélioré pour résoudre le problème de tournées de véhicules multi-dépôts

Abstract

De nos jours, les ingénieurs sont confrontés à une variété de problèmes de complexité grandissante. Ces derniers apparaissent dans différents secteurs tels que les problèmes detransport.Trouver la solution optimale dans un délai raisonnable est devenu une priorité essentielle pour toute entreprise. Notre travail porte sur le problème de Tournées de Véhicules Multi-Dépôts (Multi-Dépôts Véhicule Routing Problem MDVRP) qui est une extension de VRP classique,Il appartient à la classe des problèmes dire NP-difficiles. L’objectif est de servir un ensemble de clients à partir d’ensemble de dépôts et à travers d’un ensemble de véhicules tout en minimisant un 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. De plus, des problèmes de taille réaliste sont visés. Le but de ce mémoire est de développer une méthode efficace et simple pour la résolution de MDVRP. Pour atteindre notre objectif, nous proposons d’améliorer et d’adapter l’algorithme inspiré des réactions chimiques (ChemicalReactionOptimization CRO). Pour tester les performances de notre méthode proposée, nous l’avons testé et validé sur un ensemble de tests provenantdela littérature. Les études expérimentales faites ont montré l’efficacité de l’approche proposée de trouver des solutions de bonne qualité pour le problème étudiée dans ce travail. Mots-clés : l’optimisation combinatoire, Problème de tournées de véhicules multi - dépôts(MDVRP), Algorithme inspiré des réactions chimiques (CRO), heuristique « Route first-cluster second ».