Optimización de las misiones de un dron para la monitorización de objetivos con técnicas metaheurísticas Tabu Search

Abstract

En los últimos años, el dron o UAV (Unmanned Aerial Vehicle) se ha convertido en objeto de múltiples estudios que dan cobertura a los problemas de monitorización de objetivos o logística de redes de distribución. Al no estar condicionado por las restricciones que imponen las infraestructuras actuales, su uso permite mejorar la eficiencia, seguridad y fiabilidad del servicio. Además, los últimos avances tecnológicos como el desarrollo de materiales más ligeros y chasis más robustos, mejores sensores y algoritmos de control o la paulatina mejoría en la capacidad de las baterías, han acelerado su uso a gran escala. En este TFM, un único dron debe monitorizar a un conjunto de clientes distribuidos en un plano, realizando múltiples misiones no coincidentes en el tiempo, minimizando el número de baterías y la distancia total recorrida. El problema está sujeto a restricciones de capacidad de batería y disco duro del dron. El consumo de energía se modeliza como una función lineal que considera dos tipos de movimientos: traslación entre objetivos y hovering sobre el objetivo. Este proyecto contribuye con una herramienta heurística parametrizable que resuelve el problema planteado de forma eficiente. La herramienta consiste en una aplicación C++ en la que se ha desarrollado una metaheurística basada en el método Gradual Tabu Search. Se presenta evaluación experimental de la eficiencia de la herramienta para generar soluciones aproximadas a este problema NP-hard de forma eficiente. Tal y como veremos, de la heurística resultarán: la cantidad de viajes y la secuencia óptima del dron para cumplir con las exigencias de problema. Para un dataset de 8 escenarios representativos, se realiza análisis de sensibilidad sobre los parámetros del algoritmo con el fin de mejorar la identificación de las características respecto de la calidad de la solución aproximada resultante y de los tiempos de computación.