| Titre : | 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) |
| Auteurs : | Maroua Grid, Auteur ; Noureddine Djedi, Directeur de thèse ; Salim Bitam, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2018 |
| Format : | 1 vol. (136 p.) / 30 cm |
| Langues: | Français |
| Mots-clés: | DCVRP ; k-means ; P-BLA ; Optimisation parallèle ; GPGPU. |
| Résumé : |
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. |
| Sommaire : |
Abstract ..................... Résumé ............ Publications et Communications .............................................................................................. V AVANT PROPOS ................................................ VII Table des matières .................................................. IX Liste des figures .............................................................. XI Liste des tableaux ................................................................................................................... XIV Introduction générale ................................................................................................................ 1 Problématique ....................................................................................................................... 3 Objectifs ................................................................................................................................ 3 Organisation de la thèse ........................................................................................................ 4 1. Problème de tournées de véhicules dynamique (DVRP) 1.1. Introduction ......................................................................................................................... 6 1.2. Le problème de tournées de véhicules VRP ...................................................................... 8 1.2.1. Le problème du voyageur de commerce (Traveling Salesman Problem, TSP) .......... 8 1.2.2. Définition de VRP ..................................................................................................... 10 1.2.3. Paramètres de VRP ................................................................................................... 11 1.2.4. Formulation de VRP ................................................................................................. 12 1.3. Le problème de tournées de véhicules dynamique DVRP ............................................. 14 1.3.1. Définition de DVRP .................................................................................................. 14 1.3.2. Formulation de DVRP .............................................................................................. 16 1.3.3. Différence entre le VRP statique et le DVRP ........................................................... 18 1.3.4. Mesures de dynamisme et classification des DVRPs ................................................ 20 1.3.5. Exigences techniques ................................................................................................ 24 1.3.6. Exemples du monde réel de DVRP ........................................................................... 26 1.3.7. Variantes de DVRP ................................................................................................... 27 1.4. Conclusion .......................................................................................................................... 31 2. Les méthodes de résolution de DVRP (Etat de l’art) 2.1. Introduction ....................................................................................................................... 32 2.2. Les méthodes séquentielles ............................................................................................... 33 2.2.1. Stratégies simples ...................................................................................................... 33 2.2.2. Les heuristiques classiques ....................................................................................... 36 .2.2.2 Les méthaheuristiques ............................................................................................... 40 2.3. Les méthodes parallèles .................................................................................................... 49 2.4. Conclusion .......................................................................................................................... 55 3. Approche BLA-DCVRP (notre contribution) 3.1. Introduction ....................................................................................................................... 56 3.2. Les composants de résolution de DCVRP ....................................................................... 57 3.2.1. Le gestionnaire d'événement ..................................................................................... 58 3.2.2. La méthode de résolution .......................................................................................... 59 3.3. Optimisation par colonie d’abeilles (Etat de l’art) ......................................................... 63 3.3.1. Les abeilles dans la nature......................................................................................... 64 3.3.2. Algorithme de la vie des abeilles (Bees Life Algorithm, BLA) ................................ 66 3.4. BLA séquentielle pour le DCVRP .................................................................................... 68 3.4.1. Codage de la solution (représentation des individus)................................................ 69 3.4.2. Initialisation .............................................................................................................. 70 3.4.3. Evaluation des individus ........................................................................................... 70 3.4.4. Tri de population ....................................................................................................... 71 3.4.5. Reproduction ............................................................................................................. 72 3.4.6. Remplacement ........................................................................................................... 74 3.4.7. Recherche de nourriture ............................................................................................ 75 3.4.8. Critère d'arrêt ............................................................................................................ 75 3.5. Conclusion .......................................................................................................................... 76 4. Métaheuristiques parallèles (Etat de l’art) 4.1. Introduction ....................................................................................................................... 77 4.2. Les raisons de parallélisation des métaheuristiques ....................................................... 78 4.3. La modélisation parallèle des métaheuristiques ............................................................. 79 4.4. Les architectures parallèles .............................................................................................. 80 4.5. Les schémas d’exécution des algorithmes évolutionnaire .............................................. 82 4.5.1. Modèle maître-esclave (Master-Slave) ..................................................................... 82 4.5.2. Modèle d‟exécutions indépendantes (Independent Runs) ......................................... 83 4.5.3. Modèle d'îlot (island model) ..................................................................................... 84 4.5.4. Modèle cellulaire des algorithmes évolutionnaires (Cellular EAs) ........................... 85 4.5.5. Modèles hybrides ...................................................................................................... 85 4.6. Métaheuristiques parallèles sur GPU .............................................................................. 86 4.6.1. Architecture GPU ...................................................................................................... 86 4.6.2. Défis des GPUs pour les métaheuristiques ............................................................... 88 4.6.3. Calcul généraliste par GPU (GPGPU) ...................................................................... 89 4.7. Conclusion .......................................................................................................................... 92 5. BLA parallèle (P-BLA) pour résoudre le DCVRP (notre contribution) 5.1. Introduction ....................................................................................................................... 93 5.2. BLA parallèle (P-BLA) ..................................................................................................... 94 5.2.1. Kernel d‟initialisation ............................................................................................... 97 5.2.2. Kernel d‟évaluation ................................................................................................... 97 5.2.3. Kernel de tri des colonies d'abeilles .......................................................................... 98 5.2.4. Kernel de reproduction ............................................................................................ 100 5.2.5. Kernel de remplacement ......................................................................................... 101 5.2.6. Kernel de la recherche de nourriture ....................................................................... 101 5.3. Conclusion ........................................................................................................................ 102 6. Étude expérimentale et résultats 6.1. Introduction ..................................................................................................................... 103 6.2. Description des benchmarks ........................................................................................... 103 6.3. Réglage des Paramètres .................................................................................................. 104 6.4. Résultats et Discussion .................................................................................................... 105 6.4.1. Mesure de performance dynamique ........................................................................ 108 6.4.2. Accélération par GPU ............................................................................................. 109 6.5. Conclusion ........................................................................................................................ 111 Conclusion générale et perspectives ...................................................................................... 113 Bibliographie ........................................................................................................................... 115 Annexe A : Spécification de format pour les instances de DVRP ....................................... 124 Annexe B: Meilleures solutions trouvées .............................................................................. 132 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/3841 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/125 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
