Méthodes d'approximation au problème de routage de véhicule pour une gestion de flotte de drones ; Approximation methods to vehicle routing problem for a drone fleet management
Titel:
Méthodes d'approximation au problème de routage de véhicule pour une gestion de flotte de drones ; Approximation methods to vehicle routing problem for a drone fleet management
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...