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

Equation Chapter 1 Section 1 Trabajo Fin de Master Máster en Ingeniería Industrial Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Autor: Miguel Antonio Sanz Pérez Tutor: José Miguel León Blanco Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Sevilla, 2021 ii iii Trabajo Fin de Máster Máster en Ingeniería Industrial Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Autor: Miguel Antonio Sanz Pérez Tutor: José Miguel León Blanco Profesor contratado doctor Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 iv v Trabajo Fin de Máster: Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Autor: Miguel Antonio Sanz Pérez Tutor: José Miguel León Blanco El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2021 vi vii Agradecimientos Agradecer a todos mis amigos y compañeros que me han acompañado durante este periodo de mi vida tan bueno y fructífero, pero que sin embargo es la base para un futuro que espero me permita vivir nuevas experiencias y conocer a muchas personas que me aporten tanto como ellos me han aportado a mí. Mención especial a todos los profesores que me han ayudado a llegar hasta aquí y haberme inculcado la importancia de la educación, desde primaria hasta la universidad. Y como no podría ser de otra manera, a mi familia; mi padre, mi madre y mi hermana por apoyarme en todo momento y confiar en mi incluso cuando ni yo confiaba en mis posibilidades. Por aconsejarme y educarme para llegar a lo que soy y lo que el día de mañana seré. Muchas gracias. Miguel Antonio Sanz Pérez Sevilla, 2021 viii ix Resumen 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. xvi xvii ÍNDICE DE FIGURAS Figura 1. Experimento en el sector sanitario [1] 5 Figura 2. Comparativa entre TSP básico, 1 camión + 1 dron, y el trabajo de Ham [8] 8 Figura 3. Representación gráfica de los problemas TSP y VRP 11 Figura 4. Ejemplificación de clientes servidos por distintos vehículos 16 Figura 5. Esquemaresumen de las fases de la heurística [7] 18 Figura 6. Branch and Bound aplicado a TSP 20 Figura 7. Esquema resumen heurística en paralelo 23 Figura 8. Ejemplo de un mapa de 8 clientes 29 Figura 9. Ejemplo de un mapa de 25 clientes 29 Figura 10. Izquierda: Representación de los clientes del problema 20170608T121355407419 31 Figura 11. Tiempo de ejecución en la fase 1 para distintos números de clientes y tipologías de UAVs 46 Figura 12. Tiempo de ejecución en las fases 2 y 3 para distintos números de clientes y tipologías de UAVs 46 Figura 13. Tiempo de ejecución total para distintos números de clientes y tipologías de UAVs 47 Figura 14. Valor objetivo para distintos números de clientes y tipologías de UAVs 48 Figura 15. Comparativa por tipología UAV: Variación tiempo total respecto a tipología 101 49 Figura 16Figura 14. Comparativa por tipología UAV: Variación valor objetivo respecto a tipología 101 49 Figura 17Figura 14. Comparativa por número de UAV: Tiempo fase 1 50 Figura 18. Figura 14Comparativa por número de UAV: Tiempo fases 2+3 50 Figura 19. Comparativa por número de UAV: Tiempo total 51 Figura 20. Comparativa por número de UAV: Valor objetivo 51 Figura 21. Comparativa por número de iteraciones: Tiempo fase 1 52 Figura 22. Comparativa por número de iteraciones: Tiempo fases 2+3 52 Figura 23. Comparativa por número de iteraciones: Tiempo total 52 Figura 24. Comparativa por número de iteraciones: Valor objetivo 53 xviii xix Glosario UAV Unmanned Aerial Vehicle TSP Travelling Salesman Problem VRP Vehicle Routing Problem NP Nondeterministic Polynomial TW Time Window MILP Mixed Integer Linear Programming ILP Integer Linear Programming FSTSP Flying Sidekick Traveling Salesman Problem mFSTSP multiple Flying Sidekick Traveling Salesman Problem MVDRP Multi Visit Drone Routing Problem xx 1 1 INTRODUCCIÓN n las últimas décadas, la aparición y desarrollo de los robots móviles como los UAVs o los drones, ha provocado que múltiples empresas y organismos traten de innovar en su forma de producir o de dar servicios a sus usuarios mediante el uso de estas tecnologías. Este tipo de vehículos no tripulados son ya una realidad en multitud de ámbitos como en la aviación militar o la automatización de almacenes de paquetería. La aplicación de robots móviles voladores de corto rango y alimentados por baterías a tareas de reparto de paquetes se ha comenzado a contemplar como una posibilidad en la última década, consiguiéndose grandes avances en la planificación de rutas óptimas que deben ser recorridas por estos vehículos. Sin embargo, el uso únicamente de drones en entornos urbanos para este tipo de tareas presenta ciertos inconvenientes que se verán a lo largo de este trabajo. Es por ello, que surge la necesidad de combinar el uso de drones que agilicen las tareas de reparto con vehículos terrestres (camiones) que sirvan para realizar tanto tareas de reparto como de apoyo a los drones. 1.1 Objetivo El presente proyecto trata de analizar y mejorar un problema de actualidad como es el reparto de paquetes individuales a pequeños clientes. Estos clientes pueden ser domicilios o negocios que adquieran productos a una empresa de distribución para que esta a través de sus medios de transporte les haga llegar estos paquetes. En este caso nos centraremos en el reparto de estos paquetes en núcleos urbanos donde exista un almacén desde el que salgan y al que lleguen los vehículos de distribución o mensajería. Este problema se modelará como un sistema multiagente en el que los agentes representan los drones y el camión empleados para las tareas de reparto Por tanto, el objetivo del trabajo es realizar un estudio acerca de las distintas formulaciones y aproximaciones que se han realizado en los últimos años y seleccionar un problema que tenga aplicabilidad práctica para proceder a su implementación. En la actualidad, el esfuerzo principal se centra en diseñar algoritmos heurísticos que traten de alcanzar una ruta lo más cercana al óptimo sin que esto conlleve un coste computacional muy elevado. Para este trabajo, se ha buscado realizar una mejora de estos algoritmos heurísticos, no desde un punto de vista de la optimización de la ruta obtenida, sino desde la eficiencia computacional de la misma. Para conseguir tal objetivo, se ha planteado la segregación de un algoritmo heurístico en distintas partes que permitan ser ejecutadas en paralelo mediante el uso de múltiples hilos. Si bien esta técnica permitirá mejorar el cálculo de las rutas óptimas en cuanto al tiempo de ejecución, también será necesario realizar un estudio sobre el efecto que tiene esta implementación sobre la precisión de los resultados obtenidos respecto al óptimo y respecto a los resultados obtenidos en caso de no emplear dicha técnica. Todo esto, permitirá conocer si este tipo de técnicas son aplicables a los problemas de optimización de rutas o en caso contrario no es una buena metodología. Para ello, se plantearán más adelante distintos escenarios donde se evaluará la efectividad y la eficiencia de la implementación E 2 2 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones 1.2 Alcance Una vez visto el objetivo del presente trabajo, se procederá a realizar una breve descripción del alcance del mismo. El trabajo abarcará el estudio del efecto que tienen distintas implementaciones, tanto mediante un algoritmo exacto, como por una heurística, ejecutándose esta última en paralelo. Además, se realizarán simulaciones para los distintos parámetros que permiten modelar tanto la heurística como para distintos tipos de problemas: • Número de nodos y distancia entre ellos • Número de UAVs • Tipos de UAVs (velocidad, capacidad, autonomía) • Iteraciones realizadas por la heurística En cambio, se considerará el mismo modelo de consumo de combustible para todas las simulaciones (modelo no lineal), puesto que su efecto sobre el tiempo de ejecución es mínimo. Tampoco se le incluirán modificaciones a la heurística que introduzcan nuevos parámetros como la posibilidad de realizar operaciones tanto de entrega como de recogida, o la posibilidad de emplear múltiples almacenes de origen/destino. La implementación en paralelo de la heurística tiene como único objetivo mejorar los tiempos de ejecución del algoritmo, reduciéndolos en lo máximo posible, por lo que no se tendrá en cuenta el efecto que dicha modificación tenga sobre el valor óptimo alcanzado a la hora de diseñar la implementación, aunque si se comentará cuál es el efecto sobre dicho valor. Otra simplificación introducida es que el número de camiones será siempre uno, dicho vehículo tendrá que estar disponible en el almacén para que comience la operación de reparto, eliminando la posibilidad de que los UAVs realicen operaciones de entrega cuando dicho vehículo no está disponible inicialmente en el depósito. Se ha tomado esta decisión para simplificar el problema y evitar añadir una casuística más al estudio del efecto de la programación en paralelo sobre el tiempo de ejecución. Otro parámetro que se mantendrá constante será que el conductor deberá estar siempre disponible cuando un UAV vaya a realizar una operación de despegue o aterrizaje, impidiendo realizar al conductor una entrega de un paquete mientras un UAV realiza una tarea de despegue/aterrizaje. Por tanto, la disponibilidad del conductor quedará fuera del alcance de este trabajo. Esta casuística es más realista en la actualidad, ya que en caso contrario sería necesario que los UAVs fuesen capaces de aterrizar/despegar autónomamente desde el camión, al igual que ser capaces de cambiar sus baterías cada vez que aterrizan de forma autónoma. El contenido del documento es el siguiente:  Capítulo 2: en primer lugar, tras realizar la introducción, se recopilará y se resumirá toda la información existente acerca del problema que se quiere optimizar, pasando por las distintas fases y mejoras que han ido teniendo. Además, se comentarán algunas aplicaciones reales de la planificación de rutas mediante drones.  Capítulo 3: se realizará un análisis profundo del problema a considerar, su formulación matemática y las distintas características que provocan que el problema tenga una complejidad computacional tan elevada, siendo necesario la implementación de un algoritmo heurístico en vez de un algoritmo exacto.  Capítulo 4: Implementación en Python del algoritmo heurístico mediante multihilos que permitan ejecutar en paralelo. Esto permitirá una ganancia en cuanto al tiempo de ejecución del programa respecto al algoritmo inicial sin la posibilidad de ejecución en paralelo. Descripción detallada de las estrategias implementadas para llevar a cabo la ejecución en paralelo.  Capítulo 5: en este capítulo se recogerán los datos obtenidos de las distintas simulaciones realizadas para los distintos escenarios planteados: uso de distinto número de drones para un mismo conjunto clientes-almacén, comparativa entre la implementación exacta (casos pequeños), implementación heurística inicial y las heurísticas con ejecución en paralelo para un mismo conjunto clientes-almacén; y por último, replicar estas simulaciones para distintos conjuntos. 3 3 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones  Capítulo 6: finalmente se obtendrán unas conclusiones sobre los efectos que tiene dicha implementación sobre el algoritmo heurístico y sobre los resultados (tiempo de ejecución y solución óptima). Además, se propondrán posibles trabajos futuros que permitan ampliar el uso de la ejecución en paralelo a problemas similares, así como posibles mejoras del propio algoritmo implementado. 4 4 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones 5 2 ESTADO DEL ARTE n este capítulo se va a realizar una revisión de los distintos tipos de problemas que se encuentran relacionados con el objeto de este trabajo; es decir, problemas de transporte de mercancías mediante el uso combinado de vehículos terrestres y UAVs. También se realizará una breve descripción sobre las distintas aproximaciones que se han realizado para resolver estos problemas, y cómo estas han servido de soporte de conocimiento para conseguir implementar un algoritmo que permita cubrir las restricciones de estos problemas. 2.1 Aplicaciones El uso de vehículos aéreos autónomos en tareas de distribución de productos tiene una gran aplicabilidad y un futuro muy prometedor en distintos ámbitos, tanto civiles como militares. A continuación, se muestran algunos de los sectores en los que la aplicación de los drones o UAVs se encuentra en fase de pruebas e incluso sectores en los que dicha aplicación es una realidad.  Sector sanitario: los UAVs permiten transportar objetos poco pesados a gran velocidad y económicamente. De esto se aprovechan múltiples estudios y experimentos en el sector médico, ya que permite transportar muestras de sangre entre hospitales y laboratorios que se encuentran en regiones urbanas y que por lo tanto el tráfico es un gran inconveniente. Para ello, se están llevando a cabo experimentos como el descrito por Roca-Riu et al. [1] en el que hospitales suizos intercambian muestras de sangre y otros materiales sanitarios mediante el uso de un camión y un dron. Otra aplicación en el ámbito sanitario y de actualidad es el trabajo realizado por Adwibowo, A. [2] donde se expone la posibilidad de usar drones para transportar vacunas contra el virus COVID-19 en el Sudeste Asiático. Con esto se conseguiría llegar a zonas densamente pobladas pero cuyo acceso sea imposible por medios terrestres que sean capaces de mantener las vacunas en un intervalo de temperaturas muy bajo. Figura 1. Experimento en el sector sanitario [1] E 12 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Sin embargo, en 1959 surgió por parte de George Dantzig y John Ramser la primera definición del problema de enrutamiento de vehículos [1] o VRP de sus siglas en inglés (Vehicle Routing Problem) el cual busca minimizar el coste de visitar una serie de clientes o nodos, pero a diferencia del TSP, el problema de enrutamiento de vehículos contempla el uso de múltiples vehículos realizando las tareas de reparto a los distintos clientes de la ruta. Esta diferencia en la formulación del problema ha permitido que en la actualidad se diferencien los algoritmos diseñados para la resolución de problemas de selección de una ruta óptima para repartir a una serie de clientes dados desde un local/almacén en estos dos problemas. En el caso de este proyecto, el problema seleccionado es el TSP, y más concretamente una formulación mFTSP (multiple Flying Sidekick Traveling Salesman Problem). Aunque esta formulación incluye el uso de varios vehículos (UAVs + camión) para realizar las operaciones de reparto, estas pueden ser simplificadas. Esta simplificación se basa en reducir el problema a un único vehículo principal que es el encargado de realizar las tareas de reparto y transportar a vehículos auxiliares. Mientras que dichos vehículos auxiliares se encargarán de reducir el número de clientes que deben ser visitados por el vehículo principal. 3.2 Modelo matemático En siguiente lugar, se procederá a definir el modelo matemático del problema mFSTSP. Esta formulación del problema tiene varias características, como que cada UAV únicamente será capaz de servir a un único cliente, y para ello, necesitará de un nodo de despegue (inicio de la subruta), el nodo de servicio, y un nodo de aterrizaje (fin de la subruta del UAV). Es por ello que cada subruta llevada a cabo por un UAV tendrá asociado el número del UAV (identificador) que se encargará de realizar dicha operación, y de los 3 nodos que caracterizan su subruta. Además, cada UAV podrá realizar múltiples subrutas a lo largo de la operación de reparto, constando cada una de ellas de esta tupla de 4 elementos. Un UAV tampoco puede repetir un mismo nodo como nodo de despegue y de aterrizaje, siendo únicamente posible para el UAV aterrizar en un nodo que sea visitado por el camión, o en su defecto, en el propio almacén donde se inicia la ruta de reparto y donde finaliza. Todo esto queda resumido en las tablas siguientes (Tabla 1 y Tabla 2) donde se muestran los parámetros de la formulación matemática y las variables de decisión del problema. Tabla 1. Parámetros de la formulación matemática V Conjunto de UAVs C Conjunto de clientes/nodos 𝑪𝑪𝒗𝒗 � Conjunto de clientes que pueden ser servidos por UAVs N Conjunto de todos los nodos incluido el almacén como nodo 0 y nodo c+1 𝑵𝑵𝟎𝟎 Conjunto de nodos disponibles para iniciar una ruta (orígen) 𝑁𝑁0= {0,1,2, … , 𝑐𝑐} 𝑵𝑵+ Conjunto de nodos que serán visitados (destino) de una ruta 𝑁𝑁+= {1,2, … , 𝑐𝑐+ 1} 𝝉𝝉𝒊𝒊𝒊𝒊 Tiempo de viaje del camión del nodo i al nodo j 𝝉𝝉𝒗𝒗𝒊𝒊𝒊𝒊 ′ Tiempo de viaje de un UAV (v) desde un nodo i hasta un nodo j 𝒔𝒔𝒗𝒗,𝒊𝒊 𝑳𝑳 Tiempo de despegue de un UAV desde un nodo i 𝒔𝒔𝒗𝒗,𝒌𝒌 𝑹𝑹 Tiempo de aterrizaje + recogida de un UAV en un nodo k 𝝈𝝈𝒌𝒌 Tiempo de servicio empleado por un camión en un nodo k; k ∈ 𝑁𝑁+ 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝜎𝜎𝑐𝑐+1 ≡0 13 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones 𝝈𝝈𝒗𝒗𝒌𝒌 ′ Tiempo de servicio empleado por un UAV en un nodo k; k ∈ 𝑁𝑁+ 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝜎𝜎𝑣𝑣,𝑐𝑐+1 ′≡0 P Conjunto 〈𝑣𝑣,𝑖𝑖,𝑗𝑗,𝑘𝑘〉 que especifica todas las posibles agrupaciones de 3 nodos que pueden ser visitados por un UAV 𝒆𝒆𝒗𝒗𝒊𝒊𝒊𝒊𝒌𝒌 Autonomía de un UAV para viajar de un nodo i a un nodo j y regresar a un nodo k (en unidades de tiempo) Tabla 2. Variables de decisión 𝒙𝒙𝒊𝒊𝒊𝒊∈{𝟎𝟎,𝟏𝟏} 𝒙𝒙𝐢𝐢𝐢𝐢=𝟏𝟏 𝐬𝐬𝐢𝐢 𝐞𝐞𝐞𝐞 𝐜𝐜𝐜𝐜𝐜𝐜𝐢𝐢ó𝐧𝐧 𝐯𝐯𝐢𝐢𝐜𝐜𝐢𝐢𝐜𝐜 𝐢𝐢𝐧𝐧𝐜𝐜𝐞𝐞𝐢𝐢𝐢𝐢𝐜𝐜𝐢𝐢𝐜𝐜𝐜𝐜𝐞𝐞𝐧𝐧𝐢𝐢𝐞𝐞 𝐢𝐢𝐞𝐞𝐬𝐬𝐢𝐢𝐞𝐞 𝐞𝐞𝐞𝐞 𝐧𝐧𝐧𝐧𝐢𝐢𝐧𝐧 𝐢𝐢 𝐜𝐜𝐞𝐞 𝐧𝐧𝐧𝐧𝐢𝐢𝐧𝐧 𝐢𝐢 𝒑𝒑𝒊𝒊𝒊𝒊∈{𝟎𝟎,𝟏𝟏} 𝑝𝑝𝑖𝑖𝑖𝑖 = 1 si el nodo i aparece antes que el nodo j en la ruta del camión 𝒚𝒚𝒗𝒗𝒊𝒊𝒊𝒊𝒌𝒌∈{𝟎𝟎,𝟏𝟏} 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 = 1 si el UAV v viaja desde el nodo i para visitar el nodo j y se junta con el camión en el nodo k 𝒕𝒕�𝒊𝒊≥𝟎𝟎 Tiempo de llegada del camión al nodo i 𝒕𝒕𝒊𝒊≥𝟎𝟎 Tiempo de servicio del camión en nodo i 𝒕𝒕�𝒊𝒊≥𝟎𝟎 Tiempo de finalización de la tarea en el nodo i por parte del camión 𝒕𝒕�′𝒗𝒗𝒊𝒊≥𝟎𝟎 Tiempo de llegada del UAV al nodo i 𝒕𝒕�′𝒗𝒗𝒊𝒊≥𝟎𝟎 Tiempo de finalización de la tarea en el nodo i por parte del UAV 𝒛𝒛𝒗𝒗𝟏𝟏,𝒗𝒗𝟐𝟐,𝒌𝒌 𝑹𝑹∈{𝟎𝟎,𝟏𝟏} zv1,v2,k R= 1 si el UAV v1 es recogido en el nodo k antes que el UAV v2 𝒛𝒛𝟎𝟎,𝒗𝒗,𝒌𝒌 𝑹𝑹∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧0,𝑣𝑣,𝑣𝑣 𝑅𝑅= 1 si el camión finaliza su servicio en el nodo k antes que el UAV regrese 𝒛𝒛𝒗𝒗,𝟎𝟎,𝒌𝒌 𝑹𝑹∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧𝑣𝑣,0,𝑣𝑣 𝑅𝑅= 1 si el UAV regresa antes que el camión finalice su servicio en el nodo k 𝒛𝒛𝒗𝒗𝟏𝟏,𝒗𝒗𝟐𝟐,𝒊𝒊 𝑳𝑳∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧𝑣𝑣1,𝑣𝑣2,𝑖𝑖 𝐿𝐿= 1 si el UAV v1 despega en el nodo i antes que el UAV v2 𝒛𝒛𝟎𝟎,𝒗𝒗,𝒊𝒊 𝑳𝑳∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧0,𝑣𝑣,𝑖𝑖 𝐿𝐿= 1 si el camión finaliza su servicio en el nodo i antes que el UAV despegue 𝒛𝒛𝒗𝒗,𝟎𝟎,𝒊𝒊 𝑳𝑳∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧𝑣𝑣,0,𝑖𝑖 𝐿𝐿= 1 si el UAV despega antes que el camión finalice su servicio en el nodo i 𝒛𝒛′𝒗𝒗𝟏𝟏,𝒗𝒗𝟐𝟐,𝒌𝒌∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧′𝑣𝑣1,𝑣𝑣2,𝑣𝑣= 1 si el UAV v1despega desde el nodo i antes que v2 aterrice en i 𝒛𝒛′′𝒗𝒗𝟏𝟏,𝒗𝒗𝟐𝟐,𝒌𝒌∈{𝟎𝟎,𝟏𝟏} 𝑧𝑧′𝑣𝑣1,𝑣𝑣2,𝑣𝑣= 1 si el UAV v1aterriza en el nodo i antes que v2 despegue desde i 𝟏𝟏≤𝐮𝐮𝐢𝐢≤𝐜𝐜+𝟐𝟐 Indica el orden de visitas relativo al nodo i El objetivo del mFSTSP es minimizar el tiempo necesario para servir a todos los nodos/clientes, partiendo desde el almacén y volviendo al mismo. Para que la ruta finalice, deben volver al almacén tanto el camión como todos los UAVs que participen en las tareas de reparto. A continuación se muestran las ecuaciones que rigen el modelo matemático: 14 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Min 𝒕𝒕� 𝒄𝒄+𝟏𝟏 (1) s.a. �𝑥𝑥𝑖𝑖𝑖𝑖+�� � 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 = 1 ∀𝑗𝑗∈𝐶𝐶 𝑣𝑣∈𝑁𝑁+ 〈𝑣𝑣,𝑖𝑖,𝑖𝑖,𝑣𝑣〉∈𝑃𝑃 𝑖𝑖∈𝑁𝑁0 𝑖𝑖≠𝑖𝑖 𝑣𝑣∈𝑉𝑉 , 𝑖𝑖 ∈𝑁𝑁0 𝑖𝑖≠𝑖𝑖 (2) �𝑥𝑥0𝑖𝑖 = 1, 𝑖𝑖 ∈𝑁𝑁+ (3) �𝑥𝑥𝑖𝑖,𝑐𝑐+1= 1, 𝑖𝑖 ∈𝑁𝑁0 (4) �𝑥𝑥𝑖𝑖𝑖𝑖 =�𝑥𝑥𝑖𝑖𝑣𝑣 ∀𝑗𝑗∈𝐶𝐶 𝑣𝑣∈𝑁𝑁+ 𝑣𝑣≠𝑖𝑖 , 𝑖𝑖 ∈𝑁𝑁0 𝑖𝑖≠𝑖𝑖 (5) � � 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 ≤1 ∀𝑖𝑖∈𝑁𝑁0,∀𝑣𝑣∈𝑉𝑉, 𝑣𝑣∈𝑁𝑁+ 〈𝑣𝑣,𝑖𝑖,𝑖𝑖,𝑣𝑣〉∈𝑃𝑃 𝑖𝑖 ∈𝐶𝐶 𝑖𝑖 ≠𝑖𝑖 (6) � � 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 ≤1 ∀𝑘𝑘∈𝑁𝑁+,∀𝑣𝑣∈𝑉𝑉, 𝑖𝑖∈𝐶𝐶 〈𝑣𝑣,𝑖𝑖,𝑖𝑖,𝑣𝑣〉∈𝑃𝑃 𝑖𝑖 ∈𝑁𝑁0 𝑖𝑖≠𝑣𝑣 (7) 2 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 ≤ �𝑥𝑥ℎ𝑖𝑖+�𝑥𝑥𝑙𝑙𝑣𝑣 ∀𝑣𝑣∈𝑉𝑉,𝑖𝑖∈𝐶𝐶,𝑗𝑗∈{𝐶𝐶:𝑗𝑗≠𝑖𝑖},𝑘𝑘∈{𝑁𝑁+:〈𝑣𝑣,𝑖𝑖,𝑗𝑗,𝑘𝑘〉∈𝑃𝑃}, 𝑙𝑙∈𝐶𝐶 𝑙𝑙∈𝑣𝑣 ℎ∈𝑁𝑁0 ℎ≠𝑖𝑖 (8) 2 𝑦𝑦𝑣𝑣0𝑖𝑖𝑣𝑣 ≤ �𝑥𝑥ℎ𝑣𝑣 ∀𝑣𝑣∈𝑉𝑉,𝑗𝑗∈𝐶𝐶,𝑘𝑘∈{𝑁𝑁+:〈𝑣𝑣, 0, 𝑗𝑗,𝑘𝑘〉∈𝑃𝑃}, ℎ∈𝑁𝑁0 ℎ≠𝑣𝑣 (9) 𝑢𝑢 𝑣𝑣−𝑢𝑢𝑖𝑖≥1−(𝑐𝑐+ 2)⎝ ⎜ ⎛ 1− � 𝑦𝑦𝑣𝑣𝑖𝑖𝑖𝑖𝑣𝑣 𝑖𝑖∈𝐶𝐶 〈𝑣𝑣,𝑖𝑖,𝑖𝑖,𝑣𝑣〉∈𝑃𝑃 ⎠ ⎟ ⎞ ∀𝑣𝑣∈𝑉𝑉,𝑖𝑖∈𝐶𝐶,𝑘𝑘∈{𝑁𝑁+:𝑘𝑘≠𝑖𝑖}, (10) 𝑢𝑢 𝑖𝑖−𝑢𝑢𝑖𝑖+ 1 ≤(𝑐𝑐+ 2)(1 −𝑥𝑥𝑖𝑖𝑖𝑖) ∀𝑖𝑖∈𝐶𝐶,𝑗𝑗∈{𝑁𝑁+:𝑗𝑗≠𝑖𝑖}, (11) 𝑢𝑢 𝑖𝑖−𝑢𝑢𝑖𝑖≥1−(𝑐𝑐+ 2)𝑝𝑝𝑖𝑖𝑖𝑖 ∀𝑖𝑖∈𝐶𝐶,𝑗𝑗∈{𝐶𝐶:𝑗𝑗≠𝑖𝑖}, (12) 𝑢𝑢 𝑖𝑖−𝑢𝑢𝑖𝑖≤−1 + (𝑐𝑐+ 2)(1 −𝑝𝑝𝑖𝑖𝑖𝑖) ∀𝑖𝑖∈𝐶𝐶,𝑗𝑗∈{𝐶𝐶:𝑗𝑗≠𝑖𝑖}, (13) 𝑝𝑝 𝑖𝑖𝑖𝑖+𝑝𝑝𝑖𝑖𝑖𝑖 = 1 ∀𝑖𝑖∈𝐶𝐶,𝑗𝑗∈{𝐶𝐶:𝑗𝑗≠𝑖𝑖}. (14) El objetivo es minimizar el tiempo de finalización de la tarea de reparto del camión en el nodo c+1, el cuál se corresponde con el nodo final del almacén. Este es el tiempo total que conlleva una determinada ruta de reparto, ya que en el tiempo del camión están incluidos los tiempos de los UAVs al tener que esperar el camión a que todos los UAVs vuelvan al camión antes de dar por finalizado su tiempo en el nodo c+1. La restricción de la ecuación (2) exige que cada cliente sea visitado una única vez, ya sea tanto por un UAV como por el camión. Las restricciones (3) y (4) establecen que los nodos de inicio y final (0 y c+1) son los nodos del almacén. 15 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones La restricción (5) determina que el camión tendrá que salir desde cada nodo que ha visitado, mientras que las restricciones (6) y (7) determinan respectivamente que cada UAV solo podrá despegar/aterrizar una vez desde cada nodo, incluido el almacén. La restricción (8) exige que si un UAV despega en un nodo i y aterriza en un nodo k, el camión tiene que tener asignados ambos nodos en su ruta. La restricción (9) se encarga del caso concreto en el que el UAV sea lanzado desde el depósito, en cuyo caso el nodo k de aterrizaje tiene que ser visitado por el camión. De igual forma, la restricción (10) obliga a que el nodo i sea precedente al nodo k en la ruta del camión en caso de que un UAV despegue desde i y aterrice en k. La restricción (11) elimina subrutas para el camión, mientras que las restricciones (12) – (14) se encargan de determinar un valor apropiado para 𝑝𝑝𝑖𝑖𝑖𝑖. En el trabajo desarrollado por Murray [7] también se plantea la formulación de las restricciones temporales para los UAVs y el camión, pero quedan fuera del ámbito de estudio de este trabajo profundizar más en la formulación matemática del modelo completo. De igual forma, puede ser consultada toda la formulación desarrollada para la secuencia de aterrizajes, despegues y tiempo de servicio del camión a un cliente de un nodo concreto. 3.3 Variantes Además de la formulación descrita anteriormente, también se contemplan distintas variaciones a la formulación matemática que le dan una mayor versatilidad al problema. Aunque estas variantes pueden tener grandes implicaciones en cuanto al tiempo óptimo de la función objetivo, su efecto sobre los tiempos de ejecución es despreciable, por lo que como se expondrá más adelante en el capítulo de los resultados, estas variantes han quedado fuera del estudio llevado a cabo en este trabajo. A pesar de esto último, es necesario exponer brevemente estas variantes, ya que pueden ser puntos de partida de futuros trabajos que puedan ampliar los resultados obtenidos en este estudio. 3.3.1 Camión no requerido en el depósito Esta variante relaja las restricciones que obligan a que tanto cuando parte el camión del almacén (nodo 0), como cuando este vuelve al almacén después de recorrer la ruta (nodo c+1), los drones no tienen que realizarlo en el mismo instante. Esto permite que tanto los UAVs puedan realizar operaciones desde el nodo 0 como origen, como rutas que tengan como nodo de destino el nodo c+1. Esto provoca también que la función objetivo varíe debido a que el último vehículo en llegar al almacén (c+1) dejará de ser siempre el camión. Puesto que los UAVs pueden volver de forma independiente al almacén, es posible que la ruta del camión sea modificada para que vuelva al almacén antes de lo planificado si no existiese esta variante, siendo el UAV el que determinaría el tiempo total empleado en una ruta concreta. 3.3.2 Sistema de lanzamiento y aterrizaje automático En segundo lugar, se plantea la posibilidad de modificar la formulación matemática original de tal forma que los UAVs puedan despegar y aterrizar en el camión sin necesidad de que el conductor tenga que manipularlos, Esto permite un ahorro en el tiempo necesario para llevar a cabo una ruta, al permitir que el conductor del camión pueda estar sirviendo a un determinado cliente mientras que los UAVs despegan/aterrizan de forma autónoma en el camión. Al igual que en la variante anterior, esta variante proporciona una mejora en el valor de la función objetivo, pero no tiene ningún efecto sobre el tiempo de ejecución. Además, esta variante necesita de un sistema incorporado en el camión que permita realizar dichas maniobras, lo que disminuye la aplicabilidad del algoritmo implementado a camiones con dicha tecnología. 3.4 Heurística Tras mostrar la formulación matemática del problema y algunas variantes del mismo, se procederá a exponer la heurística empleada en este trabajo. Como se ha comentado anteriormente, esta heurística está basada en el trabajo desarrollado por Murray y Raj [7]. 16 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones En su trabajo, estos autores desarrollan una heurística para solventar el problema conocido como mFSTSP (multiple Flying Sidekick Traveling Salesman Problem). Esta heurística está dividida en 3 fases, las cuales se proceden a describir a continuación. 3.4.1 Fase I En la primera fase se trata de dividir a los clientes entre aquellos que pueden ser servidos tanto por UAVs como por el camión, y aquellos que solo pueden ser servidos por el camión. En la Figura 4 se muestra un ejemplo donde los nodos en verde son clientes que pueden ser servidos por cualquier vehículo, mientras que los nodos azules solo pueden ser servidos por el camión. Figura 4. Ejemplificación de clientes servidos por distintos vehículos1 Para conocer el número mínimo de clientes que deben ser visitados por el camión, se calcula un parámetro conocido como LTL o Lower Truck limit, el cuál se obtiene a partir del número de clientes total y el número de vehículos (UAVs) empleados en la ruta. 𝐿𝐿𝐿𝐿𝐿𝐿0=�|𝐶𝐶|−|𝑉𝑉| |𝑉𝑉|+ 1 � (15) 1 Elaboración propia 17 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones De tal forma que si en una ruta determinada consta de 50 clientes y el número de UAVs empleados es de 4, el número mínimo de clientes que deberán ser visitados por el camión será de 10. Además de esto, será necesario tener en cuenta el número de clientes que pueden ser servidos únicamente por el camión, ya sea por criterios de peso del paquete, como por cualquier otro criterio que se establezca. A lo largo de la ejecución de la heurística, el parámetro LTL irá incrementando desde su valor mínimo, hasta el máximo, el cuál coincide con el número total de clientes; es decir, que todos los clientes serán servidos por el camión. Con esto se consigue asignar en cada paso del bucle, cuantos nodos son servidos por cada tipo de vehículo, de tal forma que para valores bajos de LTL (primeros pasos del bucle), se empleará en mayor medida los UAVs para servir a los clientes, mientras que en los últimos pasos, será el camión el que realice la mayoría de movimientos, siendo el resultado del bucle la ruta con menor duración de las calculadas. Con todo esto, lo que realmente se está realizando en esta fase es la resolución de un problema TSP únicamente para aquellos clientes que serán servidos por el camión, calculándose cuáles deben de ser esos nodos para mejorar el tiempo total de la ruta del camión. Al finalizar este cálculo, es necesario realizar también una comprobación de que todos los restantes nodos pueden ser servidos por los UAVs, ya que si por ejemplo, existe un cliente muy alejado de los restantes clientes, pero este nodo ha sido identificado como nodo a ser servido por un UAV, es posible que ningún UAV tenga la autonomía necesaria para llegar hasta ese cliente. Es por ello, que se realiza dicha comprobación, y en caso de que algún nodo no pueda ser alcanzado por los UAVs, se fuerza a que dicho nodo sea visitado por el camión en vez de por los UAVs, calculándose de nuevo una solución para el problema TSP con esa nueva restricción. 3.4.2 Fase II Una vez calculada la ruta que desempeñará el camión, es el turno de calcular las rutas llevadas a cabo por los UAVs, sus nodos de salida, de servicio y de vuelta al camión. Esto se realiza en la fase 2. En esta fase se busca reducir el tiempo de espera tanto del camión como de los UAVs en los nodos de despegue y aterrizaje de los UAVs. Por su parte, la fase 2 irá asignando a cada nodo que debe ser servido por un UAV, el UAV concreto que se encargará de realizar dicho servicio, quedando identificados al final de esta fase cuáles serán los nodos visitados por UAVs y cuales por el camión, y en caso de ser visitados por UAV, cuál será el UAV encargado de dicha ruta, y cuál será el nodo desde el que despegará, y cual será el nodo en el que aterrice el UAV para juntarse de nuevo con el camión. Nuevamente se realizará un cálculo para comprobar si existe algún nodo que no tiene asignado un UAV, y en caso afirmativo, será asignado al camión. Puesto que desde la fase 3 se puede volver a la fase 2, en caso de que una ruta no sea realizable, pero dicha ruta sea consecuencia de un cálculo realizado en la fase 3, en vez de realizar la sustitución de dicho nodo para que sea servido por el camión, se saltará directamente a la fase 1 y se incrementará el valor del parámetro LTL, pasando de esta forma al siguiente paso del bucle. Esta fase se caracteriza por ser la fase con un menor peso en cuanto al coste computacional de la heurística, por lo que como se verá más adelante, la importancia de esta fase desde el punto de vista de este trabajo será muy reducida respecto a las fases 1 y 3, las cuales soportan la mayor parte del coste computacional. 3.4.3 Fase III Por último, en la fase 3 se llevan a cabo varios cálculos finales para obtener una ruta subóptima para el valor de LTL de ese paso del bucle. Es en esta fase, donde se resuelve un MILP (Mixed Integer Linear Prorgamming) para determinar el momento en el que se realiza el despegue y el aterrizaje de los UAVs en sus respectivos nodos. En siguiente lugar, se comprueba si la solución obtenida es mejor que la solución subóptima hallada hasta al momento, y en caso afirmativo, se guarda dicha ruta. Tras esto, se intenta cambiar un nodo que sea servido por el camión a un nodo que sea servido por un UAV. En este proceso se evalúan todos los nodos visitados por el camión y se busca el nodo que proporciona un mayor ahorro de tiempo. En caso de existir un nodo con esta posibilidad, se realiza el cambio y se vuelve a la fase 2 para realizar dicha modificación. Una vez finalizada estas operaciones, se realiza una búsqueda local para intentar mejorar la solución obtenida. Para esta búsqueda local se trata de reducir el tiempo de espera del camión a que los UAVs aterricen en un determinado nodo, tratando de establecer como nodo de recogida el siguiente nodo en la ruta del camión, para 18 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones que de esta forma se disminuya el tiempo de espera del camión. Esto tiene por contrapartida que el tiempo que el UAV tendrá que esperar en el nodo siguiente de la ruta aumente, pero puesto que el recurso limitante es el camión, esta acción permitirá reducir el tiempo total de la solución obtenida. Sin embargo, esto propone otros problemas tecnológicos que deberán ser resueltos, como que varios UAVs aterricen de forma prematura en un cliente antes de que el propio camión haya llegado a dicho cliente. Finalmente, la heurística vuelve a la fase 1 e incrementa el valor de LTL, pasando al siguiente paso del bucle. A continuación se muestra un esquema-resumen sobre la heurística y sus distintas fases y toma de decisiones. Figura 5. Esquemaresumen de las fases de la heurística [7] 19 4 ALGORITMO n este capítulo se expondrá la implementación llevada a cabo para poder solucionar el problema descrito anteriormente. Para ello, la implementación será tanto de un algoritmo exacto como de uno heurístico. Es en este último donde se centra este trabajo. Mejorar el tiempo de ejecución de dicho algoritmo mediante el uso de programación en paralelo. Inicialmente se realizará una breve descripción sobre el algoritmo exacto implementado y cómo ha sido implementado, para posteriormente realizar lo mismo con el algoritmo heurístico de partida. Es aquí donde, una vez expuesta la base de la heurística, se separará entre el algoritmo inicial del que se parte y el algoritmo que se ejecuta en paralelo. 4.1 Algoritmo exacto Los algoritmos exactos buscan obtener la mejor ruta posible para satisfacer a todos los clientes y las restricciones que se incluyan en el problema (ventanas de tiempo, consumo de combustible, etc…). Aunque este tipo de algoritmos permiten conocer cuál es la mejor solución posible, conllevan un alto coste computacional debido a la necesidad de comprobar todas las rutas posibles y descartar aquellas que no satisfacen alguna restricción o arrojan valores de tiempo de ruta muy elevados desde un inicio. Además, este coste computacional aumenta rápidamente conforme el número de clientes a satisfacer o nodos de la red aumenta, siendo estos algoritmos una solución poco útil para resolver este tipo de problemas. A pesar de ello, existen una gran cantidad de algoritmos aplicados a los problemas de enrutamientos, entre los que se puede destacar el algoritmo Branch and Bound (Ramificación y poda). Este algoritmo permite descartar ramas de soluciones o rutas cuyos tiempos son muy elevados respecto a una solución hallada previamente, evitando de esta forma tener que computar todas las posibles rutas involucradas. Otras metodologías como la programación lineal han sido aplicadas a este tipo de problemas con resultados buenos para pequeños grupos de clientes. En la Figura 6 se muestra un esquema del funcionamiento del algoritmo Branch and Bound, donde los vértices marcados en verde se refieren a una ruta completa cuyo coste final es de 28, mientras que los vértices rojos son otras ramas cuyas soluciones son peores. Como se puede observar, la mejor solución hasta el momento tiene un coste de 28, todas las ramas que se calculen con posterioridad a conocer dicho valor se compararán con este valor. En caso de que sea superior, se descarta esa rama, evitando consumir tiempo de ejecución en una rama que ya se conoce que su valor será peor que el mejor valor hasta ese momento. E 20 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 6. Branch and Bound aplicado a TSP2 4.1.1 Gurobi En este trabajo, la implementación del algoritmo exacto se ha llevado a cabo a través de Python, al igual que el algoritmo heurístico, pero en el caso del algoritmo exacto se ha empleado un software de solución de problemas de optimización conocido como Gurobi. Este software permite implementar algoritmos como el Branch and Bound de una forma más sencilla y con mayor poder de cálculo que si fuese implementado desde cero. Además, esta herramienta informática consta de librerías en Python, siendo únicamente necesario obtener una licencia de su página web para poder emplear esta herramienta de forma gratuita. La ejecución del algoritmo exacto se basa en un cálculo inicial para todos los vehículos sobre si son capaces o no de realizar una determinada ruta, almacenándose en caso afirmativo como una de las posibles soluciones, y descartándose en caso negativo. En siguiente lugar se asignan los tiempos de despegue y aterrizaje a cada vehículo y los tiempos de servicio para cada cliente. Finalmente se añaden las restricciones al modelo de Gurobi y se resuelve con la función model.optimize(). Esta función devuelve tres posibles soluciones: • No se ha encontrado ninguna solución o no existe una solución posible para las restricciones introducidas • Se ha encontrado solución, pero no es la solución óptima debido al tiempo de cutoff. • Se ha encontrado la solución óptima El tiempo de cutoff o tiempo de corte es un parámetro que se le pasa al modelo de Gurobi para que en caso de que el tiempo de ejecución en una determinada rama de soluciones supere un tiempo máximo, el algoritmo se detenga y finalice su ejecución. Con esto se evita que el algoritmo exacto pueda excederse más de un valor 2 Elaboración propia 21 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones límite. En caso de que la simulación finalice debido a este parámetro, la solución mínima calculada hasta ese momento será la solución que se muestre en los resultados. Para este trabajo, se ha tomado un tiempo de cutoff de 10s. 4.2 Heurística secuencial Por otra parte, los algoritmos heurísticos son empleados para obtener una solución cercana al óptimo pero sin recorrer todas las rutas posibles para un determinado número de clientes. Es por ello, que este tipo de algoritmos es empleado para agrupaciones de clientes mayores que los algoritmos exactos o para pequeñas agrupaciones pero que es necesario obtener una solución en un tiempo de ejecución muy bajo, sin importar que la solución obtenida no sea la mejor posible. Una de las metodologías más empleadas es el algoritmo de colonias de hormigas, el cual se basa en simular el proceso de buscar la ruta óptima a través de un gran número de hormigas cuyo objetivo es buscar la ruta óptima (o la más cercana al óptimo) para los clientes dados. Esta metodología fue descrita por Marco Dorigo [11] en 1993, ya que mediante la simulación de las feromonas que dejan las hormigas a su paso, se puede inferir cual es la ruta óptima. En este trabajo, el algoritmo empleado es el descrito en el paper [7]. Esta heurística, como se ha descrito en el capítulo anterior, consta de 3 fases. Para el caso en el que el algoritmo se ejecute de forma secuencial, el orden de ejecución es el que viene descrito en el capítulo 3, y más concretamente en la Figura 5. 4.3 Heurística en paralelo Finalmente se llega a la heurística en paralelo. Esta heurística recibe su nombre debido a que se ejecuta de forma paralela, mediante el uso de múltiples hilos que se encargan de realizar operaciones computacionales de cada una de las fases. Es este algoritmo el objeto principal de este trabajo, mientras que los dos algoritmos anteriores servirán como referencia para comparar los resultados obtenidos con esta implementación respecto a las implementaciones existentes en la actualidad. 4.3.1 Estudio preliminar Para realizar el diseño de este algoritmo ha sido necesario llevar a cabo un estudio preliminar sobre el uso de recursos computacionales del algoritmo heurístico base (secuencial) y observar cuales eran las fases que tenían un mayor consumo de recursos. De esta forma, se centrarían los esfuerzos en reducir los tiempos de dichas fases. En la Tabla 3 se muestran los resultados obtenidos fruto del estudio preliminar. En este estudio se ha empleado un único UAV con una configuración de alta velocidad y baja autonomía. Se ha realizado una única iteración para cada simulación. En esta tabla se muestran los resultados para 4 problemas distintos, cada uno de ellos con un número de clientes/nodos distintos, variando por tanto su complejidad y su uso de recursos computacionales. A partir de la tabla se desprende que para valores bajos de clientes, el uso de multihilos tendrá un efecto inapreciable debido al ya de por sí, bajo tiempo de ejecución. Sin embargo, conforme aumenta el número de clientes, y con ello el tiempo de ejecución, se comienza a observar ciertos patrones. El más importante es la importancia que tiene la fase 1 sobre el tiempo total de ejecución, siendo cada vez más importante. Por su parte la fase 3 es la siguiente fase con mayor efecto sobre el tiempo de ejecución, mientras que la fase 2 tiene un efecto casi nulo sobre el valor final del tiempo de ejecución. 28 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Tabla 4. Parámetros de los UAVs según su tipología VEHICLEID 1 101 102 103 104 VEHICLETYPE 1 2 2 2 2 TAKEOFFSPEED [M/S] -1 156.464 156.464 78.232 78.232 CRUISESPEED [M/S] -1 312.928 312.928 156.464 156.464 LANDINGSPEED [M/S] -1 78.232 78.232 39.116 39.116 YAWRATEDEG [DEG/SEC] -1 360 360 360 360 CRUISEALT [M] -1 50 50 50 50 CAPACITY [LBS] -1 5 5 5 5 LAUNCHTIME [SEC] -1 60 60 60 60 RECOVERYTIME [SEC] -1 30 30 30 30 SERVICETIME [SEC] 30 60 60 60 60 BATTERYPOWER [JOULE] -1 457503 904033 291094 562990 RANGE NA low high low high Como se puede observar en la tabla anterior, los UAVs que pertenecen al grupo ‘101’ son UAVs con bajo rango pero con una elevada velocidad de crucero, a diferencia de los UAVs pertenecientes al grupo ‘102’, los cuales se caracterizan por una elevada autonomía y velocidad de crucero. Por otra parte, la columna de los vehículos tipo ‘1’ se refiere al camión encargado de tanto transportar los UAVs como de ayudar en las tareas de reparto a los clientes. Esta columna tiene como valor -1 para casi todas sus filas, ya que se establece por defecto que el camión podrá cargar toda la carga necesaria sin atender a su peso, o que su autonomía es superior a la distancia recorrida para realizar la ruta de reparto. En siguiente lugar se muestran en dos imágenes la distribución espacial (mapa) de los clientes de un determinado problema, así como las restricciones impuestas a los vehículos que pueden visitar cada nodo. 29 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 8. Ejemplo de un mapa de 8 clientes4 Figura 9. Ejemplo de un mapa de 25 clientes5 4 Elaboración propia 5 Elaboración propia 30 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones En las figuras anteriores se representan dos configuraciones de problemas distintos. En la primera, el número de clientes a atender son 8, de los cuales 2 clientes tienen que ser visitados obligatoriamente por el camión (nodos azules) y 6 clientes pueden ser visitados tanto por el camión como por un UAV (nodos verdes). El nodo negro se refiere al almacén desde el cual partirán y llegarán los vehículos involucrados en la ruta de reparto. De igual forma, en la segunda figura se representa una configuración de 25 clientes, de los cuales 5 tienen que ser visitados por el camión, mientras que los demás nodos no tienen esa restricción. A partir de ahora, las restantes figuras sobre la distribución de los clientes que se representen en un mapa emplearán el mismo código de colores para identificar los nodos que tienen que ser visitados por el camión, o por camión/UAV. Por otra parte, otros parámetros se han tomado constantes, ya que su efecto sobre el tiempo de ejecución es mínimo cuando se trata de comparar entre los distintos algoritmos. Estos parámetros son:  Requerir camión en el almacén: este parámetro puede ser tanto 1 como 0. Para el caso de tomar un valor nulo, se considera que el camión no tiene que estar necesariamente en el almacén para que los drones comiencen a realizar entregas. En cambio, si toma el valor 1 (nuestro caso), se forzará a que el inicio de la operación de entrega de paquetes no sea hasta que el camión esté disponible en el almacén.  Requiere conductor: este parámetro también podrá tomar únicamente dos valores (1 o 0). Para un valor de 1, el conductor tendrá que estar disponible cada vez que un dron haga una operación de aterrizaje/despegue desde el camión, mientras que si el valor es nulo, los UAVs podrán operar de forma autónoma.  Consumo de energía: existen distintos modelos de consumo de energía por parte de los UAVs, pero para este documento se ha decidido escoger un modelo no lineal. Otras opciones serían el uso de modelos lineales, constantes o basados en distancia recorrida. 5.1 Modelo exacto En primer lugar se van a mostrar los resultados obtenidos para las simulaciones del modelo exacto, y puesto que no se trata del objetivo principal de este trabajo evaluar dicho modelo exacto, se expondrán brevemente los resultados obtenidos. Además, debido a los elevados tiempos de ejecución necesarios para poder resolver los problemas de forma exacta, se ha limitado el estudio para rutas de 8 clientes, y donde además se ha impuesto tiempo de corte al algoritmo para evitar que se extienda en exceso evaluando una determinada ramificación del problema, por lo que cuando el tiempo de ejecución es elevado, el valor objetivo obtenido puede no ser el valor óptimo, como se mostrará más adelante. En la primera tabla (Tabla 5) se muestran los resultados obtenidos para 5 problemas distintos cuando se emplea tanto 1 UAV como 4 UAVs. Estos UAVs tienen una configuración de alta velocidad de crucero y baja autonomía, lo cual provoca que en función de la configuración del problema (proximidad de los nodos entre sí), el efecto de incrementar el número de UAVs no se vea reflejado en el valor objetivo. Sin embargo, al aumentar el número de UAVs a 4, el tiempo de ejecución aumenta significativamente debido al aumento de la complejidad, y por ende, al número de posibles combinaciones/rutas que deben ser analizadas por el algoritmo. Este efecto se puede observar claramente en los dos últimos problemas, cuyo valor objetivo no varía entre el uso de 1 o 4 UAVs. Esto se debe a que en las rutas calculadas, se usa únicamente un UAV o incluso ninguno, ya que la distancia entre los nodos es muy elevada y la baja autonomía de los UAVs no permite emplear los drones para colaborar con el camión. A continuación se muestran dos imágenes, en la primera se representan los nodos del primer problema de la tabla, el cuál si tiene obtiene una mejora al aumentar el número de UAVS, ya que sus nodos están cerca entre sí, y por lo tanto los UAVs pueden realizar tareas de reparto. En cambio, en la segunda imagen se muestra el último problema, el cual tiene sus nodos muy alejados entre sí, impidiendo que los UAVs con baja autonomía puedan colaborar en las tareas de reparto. 31 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 10. Izquierda: Representación de los clientes del problema 20170608T121355407419 Derecha: Representación de los clientes del problema 20170608T1214581741656 Tabla 5. Resultados para UAVs de alta velocidad y baja autonomía ID PROBLEMA Nº UAVS TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 3,68 3408,71 20170608T121355407419 4 11,08 3268,92 20170608T121411132375 1 7,91 3916,98 20170608T121411132375 4 11,25 3856,98 20170608T121426910678 1 5,02 3192,12 20170608T121426910678 4 11,53 3115,57 20170608T121442695307 1 6,31 3127,97 20170608T121442695307 4 11,81 3127,97 20170608T121458174165 1 4,87 5527,23 20170608T121458174165 4 8,04 5527,23 6 Elaboración propia 32 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones En la Tabla 6 se muestran los resultados para los mismos problemas que en la tabla anterior, pero con UAVs de alta velocidad y autonomía. Puesto que en esta ocasión los UAVs tienen una mayor autonomía, el tiempo de ejecución aumenta al ser necesario evaluar una mayor cantidad de combinaciones. Por otra parte, se observa cómo los tiempos totales empleados en la ruta disminuyen respecto a la tabla anterior, ya que se pueden emplear más UAVs. Sin embargo, se observa otro fenómeno que podría resultar extraño en un primer momento, pero que tras analizarlo, muestra la debilidad que tiene el uso de algoritmos exactos en este tipo de problemas. Este fenómeno es el aumento del valor objetivo cuando se emplean 4 UAVs en vez de 1. Esto carece de sentido, ya que aumentar el número de UAVs no debería de repercutir negativamente sobre el tiempo total empleado en realizar en una ruta, si no que debería de mejorar el valor, o como se ha visto anteriormente, en el peor de los casos, mantener el mismo valor objetivo. En esta ocasión, este aumento se debe a la utilización de un tiempo de cutoff o corte cuando el algoritmo exacto está durante demasiado tiempo en una misma rama de la solución. Esto permite que el algoritmo exacto no eleve en exceso su tiempo de ejecución, pero tiene la contrapartida de que se dejan de calcular rutas/subrutas, cuya solución pueda ser la óptima. Debido al aumento de la complejidad al emplear un mayor número de UAVs, el efecto que tiene este tiempo de cutoff se hace cada vez más importante, hasta llegar a provocar distorsiones como las que se pueden ver en la tabla siguiente. Tabla 6. Resultados para UAVs de alta velocidad y alta autonomía ID PROBLEMA Nº UAVS TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 7,81 2831,6 20170608T121355407419 4 15,49 3009,5 20170608T121411132375 1 10,29 3060,52 20170608T121411132375 4 15,34 3180,81 20170608T121426910678 1 10,32 2895,11 20170608T121426910678 4 15,62 2826,96 20170608T121442695307 1 10,37 2428,75 20170608T121442695307 4 16,87 1909,75 20170608T121458174165 1 10,21 4351,94 20170608T121458174165 4 13,57 5085,69 Para finalizar, las dos últimas configuraciones establecidas en este proyecto; baja velocidad y autonomía, y baja velocidad y alta autonomía se muestran en las tablas siguientes (Tabla 7 y Tabla 8). En estas tablas se pueden observar los efectos mencionados anteriormente para las dos configuraciones de UAVs anteriores. Además, a partir de la comparación con las configuraciones anteriores, se desprende que el valor objetivo se ve influenciado en mayor medida por la autonomía de los UAVs que por la velocidad de los mismos, ya que para igualdad de velocidades y distintas autonomías, el cambio observado en el valor objetivo es mucho mayor que cuando se comparan dos configuraciones de UAVs con autonomías similares, pero velocidades distintas. 33 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Tabla 7. Resultados para UAVs de baja velocidad y baja autonomía ID PROBLEMA Nº UAVS TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 10,19 3498,92 20170608T121355407419 4 13,12 3422,62 20170608T121411132375 1 10,19 3789,38 20170608T121411132375 4 13,11 4117,35 20170608T121426910678 1 10,22 3422,1 20170608T121426910678 4 13,79 3530,81 20170608T121442695307 1 10,25 2870,11 20170608T121442695307 4 14,41 2477,53 20170608T121458174165 1 6,09 5133,03 20170608T121458174165 4 11,8 5133,03 Tabla 8. Resultados para UAVs de baja velocidad y alta autonomía ID PROBLEMA Nº UAVS TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 10,36 3285,22 20170608T121355407419 4 16,79 2553,81 20170608T121411132375 1 10,32 3638,32 20170608T121411132375 4 15,95 2840,07 20170608T121426910678 1 10,33 3150,78 20170608T121426910678 4 16,13 2932,32 20170608T121442695307 1 10,39 3008,53 20170608T121442695307 4 17,2 2001,78 20170608T121458174165 1 10,3 4582,01 20170608T121458174165 4 15,56 3230 34 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones 5.2 Heurística secuencial vs paralela Una vez expuestos los resultados para el algoritmo exacto, el siguiente paso es mostrar los resultados obtenidos mediante la implementación de la heurística descrita en capítulos anteriores, así como mostrar una comparativa entre la heurística secuencial, paralela y el algoritmo exacto. Para ello, se han dividido estos resultados por los distintos factores que pueden afectar tanto al valor objetivo como al tiempo de ejecución. Estos son:  Número de clientes o nodos  Tipología de los UAVs  Número de UAVs empleados  Número de iteraciones del algoritmo heurístico 5.2.1 Comparación por número de clientes (nodos) En primer lugar, se comenzará por el estudio de los resultados obtenidos en función del número de clientes o nodos. Puesto que este parámetro es el principal en cuanto al efecto que provoca sobre el tiempo de ejecución y el valor objetivo, se realizará un análisis más detallado, descomponiendo los resultados en problemas de 8, 25 50 y 100 clientes. 5.2.1.1 8 clientes En la Tabla 9 se muestran los resultados de la heurística secuencial para el caso de que los UAVs empleados tengan una alta velocidad y una baja autonomía. En esta tabla se observan los resultados para distintos problemas en función del número de UAVs y del número de iteraciones del algoritmo heurístico. Estos resultados vienen descritos por los tiempos empleados en las distintas fases de la heurística, el tiempo total de ejecución y el valor objetivo obtenido. Desde un primer momento, contrastan los valores de tiempo de ejecución obtenidos mediante el algoritmo heurístico frente al algoritmo exacto, aunque esto podrá observase mejor más adelante. Otro aspecto que se puede observar, es que para ciertos problemas, el valor objetivo es independiente del número de UAVs o de iteraciones. Esto se debe que al igual que el algoritmo exacto tenía sus ventajas y desventajas, la heurística permite acercarnos al valor objetivo en un tiempo de ejecución muy bajo, pero sin embargo, puede descartar ciertas ramas de soluciones que inicialmente puedan parecer poco probables de ser la solución óptima, llevando a que en ciertos casos, incluso aumentando el número de iteraciones, el algoritmo no sea capaz de aproximarse más a la solución óptima. Esto se verá en mayor profundidad en el apartado destinado al estudio del efecto del número de iteraciones sobre el valor objetivo y el tiempo de ejecución. Un aspecto a destacar de los resultados mostrados es el tiempo empleado en la fase 2. Como se había mencionado anteriormente, esta fase de la heurística es la menos relevante desde un punto de vista del tiempo de ejecución, y esto queda claramente evidenciado en esta tabla, ya que a pesar de que el tiempo total es muy bajo, la influencia de la fase 2 es prácticamente nula. De igual forma, la fase 1 tiene un elevado peso en el tiempo de ejecución, sobre todo cuando se incrementa el número de iteraciones, permaneciendo casi invariable el tiempo empleado en la fase 3. Como se irá viendo conforme se aumente el número de clientes a visitar, el peso de cada fase irá variando, llegando a pasar a ser la fase 3 la fase con mayor peso en el tiempo total de ejecución. Sin embargo, y como se ha comentado anteriormente, la fase 2 permanecerá siempre en un segundo plano en lo que a tiempo de ejecución se refiere. 35 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Tabla 9. Heurística secuencial: UAVs de alta velocidad y baja autonomía para 8 clientes ID PROBLEMA Nº UAV ITER T1 T2 T3 TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 1 0,02 - 0,01 0,03 3425,66 20170608T121355407419 4 1 0,03 - 0,01 0,03 3282,74 20170608T121355407419 1 10 0,08 - 0,01 0,09 3425,66 20170608T121355407419 4 10 0,11 0 0,01 0,12 3282,74 20170608T121411132375 1 1 0,02 0 0,02 0,04 4024,26 20170608T121411132375 4 1 0,02 0 0,03 0,05 4024,26 20170608T121411132375 1 10 0,05 0 0,04 0,09 4024,26 20170608T121411132375 4 10 0,08 0 0,04 0,12 4024,26 20170608T121426910678 1 1 0,02 0 0,03 0,05 3222,12 20170608T121426910678 4 1 0,02 0 0,04 0,06 3192,12 20170608T121426910678 1 10 0,08 0 0,05 0,14 3205,57 20170608T121426910678 4 10 0,1 0 0,05 0,15 3192,12 20170608T121442695307 1 1 0,02 0 0,01 0,03 3168,29 20170608T121442695307 4 1 0,03 0 0,03 0,06 3251,66 20170608T121442695307 1 10 0,1 - 0,01 0,11 3168,29 20170608T121442695307 4 10 0,1 0 0,03 0,13 3251,66 20170608T121458174165 1 1 0,01 - 0 0,01 5527,23 20170608T121458174165 4 1 0,01 - 0 0,01 5527,23 20170608T121458174165 1 10 0,01 - 0 0,01 5527,23 20170608T121458174165 4 10 0,02 - 0 0,02 5527,23 En la siguiente tabla se muestran los resultados de la heurística en paralelo para la misma tipología de UAVs que en la tabla anterior, alta velocidad y baja autonomía. Esto permitirá comparar los resultados obtenidos entre ambas simulaciones sin tener que atender al efecto que provoca la tipología de los UAVs sobre los resultados. Como era de esperar, al tratarse de problemas de 8 clientes únicamente, los valores tanto de tiempo de ejecución como de valor objetivo no varían significativamente respecto a la implementación secuencial. Sin embargo, se pueden observar ciertas tendencias que en problemas de mayor complejidad se escenificarán con mayor claridad. Se trata de la disminución del tiempo de la fase 1, gracias a la implementación en paralelo de dicha fase, pero sin embargo, se produce un empeoramiento en los tiempos de las fases 2 y 3, ya que los cálculos realizados por la fase 1 no son los óptimos, al no contar con toda la información. Esto se debe a que la comunicación existente entre la fase 1 y las fases 2 y 3 permite que estas dos últimas fases siempre tengan la información actualizada 36 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones sobre las rutas calculadas por la fase 1, pero sin embargo la fase 1 recibe los resultados de las fases 2 y 3 con retraso. Esto provoca que los cálculos llevados por la fase 1 no sean tan buenos como los realizados por la heurística secuencial, forzando a las fases 2 y 3 a realizar más cálculos intermedios hasta poder llegar a una solución subóptima. Tabla 10. Heurística en paralelo: UAVs de alta velocidad y baja autonomía para 8 clientes ID PROBLEMA Nº UAV ITER T1 T2 T3 TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170608T121355407419 1 1 0,02 - 0,01 0,03 3425,66 20170608T121355407419 4 1 0,02 - 0,01 0,03 3282,74 20170608T121355407419 1 10 0,08 - 0,01 0,09 3425,66 20170608T121355407419 4 10 0,1 - 0,02 0,11 3282,74 20170608T121411132375 1 1 0,01 - 0,02 0,03 4024,26 20170608T121411132375 4 1 0,01 0 0,03 0,04 4024,26 20170608T121411132375 1 10 0,03 - 0,05 0,07 4024,26 20170608T121411132375 4 10 0,05 - 0,05 0,1 4024,26 20170608T121426910678 1 1 0,01 0 0,03 0,04 3222,12 20170608T121426910678 4 1 0 0 0,04 0,05 3192,12 20170608T121426910678 1 10 0,04 0 0,07 0,11 3205,57 20170608T121426910678 4 10 0,07 0 0,06 0,13 3192,12 20170608T121442695307 1 1 0,01 - 0,01 0,03 3168,29 20170608T121442695307 4 1 0,01 0 0,03 0,04 3251,66 20170608T121442695307 1 10 0,09 - 0,01 0,1 3168,29 20170608T121442695307 4 10 0,08 0 0,05 0,12 3251,66 20170608T121458174165 1 1 0,01 - 0 0,01 5527,23 20170608T121458174165 4 1 0,01 - 0 0,01 5527,23 20170608T121458174165 1 10 0,01 - 0 0,01 5527,23 20170608T121458174165 4 10 0,01 - 0,01 0,02 5527,23 Por último en la Tabla 11 se muestra una comparativa entre la heurística en paralelo y la secuencial. Además, se han añadido los resultados del algoritmo exacto para poder comparar los valores de los tres algoritmos. Los parámetros de los UAVs son los mismos que los empleados anteriormente: alta velocidad y baja autonomía. A partir de los valores mostrados en la tabla, se puede observar la clara mejora que ofrece el algoritmo heurístico frente al algoritmo exacto, que incluso para problemas pequeños (8 clientes), la reducción del tiempo de ejecución es muy notable, sin que esto perjudique en exceso al valor objetivo del algoritmo exacto. 37 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Esto se produce para ambos algoritmos heurísticos, tanto cuando se ejecuta secuencialmente como cuando se ejecuta en paralelo. Sin embargo, al tratarse de problemas de una complejidad baja, el efecto del tiempo de ejecución en paralelo es prácticamente nulo, al igual que el efecto sobre el valor objetivo. Es por ello que si el objetivo de este trabajo fuese mejorar el tiempo de ejecución de este tipo de problemas, la aproximación llevada a cabo con este algoritmo de ejecución en paralelo no sería la más adecuada. Sin embargo, más adelante se mostrará la importante mejora que ofrece esta implementación para problemas de mayor magnitud (50 o más clientes) frente a la ejecución secuencial, lo cual se alinea con el propósito inicial del trabajo. Tabla 11. Heurística secuencial vs paralela vs algoritmo exacto: UAVs de alta velocidad y baja autonomía para 8 clientes ID PROBLEMA TIEMPO EJECUCIÓN PARALELO [SEC] VALOR OBJETIVO PARALELO [SEC] TIEMPO EJECUCIÓN SECUENCIAL [SEC] VALOR OBJETIVO SECUENCIAL [SEC] TIEMPO EJECUCIÓN EXACTO [SEC] VALOR OBJETIVO EXACTO [SEC] 20170608T121355407419 0,03 3425,66 0,03 3425,66 3,5 3408,7 20170608T121355407419 0,03 3282,74 0,03 3282,74 11,1 3268,9 20170608T121355407419 0,09 3425,66 0,09 3425,66 3,5 3408,7 20170608T121355407419 0,11 3282,74 0,12 3282,74 11,1 3268,9 20170608T121411132375 0,03 4024,26 0,04 4024,26 7,9 3917,0 20170608T121411132375 0,04 4024,26 0,05 4024,26 11,3 3857,0 20170608T121411132375 0,07 4024,26 0,09 4024,26 7,9 3917,0 20170608T121411132375 0,1 4024,26 0,12 4024,26 11,3 3857,0 20170608T121426910678 0,04 3222,12 0,05 3222,12 4,7 3192,1 20170608T121426910678 0,05 3192,12 0,06 3192,12 11,4 3115,6 20170608T121426910678 0,11 3205,57 0,14 3205,57 4,7 3192,1 20170608T121426910678 0,13 3192,12 0,15 3192,12 11,4 3115,6 20170608T121442695307 0,03 3168,29 0,03 3168,29 5,5 3128,0 20170608T121442695307 0,04 3251,66 0,06 3251,66 11,7 3128,0 20170608T121442695307 0,1 3168,29 0,11 3168,29 5,5 3128,0 20170608T121442695307 0,12 3251,66 0,13 3251,66 11,7 3128,0 20170608T121458174165 0,01 5527,23 0,01 5527,23 4,4 5527,2 20170608T121458174165 0,01 5527,23 0,01 5527,23 7,3 5527,2 20170608T121458174165 0,01 5527,23 0,01 5527,23 4,4 5527,2 20170608T121458174165 0,02 5527,23 0,02 5527,23 7,3 5527,2 44 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones En la Tabla 17 se muestra una comparativa de los resultados entre la heurística secuencial y la heurística paralela. En primer lugar, destaca que se obtengan valores superiores de tiempo de ejecución para la ejecución paralela frente a la secuencial en dos ocasiones. Ambas simulaciones se corresponden con dos problemas que son evaluados con 4 UAVs y 10 iteraciones, lo cual provoca que la fase 1 aumente considerablemente su tiempo de ejecución. Como ya se ha comentado anteriormente, este hecho provoca que la ejecución en paralelo pierda efectividad. Además, en estos dos casos sucede que el tiempo de la fase 1 ya era el predominante en el algoritmo secuencial, por lo que la introducción del algoritmo en paralelo tiene un efecto adverso, ya que debido a la concepción del mismo y su necesidad de comunicarse entre los distintos hilos ejecutándose en paralelo, se introduce una pérdida de tiempo que en el algoritmo secuencial no existía, dando lugar a un efecto negativo en el cómputo global del tiempo de ejecución. Por otra parte, el valor objetivo permanece en la mayoría de casos inmutable entre ambos algoritmos, pero en dos ocasiones el valor es inferior para la ejecución secuencial, y en otras dos ocasiones lo es para la ejecución en paralelo. A pesar de esta variación, la diferencia es muy pequeña y por lo tanto no debe ser tenido en cuenta a la hora de sacar conclusiones. Este efecto se debe a la propia heurística del problema, la cual puede llevar a que ante variaciones en la subruta calculada por la fase 1 (paralelo o secuencial), los resultados difieran en mayor medida que para otros problemas, llevando a las fases 2 y 3 a alcanzar resultados distintos. 5.2.1.4 100 clientes Por último, se llega a los problemas de 100 clientes, los cuales serán los problemas más complejos que sean objeto de estudio en este trabajo. Debido a la magnitud de estos problemas, se ha decidido reducir las simulaciones realizadas a estos problemas a las distintas tipologías de UAVs, tomando constante tanto el número de UAVs como el número de iteraciones. Esto evita que los tiempos de ejecución sea muy elevados tanto para la heurística secuencial como paralela. Tabla 18. Heurística secuencial: UAVs de alta velocidad y baja autonomía para 100 clientes ID PROBLEMA Nº UAV ITER T1 T2 T3 TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170606T115437348436 1 1 59,76 3 25,99 88,76 19335,41 20170606T115823934453 1 1 34,4 2,91 29,87 67,18 19144,83 20170606T120227545709 1 1 41,68 4,24 18,72 64,64 20037,26 20170606T121241353494 1 1 32,61 2,75 47,4 82,76 19014,19 20170606T121632081849 1 1 40,53 6,03 22,41 68,97 18689,6 Tabla 19. Heurística en paralelo: UAVs de alta velocidad y baja autonomía para 100 clientes ID PROBLEMA Nº UAV ITER T1 T2 T3 TIEMPO EJECUCIÓN [SEC] VALOR OBJETIVO [SEC] 20170606T115437348436 1 1 38,77 4,47 39,41 82,64 19335,41 20170606T115823934453 1 1 7,03 4,36 46,6 57,99 19144,83 20170606T120227545709 1 1 24,89 6,66 27,19 58,74 20037,26 20170606T121241353494 1 1 8,58 3,93 61,64 74,15 19030,22 20170606T121632081849 1 1 19,21 8,62 32,76 60,59 18689,6 45 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Tabla 20. Heurística secuencial vs heurística en paralelo: UAVs de alta velocidad y baja autonomía para 100 clientes ID PROBLEMA TIEMPO EJECUCIÓN SECUENCIAL [SEC] VALOR OBJETIVO SECUENCIAL [SEC] TIEMPO EJECUCIÓN PARALELO [SEC] VALOR OBJETIVO PARALELO [SEC] 20170606T115437348436 88,76 19335,41 82,64 19335,41 20170606T115823934453 67,18 19144,83 57,99 19144,83 20170606T120227545709 64,64 20037,26 58,74 20037,26 20170606T121241353494 82,76 19014,19 74,15 19030,22 20170606T121632081849 68,97 18689,6 60,59 18689,6 En la Tabla 20 se comparan los valores de las simulaciones, destacando nuevamente un valor objetivo superior en la ejecución en paralelo frente a la ejecución secuencial. Al igual que sucedía para algunos problemas de 50 clientes, este efecto es causado por la propia heurística y su dependencia del valor inicial calculado por la fase 1, la cual a su vez depende de la comunicación establecida entre los hilos ejecutados en paralelo, y puesto que la información es transferida con retraso, esto puede llegar a causar este tipo de fenómenos. Sin embargo, y al igual que sucedía anteriormente, su efecto es prácticamente despreciable sobre el valor objetivo. 5.2.1.5 Comparativa Para finalizar este apartado del estudio se realizará una breve recopilación de la información mostrada hasta ahora en tablas en forma de gráficas de barras que permitan resumir lo expuesto anteriormente. Para llevar a cabo esta comparativa, se dividirá este apartado en:  Evaluación de fases: o Fase 1 o Fases 2 y 3  Tiempo total de ejecución  Valor objetivo A su vez, se atenderá tanto a distintos tipos de problemas (diferente cantidad de clientes) como distintos tipos de UAVs: alta/baja velocidad y alta/baja autonomía. En la primera figura se representan los tiempos de ejecución de la fase 1 para cada una de las tipologías de UAVs y para cada agrupación de problemas por número de clientes. En los apartados anteriores se han mostrado en tablas las simulaciones siempre para una misma tipología de UAV, la cual se correspondía con la tipología 101 (alta velocidad y baja autonomía). En cambio, en esta primera imagen se pueden extraer conclusiones de los restantes tipos de UAVs. En primer lugar, para valores elevados de T1 para el algoritmo heurístico secuencial, el algoritmo paralelo pierde eficiencia, ya que valores altos de T1 significa que su peso sobre el valor total del tiempo de ejecución es muy predominante, impidiendo acelerar la obtención de la ruta subóptima. Esto último se podrá observar y comprender mejor con las gráficas de las fases 2 y 3 del algoritmo que se muestran en la Figura 11. En siguiente lugar, es necesario comentar que estos son los valores medios, sin atender a otros criterios como el número de iteraciones, puesto que esta casuística será estudiada más adelante en el apartado destinado para ello. 46 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 11. Tiempo de ejecución en la fase 1 para distintos números de clientes y tipologías de UAVs Figura 12. Tiempo de ejecución en las fases 2 y 3 para distintos números de clientes y tipologías de UAVs 47 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones En la Figura 11 se muestran los resultados de los tiempos de ejecución medios de las fases 2 y 3. Como era de esperar, estos tiempos son superiores para el algoritmo ejecutado en paralelo que para el algoritmo ejecutado de forma secuencial. Esto se debe al empeoramiento de las subrutas calculadas por la fase 1 cuando se ejecuta en paralelo, como ya se ha expuesto anteriormente. Un aspecto importante y que ha sido mencionado en los resultados de la fase 1 es el efecto que tiene la predominancia de la fase 1 sobre el resto de fases cuando se evalúan los tiempos de ejecución, ya que cuando esta predominancia es muy elevada, como puede ser el caso de la gráfica para los UAVs de tipo 104 y 100 clientes, donde la diferencia entre la fase 1 y las fases 2+3 es muy elevada, provocando que el ahorro de tiempo en la fase 1 sea muy bajo, mientras que si nos fijamos en esa misma gráfica (104), pero para 50 clientes, las fases 2+3 representan prácticamente la mitad del tiempo de ejecución, lo que permite que el ahorro de tiempo de ejecución en la fase 1 sea muy elevado sin que exista un perjuicio muy elevado en las fases 2 y 3. En siguiente lugar se muestran las gráficas para el tiempo total de ejecución (Figura 12), la cual permitirá dar una visión completa sobre el efecto del número de clientes sobre el tiempo de ejecución. Figura 13. Tiempo de ejecución total para distintos números de clientes y tipologías de UAVs Al igual que sucedía en las figuras de los tiempos de ejecución por fases, para el tiempo total de ejecución se cumple que en aquellos casos donde los tiempos de la fase 1 y las fases 2+3 son similares, el tiempo total de ejecución se ve reducido en mayor medida que en los casos en los que la fase 1 ejerce una fuerte predominancia sobre las otras dos fases. Finalmente se muestran las gráficas del valor objetivo para las distintas clasificaciones por clientes y por tipología de UAVs. Al igual que sucedía en los apartados anteriores, donde este valor objetivo no se veía influenciado por el uso del algoritmo en paralelo para UAVs del tipo 101, ahora se puede observar también en la Figura 13 que para el resto de tipologías los resultados son los mismos para un algoritmo que para el otro. 48 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 14. Valor objetivo para distintos números de clientes y tipologías de UAVs 5.2.2 Comparación por tipo de UAV Una vez finalizado el apartado de resultados en función del número de clientes, se explicará la influencia que ejercen los distintos tipos de UAVs sobre el tiempo total de ejecución y sobre el valor objetivo. Este análisis ya se ha realizado brevemente en el apartado anterior, ya que ejercía una gran influencia. Es por ello que en esta ocasión se representará la información de forma distinta a anteriormente. En las gráficas que se mostrarán en este apartado no se mostrarán los valores absolutos de tiempo de ejecución y de valor objetivo, si no que se mostrará su variación porcentual respecto a un valor de referencia. Este valor de referencia será el valor de las simulaciones para la tipología 101 de UAV, de la que se ha extraído casi toda la información del apartado anterior. Es por ello, que al tener perfectamente identificado el comportamiento del algoritmo ante ese tipo de UAVs, se mostrarán los resultados del resto respecto a dicho valor. En la Figura 14 se muestra la comparativa de las distintas tipologías de UAVs por su tiempo total de ejecución en función del número de clientes, siendo para el valor de 8 clientes el único en el que se incluye también el algoritmo exacto. A partir de las gráficas se observa que la tipología 101 es siempre la que conlleva un menor tiempo de ejecución, siendo la más cercana la tipología 102 para pocos clientes (8 y 25), y la tipología 103 para problemas más complejos (100 clientes). En contrapartida, la tipología 104 es la más costosa en cuanto a recursos computacionales, ya que es la que conlleva más tiempo de ejecución. Esto tiene sentido ya que esta tipología (baja velocidad y alta autonomía) es justo la contraria a la tipología 101 (alta velocidad y baja autonomía). Con todo esto, se puede extraer que cuando se emplean UAVs de alta velocidad (101 y 102), los tiempos de ejecución son bajos para problemas simples, mientras que valores bajos de autonomía (101 y 103) permiten reducir el tiempo de ejecución cuando se trata de un problema más complejo, ya que se reducen el número de posibilidades al descartarse subrutas al no ser alcanzables por los UAVs. 49 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 15. Comparativa por tipología UAV: Variación tiempo total respecto a tipología 101 Figura 16Figura 14. Comparativa por tipología UAV: Variación valor objetivo respecto a tipología 101 50 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Por último, en la Figura 15 se muestran las mismas gráficas pero para los valores objetivos. En esta ocasión, tener valores bajos de velocidad (103-104) provoca que aumente el valor objetivo cuando el problema es complejo (50-100 clientes). En cambio, para problemas simples (8-25), todas las tipologías ofrecen valores objetivos inferiores a los de la tipología de referencia (101). 5.2.3 Comparación por número de UAVs La siguiente comparativa que se va a realizar es el efecto que tiene la variable número de UAVs sobre las simulaciones. Para ello, se va a emplear nuevamente la tipología de UAV 101 (alta velocidad, baja autonomía) para comparar los resultados obtenidos. En primer lugar se muestra la gráfica para 1 UAV y para 4 UAVs con sus tiempos medios en la fase 1 para distintos números de clientes. Se puede observar que los valores tanto para el algoritmo secuencial como para el paralelo son superiores cuando se emplean 4 UAVs que cuando se emplea 1, ya que al tener más UAVs, el problema se vuelve más complejo y aparecen más posibles combinaciones a evaluar. Por otra parte, y como se ha comentado anteriormente, debido al elevado coste computacional que tiene simular problemas de 100 clientes, se ha decidido simular únicamente estos problemas para 1 iteración, 1 uav y todas las tipologías de UAV, por lo que como se puede observar en la gráfica para 4 UAVs, no existen valores para 100 clientes. En cuanto a la diferencia entre la heurística secuencial y paralela, se observa que el ahorro de tiempo en la fase 1 es muy superior para 1 UAV que para 4, ya que el tiempo invertido en las fases 2 y 3 es similar al tiempo de la fase 1, como se puede observar comparando las dos gráficas de fase 1 (Figura 16) con las de las fases 2 y 3 (Figura 17). Este efecto de ahorro de tiempo también puede observarse en las gráficas del tiempo total de ejecución, aunque la diferencia entre 1 UAV y 4 es inferior que en la fase1, sigue obteniéndose un ahorro mayor en simulaciones con 1 UAV que con 4. Figura 17Figura 14. Comparativa por número de UAV: Tiempo fase 1 Figura 18. Figura 14Comparativa por número de UAV: Tiempo fases 2+3 51 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 19. Comparativa por número de UAV: Tiempo total Figura 20. Comparativa por número de UAV: Valor objetivo Por último, como se lleva viendo en todos los resultados anteriores, cambiar el número de UAVs no afecta directamente en una mejora o un empeoramiento del valor objetivo. 5.2.4 Comparación por número de iteraciones Finalmente, se va a repetir el mismo estudio que para el número de UAVs, pero en este caso para el número de iteraciones del algoritmo heurístico. En las gráficas siguientes se puede observar que los resultados obtenidos, y por lo tanto, las conclusiones que se pueden extraer son muy similares a las de la comparativa por número de UAVs. La fase 1 tiene un mayor ahorro para los casos en los que se simula una única iteración, ya que el peso de la fase 1 es muy cercano al peso de las fases 2 y 3, conllevando por tanto una mejora del tiempo total de ejecución. Por otra parte, los valores absolutos de cada una de las gráficas son superiores en el caso de 10 iteraciones que en el caso de 1 iteración. Esto era de esperar, ya que al aumentar el número de iteraciones del algoritmo, se incrementa el tiempo de ejecución, sin embargo, a pesar de que estas iteraciones se aumenten en 10 veces, el tiempo de ejecución no se incrementa de forma proporcional. Esto se debe a que una vez obtenida una ruta subóptima, las nuevas rutas se van comparando continuamente con dicha ruta, y en el momento que una subruta y su rama de posibles soluciones supera en tiempo a dicha ruta subóptima, se pasa al siguiente paso en el bucle, consiguiendo reducir drásticamente el tiempo de ejecución de cada nueva iteración que se calcula. En contrapartida, cada iteración que se añade incrementa el tiempo total de ejecución, pero sin embargo no ofrece una mejora sobre el valor objetivo significativa, por lo que este fenómeno puede deberse tanto a un efecto positivo como uno negativo. El punto negativo sería que la heurística empleada en este trabajo no es capaz de encontrar las rutas óptimas cuando el problema crece en complejidad, quedándose en mínimos locales, pero siendo incapaz de alcanzar el mínimo global. El punto positivo podría ser que la ruta subóptima calculada con la primera iteración ya se acerca mucho al óptimo global, por lo que aumentar el número de iteraciones genera un beneficio muy pequeño. 52 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Para poder conocer cuál de las dos opciones es la correcta, sería necesario ejecutar el algoritmo exacto para problemas de mayor complejidad, pero como se ha comentado anteriormente, incluso para problemas de complejidad media-baja (25 clientes), simular el algoritmo exacto ha sido inviable con los medios computacionales habilitados para este proyecto. Figura 21. Comparativa por número de iteraciones: Tiempo fase 1 Figura 22. Comparativa por número de iteraciones: Tiempo fases 2+3 Figura 23. Comparativa por número de iteraciones: Tiempo total 53 Desarrollo y programación de una aplicación multihilo para planificación de rutas de drones Figura 24. Comparativa por número de iteraciones: Valor objetivo Por último, se incluyen dos tablas en las que se observa la baja efectividad que se obtiene aumentando el número de iteraciones, ya que mientras que el óptimo local mejora muy levemente, el tiempo de ejecución de la heurística aumenta considerablemente. En la primera tabla se muestran los resultados para simulaciones con 50 clientes y el algoritmo heurístico ejecutado en paralelo. Tabla 21. Heurística en paralelo: Comparativa para distintas iteraciones para problemas de 50 clientes ID PROBLEMA VALOR OBJETIVO [SEC] (1 ITER) VALOR OBJETIVO [SEC] (10 ITER) VALOR OBJETIVO [SEC] (100 ITER) 20170606T114000833192 12806,86 12806,86 12806,86 20170606T114145593946 12726,22 12638,89 12638,89 20170606T114330252507 12515,7 12515,7 12515,70 20170606T114511221132 10954,97 10925,85 10925,85 20170606T114654882472 12678,58 12629,29 12629,29 En segundo lugar, se muestran la comparativa para problemas de 100 clientes. En esta ocasión se han incluido también los tiempos de ejecución para que se pueda observar el incremento que existe entre el tiempo empleado en 1 iteración y en 100 iteraciones, mientras que la mejora del mínimo local es muy reducida.