Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones

Abstract

Este trabajo trata de profundizar en los conocimientos existentes sobre el uso combinado de vehículos terrestres como camiones de reparto y nuevos vehículos aéreos no tripulados como lo son los UAVs o los drones en tareas de reparto a domicilio. Este tipo de tareas han ganado popularidad en la última década debido al incremento de las ventas a través de Internet y su correspondiente necesidad de enviar los paquetes a sus clientes. El bajo coste de este tipo de vehículos, sumado al ahorro de tiempo por trayecto al evitar el tráfico en las ciudades ha permitido que se hayan elaborado numerosos trabajos que buscan modelar y resolver este tipo de problemas. La planificación de las rutas es un problema NP-Hard, por lo que para problemas a gran escala (cientos e incluso miles de nodos) es necesario emplear algoritmos heurísticos que permitan hallar una solución cercana al óptimo sin que el tiempo de computación se eleve exponencialmente. Por ello, se ha tomado como referencia el estado del arte actual y se ha tratado de mejorar un algoritmo heurístico mediante el uso de ejecución en paralelo. La ejecución en paralelo o también conocida como multihilo permite acelerar la ejecución de algoritmos con alto coste computacional de tal forma que se emplean los recursos computacionales de forma óptima. Para conseguir esta reducción del tiempo de ejecución de un algoritmo, es necesario en cambio sacrificar otros aspectos de la heurística original, y en este trabajo se tratará de medir cuales son las ventajas y desventajas de emplear esta técnica.

This work tries to deepen the existing knowledge on the combined use of land vehicles such as delivery trucks and new unmanned aerial vehicles such as UAVs or drones in home delivery tasks. These types of tasks have gained popularity in the last decade due to the increase in sales over the Internet and the corresponding need to send the packages to their customers. The low cost of this type of vehicles, added to the saving of time per journey by avoiding traffic, has led to the development of numerous works that seek to model and solve this type of problems. Route planning is a NP-Hard problem, so for large-scale problems (hundreds and even thousands of nodes) it is necessary to use heuristic algorithms that allow finding an optimal solution without the computation time rising exponentially. Therefore, the current state of art has been taken as a reference and has been made an attempt to improve a heuristic algorithm through the use of parallel execution. The execution in parallel or also known as multithreading allows to accelerate the execution of algorithms with high computational cost in such a way that computational resources are used optimally. To achieve this reduction in the execution time of an algorithm, it is necessary to sacrifice other aspects of the heuristics. This work tries to measure the advantages and disadvantages of using this technique.