Recherche rapide
Fiche descriptive
Méthodes d'approximation au problème de routage de véhicule pour une gestion de flotte de drones (Document en Anglais)
Accéder au(x) document(s) : Droits d'auteur : Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Modalités de diffusion de la thèse :
Modalités de diffusion de la thèse :
Auteur : Sukarno Setyawan Ajie
Date de soutenance : 04-12-2019
Directeur(s) de thèse : Ben Atitallah Rabie
- Delot Thierry
Président du jury : Djemai Mohamed
Membres du jury : Ben Atitallah Rabie
- Delot Thierry
- Ben Othman Jalel
- Chu Feng
- Sehab Rabia
Rapporteurs : Ben Othman Jalel
- Chu Feng
Laboratoire : Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines - LAMIH
Ecole doctorale : Sciences pour l'ingénieur (SPI)
Sukarno, Setyawan Ajie
Nom
Sukarno
Prénom
Setyawan Ajie
Nationalité
ID
Date de soutenance : 04-12-2019
Directeur(s) de thèse : Ben Atitallah Rabie
Ben Atitallah, Rabie
Nom
Ben Atitallah
Prénom
Rabie
Delot, Thierry
Nom
Delot
Prénom
Thierry
Président du jury : Djemai Mohamed
Djemai, Mohamed
Nom
Djemai
Prénom
Mohamed
Membres du jury : Ben Atitallah Rabie
Ben Atitallah, Rabie
Nom
Ben Atitallah
Prénom
Rabie
Delot, Thierry
Nom
Delot
Prénom
Thierry
Ben Othman, Jalel
Nom
Ben Othman
Prénom
Jalel
Chu, Feng
Nom
Chu
Prénom
Feng
Sehab, Rabia
Nom
Sehab
Prénom
Rabia
Rapporteurs : Ben Othman Jalel
Ben Othman, Jalel
Nom
Ben Othman
Prénom
Jalel
Chu, Feng
Nom
Chu
Prénom
Feng
Laboratoire : Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines - LAMIH
Ecole doctorale : Sciences pour l'ingénieur (SPI)
Discipline : Informatique
Classification : Informatique, Sciences de l'ingénieur
Mots-clés : Problème de routage de véhiculeAlgorithme génétiqueAlgorithme de sauvegardeScénario dynamiqueProblème de routage de véhicule ouverte en reverseInterface utilisateur graphiqueA*
Routage (informatique) --Algorithmes génétiques --Drones --Interfaces graphiques (informatique) --A*
Résumé : Aujourd’hui, le drone joue un rôle important dans les activités civiles et deviendra de plus en plus important à l’avenir. Récemment, de nouvelles tendances se dirigent vers la gestion d’une flotte de drones afin de réaliser les missions données. Ce problème ouvre de nombreuses idées de recherche, et notre projet est fait pour répondre au défi, développer une plateforme de gestion de flotte de drones. Entre plusieurs approches, le problème de routage de véhicule (VRP) est une étude parfaite pour relever ce défi, afin de répartir les tâches et de trouver le meilleur chemin pour chaque drone, en tenant compte de plusieurs contraintes. Comme les VRP sont classés comme un problème d’optimisation NP-hard, une méthode d’approximation est considérée comme mise en œuvre dans ce projet. L’algorithme génétique (GA), est appliqué dans ce projet, puisqu’il s’agit de l’un des algorithmes les plus utilisés pour résoudre le VRP parmi plusieurs méthodes d’approximation. Nous avons observé que l’AG convient pour être utilisé dans ce projet, mais lorsque le nombre de points à traiter serait considérablement accru, le nombre d’itérations pour obtenir un résultat satisfaisant sera extrêmement augmenté. Ce problème nous a amenés à hybrider GA avec l’algorithme de sauvegarde (SA) afin de générer la population initiale, pour qu’elle ne soit plus générée aléatoirement comme d’habitude. Comme nous l’avons testé, cette méthode proposée peut améliorer les performances de l’algorithme de manière très satisfaisante et réduire le nombre d’itérations de plus de 90%. De plus, un scénario dynamique dans le VRP est pris en compte dans ce travail, c’est-à-dire l’émergence d’un ou plusieurs nouveaux points qui apparaissent quand la mission a déjà été lancée et qui nécessitent une visite d’un seul drone. Pour faire face à ce scénario dynamique, un problème de routage de véhicule ouvert en sens inverse (ROVRP) est considéré. Le ROVRP est utilisé pour définir un ensemble d’itinéraires de véhicules de retour au dépôt, lors de la construction de nouveaux chemins en raison d’un scénario dynamique. Nous décidons de choisir une méthode heuristique pour résoudre le ROVRP, puisqu’il s’agit d’un problème d’optimisation NP-hard, et nous préférons appliquer l’algorithme de sauvegarde (SA) à ce projet, en raison de leur rapidité et de leur simplicité. A notre point de vue, la vitesse est l’un des aspects les plus importants du choix d’un algorithme pour résoudre un scénario dynamique dans un VRP. Notre méthode proposée est divisée en deux phases : regroupement et routage. Et nos résultats expérimentaux montrent que notre méthode proposée peut donner plus de 95% de précision. Afin de simuler et d’examiner les méthodes proposées, une interface utilisateur graphique (GUI) est développée. Il existe un cadre disponible pour développer cet outil, et Netlogo est considéré comme le cadre choisi.
Classification : Informatique, Sciences de l'ingénieur
Mots-clés : Problème de routage de véhiculeAlgorithme génétiqueAlgorithme de sauvegardeScénario dynamiqueProblème de routage de véhicule ouverte en reverseInterface utilisateur graphiqueA*
Routage (informatique) --Algorithmes génétiques --Drones --Interfaces graphiques (informatique) --A*
Résumé : Aujourd’hui, le drone joue un rôle important dans les activités civiles et deviendra de plus en plus important à l’avenir. Récemment, de nouvelles tendances se dirigent vers la gestion d’une flotte de drones afin de réaliser les missions données. Ce problème ouvre de nombreuses idées de recherche, et notre projet est fait pour répondre au défi, développer une plateforme de gestion de flotte de drones. Entre plusieurs approches, le problème de routage de véhicule (VRP) est une étude parfaite pour relever ce défi, afin de répartir les tâches et de trouver le meilleur chemin pour chaque drone, en tenant compte de plusieurs contraintes. Comme les VRP sont classés comme un problème d’optimisation NP-hard, une méthode d’approximation est considérée comme mise en œuvre dans ce projet. L’algorithme génétique (GA), est appliqué dans ce projet, puisqu’il s’agit de l’un des algorithmes les plus utilisés pour résoudre le VRP parmi plusieurs méthodes d’approximation. Nous avons observé que l’AG convient pour être utilisé dans ce projet, mais lorsque le nombre de points à traiter serait considérablement accru, le nombre d’itérations pour obtenir un résultat satisfaisant sera extrêmement augmenté. Ce problème nous a amenés à hybrider GA avec l’algorithme de sauvegarde (SA) afin de générer la population initiale, pour qu’elle ne soit plus générée aléatoirement comme d’habitude. Comme nous l’avons testé, cette méthode proposée peut améliorer les performances de l’algorithme de manière très satisfaisante et réduire le nombre d’itérations de plus de 90%. De plus, un scénario dynamique dans le VRP est pris en compte dans ce travail, c’est-à-dire l’émergence d’un ou plusieurs nouveaux points qui apparaissent quand la mission a déjà été lancée et qui nécessitent une visite d’un seul drone. Pour faire face à ce scénario dynamique, un problème de routage de véhicule ouvert en sens inverse (ROVRP) est considéré. Le ROVRP est utilisé pour définir un ensemble d’itinéraires de véhicules de retour au dépôt, lors de la construction de nouveaux chemins en raison d’un scénario dynamique. Nous décidons de choisir une méthode heuristique pour résoudre le ROVRP, puisqu’il s’agit d’un problème d’optimisation NP-hard, et nous préférons appliquer l’algorithme de sauvegarde (SA) à ce projet, en raison de leur rapidité et de leur simplicité. A notre point de vue, la vitesse est l’un des aspects les plus importants du choix d’un algorithme pour résoudre un scénario dynamique dans un VRP. Notre méthode proposée est divisée en deux phases : regroupement et routage. Et nos résultats expérimentaux montrent que notre méthode proposée peut donner plus de 95% de précision. Afin de simuler et d’examiner les méthodes proposées, une interface utilisateur graphique (GUI) est développée. Il existe un cadre disponible pour développer cet outil, et Netlogo est considéré comme le cadre choisi.
Type de contenu : Texte
Format : PDF
Format : PDF
Identifiant : uvhc-ori-oai-wf-1-2767
Type de ressource : Thèse
Type de ressource : Thèse