Approximation methods to vehicle routing problem for a drone fleet management
Méthodes d'approximation au problème de routage de véhicule pour une gestion de flotte de drones
Résumé
Nowadays, drone plays a big role in civilian purposes, and it will getting bigger and more important in the future. Because of it’s flexibility and versatility, the application of drone is more extensive. Incertain fields of implementation, applying a team of drones will improve the effectiveness and efficiency of the application, such as in search and rescue, military purpose, agriculture and surveillance. Recently, there is a challenging issue to manage a team of drones in order to achieve the given mission. This issue opens many research opportunities, and our project is made to answer this challenge, to develop a platform for managing a fleet of drones. Among several approaches, vehicle routing problem (VRP) is one of a considered study to answer this challenge, in order to allocate the tasks and find the best path for each drone, with several constraints to be considered. There are many methods to solve VRP, and could be categorized into two groups i.e. exact and approximation method. But since VRP is classified as an NP-hard optimization problem, an approximation method is considered to be implemented in this project. Genetic Algorithm (GA), an approximation method which designed by an inspiration to the evolutionary ideas of genetic and natural selection, is applied in this project, since it is one of most used algorithm to solve VRP, among several approximation method. We observed that GA is suitable to be implemented in this project, but when the number of to-be-visited-points is hugely augmented, the number of iterations to get a satisfactory result would be extremely increased. This issue led us to hybridize GA with Clarke and Wright’s saving algorithm (SA) in order to generate the initial population, so that it is no longer randomly generated as usually done. Eventually, this proposed hybrid method can improve the performance of the algorithm very satisfactorily, and reduce the number of iteration more than 90%. Furthermore, a dynamic scenario in VRP is taken into account in this work i.e. an emerge of one or several new points that appear once the mission is already launched, and require a visit by a single drone. To deal with this dynamic scenarios, a Reverse Open Vehicle Routing Problem (ROVRP) is considered to be implemented. We decide to choose a heuristic method in solving the ROVRP, as it is classified as an NP-hard optimization problem, and we prefer to apply Clarke and Wright’s Saving Algorithm (SA) in this project, due to their speed and simplicity. In our point of view, speed is one most considerable thing in choosing algorithm to solve dynamic scenario in VRP. Our proposed method is devided into two phases i.e. clustering and routing. And the experimental results show that our proposed method can give more than 95% accuracy. In order to simulate and investigate the proposed methods, a Graphical User Interface (GUI) is developed. There are some available framework to develop this tool, and Netlogo is considered as the chosen framework.
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.
Origine : Version validée par le jury (STAR)