Bee life Parallèle sur GPU pour résoudre le problème dynamique de tournées de véhicules avec une contrainte de capacité (DCVRP)

Abstract

De nos jours, il existe encore un écart important entre les exigences et la performance des systèmes d'aide à la décision pour de nombreux problèmes tels que le problème de planification de tournées de véhicules. Ce problème consiste à concevoir un ensemble de routes optimales pour une flotte de véhicules visant à servir un nombre donné de clients. Néanmoins, de nouvelles demandes (clients) pourraient être introduites pendant qu'un plan préalable est en cours de réalisation. Par conséquent, les routes doivent être recalculées de manière dynamique. Dans cette thèse, nous proposons une nouvelle méthode d'optimisation combinatoire parallèle appelée Parallel Bees Life Algorithm (P-BLA), basée sur l'unité de traitement graphique (GPU) pour résoudre efficacement le problème dynamique de tournées des véhicules (DCVRP), en termes de temps d'exécution. La réduction de la complexité de calcul a été souvent considérée comme l'inconvénient majeur des méthodes d'optimisation classiques. L‟algorithme P-BLA a été développé en utilisant le logiciel CUDA, et a été implémenté sur GPU en se basant sur le modèle d'îlot. Nous avons réalisé, en outre, un ensemble de comparaisons entre P-BLA avec des méthodes conventionnelles comme l‟algorithme génétique, système de fourmi, recherche Tabou et avec BLA séquentiel. P-BLA a fourni des résultats efficaces obtenus à partir des benchmarks de DCVRP les plus testés.