Reconstrucción de trayectorias de aeronaves usando Simulated Annealing para resolver una versión del problema del viajante (TSP)

ESCUELA DE INGENIER´ IA INFORM ´ ATICA DE SEGOVIA Grado en Ingenier´ıa Inform´ atica de Servicios y Aplicaciones Reconstrucci´ on de trayectorias de aeronaves usando Simulated Annealing para resolver una versi´ on del problema del viajante (TSP) Alumna: Mar´ ıa Zorita M´ ınguez Tutores: Miguel ´ Angel Mart´ ınez Prieto Anibal Breg´ on Breg´ on “Todos tus sue˜nos pueden hacerse realidad si tienes el coraje de perseguirlos” Walt Disney “La confianza en s´ı mismo es el primer secreto del ´exito” Ralph Waldo Emerson Agradecimientos Quiero dar las gracias en primer lugar a mis tutores, Anibal Breg´on Breg´on y Miguel ´ Angel Mart´ınez Prieto, por darme la posibilidad de participar en el proyecto “AIRPORTS” en el que ellos colaboran, as´ı como por toda su dedicaci´on y apoyo en el desarrollo del mismo. Adem´as, dar las gracias a mi tutor del Trabajo de Fin de Grado de Matem´aticas, Pedro C´esar ´ Alvarez Esteban, ya que junto con mis tutores me ha permitido formar parte de este proyecto y con ello poder realizar ambos trabajos de fin de carrera de manera coordinada y conjunta. Tambi´en dar las gracias a Boeing Research and Technology Europe (BR&T-E), ya que la realizaci´on del presente trabajo se enmarca en la colaboraci´on que llevan a cabo diversos miembros de la Universidad de Valladolid con ellos. Por ello, quiero agradecerles toda la informaci´on y datos aportados sobre las trayectorias de los vuelos, dado que han sido de gran importancia para la realizaci´on del trabajo. Dar las gracias tambi´en a mi compa˜nero Juan Manuel Velasco Heras por su apoyo y amistad durante estos 5 a˜nos que hemos estado juntos, y en particular, por la convivencia durante los ´ultimos a˜nos de la carrera. Adem´as, dar las gracias a toda mi familia y amigos, y en especial a mi madre, por su apoyo incondicional y por darme ´animos en los momentos que m´as lo necesitaba. i Resumen Una de las l´ıneas de investigaci´on del proyecto AIRPORTS (CIEN, 2015), liderado por Boeing Research and Technology Europe (BR&T-E), se centra en el estudio de la eficiencia de los vuelos de diferentes aeronaves comerciales teniendo en cuenta las trayectorias que describen. Dichas trayectorias se construyen a partir de datos ADS-B que son obtenidos de diferentes proveedores y captados por entidades receptoras presentes a lo largo del planeta. El problema surge cuando al realizar la fusi´on de todos los datos capturados para construir cada una de las trayectorias, se observa el fallo en el alineamiento temporal de las se˜nales, debido principalmente, al retardo en el tiempo de recepci´on de los mensajes y a la falta de sincronizaci´on horaria presente en algunas entidades receptoras. Por ello, el presente proyecto tiene como objetivos principales abordar el problema comentado con anterioridad, logrando reconstruir las trayectorias reales proporcionadas mediante la aplicaci´on de ciertos algoritmos, as´ı como reasignar los tiempos a los datos alterados en la reordenaci´on. Para ello, se busca modelizar el problema planteado como una variante del problema conocido como “El problema del viajante” (Traveling Salesman Problem, TSP), donde los nodos inicial y final son diferentes, buscando el camino hamiltoniano de m´ınima longitud. El algoritmo estudiado y analizado para resolver dicho problema ser´a el Simulated Annealing, ya que se tiene constancia de que funciona bien en contextos y situaciones muy diversas. Se trata de un algoritmo estoc´astico de optimizaci´on, dise˜nado principalmente para resolver problemas generales en los que existen muchos ´optimos locales, y que por sus caracter´ısticas, se espera que funcione bien y se obtengan resultados satisfactorios en el caso del problema planteado. Esto se debe a que en dicho problema la soluci´on ´optima global dista poco o no demasiado de la soluci´on de partida. Una vez realizado el proyecto, se puede concluir que los objetivos fijados han sido cumplidos con ´exito, ya que se ha podido dar una soluci´on escalable al problema planteado mediante la implementaci´on de la heur´ıstica de mejora Simulated Annealing usando el modelo de programaci´on MapReduce. Dado que los resultados obtenidos al aplicar dicho algoritmo a las distintas trayectorias de vuelo mejoran la situaci´on de partida, el estudio realizado sirve para mejorar y avanzar en la gesti´on del tr´afico a´ereo. Palabras claves: Recocido simulado, El problema del viajante, ADS-B, Big Data. iii Abstract One of the research lines of the AIRPORTS project (CIEN, 2015), led by Boeing Research and Technology Europe (BR&T-E), focuses on the study of flight efficiency of different commercial aircrafts taking into account the flight paths. These flight paths are constructed from ADS-B data that are obtained from different providers and collected by receivers present throughout the planet. The problem arises when merging all the captured data used for constructing each one of the flight paths, the error in the temporal alignment of the signals is observed, mainly due to the delay time of reception of the messages and lack of time synchronization between the receivers. Therefore, this project aims at addressing the problem discussed previously, managing to reconstruct the real flight paths provided by applying certain algorithms as well as reassigning the times to the altered data in the reording. To do this, we seek to model the problem raised as a variant of the problem known as “The Traveling Salesman Problem (TSP)”, where the initial and final vertex are different, looking for the Hamiltonian path of minimum length. The algorithm studied and analyzed to solve this problem will be the Simulated Annealing since it is known to provide good performance in very diverse contexts and situations. It is a stochastic optimization algorithm, designed mainly to solve general problems in which there are many local optimum, and because of its characteristics, it’s expected to work well and obtain satisfactory results in the case of the problem posed. This is because in case of the problem raised, the global optimal solution is not far from the starting point solution. Once the project is finished, it can be concluded that the goals set have been met successfully met, as it has been possible to provide a scalable solution to the problem raised through an implementation of the Simulated Annealing improvement heuristics using the MapReduce programming model. Given that the results obtained by applying this algorithm to the different flight paths improve the starting situation, the study carried out serves to improve the Air Traffic Management operations. Keywords: Simulated Annealing, Traveling Salesman Problem, ADS-B, Big Data. iv ´ Indice general Lista de figuras VII Lista de tablas IX 1. Introducci´on 1 1.1. Motivaci´on.................................... 2 1.2. Objetivos .................................... 3 1.3. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Plan del proyecto 7 3. Air Traffic Management (ATM) 13 3.1. Single European Sky ATM Research (SESAR) . . . . . . . . . . . . . . . . 14 3.2. ADS ....................................... 16 3.3. AIRPORTS ................................... 18 3.4. Problemaaconsiderar ............................. 20 4. Traveling Salesman Problem (TSP) 23 4.1. Definici´on .................................... 23 4.2. Historia ..................................... 23 4.3. Aplicaciones................................... 26 4.4. Complejidad................................... 27 4.5. Teor´ıadeGrafos ................................ 28 4.6. Heur´ısticas para encontrar una ruta factible . . . . . . . . . . . . . . . . . 32 4.6.1. Heur´ısticas constructivas . . . . . . . . . . . . . . . . . . . . . . . . 32 4.6.1.1. Heur´ıstica del vecino m´as pr´oximo . . . . . . . . . . . . . 32 4.6.1.2. Heur´ıstica de inserci´on . . . . . . . . . . . . . . . . . . . . 34 4.6.1.3. Heur´ıstica de Christofides . . . . . . . . . . . . . . . . . . 35 4.6.2. Heur´ısticas de mejora . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.6.2.1. Heur´ısticas de mejora k-opt o de Lin-Kernighan . . . . . . 36 4.6.2.2. Heur´ısticas de mejora aleatorias . . . . . . . . . . . . . . . 37 4.7. Fundamento te´orico de la soluci´on . . . . . . . . . . . . . . . . . . . . . . . 45 5. Estudio preliminar de los algoritmos en R-Studio 51 5.1. Descripci´on del entorno y herramientas usadas . . . . . . . . . . . . . . . . 53 5.2. Implementaci´on del dashboard . . . . . . . . . . . . . . . . . . . . . . . . . 56 v 1.1. Motivaci´on Dentro de este marco de investigaci´on, surge el proyecto “AIRPORTS (CIEN, 2015)” liderado por Boeing Research and Technology Europe, el cual, entre otras muchas l´ıneas de investigaci´on, busca estudiar como mejorar la eficiencia de los vuelos de aeronaves comerciales en funci´on de la trayectoria que estos describen al realizar dicho vuelo. Dichas aeronaves est´an equipadas con un sistema conocido como Automatic Dependant Surveillance Broadcast (ADS-B) que se encarga de enviar diferentes mensajes ADS-B describiendo el estado del vuelo en cada momento. Estos mensajes contienen informaci´on de importancia como: el identificador del mensaje, el tiempo de recepci´on (timestamp), la posici´on (en t´erminos de longitud, latitud y altitud) de la aeronave, su velocidad (tanto horizontal como vertical), si est´a o no en suelo, la fecha de realizaci´on, etc. Adem´as, se necesitan diferentes redes de sensores distribuidas por distintas partes del planeta, las cuales, permiten obtener diversas fuentes de datos ADS-B. Dichas redes de sensores pueden ser comerciales o no. Una vez que se reciben los mensajes ADS-B que describen el estado del vuelo, el equipo del proyecto “AIRPORTS” los utiliza para reconstruir las distintas trayectorias de vuelo. Gracias a su reconstrucci´on es posible realizar su estudio, y para ello, se usa una plataforma Big Data, la cual, es un prototipo que permite calcular una gran variedad de m´etricas de eficiencia. 1.1. Motivaci´on La motivaci´on de este proyecto surge cuando al estudiar dichas trayectorias nos damos cuenta de que hay problemas con respecto al alineamiento temporal de las se˜nales obtenidas. Las causas principales de dicho problema son: el retardo en el tiempo de recepci´on de dichos mensajes y la falta de sincronizaci´on horaria existente entre algunas entidades receptoras. Por lo tanto, nuestro prop´osito es dar una soluci´on a dicho problema, reconstruyendo las trayectorias para obtener soluciones lo m´as pr´oximas posibles a las trayectorias que realmente fueron voladas por las aeronaves. El objeto de estudio presenta cierta relaci´on con problemas ya existentes y estudiados desde hace mucho tiempo como es la teor´ıa de grafos, la optimizaci´on, etc. pudiendo adem´as ser formulado como un problema matem´atico que es una variante del famoso problema conocido como “El problema del viajante o Traveling Salesman Problem (TSP)”. Dicho problema consiste en lo siguiente: dado un n´umero nde ciudades, se debe buscar el camino de coste m´ınimo formado por n+ 1 ciudades que pase por cada una de ellas en una ´unica ocasi´on, excepto para la primera, que tiene que ser visitada dos veces puesto que la ciudad de partida y de llegada deben coincidir, esto es, son la misma. 2 1.2. Objetivos 1.2. Objetivos El presente trabajo tiene los siguientes objetivos: 1. Realizar un estudio y an´alisis del comportamiento de distintos algoritmos cuando son aplicados a diferentes vuelos. Los subobjetivos que se derivan son: a. Construir un dashboard usando el entorno R-Studio. Con ello se pretende facilitar la realizaci´on del estudio preliminar sobre el funcionamiento de cada uno de los algoritmos considerados sobre distintos ejemplos. b. Aplicar, usando dicho dashboard, los algoritmos a mensajes ADS-B que definen vuelos reales, para as´ı poder hacer una comparativa de los mismos en cuanto a la distancia mejorada entre la trayectoria ordenada y la de partida, as´ı como en funci´on del tiempo de ejecuci´on. 2. Una vez realizado dicho estudio, considerar aquellos algoritmos que mejor se adapten o comporten frente al problema del fallo en la asignaci´on de tiempos en mensajes ADS-B. El subobjetivo que se deriva es el siguiente: a. Implementar de manera escalable usando el lenguaje Java y el modelo de programaci´on MapReduce el algoritmo propuesto en el proyecto, esto es, el Simulated Annealing. 3. Una vez aplicados los algoritmos correspondientes para ordenar las trayectorias, reasignar los tiempos o timestamps a los puntos que han sufrido cambios al realizar dicha ordenaci´on. El subobjetivo que se deriva es el siguiente: a. Estudiar y analizar diferentes modelos de optimizaci´on para realizar la interpolaci´on de los tiempos asociados a los puntos que han sufrido cambios. Con el logro de dichos objetivos se podr´a: Obtener una aproximaci´on m´as realista acerca de las trayectorias que realmente fueron voladas por las aeronaves, y como consecuencia de ello, utilizar los datos correspondientes para mejorar tanto la eficiencia como la seguridad del tr´afico a´ereo actual. 1.3. Estructura del documento El presente trabajo se va a estructurar en una serie de cap´ıtulos que se detallan y describen a continuaci´on: Cap´ıtulo 1. Introducci´on: Durante este cap´ıtulo, que es el presente, se realiza una peque˜na introducci´on para describir brevemente cu´al es el motivo por el que se plantea la realizaci´on del trabajo, as´ı como los objetivos que se persiguen conseguir. Cap´ıtulo 2. Plan del proyecto: Durante este cap´ıtulo se describe la metodolog´ıa o planificaci´on seguida para el desarrollo del presente trabajo de investigaci´on, esto es, c´omo se han ido realizando las diferentes tareas desde el inicio hasta la finalizaci´on del mismo. 3 1.3. Estructura del documento Cap´ıtulo 3. Air Traffic Management (ATM): Durante este cap´ıtulo se describe la situaci´on de la gesti´on del tr´afico a´ereo existente en la actualidad, as´ı como los nuevos sistemas de mejora que se est´an desarrollando. Tambi´en, se da una explicaci´on detallada sobre la importancia que tienen los mensajes ADS-B a la hora de determinar las trayectorias seguidas por las aeronaves, y los problemas que estos sistemas plantean. Finalmente, se describe el problema encontrado sobre el fallo en la sincronizaci´on de los tiempos de dichos mensajes, siendo el prop´osito del trabajo su mejora y resoluci´on. Como consecuencia de dicha mejora, se podr´an obtener trayectorias m´as pr´oximas a las que realmente fueron voladas por las aeronaves y realizar la reasignaci´on de tiempos correspondiente para aquellos puntos cuyo orden ha sido alterado. Para la realizaci´on de la primera parte de dicho cap´ıtulo ha sido de gran utilidad la lectura de los art´ıculos [10], [11] y [12] proporcionados por los tutores, ya que me han ayudado a conocer en mayor profundidad el entorno aeron´autico. Cap´ıtulo 4. Traveling Salesman Problem (TSP): Durante este cap´ıtulo se describe el problema del viajante ya que es una variante del problema que debemos resolver. Para resolver este problema existen diversos m´etodos que encuentran una ruta factible a trav´es de la b´usqueda de ciclos hamiltonianos, pero en la realizaci´on del trabajo, nos centraremos en los algoritmos de mejora, y en particular, en el algoritmo Simulated Annealing. Este algoritmo se caracteriza por ser estoc´astico y por funcionar de manera adecuada en bastantes ocasiones, principalmente, en el caso en que la soluci´on de partida sea pr´oxima a la ´optima, que es la situaci´on que tendremos en la pr´actica. Aunque no se detallar´an de manera formal los fundamentos matem´aticos sobre los que se basa la convergencia asint´otica del algoritmo, si se mencionar´an los resultados fundamentales. Cap´ıtulo 5. Estudio preliminar de los algoritmos en R-Studio: Durante este cap´ıtulo se describen los objetivos y la funcionalidad que se pretende conseguir con la realizaci´on del dashboard, la implementaci´on realizada sobre el mismo usando el entorno R-Studio, as´ı como las herramientas necesarias para ello. Cap´ıtulo 6. An´alisis de los resultados obtenidos: Durante este cap´ıtulo se realiza un an´alisis y comparativa de los resultados obtenidos al aplicar una serie de m´etodos (tanto en t´erminos de distancia, de eficacia como tiempo de ejecuci´on) para reordenar las trayectorias de un conjunto de vuelos dados. Adem´as, se analiza el comportamiento del algoritmo Simulated Annealing cuando es aplicado a un conjunto grande de vuelos para distintas configuraciones de ventanas (sin usar ventanas de tiempo, usando ventanas del mismo tama˜no en el aeropuerto y vuelo y cuando se usan ventanas de distinto tama˜no en ambas zonas). Esto sirve para poder determinar en qu´e situaciones el algoritmo funciona mejor, esto es, arroja resultados m´as pr´oximos a la soluci´on ´optima. Cap´ıtulo 7. Implementaci´on del Simulated Annealing usando MapReduce: Durante este cap´ıtulo se explican las herramientas y el entorno necesario para realizar una implementaci´on escalable en MapReduce del algoritmo Simulated Annealing. Adem´as, se detalla c´omo se ha realizado la correspondiente reasignaci´on de tiempos para cada uno de 4 1.3. Estructura del documento los mensajes ADS-B una vez obtenida la trayectoria ordenada tras aplicar el algoritmo implementado. Cap´ıtulo 8. Conclusiones y trabajo futuro: Finalmente, en este ´ultimo cap´ıtulo se detallan las conclusiones obtenidas sobre la realizaci´on del trabajo, as´ı como el aprendizaje obtenido con el mismo y el posible trabajo futuro a realizar. Conviene decir que la realizaci´on del presente Trabajo de Fin de Grado se ha realizado de manera paralela con el Trabajo de Fin de Grado de Matem´aticas. Por ello, la tem´atica de ambos es la misma, pero mientras que el de Matem´aticas se centra principalmente en el estudio y an´alisis te´orico de la convergencia del algoritmo Simulated Annealing, el de Inform´atica busca implementar una soluci´on escalable que permita resolver el problema planteado en la pr´actica. Ha sido de gran utilidad poder realizar ambos trabajos de manera conjunta puesto que as´ı se ha podido profundizar m´as en el estudio del algoritmo y con ello dar una buena soluci´on al problema planteado. Tambi´en, conviene se˜nalar que dicho trabajo se ha realizado a la par que el Trabajo de Fin de Grado de Inform´atica llevado a cabo por mi compa˜nero Juan Manuel Velasco Heras. Aunque el objetivo de ambos trabajos es el mismo, yo me he centrado en estudiar la heur´ıstica de mejora Simulated Annealing que se basa en la aleatoriedad o el azar, y ´el las heur´ısticas de mejora local, como es el caso del m´etodo 2-opt oLin-Kernighan, que se basan en la realizaci´on de intercambios. Todo esto ha enriquecido el trabajo realizado y ha permitido realizar una comparativa de los resultados obtenidos por dichos algoritmos para sacar conclusiones sobre su funcionamiento. 5 1.3. Estructura del documento 6 Cap´ıtulo 2 Plan del proyecto Durante este cap´ıtulo se pretende describir el plan de proyecto seguido para realizar el presente trabajo. Al ser un proyecto de investigaci´on, aunque se parte de unos objetivos claros, los cuales fueron comentados en el Cap´ıtulo 1, todas las etapas y pasos a realizar no est´an perfectamente definidos al comienzo. Por ello, en este caso, las metodolog´ıas tradicionales no son apropiadas y, se puede decir, que el desarrollo del mismo se ajusta a una metodolog´ıa de tipo ´agil ya que el trabajo se ha ido realizando de forma iterativa e incremental. Durante cada sprint o iteraci´on se realizan una serie de tareas o actividades que se contrastan con los clientes, en este caso los tutores, para dar paso a la realizaci´on de las siguientes tareas y as´ı sucesivamente. Por lo tanto, se trata de un plan de proyecto donde, tras cada iteraci´on, se consiguen una serie de funcionalidades establecidas, logrando cada vez estar m´as cerca de alcanzar los objetivos fijados al comienzo. A continuaci´on, se describe el plan de proyecto seguido, el cual, puede dividirse b´asicamente en cuatro iteraciones diferentes. En cada una de estas iteraciones se realizan una serie de actividades y para que sea m´as claro, se muestra para cada etapa una tabla con las actividades de las que consta, as´ı como una estimaci´on del tiempo y el estado de las mismas. Cabe destacar que aunque la realizaci´on del trabajo comenz´o en el mes de Septiembre, esto es, con el comienzo del curso, no fue hasta mediados-finales de Enero cuando se empez´o a dedicar un mayor tiempo a su desarrollo. Esto fue debido a que en el primer cuatrimestre todav´ıa hab´ıa asignaturas y a que al principio me centr´e m´as en el Proyecto de Fin de Carrera de Matem´aticas, dado que antes de poder programar los algoritmos usando distintos programas y lenguajes de programaci´on, era necesario conocer el funcionamiento de los mismos en mayor profundidad. Sprint 1 →Consta de todas aquellas tareas iniciales que tienen como objetivo conocer en mayor profundidad el entorno aeron´autico, as´ı como el problema del viajante o TSP, junto con los distintos algoritmos que permiten su resoluci´on. 7 ID Descripci´on Tiempo estimado Estado T-01 Investigar y profundizar en el estudio del entorno aeron´autico y la gesti´on del tr´afico a´ereo. 12 horas Acabada T-02 Entender y especificar con claridad el problema sobre el alineamiento de las trayectorias obtenidas por Boeing. 5 horas Acabada T-03 Lectura y consulta de documentos y libros relacionados con el problema del viajante (TSP) y los diferentes algoritmos que permiten su resoluci´on. 45 horas Acabada T-04 Redacci´on de la introducci´on (Cap´ıtulo 1) junto con los Cap´ıtulos 3 y 4 del presente documento. 50 horas Acabada 112 horas Tabla 2.1: Descripci´on de las tareas de la primera etapa Sprint 2 →Consta de todas aquellas tareas centradas en el estudio y dise˜no del dashboard usando el entorno de trabajo R-Studio, as´ı como el an´alisis de los resultados obtenidos. ID Descripci´on Tiempo estimado Estado T-05 Instalaci´on de R-Studio.0.25 horas Acabada T-06 Instalaci´on de los distintos paquetes y librer´ıas necesarios para la realizaci´on del dashboard. 0.35 horas Acabada T-07 Aprendizaje y documentaci´on sobre la creaci´on del dashboard usando R-Studio.35 horas Acabada T-08 Creaci´on de la versi´on inicial del dashboard (funcionalidad b´asica). 30 horas Acabada T-09 Creaci´on de una segunda versi´on que incluye la posibilidad de elegir ventanas de tiempo tanto en las zonas del aeropuerto como en la zona central del vuelo. 45 horas Acabada T-10 Mejora del dashboard incluyendo una interfaz gr´afica m´as visual para el usuario. Esto permite que sea m´as usable y que la informaci´on mostrada sea m´as representativa, logrando as´ı mejorar su satisfacci´on. 25 horas Acabada Sigue en la siguiente p´agina... 8 ID Descripci´on Tiempo estimado Estado T-11 Mejora del dashboard a˜nadiendo la posibilidad de realizar bater´ıas de pruebas seleccionando los vuelos, m´etodos y consideraciones deseadas, y tras ello, visualizar los resultados (en t´erminos de distancia, eficacia y tiempo de ejecuci´on) en una tabla. Adem´as, se a˜nade la posibilidad de descargar en formato csv la informaci´on de cada tabla. 28 horas Acabada T-12 Implementar la parte asociada a la asignaci´on de los nuevos tiempos tras la reordenaci´on, a˜nadir los comentarios que faltaban al c´odigo y limpieza del mismo. 25 horas Acabada T-13 An´alisis de los resultados obtenidos una vez aplicados los distintos m´etodos a diversos vuelos. 15 horas Acabada T-14 Aplicaci´on de los distintos algoritmos a una serie de vuelos dados para las distintas posibilidades de configuraciones de ventanas, y en particular, para el Simulated Annealing. 20 horas Acabada T-15 Redacci´on de los Cap´ıtulos 5 y 6. 30 horas Acabada 253.6 h Tabla 2.2: Descripci´on de las tareas de la segunda etapa Sprint 3 →Consta de todas aquellas tareas centradas en la implementaci´on del algoritmo Simulated Annealing en Java as´ı como su integraci´on en MapReduce. El objetivo es dar soporte a la computaci´on paralela de grandes conjuntos de datos provenientes de distintos vuelos. Con ello, se consigue una soluci´on eficiente y escalable para el problema planteado. ID Descripci´on Tiempo estimado Estado T-16 Consulta y b´usqueda de ayuda sobre la implementaci´on del algoritmo Simulated Annealing o la obtenci´on del pseudoc´odigo. 5 horas Acabada T-17 Comienzo de la implementaci´on del algoritmo en NetBeans 8.2 (primeras clases y funcionamiento b´asico). 15 horas Acabada T-18 Continuaci´on de la implementaci´on incluyendo una interfaz gr´afica que muestra tanto la distancia obtenida al aplicar el algoritmo como el tiempo de ejecuci´on. 18 horas Acabada T-19 Ampliaci´on de la implementaci´on considerando las distintas configuraciones de ventanas de tiempo tanto en las zonas del aeropuerto como en la zona central del vuelo. 15 horas Acabada Sigue en la siguiente p´agina... 9 ID Descripci´on Tiempo estimado Estado T-20 An´alisis de los resultados obtenidos. 2 horas Acabada T-21 B´usqueda y aprendizaje sobre el uso de MapReduce (tutoriales, gu´ıas, etc.). 20 horas Acabada T-22 Instalaci´on de X2Go Cliente para poder usar la m´aquina virtual Cloudera y realizaci´on del programa WordCount en Java para familiarizarme con el uso de MapReduce. 5.35 horas Acabada T-23 Adaptaci´on de la implementaci´on del algoritmo en NetBeans usando MapReduce.8 horas Acabada T-24 Implementar la parte asociada a la asignaci´on de tiempos tras la reordenaci´on de las trayectorias, a˜nadir ciertos comentarios que faltaban al c´odigo y limpieza del mismo. 25 horas Acabada T-25 Redacci´on del Cap´ıtulo 7. 15 horas Acabada 128.35 h Tabla 2.3: Descripci´on de las tareas de la tercera etapa Sprint 4 →Consta de todas aquellas actividades relacionadas con las pruebas y validaciones de los resultados obtenidos, la correcci´on de errores, as´ı como la formulaci´on de las conclusiones sobre el trabajo. ID Descripci´on Tiempo estimado Estado T-26 Realizaci´on de diversas pruebas sobre el correcto funcionamiento del dashboard y el proyecto creado usando el modelo de programaci´on MapReduce. 25 horas Acabada T-27 Evaluaci´on final de los resultados obtenidos y conclusiones del trabajo (redacci´on del Cap´ıtulo 8). 8 horas Acabada T-28 Redacci´on del esquema de trabajo realizado (Cap´ıtulo 2 del presente documento) y revisi´on final del documento. 15 horas Acabada 48 horas Tabla 2.4: Descripci´on de las tareas de la cuarta etapa 10 Sumando las horas totales de las cuatro tablas mostradas con anterioridad, se obtiene un total de 541.95 horas. Como se puede apreciar, el sprint o iteraci´on de mayor duraci´on es el segundo, esto es, aquel cuyo principal objetivo era la creaci´on del dashboard usando R-Studio, junto con el an´alisis de los resultados obtenidos al ejecutar los diferentes algoritmos a los vuelos proporcionados, haciendo uso del mismo. Tras ello, el siguiente sprint de mayor duraci´on es el tercero, dado que la implementaci´on del algoritmo Simulated Annealing en MapReduce era algo novedoso ya que no conoc´ıa dicho modelo de programaci´on. Por ello, ha sido necesario dedicar un tiempo para entenderlo y saber usarlo antes de poder realizar la implementaci´on del algoritmo. El primer sprint tambi´en ha requerido de bastantes horas, dado que antes de comenzar las distintas implementaciones era necesario conocer en mayor profundidad el entorno aeron´autico, el funcionamiento del problema del viajante o TSP, as´ı como de los distintos algoritmos que permiten su resoluci´on, centr´andome en especial en el estudio del comportamiento del algoritmo Simulated Annealing. Cabe destacar, como ya se coment´o en la Introducci´on, que dicho Trabajo de Fin de Grado se realiza de manera coordinada con el Trabajo de Fin de Grado de Matem´aticas. Aunque en ambos hay partes comunes (ese era el objetivo al realizarlo de esta manera), la l´ınea de trabajo de cada uno de ellos es diferente. Mientras que en el de Matem´aticas el pilar fundamental es el estudio te´orico de la convergencia del algoritmo Simulated Annealing, en el de Inform´atica, es la implementaci´on de una soluci´on escalable que permita resolver el problema que se nos plantea mediante el uso de dicho algoritmo. Por ello, aunque las horas dedicadas al estudio y an´alisis te´orico sobre la convergencia de dicho algoritmo no se describen ni detallan en profundidad en el presente documento, cabe decir que antes de realizar las implementaciones pr´acticas se dedicaron varios meses a realizar dicho trabajo. Por todo esto, se puede decir que ha sido de gran utilidad realizar dichos trabajos de manera conjunta. Por un lado, en el Trabajo de Fin de Grado de Matem´aticas he podido corroborar los resultados te´oricos descritos sobre la convergencia del algoritmo mediante su visualizaci´on pr´actica. Por otro lado, para el de Inform´atica, he podido entender en detalle y profundidad el funcionamiento de dicho algoritmo antes de realizar la implementaci´on del mismo usando el modelo de programaci´on MapReduce, lo cual, me ha ayudado a ir m´as r´apido en su realizaci´on y entender cada uno de los pasos realizados. Aunque el cuarto sprint es el de menor duraci´on, tambi´en tiene mucha importancia, dado que es necesario realizar una bater´ıa de pruebas y comprobaciones para verificar el correcto funcionamiento del dashboard creado y la implementaci´on del algoritmo en MapReduce, junto con una revisi´on del presente documento para evitar posibles errores. 11 3.3. AIRPORTS Este tipo de sistemas presentan grandes ventajas como son: ·Proporcionan informaci´on de posici´on en tiempo real que obtienen de un sistema de navegaci´on que, por lo general, es m´as preciso que un sistema basado en radar. Adem´as, abarcan un ´area de cobertura mucho m´as extensa que la de radar. Por lo tanto, al tener mayor precisi´on se garantiza una mayor seguridad y una mayor capacidad para controlar el espacio a´ereo. ·Los mensajes ADS-B permiten reconstruir la trayectoria seguida por el vuelo. ·Permite a las unidades ATS mayor facilidad a la hora de identificar y monitorizar la aeronave a trav´es de los datos recibidos de la misma. Por lo tanto, tienen un conocimiento m´as preciso del tr´afico a´ereo existente. ·Alerta de la situaci´on en la que se encuentra cada una de las aeronaves. ·Permite realizar cambios de manera r´apida y sencilla mediante la comunicaci´on de voz en caso de la existencia de alg´un peligro. ·Permite que se reduzca la carga de trabajo que tienen los controladores a´ereos. ·Permite reducir tambi´en el tiempo de uso del canal a trav´es del cual se transmiten los mensajes. ·Se reducen los retrasos de las aeronaves tanto en el despegue, el rodaje y el aterrizaje en pista. Aunque los sistemas ADS-B presentan una gran variedad de ventajas es cierto que tienen algunos inconvenientes, siendo, el principal de ellos, los problemas de escalabilidad que presentan cuando tienen que tratar grandes vol´umenes de datos, algo muy frecuente dado que los mensajes ADS-B se emiten dos veces por segundo por cada una de las aeronaves. Otro de los inconvenientes es que, en la actualidad, no existe una adecuada cobertura sobre la infraestructura a nivel mundial y, adem´as, muchas aeronaves a´un no disponen del equipamiento adecuado para el tratamiento de mensajes ADS-B. 3.3. AIRPORTS “AIRPORTS” es un proyecto en el que participan varias instituciones espa˜nolas (como es el caso de la Universidad de Valladolid) y que est´a liderado por Boeing Research and Technology Europe (BR&T-E). En dicho proyecto se comunican y coordinan entre s´ı distintas l´ıneas de investigaci´on que buscan desarrollar soluciones tecnol´ogicas que contribuyan a modernizar y mejorar el transporte a´ereo futuro, esto es, optimizar el uso del espacio a´ereo como consecuencia del gran aumento en el n´umero de vuelos al que nos enfrentamos en la actualidad. Una de las contribuciones m´as importantes de dicho proyecto en la optimizaci´on del tr´afico a´ereo, se basa en la explotaci´on de las nuevas tecnolog´ıas y m´etodos de trabajo que surgen, como 18 3.3. AIRPORTS consecuencia de los estudios realizados en el campo de Big Data. El t´ermino Big Data se refiere a conjuntos de datos de gran tama˜no, complejidad y velocidad de crecimiento lo que hace dif´ıcil su captura, gesti´on, tratamiento, manejo, etc. mediante el uso de las tecnolog´ıas y herramientas convencionales. Por ello, es necesario usar nuevos mecanismos y herramientas que permitan trabajar con esa gran cantidad de datos obtenidos (de esto se ocupa el campo de la ciencia de datos o data science). Como ya se coment´o, las aeronaves emiten y reciben un gran n´umero de mensajes de tipo ADS-B. Estos mensajes provienen de diferentes proveedores abarcando cada uno de ellos una zona determinada del espacio a´ereo. Dentro del conjunto de proveedores existentes se destacan OpenSky y Frambuesa, los cuales, obtienen sus datos usando la t´ecnica ADS-B. A continuaci´on se detallan los aspectos m´as destacados de cada uno de ellos haciendo uso de las p´aginas web indicadas para cada uno de los proveedores considerados. OpenSky: Es una asociaci´on que tiene su sede en Burgdorf (Suiza). OpenSky Network comenz´o en el 2012 como un proyecto de investigaci´on entre Suiza, Alemania y Reino Unido, pero hasta el 2015 no se fund´o la asociaci´on. Su objetivo es mejorar la seguridad, confiabilidad y eficiencia del espacio a´ereo, y para ello, se encarga de adquirir, recopilar, procesar y registrar datos sobre el control del tr´afico a´ereo. No tiene prop´ositos comerciales, por lo que el acceso a dichas fuentes de datos es gratuito para investigaciones realizadas en instituciones acad´emicas y gubernamentales. Para lograr su objetivo cuenta con una red de sensores (aproximadamente 1000), donde la mayor´ıa se encuentran distribuidos entre Europa y EE.UU. Dicho proveedor destaca por la calidad de los datos que obtiene. La informaci´on est´a disponible en: https:// opensky-network.org/. Figura 3.3: Cobertura del proveedor OpenSky Frambuesa: Se trata de un sensor con propiedad de BR&T-E que trabaja en el aeropuerto de Madrid-Barajas. 19 3.4. Problema a considerar Frambuesa ofrece mensajes ADS-B en bruto. Dichos mensajes enviados permiten obtener descripciones de vectores de posici´on de las aeronaves, siendo en este caso, mucho m´as reducidos que para el caso del resto de proveedores. Adem´as, dicho servicio abarca una ´area mucho m´as reducida que el resto de proveedores, pero tiene la ventaja de ofrecer una mayor densidad de mensajes dentro del ´area cercana al aeropuerto de Madrid-Barajas. Tambi´en, presenta una mayor rapidez entregando mensajes que OpenSky pues manda 1 mensaje por cada segundo, mientras que OpenSky manda 1 por cada 5 segundos. Figura 3.4: Cobertura del proveedor Frambuesa En muchas ocasiones suele ocurrir que una zona del espacio a´ereo est´e cubierta por diferentes proveedores por lo que se reciben m´ultiples mensajes ADS-B, y en consecuencia, surge la necesidad de fusionarlos y coordinarlos. Gracias al desarrollo en el campo de Big Data y a su contribuci´on, es posible tratar todos esos datos obtenidos, logrando mejorar la calidad y el valor de los mismos. As´ı, se consigue una mayor fiabilidad de los datos resultantes. 3.4. Problema a considerar Como ya se ha indicado, el presente trabajo busca resolver el problema sobre el alineamiento temporal de las trayectorias de las aeronaves, que son construidas a partir de las se˜nales que estas transmiten. Dicho problema puede formularse como sigue: Problema: La construcci´on realizada sobre las trayectorias voladas por las aeronaves, teniendo en cuenta los datos recibidos sobre la posici´on (altitud, longitud y latitud), velocidad, etc. as´ı como el tiempo asignado en los mensajes ADS-B, no resulta ser del todo correcta. Motivos: El principal motivo se debe a que el tiempo horario que es asignado a cada uno de los mensajes ADS-B recibidos sobre la posici´on, (en t´erminos de latitud, longitud y altitud), identificaci´on, etc. de cada una de las aeronaves que se conoce como timestamp, no es el correcto. Dicho inconveniente surge por ser dicho timestamp asignado por la entidad receptora y no por la aeronave que env´ıa el mensaje. 20 3.4. Problema a considerar As´ı, lo que ocurre, es que aunque los mensajes ADS-B son enviados por la aeronave en el momento adecuado y siguiendo el orden correcto, estos no llegan a la entidad receptora en ese mismo orden. Esto es debido principalmente al retardo en el tiempo de recepci´on de dichos mensajes y a la falta de sincronizaci´on horaria que existe entre algunas entidades receptoras. Consecuencias: Por lo tanto, como es la entidad receptora la encargada de asociar el timestamp a cada uno de dichos mensajes ADS-B que recibe, al llegar en orden incorrecto, el tiempo que les asigna es err´oneo provocando que los mensajes se registren en un orden inadecuado. As´ı, las trayectorias construidas teniendo en cuenta los datos presentes en dichos mensajes, resultan ser err´oneas. Esto se puede observar analizando algunas de las trayectorias construidas a partir de las fuentes de datos ADS-B del proyecto “AIRPORTS”. En la figura 3.5 se muestra el problema comentado con anterioridad. Figura 3.5: Problema planteado sobre el alineamiento temporal Tambi´en es posible que en las trayectorias se encuentre otro tipo de problemas, los cuales, son debidos a la presencia de outlayers. Sobre este tipo de problemas ya se est´a trabajando para su resoluci´on y su aparici´on en las distintas trayectorias se ha reducido de manera considerable. Aunque este no ser´a un problema que tengamos que tratar conviene mencionarlo, ya que a simple vista, podr´ıa ser confundido con el problema asociado a la asignaci´on de tiempos que motiva la realizaci´on de este proyecto. Por lo tanto, uno de los principales objetivos del desarrollo de este trabajo, consiste en analizar las trayectorias construidas a partir de los datos proporcionados por diversas 21 3.4. Problema a considerar fuentes de datos ADS-B, y una vez determinadas aquellas que presentan alguna anomal´ıa por asignaci´on de tiempos, corregirlas mediante la aplicaci´on de una soluci´on escalable basada en la ejecuci´on de ciertos algoritmos. Como ya se coment´o, dicho problema tiene una relaci´on directa con el problema del viajante o TSP, por lo que en la siguiente secci´on se realizar´a una descripci´on y explicaci´on del mismo, para as´ı poder formular de manera te´orica el problema que se pretende resolver sobre la reconstrucci´on de las trayectorias. Con ello se tendr´a el conocimiento necesario para abordarlo y buscar una soluci´on pr´actica para resolverlo. 22 Cap´ıtulo 4 Traveling Salesman Problem (TSP) 4.1. Definici´on El problema del viajante tambi´en conocido como “Traveling Salesman Problem (TSP)”, consiste en determinar la ruta m´as corta posible que recorre un conjunto de ciudades (de manera general nodos), de manera que el nodo final coincida con el nodo de partida y que todas las ciudades sean visitadas una ´unica vez. Dicho problema ha sido estudiado durante muchos a˜nos y a´un es objeto de estudio dentro de la optimizaci´on combinatoria pues, aunque aparentemente parezca un problema f´acil de resolver debido a que el n´umero de posibles caminos que existe entre un conjunto de nodos sea finito, en realidad no lo es. Se trata de un problema complejo de resolver, de hecho, es un problema de tipo NP-Duro. Por ello, incluso se considera la posibilidad de no llegar nunca a encontrar un algoritmo que, en todas las situaciones posibles, encuentre la soluci´on ´optima. Para desarrollar el contenido de los apartados de esta secci´on se ha usado el libro de William J.Cook [1] y el de E.L. Lawler y otros [2]. 4.2. Historia El estudio del problema del viajante surgi´o hace muchos a˜nos y es debido principalmente a la gran utilidad que presenta en las situaciones de la vida real estando muy relacionado con la log´ıstica, la distribuci´on de productos, el transporte, etc. En el a˜no 1832 se dio a conocer en Alemania el primer libro sobre este tema denominado “El viajante de comercio: c´omo debe ser y qu´e debe hacer para conseguir comisiones y triunfar en su negocio. Por un viajante de comercio veterano”. Durante los siguientes a˜nos, muchos matem´aticos se dedicaron a investigar sobre dicho problema, sin embargo, no fue hasta el a˜no 1930 cuando fue definido formalmente en t´erminos matem´aticos. Dicha formulaci´on fue realizada por el matem´atico y economista 23 4.2. Historia Karl Menger quien consider´o en un primer momento como m´etodo de resoluci´on la fuerza bruta, aunque pronto observ´o que no era un m´etodo eficiente y menos a´un ´optimo. Poco despu´es Hassler Whitney dio a conocer dicho problema con el t´ermino anglosaj´on “Traveling Salesman Problem” y, poco a poco, en las d´ecadas de los 50 y 60 dicho problema gan´o mucha popularidad como consecuencia principalmente de la publicidad llevada a cabo por Procter and Gamble en 1962. En ella, se propuso un concurso donde se pod´ıa obtener un premio de 10.000 d´olares si se resolv´ıa el problema del viajante para un conjunto de 33 ciudades de EE.UU. Result´o ser un problema complejo de resolver y, aunque nadie logr´o llevarse el premio, se pudo demostrar que ya en el a˜no 1954, esto es, 8 a˜nos antes, tres matem´aticos de Rand Corp. (George Dantzing, Ray Fulkerson y Selmer Johnson) hab´ıan encontrado la soluci´on ´optima para un conjunto de exactamente 49 ciudades. Para ello desarrollaron el m´etodo de los Planos de Corte y lo aplicaron a su estudio obteniendo resultados muy positivos. Este resultado fue un gran avance y, de hecho, supuso un reto a superar que no se logr´o hasta 1971, esto es, 17 a˜nos despu´es, cuando los investigadores de IBM Michael Held y Richard Karp resolvieron el problema para el caso de 64 ciudades distribuidas al azar en una regi´on cuadrada, donde los costos eran considerados como la distancia en l´ınea recta entre cada par de ellas. Cuatro a˜nos m´as tarde, concretamente en 1975, Panagiotis Miliotis logr´o la soluci´on ´optima para el caso de 80 puntos distribuidos de manera aleatoria. Ya en 1977 Gr¨otschel public´o su Tesis Doctoral en la que determinaba la soluci´on ´optima para el caso de 120 ciudades. Fue entonces cuando se asociaron Padberg y el investigador de IBM Harlan Crowder obteniendo la soluci´on ´optima para el problema de 318 ciudades distribuidas en un tablero de circuitos. La ocurrencia de todos estos sucesos fueron muy relevantes en la historia del TSP y dieron lugar a un gran avance en el desarrollo de dicho problema, ya que, Gr¨otschel y Padberg de manera independiente lograron hallar la soluci´on ´optima para el caso de 532 ciudades en Estados Unidos, 666 localizaciones en el mundo, 1.002 ciudades con problemas de perforaci´on, y posteriormente, de 2.392 ciudades. M´as tarde en 1988, como consecuencia de los ´exitos ocurridos, Vasek Chv´atal y William J.Cook se unieron en el estudio del problema logrando en el a˜no 1992 resolverlo para el caso de 3.038 ciudades, para lo que hicieron uso de una amplia red de computadoras que trabajaban en paralelo. Siguiendo con ello, lograron en 1998 encontrar la ruta ´optima de 13.509 ciudades en Estados Unidos, otra de 24.978 en Suecia en el a˜no 2004, y finalmente, otra en 2006 de 85.900 ciudades. Todos estos avances en el estudio y desarrollo del problema del viajante fueron posibles gracias al uso de una herramienta inform´atica denominada Concorde que se comenz´o a usar ya en el a˜no 1992. Se trata de un programa en Cmuy usado actualmente (intentando su mejora y avance) para este tipo de problemas de optimizaci´on de redes y, que en a˜nos 24 4.2. Historia anteriores, supuso una gran revoluci´on en el avance del TSP. En la Figura 4.1 se puede ver el avance producido gracias al uso de la herramienta Concorde puesto que se pas´o muy r´apidamente de encontrar la ruta ´optima para el caso de 33 ciudades (se corresponde con la ruta negra) y de 120 ciudades (se corresponde con la azul) a lograr la soluci´on ´optima para el caso de 15112 ciudades (se corresponde con la ruta roja). Figura 4.1: Tres recorridos distintos en Alemania ([1, p´ag. 14]) En la Figura 4.2 se muestra de manera gr´afica la evoluci´on en el avance de resultados obtenidos a medida que aumenta el n´umero de ciudades consideradas. Se aprecia como a partir del 2006 dicho aumento es exponencial. Figura 4.2: Evoluci´on de ciudades resueltas a lo largo de los a˜nos 25 4.3. Aplicaciones 4.3. Aplicaciones El problema del viajante o TSP ha sido y sigue siendo uno de los principales problemas de estudio en el desarrollo del dise˜no de algoritmos y de la teor´ıa de complejidad computacional, debido principalmente a su contribuci´on y aplicaci´on en diferentes ´areas para mejorar y resolver diversas situaciones y problemas de la vida diaria. Las principales ´areas de aplicaci´on son la log´ıstica y distribuci´on, as´ı como la programaci´on de curvas de producci´on. Al inicio, las mejoras del TSP ten´ıan como objetivo conseguir aplicarlo de manera directa, como por ejemplo en rutas de autobuses escolares o de una empresa de lavander´ıa. Poco a poco el ´ambito de aplicaci´on fue creciendo y hoy en d´ıa incluso es ´util para problemas en el ´ambito gen´etico (creaci´on de clusters de genes) y biol´ogico (creaci´on de ´arboles filogen´eticos). Se detallan a continuaci´on las aplicaciones m´as importantes dentro del ´area de log´ıstica as´ı como en la industria: Log´ıstica: El TSP tiene aplicaciones muy abundantes en log´ıstica como son las siguientes. ·Vendedores, Turistas: Suelen usar alg´un tipo de sistema para planificar las rutas tur´ısticas de manera que est´an sean ´optimas tanto en tiempo como en coste volviendo al punto de partida. Dichos planificadores suelen basarse en algoritmos de resoluci´on de tipo TSP. ·Rutas escolares y laborales: Al igual que en el caso anterior se determinan rutas mediante algoritmos de tipo TSP para ahorrar costes y tiempo. ·Transporte de paquetes y mercanc´ıas: Este tipo de problemas se suele adaptar mejor a problemas de arcos en lugar de problemas de nodos como es el caso del TSP pero, sin embargo resulta ´util cuando las distancias entre lugares a repartir son lejanas o s´olo se desea visitar un lugar concreto. Sector Industrial: Aunque las aplicaciones del TSP en la industria son menos abundantes tambi´en son importantes y se podr´ıan considerar las siguientes. ·Secuenciaci´on de las tareas: Consiste en realizar diversas tareas de la manera m´as r´apida posible minimizando el costo de su producci´on, y para ello, el orden de su realizaci´on debe ser independiente entre las mismas. En este caso cada una de las tareas se asemeja al papel de una ciudad y el tiempo que se tarda en realizar una tarea ihabiendo hecho antes la tarea jes lo que equivale a la distancia entre las ciudades. ·Producci´on de placas de circuitos electr´onicos: Consiste en realizar agujeros en una placa mediante la perforaci´on autom´atica de la misma y, para ello se usa la t´ecnica del TSP donde se consideran cada uno de los puntos a perforar como una ciudad diferente de manera que el tiempo en crear dichas placas se reduce al m´ınimo posible. 26 4.4. Complejidad Existen m´as aplicaciones del TSP, aunque algunas de ellas tienen una relaci´on menos intuitiva con dicho problema, ya que no requieren de movimientos f´ısicos. Algunas de dichas aplicaciones es el caso de la b´usqueda de planetas o la organizaci´on de datos en diferentes grupos, lo cual, es usado tanto en la miner´ıa de datos como para la extracci´on de patrones en los datos. 4.4. Complejidad La clasificaci´on de los problemas a resolver puede realizarse seg´un su complejidad y, seg´un dicho criterio se distingue entre problemas NP, problemas P y problemas NP-Completos de forma que, hasta el momento, los problemas de tipo P y NP-Completos tienen intersecci´on vac´ıa siendo ambos problemas de tipo NP. Un problema de tipo P es aquel que se resuelve en tiempo polinomial por un algoritmo determinista (ej: una m´aquina de Turing determinista), mientras que un problema NP es aquel que se resuelve en tiempo polinomial por un algoritmo no determinista (ej: una m´aquina de Turing no determinista). Los problemas de tipo NP-Completo son problemas de tipo NP-Duro que est´an contenidos en la clase de problemas NP, siendo xun problema NP-Duro si cualquier problema que pertenezca a la clase de problemas NP puede reducirse en tiempo polinomial a x. En la Figura 4.3 se muestra un gr´afico de la relaci´on existente entre este tipo de problemas para que sea m´as clara y visual. Para ello se ha considerado que P 6= NP ya que el resultado contrario hasta el momento no ha sido probado. Figura 4.3: Diagrama de Venn siendo P 6= NP Como ya se coment´o, el problema del viajante o TSP es considerado a d´ıa de hoy como un problema NP-Duro, luego, todo problema que pertenezca a la clase de problemas de tipo NP puede transformarse en tiempo polinomial en ´el. Frente a estos conceptos surge la cuesti´on de encontrar alg´un problema NP-Completo que sea de tipo P ya que, en ese caso, se obtendr´a que P = NP. Dicho resultado se dio a 27 4.6. Heur´ısticas para encontrar una ruta factible 4.6.1.2. Heur´ıstica de inserci´on Son un conjunto de m´etodos que se basan en construir circuitos usando un determinado conjunto de v´ertices, y posteriormente, se van insertando uno a uno los restantes v´ertices en dicho circuito hasta formar un circuito hamiltoniano. De manera gen´erica, supongamos que se tiene un grafo G= (V, A) de nv´ertices descrito seg´un la Secci´on 4.5. Los pasos a seguir son los siguientes: Algoritmo 2 Heur´ıstica de inserci´on 1: Se selecciona un conjunto inicial de jv´ertices 2: Se considera el subgrafo W=V\ {v´ertices seleccionados del conjunto} 3: mientras W6=∅hacer 4: Se considera un v´ertice vi∈Wseg´un un determinado m´etodo (se explican a continuaci´on los m´as usados) 5: Se inserta dicho v´ertice vide manera que el coste del circuito se incremente lo menos posible 6: Se considera W=W\ {i} 7: fin mientras Existen diferentes m´etodos de inserci´on seg´un el criterio usado para a˜nadir los nodos. Estos fueron descritos por Robacker y son los siguientes: Definici´on 4.5 (Inserci´on m´as cercana).Consiste en elegir la ciudad o v´ertice vim´as cercana a las ciudades del circuito actual, esto es, si Wes el circuito actual, dmin(vi) = min{dmin(vj) : vj∈W}. Definici´on 4.6 (Inserci´on m´as lejana).Consiste en elegir la ciudad o v´ertice vim´as alejada de las ciudades del circuito actual, esto es, si Wes el circuito actual, dmin(vi) = max{dmin(vj) : vj∈W}. Definici´on 4.7 (Inserci´on m´as aleatoria).Consiste en elegir la ciudad o v´ertice vial azar, esto es, sin seguir ning´un criterio. Definici´on 4.8 (Inserci´on m´as barata).Consiste en elegir la ciudad o v´ertice vique produce el menor incremento de coste posible, esto es, que mantiene el circuito existente lo m´as corto posible. Figura 4.9: Elecciones seg´un el m´etodo elegido 34 4.6. Heur´ısticas para encontrar una ruta factible En la Figura 4.9 se muestran las diferentes elecciones de nodos seg´un el m´etodo de inserci´on m´as lejano, m´as cercano y m´as barato para insertar al ciclo de 4 v´ertices actual. Para el caso de la inserci´on m´as lejana habr´ıa que a˜nadir el nodo jal actual circuito, en el caso m´as cercano el nodo ky en el caso m´as barato el nodo i, pues con ´el se obtiene el circuito menor posible a partir del actual. Si se considera el tipo aleatorio, entonces se elegir´ıa un nodo al azar entre los existentes. 4.6.1.3. Heur´ıstica de Christofides Fue creada por Christofides en 1976 ([1, p´ag. 72]) y est´a muy relacionada con los ´arboles de coste m´ınimo, por ello, antes de explicar el m´etodo es necesario entender este tipo de ´arboles. Un ´arbol de coste m´ınimo de un grafo es un subgrafo que es un ´arbol y, adem´as, contiene todos los v´ertices del grafo inicial con el m´ınimo coste posible. La b´usqueda de este tipo de ´arboles es un problema que se puede resolver en tiempo polinomial mediante algoritmos eficientes a diferencia de lo que ocurre con el TSP. Por ello, su uso es ´util, ya que la soluci´on de este tipo de problemas proporciona una cota del coste de la soluci´on ´optima para el TSP que es m´ınima. Esto se debe a que si de un circuito que es soluci´on eliminamos una arista se obtiene un ´arbol que posee un ´unico camino de uni´on entre las distintas ciudades. Por ello, como la soluci´on ´optima debe tener una arista m´as que el ´arbol anterior, ya que debe ser un circuito cerrado, el coste de dicha soluci´on ´optima va a ser necesariamente mayor que el del ´arbol de m´ınimo coste. El m´etodo de Christofides es un algoritmo que busca soluciones aproximadas a la ´optima, de manera que si el coste de la soluci´on aproximada es xy el de la soluci´on ´optima es y, entonces x≤3 2y. Comienza buscando el ´arbol de m´ınimo coste Lde un grafo Gcompleto y etiquetado. Tras ello se elige el conjunto de v´ertices de grado impar del ´arbol Ly se halla un apareamiento perfecto M(conjunto de aristas sin v´ertices en com´un) de m´ınimo peso en Gsobre dichos v´ertices considerados. Tras ello se forma un multigrafo (en ´el dos nodos pueden estar conectados por m´as de una arista) mediante la combinaci´on de las aristas de MyL. Finalmente, se obtiene un circuito euleriano en dicho multigrafo y, quitando los nodos ya visitados, se obtiene el circuito hamiltoniano buscado. A continuaci´on, en la Figura 4.10 se muestra un ejemplo de lo anteriormente comentado. El primer dibujo se corresponde con el grafo completo Gdel cual se quiere hallar la ruta ´optima. Para ello, primero se busca el ´arbol de m´ınimo coste que se muestra en el segundo dibujo, y despu´es, tras encontrar el par de v´ertices de grado impar se forma el emparejamiento Ma partir del grafo Gsobre esos v´ertices. Finalmente, el ´ultimo dibujo se corresponde con el multigrafo uni´on de LyMque como resulta ser un circuito hamiltoniano de m´ınimo coste termina la b´usqueda. 35 4.6. Heur´ısticas para encontrar una ruta factible Figura 4.10: Ejemplo heur´ıstica de Christofides 4.6.2. Heur´ısticas de mejora Se trata de una serie de m´etodos que buscan mejorar soluciones ya encontradas y, para ello, siguen diversas t´ecnicas. Se puede distinguir entre m´etodos que se basan en realizar intercambios y otros que se basan en el azar o aleatoriedad. 4.6.2.1. Heur´ısticas de mejora k-opt o de Lin-Kernighan Son procedimientos que consisten en intercambiar diversas aristas de una soluci´on inicial de partida buscando mejorarla y conseguir una nueva soluci´on m´as pr´oxima a la ´optima. Se conocen gracias a las primeras definiciones desarrolladas por Flood [1]. Dichos m´etodos se basan por lo tanto en realizar k-intercambios de aristas e ir generando rutas k-´optimas hasta que no sea posible mejorarlas m´as. Para entender estos m´etodos es necesario entender unos conceptos previos, por lo que antes de detallar c´omo funcionan vamos a explicarlos. El proceso de realizar un k-intercambio de aristas en una ruta inicial dada consiste en eliminar exactamente karistas de dicha ruta y reemplazarlas por otras karistas diferentes de manera que la nueva ruta obtenida sea mejor que la anterior, esto es, de menor coste. En ese caso, dicha ruta se conoce como k-´optima. La complejidad de este tipo de m´etodos es O(nk) (siendo nel n´umero de nodos), ya que en cada paso, el n´umero de posibles elecciones es n k. Sin embargo, aunque a mayor valor de kmejores soluciones se esperan obtener, el n´umero de operaciones a realizar crece mucho. Por ello, lo m´as usual es usar un valor de kno mayor que 3, pues en otro caso el coste temporal ser´ıa muy grande, no siendo recomendable. Para que resulte m´as claro dicho procedimiento, se describe el caso en que k= 2. El proceso comienza con un ciclo hamiltoniano inicial y con el valor de la variable mejora = 1. Tras ello, mientras mejora valga 1, esto es, se encuentren soluciones mejores, se establece mejora a 0 y se van seleccionando los v´ertices que no han sido explorados. Para cada uno 36 4.6. Heur´ısticas para encontrar una ruta factible de ellos se realizan todos los posibles movimientos de dos intercambios que incluyan a dicho v´ertice y uno sucesor. Si alguno de dichos intercambios reduce la distancia actual, se elige el mejor de ellos y mejora pasa a valer 1. Tras ello, dicho v´ertice se considera explorado y se sigue con el resto hasta que mejora vale 0 pues, en ese caso, ning´un intercambio mejora la distancia actual. El coste computacional en cada paso no es grande siendo del orden de O(n2). A continuaci´on, se muestra un ejemplo sencillo de este m´etodo que como vemos se basa en la idea de eliminar “cruces” entre aristas aunque, en la pr´actica, esto es dif´ıcil de visualizar. En el ejemplo de la Figura 4.11 se puede ver en el primer dibujo que las aristas en color rojo forman la ruta de partida con un coste de 24 unidades, mientras que en el segundo dibujo, al intercambiar las aristas de mayor coste (la de 8 y 6) por otras de menor coste (la de 4 y 2) se obtiene una mejor soluci´on, siendo el coste de esta de 16 unidades. Figura 4.11: Ejemplo heur´ıstica 2-opt Una variante de esta heur´ıstica se denomina V-opt y difiere del k-opt en que las aristas que son eliminadas no est´an fijas, sino que, dicho n´umero aumenta con el n´umero de iteraciones que se hacen. Dentro de esta heur´ıstica destaca el m´etodo Lin-Kernighan. Se trata de una de las mejores heur´ısticas que se conocen para resolver el problema del viajante. Consiste en ir intercambiando un n´umero diferente de aristas seg´un sea m´as conveniente en cada caso. 4.6.2.2. Heur´ısticas de mejora aleatorias Estos m´etodos usan diversas t´ecnicas para ir generando soluciones o rutas que est´en cada vez m´as pr´oximas a la ruta ´optima logrando conseguir buenos resultados en un tiempo reducido. Algoritmos Gen´eticos: Son m´etodos que se basan en simular los fen´omenos naturales de evoluci´on. Se parte de una poblaci´on inicial generada de manera aleatoria (conjunto de nodos al azar) que sigue un proceso con las siguientes etapas: ·Selecci´on: Consiste en elegir de la poblaci´on actual aquellos descendientes que poseen las mejores caracter´ısticas. Para ello, existe una funci´on fitness que mide la calidad de cada una de las distintas alternativas. 37 4.6. Heur´ısticas para encontrar una ruta factible ·Cruce: Consiste en el traspaso de informaci´on gen´etica entre cromosomas de los padres a los descendientes y, en el problema del TSP equivale a realizar saltos entre distintos estados del espacio de b´usqueda. ·Mutaci´on: Tras el cruce, cada uno de los nuevos individuos generados puede sufrir mutaciones con una determinada probabilidad p, que si es menor que la tasa de mutaci´on (se elige en el rango [0.001,0.05]), entonces se lleva a cabo dicha mutaci´on. Una vez realizadas estas etapas se eligen las mejores soluciones entre las existentes (las anteriores m´as las nuevas obtenidas) volviendo a realizar el proceso descrito. As´ı, se logra obtener diversas soluciones y a medida que aumentan las iteraciones est´an m´as pr´oximas a la soluci´on ´optima. El procedimiento seguido en los algoritmos gen´eticos para buscar soluciones ´optimas se muestra en la Figura 4.12 de manera gr´afica. Figura 4.12: Procedimiento algoritmos gen´eticos B´usqueda tab´u: Es un algoritmo de b´usqueda local desarrollado por Fred Glover [7] que trata de evitar que la b´usqueda se quede bloqueada en ´optimos locales no llegando a encontrar soluciones pr´oximas a la ´optima. Para ello, hace uso de estructuras de memoria que pueden ser a corto (denominado lista tab´u) o largo plazo permitiendo moverse a soluciones que sean peores que la actual para poder escapar de esos ´optimos locales. En las de corto plazo, se almacenan las acciones o eventos m´as recientes, mientras que en las de largo plazo, se guardan los datos asociados a las frecuencias de ciertos eventos. La memoria a corto plazo se suele denominar lista tab´u, ya que en ella se almacenan los movimientos m´as recientes, denominados movimientos tab´u, prohibiendo su elecci´on. As´ı, se consigue salir de los ´optimos locales evitando un ciclo repetitivo, pero para ello, se permiten peores soluciones. Estos movimientos considerados tab´u pueden salir de dicha lista, cuando tras analizarlos, se observa que producen mejores resultados que los actuales. Esta t´ecnica se conoce como regla de aspiraci´on. Por otro lado, la memoria a largo plazo es muy importante ya que trata de diversificar la b´usqueda, permitiendo as´ı, explorar zonas que no han sido visitadas con anterioridad. 38 4.6. Heur´ısticas para encontrar una ruta factible En la Figura 4.13a se muestra un movimiento de intercambio, y en Figura 4.13b, c´omo se van almacenando o eliminando de la lista tab´u dichos movimientos. (a) Movimiento de intercambio (b) Elementos lista tab´u Figura 4.13: B´usqueda tab´u Colonia de hormigas: Al igual que los algoritmos gen´eticos se basa en imitar los procesos naturales. Consiste en estudiar el comportamiento que siguen las hormigas cuando salen del hormiguero para explorar otras regiones en busca de alimento. Despu´es de realizar diversas observaciones, se pudo comprobar que ´estas siguen el rastro de las feromonas que van dejando a lo largo del recorrido realizado. Si se tiene un conjunto de nhormigas que salen del hormiguero, cada una de ellas hace su propio recorrido marcando cu´al es el camino seguido mediante el rastro de feronomas que dejan. Como a medida que pasa el tiempo el rastro de feromonas se evapora, los caminos que son m´as largos tienen menos probabilidades de ser seguidos pues en ellos se reduce la fuerza de atracci´on que mueve a las hormigas en su elecci´on. Este proceso de evaporaci´on es ´util ya que permite que se detenga convergiendo en ´optimos locales. Por ello, cuando se encuentra un camino que es bueno, esto es, de menor distancia hay m´as posibilidades para que el resto de hormigas lo sigan. Este hecho fue considerado para aplicarlo a la resoluci´on del TSP buscando encontrar en un grafo completo el camino hamiltoniano de menor coste. En este caso, el agente que se mueve entre las ciudades juega el papel de la hormiga. Se considera que varias hormigas parten de distintas ciudades, cada una de las cuales realiza un recorrido entre las mismas, visitando una ´unica vez cada ciudad y volviendo a la de partida. Tras ello, se van dejando feromonas en el camino, de manera que cuando el recorrido realizado es corto se potencia el rastro de feromonas en el mismo para la siguiente iteraci´on y si es largo no. Esto hace que se evapore dicho rastro en el caso de caminos largos. As´ı, a medida que se realizan las iteraciones se logra potenciar los recorridos con distancias m´as cortas logrando estar cada vez m´as cerca del ´optimo. En la Figura 4.14 se muestra de manera gr´afica el proceso seguido por dicho m´etodo, donde se puede ver como la mayor´ıa de las hormigas eligen el recorrido m´as corto, ya que es el que tiene mayor rastro de feromonas. 39 4.6. Heur´ısticas para encontrar una ruta factible Figura 4.14: M´etodo colonia de hormigas Simulated Annealing: Dicho m´etodo fue descrito de manera independiente por Scott Kirkpatrick, C. Daniel Gelatt y Mario P. Vecchi, as´ı como por Vlado ˇ Cern´y en los a˜nos 80 ([1, p´ag. 86]) y est´a relacionado con el campo de la termodin´amica. Como dicho m´etodo es el objeto de estudio del presente trabajo, se detalla con mayor formalidad a continuaci´on. El algoritmo Simulated Annealing es una heur´ıstica que tiene como prop´osito encontrar un valor lo m´as pr´oximo posible al valor ´optimo de una funci´on objetivo determinada. Por lo tanto, se trata de un m´etodo de optimizaci´on global que tiene la ventaja de resolver problemas de optimizaci´on gen´ericos, de manera r´apida y eficiente, en espacios de estados (o soluciones) grandes. A continuaci´on, se introduce la notaci´on que se va a usar para describir el algoritmo: S={soluciones posibles del problema a optimizar}, siendo finito y denominado espacio de soluciones. f: Es la funci´on objetivo a optimizar que va del espacio de soluciones posibles a la recta real, esto es, f:S−→ R (S, f): Es un par que simboliza una determinada instancia del problema de optimizaci´on combinatoria. Para cada soluci´on o estado i∈Sse considera el conjunto Si⊆Scomo el conjunto de las soluciones pr´oximas a i, esto es, el entorno de i. Se tiene que j∈Si⇔ i∈Sj. Sopt ={soluciones ´optimas del problema a optimizar}. fopt: Es el valor de la funci´on objetivo en una soluci´on ´optima del problema de optimizaci´on. Por ejemplo, para el caso del problema del viajante se debe buscar iopt ∈Sopt tal que f(iopt)≤f(i), ∀i∈Sdonde iopt es una soluci´on global ´optima de dicho problema. (pues se trata de un problema de minimizaci´on) ck: Es el valor del par´ametro de control en la iteraci´on ko paso k-´esimo. 40 4.6. Heur´ısticas para encontrar una ruta factible Lk: Es el n´umero de transacciones o movimientos a realizar en la iteraci´on ko paso k-´esimo. Definici´on 4.9. Una transici´on es un proceso formado por dos etapas donde, en la primera se aplica un mecanismo para generar una soluci´on o estado sucesor del actual, y tras ello, se aplica el criterio de aceptaci´on (Definici´on 4.10) para ver si se sigue con la soluci´on o estado actual, o se elige el sucesor. Una vez que se tienen los estados, espacio de soluciones, funci´on objetivo, etc. es necesario determinar c´omo se va a llevar a cabo la aceptaci´on de los diferentes estados. Dicho proceso sigue el siguiente criterio. Definici´on 4.10 (Criterio de aceptaci´on).Sea (S, f)una instancia de un problema de optimizaci´on combinatoria y sean i, j ∈Sdos soluciones con valores o costes asociados f(i),f(j)respectivamente. Se define el criterio de aceptaci´on para pasar del estado i al estado j mediante la siguiente probabilidad: Pc(aceptar j) = (1 si f(j)≤f(i) exp f(i)−f(j) csi f(j)> f(i),(4.1) donde c∈R+es denominado el par´ametro de control. Es importante se˜nalar que, a la hora de determinar la convergencia o no del algoritmo, el comportamiento de dicho par´ametro cva a tener gran importancia. Una vez que ya se tienen todos los conceptos y criterios anteriores, se describe el proceso seguido para llevar a cabo la aplicaci´on del algoritmo Simulated Annealing. Dada (S, f) una instancia de un problema de optimizaci´on combinatoria, para encontrar un valor pr´oximo al valor ´optimo de la funci´on objetivo f, se siguen los siguientes pasos: Algoritmo 3 Simulated Annealing 1: Se inicializa el estado inicial iinicial, el valor inicial del par´ametro de control c0y el n´umero de transiciones o movimientos a realizar en la iteraci´on inicial, esto es, L0 2: Se fija k= 0, i=iinicial 3: mientras no se cumpla el criterio de parada hacer 4: para l= 1, ..., Lkhacer 5: Se genera un nuevo estado j∈Si 6: si f(j)≤f(i)entonces 7: devolver i=j 8: si no 9: si exp f(i)−f(j) ck> random[0,1) 10: devolver i=j 11: fin si 12: k=k+ 1 13: Se calcula el valor Lk 14: Se calcula el valor ck 15: fin mientras 41 4.6. Heur´ısticas para encontrar una ruta factible Se tiene que random[0,1) es una variable aleatoria uniforme en [0,1), el paso 5 es el mecanismo de generaci´on de nuevos estados (se eligen estados dentro del entorno del estado actual) y los pasos 6, 7, 8, 9, 10 y 11 se corresponden con el mecanismo llevado a cabo para aceptar o no dichos estados generados. El criterio de parada usado para finalizar dicho proceso, puede venir dado fijando un n´umero m´aximo de iteraciones posibles a realizar, o bien cuando tras un n´umero de iteraciones, no se consigue mejorar el estado o soluci´on actual. Por lo tanto, dicho algoritmo se trata de una heur´ıstica de b´usqueda local que permite llevar a cabo movimientos que lleven del estado actual a otros peores durante el inicio del proceso, y a medida que se va descendiendo de manera gradual el valor del par´ametro de control c, dicha probabilidad se reduce para evitar as´ı alejarse del valor ´optimo de la funci´on objetivo. El inter´es de permitir aceptar estados peores que el actual en las primeras etapas, es lo que permite al algoritmo escapar de ´optimos locales, permitiendo as´ı explorar todo el espacio de estados S. Adem´as, si la disminuci´on de cse realiza lentamente, se puede garantizar que el algoritmo encuentra el ´optimo global con una probabilidad cercana a 1. Como consecuencia de ello, supone una mejora con respecto a otros algoritmos de b´usqueda local, como es el caso del Hill Climbing. Este algoritmo presenta el inconveniente de quedarse bloqueado en ´optimos locales por no permitir ir a soluciones peores que la actual. En la Figura 4.15 que se muestra a continuaci´on, se observa el inconveniente de la b´usqueda local determinista, ya que por ejemplo, Hill Climbing quedar´ıa bloqueado en el m´ınimo local sin llegar a alcanzar el global. Figura 4.15: Problema de la b´usqueda determinista 42 4.6. Heur´ısticas para encontrar una ruta factible La demostraci´on de la convergencia asint´otica del algoritmo Simulated Annealing de una funci´on fal conjunto de soluciones ´optimas Sopt se basa en probar lo siguiente: l´ım k→∞ P(Xk∈Sopt)=1,(4.2) siendo Xkla variable estoc´astica correspondiente al estado k-´esimo del proceso estoc´astico de Markov considerado. Un proceso estoc´astico es sucesi´on de observaciones X1,X2,... (variables estoc´asticas) cuyos valores no se pueden predecir exactamente, esto es, son aleatorios, pero sin embargo, s´ı es posible especificar las probabilidades para los distintos posibles valores en cada instante determinado. Para ello, se requiere definir y demostrar una serie de resultados que no se detallar´an, aunque s´ı se describir´a de manera resumida el procedimiento para probar la convergencia del algoritmo. Se basa en lo siguiente: Definici´on 4.11. Dada (S, f)una instancia de un problema de optimizaci´on combinatoria y una estructura de estados vecinos adecuada con valor de c fijo, se considera la distribuci´on cuyas componentes vienen dadas por: qi(c) = 1 N0(c)exp −f(i) cy N0(c) = X j∈S exp −f(j) c,(4.3) siendo N0(c)una constante de normalizaci´on. A partir de la definici´on anterior, se puede demostrar lo siguiente: l´ım c→0qi(c) = 1 |Sopt|χSopt (i)donde χSopt (i) = 1si i ∈Sopt 0si i 6∈ Sopt .(4.4) El resultado que se obtiene de la expresi´on (4.4) anterior tiene mucha importancia, ya que cuando el valor de cdecrece a 0, la distribuci´on qse comporta de manera adecuada. Este comportamiento se debe a que dicha distribuci´on en el l´ımite es uniforme sobre el conjunto de soluciones ´optimas Sopt y, por ser un conjunto finito, se podr´a obtener la expresi´on dada en (4.2). En el algoritmo Simulated Annealing dado un estado i∈S, se busca otro estado j∈Si, esto es, dentro del espacio de estados o soluciones pr´oximas a la actual. Por lo tanto, se puede ver que la generaci´on de un nuevo estado s´olo depende del estado anterior. Como las cadenas de Markov sirven para modelizar las transiciones que se llevan a cabo en un determinado sistema de estados, debido a su analog´ıa con el proceso Simulated Annealing, dicho algoritmo puede describirse matem´aticamente usando cadenas de Markov. (Para m´as informaci´on sobre cadenas de Markov consultar los libros de Kai Lai Chung [19] y Isaacson, D. and R. Madsen [20]). Finalmente, usando cadenas de Markov, bien homog´eneas (aquellas en las que la probabilidad de ir del estado ial estado jen un determinado paso no depende del tiempo en 43 4.7. Fundamento te´orico de la soluci´on 50 Cap´ıtulo 5 Estudio preliminar de los algoritmos en R-Studio Durante este cap´ıtulo se describe c´omo se ha realizado el dashboard en el entorno de desarrollo R-Studio. Los objetivos de su realizaci´on son los siguientes: por un lado, obtener las trayectorias ordenadas tras la aplicaci´on de los distintos algoritmos a los vuelos proporcionados, y por el otro, realizar la reasignaci´on de tiempos a los datos que han sido alterados en la reordenaci´on usando para ello un modelo de interpolaci´on lineal. Con ello, se podr´a llevar a cabo un estudio sobre el comportamiento de los diferentes algoritmos, para as´ı realizar una comparativa de los mismos en t´erminos de distancia recorrida y tiempo de ejecuci´on. Dicho estudio se realiza en el Cap´ıtulo 6. Por lo tanto, antes de comenzar a describir las herramientas, entorno, etc. usado y la implementaci´on realizada vamos a describir las funcionalidades que perseguimos obtener con su realizaci´on. Esto es, describiremos los requisitos funcionales del dashboard a desarrollar en R-Studio. Dichos requisitos ser´an los siguientes: RF-01: El dashboard permitir´a al usuario elegir entre visualizar mapas, visualizar la tabla de datos de un vuelo y realizar una bater´ıa de pruebas o experimentos. RF-02: El dashboard permitir´a al usuario elegir entre un conjunto de vuelos. RF-03: El dashboard permitir´a al usuario elegir el rango de datos a considerar para el vuelo elegido. RF-04: El dashboard mostrar´a un mapa en 2 dimensiones (2D) teniendo en cuenta los datos considerados sobre el vuelo elegido para describir la trayectoria de vuelo. RF-05: El dashboard mostrar´a un mapa en 3 dimensiones (3D) teniendo en cuenta los datos considerados sobre el vuelo elegido para describir la trayectoria de vuelo. RF-06: El dashboard permitir´a al usuario cambiar la capa o layer de visualizaci´on del mapa en 2D. RF-07: El dashboard mostrar´a un minimapa en el mapa en 2D, para que en caso de hacer zoom, se pueda conocer la zona donde se encuentra. 51 RF-08: El dashboard mostrar´a unas gr´aficas de velocidad frente a tiempo y de altura frente a tiempo del vuelo elegido y el rango de datos indicado. RF-09: El dashboard permitir´a al usuario visualizar en el mapa en 2D la informaci´on asociada a un determinado mensaje. RF-10: El dashboard permitir´a al usuario seleccionar los datos a visualizar en los mapas y gr´aficos seg´un el proveedor indicado. RF-11: El dashboard permitir´a al usuario elegir entre la opci´on de visualizar en los mapas los datos por colores en funci´on del tipo de proveedor o sin colores. RF-12: El dashboard mostrar´a al usuario una tabla con los datos del vuelo indicado teniendo en cuenta el rango de datos considerado. RF-13: El dashboard permitir´a al usuario filtrar los datos que desea buscar en la tabla. RF-14: El dashboard permitir´a al usuario elegir un algoritmo de resoluci´on entre un conjunto de ellos. RF-15: El dashboard permitir´a al usuario elegir para el caso del algoritmo Simulated Annealing, un algoritmo previo de resoluci´on, el n´umero de iteraciones a realizar, as´ı como la temperatura considerada. RF-16: El dashboard permitir´a al usuario ejecutar el algoritmo indicado mediante tres posibilidades diferentes: sin usar ventanas de tiempo, usando ventanas de tiempo del mismo tama˜no y usando ventanas de tiempo de distinto tama˜no en las zonas del aeropuerto y la zona central del vuelo. RF-17: El dashboard permitir´a en el caso de usar ventanas de tiempo, indicar al usuario los datos asociados a cada una de las zonas consideradas, as´ı como el tama˜no de la ventana en el aeropuerto y en el vuelo, y el solapamiento de ventanas en cada caso. RF-18: El dashboard mostrar´a al usuario en los mapas la informaci´on necesaria para poder distinguir entre los datos que han sido alterados y los que no tras la reordenaci´on. RF-19: El dashboard permitir´a al usuario elegir visualizar la trayectoria ordenada y/o no ordenada en el mapa en 2D y 3D. RF-20: El dashboard mostrar´a al usuario la informaci´on asociada a la distancia total en km de la trayectoria original y la ordenada, as´ı como el n´umero de puntos que han sido alterados o no tras la reordenaci´on. RF-21: El dashboard mostrar´a al usuario tras ejecutar un algoritmo cuatro columnas nuevas en la tabla (distancia,time nuevo,tag orig ytag ord). RF-22: El dashboard mostrar´a al usuario, tras ejecutar un determinado algoritmo, una gr´afica donde se representa el tiempo de cada punto tras realizar la interpolaci´on de los err´oneos frente a la distancia de cada uno de ellos con respecto al primero. 52 5.1. Descripci´on del entorno y herramientas usadas RF-23: El dashboard permitir´a visualizar en la gr´afica anterior un gradiente en funci´on de la altura de cada uno de los puntos considerados. RF-24: El dashboard permitir´a al usuario realizar una bater´ıa de pruebas o experimentos de manera din´amica. RF-25: El dashboard permitir´a al usuario elegir un conjunto de vuelos, de algoritmos y las opciones de ventanas deseadas y realizar su ejecuci´on. RF-26: El dashboard mostrar´a al usuario tres tablas sobre los resultados obtenidos en t´erminos de distancia, eficacia y tiempo de ejecuci´on, as´ı como unas m´etricas asociadas (media aritm´etica, median absolute desviation y desviaci´on est´andar muestral). RF-27: El dashboard permitir´a al usuario descargar los datos mostrados en las tablas en formato csv para poder guardar dicha informaci´on. 5.1. Descripci´on del entorno y herramientas usadas El procedimiento seguido para la realizaci´on del dashboard ha sido el siguiente: 1. Instalaci´on de R-Studio: Para ello se ha descargado la versi´on gratuita de la p´agina web https://www.rstudio.com/products/rstudio/download/. Se ha usado dicho entorno de desarrollo o IDE dado que, principalmente est´a dedicado a la computaci´on estad´ıstica, el dise˜no de gr´aficos y por ser el m´as usado para crear aplicaciones en R. La apariencia de dicho entorno se muestra en la Figura 5.1. En ella, se puede apreciar que consta de 4 pantallas (el editor de texto, la consola, una zona de visualizaci´on de gr´aficas, ayuda, paquetes, etc. y por ´ultimo el entorno de trabajo junto con el historial). El lenguaje de programaci´on usado en este entorno es R, el cual, es utilizado principalmente para el an´alisis estad´ıstico, aunque tambi´en es muy usado en investigaci´on cient´ıfica, miner´ıa de datos, investigaci´on biom´edica, bioinform´atica y matem´aticas financieras. Entre sus caracter´ısticas y ventajas podemos destacar las siguientes: ·Es multiplataforma. ·Es un proyecto colaborativo y abierto, lo que permite el desarrollo de nuevas librer´ıas y la realizaci´on de mejoras. ·Es un lenguaje interpretado, esto es, funciona mediante comandos. ·Proporciona una gran variedad de herramientas estad´ısticas para el an´alisis de datos y la generaci´on de gr´aficos de alta calidad (de ah´ı su gran uso en el trabajo). ·Permite manejar una gran cantidad de datos (usado en Data Science). ·Funciona con diferentes tipos de hardware y software (Linux, Windows, etc.) ·Con el uso de las librer´ıas y paquetes se puede ampliar su configuraci´on b´asica. Estas ser´an detalladas a continuaci´on, pero cabe destacar que han sido de gran utilidad para la realizaci´on de la interfaz del dashboard aquellas que se basan en la visualizaci´on de 53 5.1. Descripci´on del entorno y herramientas usadas gr´aficos. Tambi´en han sido muy ´utiles aquellos paquetes que contienen los algoritmos o m´etodos que han sido aplicados a la ordenaci´on de las trayectorias obtenidas. Por lo tanto, se trata de un lenguaje de programaci´on muy usado, lo cual hace que su mejora sea continua, estando en la actualidad en constante avance y crecimiento. Figura 5.1: Entorno de R-Studio 2. Instalaci´on de librer´ıas de R: Una vez instalado el entorno de R-Studio, es necesario instalar una serie de librer´ıas de Rpara poder realizar el dashboard. Como Rposee muchas librer´ıas, s´olo detallar´e aquellas que han sido usadas en la creaci´on del dashboard. Para instalar nuevos paquetes existen b´asicamente dos formas diferentes: 1) Usar la consola de comandos poniendo directamente install.packages(“nombre paquete”). 2) Usar la zona denominada gr´aficas, paquetes, ayuda, etc. de la Figura 5.1. Para ello, tras seleccionar la pesta˜na paquetes se puede instalar un nuevo paquete o actualizar alguno de los existentes. Una vez que se han instalado los paquetes, para hacer uso de ellos es necesario poner la sentencia library(paquete) para cada uno de los paquetes que se necesiten. Todas estas sentencias se ponen al comienzo del script usado para implementar el dashboard y sirven para cargar los paquetes requeridos para su ejecuci´on. Debido a las caracter´ısticas que presenta el tipo de proyecto a realizar, ha sido necesario usar la librer´ıa Shiny. Se trata de una librer´ıa de Rmuy ´util, ya que facilita la creaci´on de aplicaciones web interactivas directamente desde R, pudiendo adem´as incluirse temas 54 5.1. Descripci´on del entorno y herramientas usadas css adicionales, acciones de JavaScript, etc. Adem´as, ha sido necesario instalar otras librer´ıas para poder desarrollar el dashboard como son las siguientes: ·png: Dicho paquete debe instalarse para poder instalar el paquete Leaflet. ·leaflet: Dicho paquete permite manejar mapas, por lo que su uso es imprescindible para visualizar las trayectorias voladas por las aeronaves. ·shinydashboard: Dicho paquete facilita el uso del dashboard creado usando Shiny mediante el uso de diversos paneles de control. ·shinycssloaders: Dicho paquete nos ha permitido instalar una serie de spinners que se visualizan mientras se cargan los datos necesarios para dibujar los mapas, gr´aficas, visualizar las tablas, etc. ·shinyalert: Dicho paquete sirve para mostrar al usuario diversos mensajes de alerta en el caso de que haya introducido alg´un dato err´oneo en los campos. ·ggplot2: Dicho paquete permite realizar gr´aficos. ·plotly: Dicho paquete lo que hace es mejorar el aspecto y la apariencia de las gr´aficas obtenidas con ggplot2. Se ha usado para la realizaci´on de todos los gr´aficos y mapas del dashboard. ·geosphere: Dicho paquete se ha usado para calcular la distancia del Haversiano en la esfera. ·TSP: Dicho paquete permite resolver el problema del viajante o TSP mediante el uso de diversos m´etodos. ·dplyr: Dicho paquete ha sido usado para realizar operaciones de manera sencilla y r´apida sobre los datasets. ·stats: Dicho paquete se ha usado para realizar c´alculos estad´ısticos y generar n´umeros aleatorios. Adem´as, contiene la funci´on optim() que se ha usado para resolver el problema del viajante o TSP mediante el m´etodo Simulated Annealing. ·DT: Dicho paquete proporciona una interfaz usable y manejable adem´as de bonita para la visualizaci´on de las tablas de datos en R. Permite mostrar los datos como tablas en p´aginas HTML y DataTables, proporciona filtrado, paginaci´on, clasificaci´on y muchas otras caracter´ısticas. ·readr: Dicho paquete permite leer datos de diferentes formatos de archivos como csv, tsv yfwf. ·shinyBS: Dicho paquete se ha usado para mostrar ventanas emergentes informativas al usuario. ·yasp: Dicho paquete permite aplicar ciertas funciones para el manejo de Strings. ·tibble: Dicho paquete proporciona un manejo sencillo de dataframes (conjuntos de datos). ·stringr: Dicho paquete permite realizar diversas manipulaciones sobre caracteres de datos (Strings). 55 5.2. Implementaci´on del dashboard 5.2. Implementaci´on del dashboard Para desarrollar el dashboard se ha usado el lenguaje de programaci´on Rpues como ya se coment´o es muy usado en la actualidad. Para crear el dashboard se ha hecho uso de la librer´ıa conocida como Shiny. Dicha librer´ıa ha sido de gran utilidad para el desarrollo del proyecto ya que permite crear con cierta facilidad aplicaciones web visuales e interactivas para el usuario. Esto se logra gracias a que en su c´odigo fuente se integra c´odigo de otros lenguajes como HTML, CSS o JavaScript sin necesidad de hacer uso directo de ellos. Shiny implementa la programaci´on reactiva que consiste en vincular los valores de entrada con los de salida, esto es, cuando una entrada (input) cambia, el servidor reconstruye cada salida (output) que depende de ella (tambi´en si la dependencia es indirecta) de manera autom´atica. Adem´as, dispone de widgets y herramientas que permiten hacer aplicaciones bonitas y visuales adem´as de interactivas. Si se quiere obtener m´as informaci´on se puede consultar la p´agina web: http://shiny.rstudio.com/ Antes de comenzar a desarrollar el dashboard es necesario instalar el paquete de Shiny mediante el comando siguiente: install.packages(“shiny”). Los dashboards desarrollados haciendo uso de Shiny constan b´asicamente de dos partes, que son las siguientes: 1. Interfaz de usuario (ui.R) →En esta parte se encuentra todo el c´odigo asociado a la interfaz gr´afica del dashboard creado, esto es, asociado a los componentes que se quieren mostrar. Est´a distribuido en tres partes, las cuales, conforman el cuadro de mando: el encabezado, el men´u lateral y el cuerpo o Body. Viene definido de la forma siguiente: #Librer ´ı as b´a si ca s para l a i n t e r f a z de usuario . library( shiny ) library(shinydashboard) ui = dashboardPage( #Encabezado , men´u l a t e r a l y cuerpo ( body ) . dashboardHeader () , dashboardSidebar ( ) , dashboardBody() ) 2. Servidor (server.R) →En esta parte se encuentran todas las funciones necesarias para realizar los an´alisis, operaciones y gr´aficos que se muestran en la interfaz de usuario del dashboard, esto es, contiene la l´ogica de la programaci´on. Por lo tanto, la estructura b´asica de un dashboard en Shiny viene dada como: library( shiny ) library(shinydashboard) 56 5.3. Manual de usuario del dashboard creado # I n t e r f a z de usuario ui <−fluidPage () # Parte del ser vi dor se rv er <−function( input , output ) {} # Ejecuta e l dashboard shinyApp ( ui = ui , s er ver = ser ve r ) Finalmente, en la Figura 5.2 se muestra la arquitectura b´asica del dashboard desarrollado en Shiny. Como vemos consta de una parte cliente y otra parte servidor que interact´uan entre s´ı. Figura 5.2: Arquitectura de Shiny [16] 5.3. Manual de usuario del dashboard creado Como ya se ha comentado, el dashboard desarrollado se basa principalmente en la visualizaci´on de trayectorias, recorridos (tanto ordenados como no ordenados), datos de vuelos, resultados obtenidos de la ejecuci´on de los distintos m´etodos, etc. para as´ı poder realizar una comparativa de los mismos en t´erminos de distancia recorrida y tiempo de ejecuci´on. Adem´as, una vez ordenadas las trayectorias, se realiza la reasignaci´on de timestamps para los datos que han sufrido cambios, as´ı como la representaci´on gr´afica de todos ellos. Ahora, se explica el funcionamiento del dashboard y para que sea m´as visual y se entienda mejor, se muestran una serie de im´agenes de la interfaz asociada a cada una de las explicaciones dadas. Existen diversas funcionalidades en el dashboard, las cuales son: Dashboard Mapa 2D: Es la pesta˜na que se visualiza al iniciar el dashboard. En ella se puede visualizar un mapa con la trayectoria descrita por el vuelo que aparece indicado (por defecto el primero del selector “Seleccionar vuelo”), siendo estos le´ıdos de una carpeta denominada Vuelos. Dicha trayectoria se construye con los mensajes ADS-B obtenidos de cada proveedor, cada uno de los cuales se indica con un determinado color (existe la posibilidad de que aparezcan todos con el mismo color pulsando en la opci´on “Con colores” que se visualiza en la parte derecha del mapa y de eliminar la visualizaci´on de los datos de un determinado proveedor pulsando el checkbox correspondiente) y vienen 57 5.3. Manual de usuario del dashboard creado unidos mediante una l´ınea roja. En el caso en que se eliminen los datos de todos los proveedores de un vuelo, se visualizar´a la trayectoria de la ruta de partida. En la imagen de la Figura 5.3 se muestra el caso en que s´olo se consideran los datos asociados al proveedor OpenSky. Adem´as, existe la posibilidad de visualizar la informaci´on de un determinado mensaje ADS-B pulsando sobre el mismo. Tambi´en, se puede cambiar la “capa o layer de visualizaci´on” del mapa (hay varias posibilidades) y ver un minimapa para saber en caso de aplicar zoom al mapa, la zona donde nos encontramos. Justo debajo de dicho mapa se muestran dos gr´aficas que representan el tiempo frente a la altura y la velocidad de los datos del correspondiente vuelo. Es posible cambiar desde el men´u lateral izquierdo el vuelo considerado, as´ı como restringir los datos con el slider “Rango de observaciones”. Todos estos cambios se realizan sin tener que recargar la p´agina, y los mapas y gr´aficos se muestran de manera inmediata. Adem´as, como se ve en la Figura 5.3 el filtrado por proveedores tambi´en se visualiza en las gr´aficas de velocidad y altura. Figura 5.3: Parte superior pesta˜na mapa en 2D con filtrado de proveedores En las im´agenes de las interfaces asociadas a las Figuras 5.4 y 5.5 se visualizan las explicaciones dadas con anterioridad. La interfaz de la Figura 5.5 es com´un para la visualizaci´on del Mapa en 2D, 3D y la gr´afica Distancia vs Tiempo cambiando s´olo la parte superior ya que el men´u lateral izquierdo tambi´en se mantiene. 58 5.3. Manual de usuario del dashboard creado Figura 5.4: Parte superior pesta˜na mapa en 2D Figura 5.5: Parte inferior pesta˜na mapa en 2D, en 3D y Distancia vs Tiempo 59 5.3. Manual de usuario del dashboard creado que haya columna de velocidades en el dataset considerado, se calcula el valor de los pesos que se denota por p0yp1. El valor de p0se obtiene como la media aritm´etica de las velocidades desde el anterior punto bueno hasta el punto a interpolar excluyendo los puntos nulos. De la misma manera, el valor de p1se obtiene como la media aritm´etica de las velocidades desde el punto a interpolar hasta el siguiente punto bueno excluyendo los puntos nulos. Si no hay velocidades, se supone que esta es proporcional a la altura para hallar los valores de los pesos p0yp1del punto a interpolar. 5. Finalmente, para hallar el valor del timestamp que le corresponde al punto que se desea interpolar, se usa la siguiente expresi´on: tpuntoInterpolar =(d1p1+ 1)tanteriorBueno + (d0p0+ 1)tposteriorBueno d1p1+d0p0+ 2 donde d1es la distancia existente entre pposteriorBueno y el punto a interpolar y d0es la distancia existente entre panteriorBueno y el punto a interpolar. En las Figuras 5.13 y 5.14 se muestra dicha representaci´on gr´afica, donde el eje horizontal se corresponde con el timestamp de cada punto y el eje vertical con la distancia entre cada punto y el punto inicial. En este caso se ha usado el m´etodo de ejecuci´on Concorde. En la imagen de la Figura 5.14 se muestra dicha representaci´on de forma ampliada, y en ella se puede ver que la interpolaci´on llevada a cabo es lineal. El estudio y an´alisis realizado ha permitido observar que donde se produce un mayor n´umero de alteraciones es en las zonas de los aeropuertos, esto es, en el despegue y aterrizaje. Como ya se coment´o, es debido a que en estas zonas las trayectorias seguidas tienen m´as quiebros y zig-zag, mientras que en la zona del vuelo son m´as rectas. Figura 5.13: Correcci´on de timestamps para los puntos alterados 66 5.3. Manual de usuario del dashboard creado Figura 5.14: Correcci´on de timestamps para los puntos alterados (ampliado) Adem´as, se ofrece la posibilidad de visualizar en la representaci´on un gradiente de colores que depende de la velocidad de cada punto. Esto ha ayudado a determinar d´onde hay m´as o menos errores en las distintas trayectorias ya que en las zonas de los aeropuertos la velocidad es menor que en el vuelo. Esto se puede ver en la imagen de la Figura 5.15 donde la zona del aeropuerto es la que se corresponde con el color amarillo. Figura 5.15: Gradiente en funci´on de la velocidad de cada punto 67 5.3. Manual de usuario del dashboard creado Dashboard Table: Tambi´en, es posible visualizar un listado con los datos de un determinado vuelo (el indicado en el selector “Seleccionar vuelo”), y para ello, se debe seleccionar en el men´u lateral izquierdo la opci´on “Tablas”. Esto mostrar´a una apariencia como la de la interfaz de la Figura 5.16. Desde ah´ı usando el filtrador podemos buscar aquellas filas que tengan alguna coincidencia con la informaci´on indicada. Tambi´en podemos ir visualizando las diferentes p´aginas de datos mediante un paginador al igual que desplazarnos en horizontal por la tabla con un scroll. Por ´ultimo, con el slider asociado al rango podemos restringir los datos a visualizar en la tabla, as´ı como se pod´ıa hacer para la visualizaci´on de los mapas y gr´aficas. Conviene mencionar que tras ejecutar un m´etodo se a˜naden cuatro columnas m´as a la tabla: “tag original” que indica la posici´on de los datos antes de la ordenaci´on, “tag - ordenado” que almacena su posici´on tras haber sido ordenados con el m´etodo indicado, “distancia” que calcula la distancia de cada punto con respecto al primero y por ´ultimo “timestamp ordenado” que almacena el tiempo reasignado tras la ordenaci´on (cambia para los puntos que han sido alterados). El uso de las columnas “tag original” y “tag - ordenado” permite conocer los puntos que han sido alterados y los que no al aplicar el algoritmo indicado, para as´ı poder visualizarlos en los mapas y asignarles el “timestamp - ordenado”. Esto puede verse en la interfaz de la Figura 5.17. Figura 5.16: Tabla de datos con filtrado por proveedor osky 68 5.3. Manual de usuario del dashboard creado Figura 5.17: Tabla de datos con columnas a˜nadidas tras ejecutar un algoritmo En la imagen que se muestra en la Figura 5.18 se puede ver tambi´en el efecto que produce realizar el filtrado por proveedores. En esta imagen se ha dejado s´olo el proveedor Frambuesa y como en dicho vuelo no hab´ıa datos de ese proveedor, no aparece ning´un dato en la tabla. Figura 5.18: Tabla de datos con filtrado por proveedores 69 5.3. Manual de usuario del dashboard creado Dashboard Bater´ıa de Pruebas: Otro de los aspectos interesantes del dashboard es que permite realizar una bater´ıa de pruebas para las opciones deseadas. Para ello, se debe seleccionar la pesta˜na “Pruebas”, y tras ello, indicar en el selector “Elegir vuelos” los vuelos deseados, en el selector “Elegir m´etodos” los m´etodos a aplicar (ver Figura 5.19) y en el checkbox “Ventanas” el tipo de ventanas que se quiere usar para su resoluci´on. Al igual que en la parte de los mapas, en funci´on de la opci´on elegida aparecer´an los par´ametros u opciones necesarios para su ejecuci´on. Tambi´en en el caso de que alg´un valor sea err´oneo, se mostrar´a un mensaje informativo al usuario (ver Figura 5.20). Figura 5.19: Selector para elegir algoritmos Figura 5.20: Mensaje de error en campo num´erico 70 5.3. Manual de usuario del dashboard creado A continuaci´on, en la Figura 5.21, se ha elegido la opci´on que tiene m´as par´ametros y opciones a determinar. Figura 5.21: Ejecutando una bater´ıa de pruebas Tras realizar todas las ejecuciones indicadas, se visualiza una tabla de resultados donde aparece la longitud obtenida (Figura 5.22), la eficacia obtenida (Figura 5.23) y el tiempo de ejecuci´on (Figura 5.24) para cada uno de los m´etodos aplicados a cada uno de los vuelos elegidos. Adem´as, para todos los resultados se aplican diversas m´etricas con el objetivo de poder visualizar de forma r´apida, que algoritmo es el m´as adecuado. Las m´etricas usadas son la media aritm´etica, la desviaci´on absoluta media conocida como MAD y la desviaci´on est´andar muestral. Se tiene que MAD =Mediana(|xi−Mediana(X)|) siendo Xel conjunto de valores considerados, esto es, X={xi:i∈N+}. El valor de la efectividad o eficacia, se ha calculado restando a la distancia original la distancia obtenida y dividiendo este resultado por la distancia original. Todo ello se multiplica por 100 obteniendo un valor en tanto por ciento. As´ı, aquellos m´etodos que obtengan un mayor valor ser´an los m´as eficientes. Adem´as, se pueden obtener valores negativos en el caso en que la aplicaci´on del m´etodo aumente la longitud de la ruta de partida. En este caso dichos valores aparecen en color rojo como se observa en la Figura 5.23. Por ´ultimo, existe la posibilidad de guardar los resultados obtenidos de las ejecuciones en formato csv, y para ello, basta con pulsar el bot´on Descargar que aparece justo debajo de cada tabla. 71 5.3. Manual de usuario del dashboard creado Figura 5.22: Resultado de la bater´ıa de pruebas para la longitud Figura 5.23: Resultado de la bater´ıa de pruebas para la efectividad Figura 5.24: Resultado de la bater´ıa de pruebas para el tiempo de ejecuci´on 72 Cap´ıtulo 6 An´alisis de los resultados obtenidos En este cap´ıtulo, se comenzar´a realizando un an´alisis de los resultados obtenidos al ejecutar el m´etodo de resoluci´on Simulated Annealing a un conjunto de 96 vuelos proporcionados por los tutores. Se aplicar´a dicho m´etodo con todas las posibles configuraciones de ventanas (sin usar ventanas de tiempo, usando ventanas de tiempo del mismo tama˜no y con ventanas de tiempo de distinto tama˜no en la zona del aeropuerto). Despu´es se realizar´a un estudio general de los diferentes algoritmos de resoluci´on descritos en la Secci´on 4.6 del Cap´ıtulo 4, y tras ello, se llevar´a a cabo una comparativa de los mismos en funci´on de los resultados obtenidos en cuanto a distancia recorrida y tiempo de ejecuci´on. Esto permitir´a comparar nuestro algoritmo de estudio con el resto. Para su realizaci´on se va a hacer uso del dashboard implementado en el entorno R-Studio, en concreto se usar´a la parte asociada a la bater´ıa de pruebas, ya que permite ejecutar todos los vuelos de una sola vez. 6.1. Simulated Annealing usando diferentes configuraciones de ventanas Durante el desarrollo de esta secci´on se va a realizar un an´alisis y estudio sobre el comportamiento del algoritmo Simulated Annealing para ver bajo qu´e configuraciones de ventanas o situaciones obtiene mejores resultados. Para ello, se va a usar un conjunto de 96 vuelos. As´ı, usando la bater´ıa de pruebas de R-Studio, obtendremos de manera din´amica diferentes tablas de resultados similares a las de las interfaces de las Figuras 5.22, 5.23 y 5.24. Dichas tablas nos permitir´an comparar los resultados obtenidos, y en este caso, al tener un conjunto grande de vuelos, nos fijaremos en los resultados de las distintas m´etricas consideradas (media aritm´etica, median absolute deviation (MAD) y la desviaci´on est´andar muestral). Una vez se tengan dichos resultados, se analizar´an para decidir bajo qu´e configuraciones se comporta mejor o peor el algoritmo de estudio. 73 6.1. Simulated Annealing usando diferentes configuraciones de ventanas La m´aquina usada para realizar las distintas pruebas es un ordenador port´atil HP Pavilion x360 Convertible con un procesador Intel Core i5-7200U, cuya velocidad var´ıa entre 2.5 GHz y 2.7 GHz, con memoria RAM de 8 GB y Sistema Operativo Windows 10 Home. Siguiendo la notaci´on del Cap´ıtulo 4 se considerar´a: ·Para ventanas del mismo tama˜no: En este caso, tser´a el tama˜no de ventana y sel solapamiento tanto en la zona del vuelo como en los aeropuertos. ·Para ventanas de distinto tama˜no en la zona del aeropuerto y en vuelo: En este caso, tvser´a el tama˜no de ventana en vuelo, svel solapamiento en vuelo, tael tama˜no de ventana en aeropuerto y sael solapamiento en aeropuerto. Para realizar las pruebas se ha considerado un tama˜no de ventana de 100 con solapamiento de 20 cuando las ventanas son del mismo tama˜no, y para el caso en que se hace distinci´on en la zona de los aeropuertos, se ha considerado un tama˜no de ventana de 20 y solapamiento de 5 en dichas zonas. Como ya se coment´o, la disminuci´on del tama˜no de ventana y de solapamiento en estas zonas con respecto a la zona central del vuelo es debido a que al realizar el avi´on m´as maniobras, las trayectorias suelen presentar m´as quiebros y zig-zag, siendo m´as adecuado en estos casos reducir el n´umero de datos considerados para realizar la ejecuci´on del algoritmo. A continuaci´on, se muestran los resultados obtenidos de las distintas ejecuciones realizadas usando un determinado valor de temperatura y n´umero de iteraciones. Para las distintas configuraciones de ventanas usadas se muestran los resultados obtenidos sobre la distancia de la trayectoria ordenada (en kil´ometros), la eficacia obtenida (en porcentaje) y el tiempo de ejecuci´on (en segundos) respectivamente. Prueba 1: 10000 iteraciones y temperatura 3 =⇒ Configuraci´on usada Media aritm´etica MAD Desviaci´on est´andar muestral Sin aplicar algoritmo de resoluci´on 1868.65 km 948.83 km 1265.18 km Simulated Annealing −→ Distancia tras reordenar (km) Sin usar ventanas 1852.44 km 948.92 km 1246.33 km t=100 y s =20 1635.42 km 871.94 km 960.58 km tv=100,sv=20,ta=20 y sa=51631.99 km 860.44 km 956.80 km Simulated Annealing −→ Eficacia obtenida ( %) Sin usar ventanas 0.54 % 0.03 % 3.03 % t=100 y s =20 7.53 % 4.20 % 13.15 % tv=100,sv=20,ta=20 y sa=57.66 % 3.98 % 12.92 % Simulated Annealing −→ Tiempo de ejecuci´on (sg) Sin usar ventanas 2.81 sg 1.23 sg 1.17 sg t=100 y s =20 23.48 sg 13.38 sg 12.50 sg tv=100,sv=20,ta=20 y sa=533.52 sg 14.93 sg 14.05 sg Tabla 6.1: Simulated Annealing con 10000 iteraciones y temperatura 3 74 6.1. Simulated Annealing usando diferentes configuraciones de ventanas Prueba 2: 10000 iteraciones y temperatura 1 =⇒ Configuraci´on usada Media aritm´etica MAD Desviaci´on est´andar muestral Sin aplicar algoritmo de resoluci´on 1868.65 km 948.83 km 1265.18 km Simulated Annealing −→ Distancia tras reordenar (km) Sin usar ventanas 1852.65 km 948.80 km 1246.48 km t=100 y s =20 1589.61 km 818.75 km 939.68 km tv=100,sv=20,ta=20 y sa=51589.63 km 823.59 km 937.04 km Simulated Annealing −→ Eficacia obtenida ( %) Sin usar ventanas 0.54 % 0.05 % 2.96 % t=100 y s =20 9.93 % 6.72 % 12.99 % tv=100,sv=20,ta=20 y sa=59.93 % 6.76 % 12.92 % Simulated Annealing −→ Tiempo de ejecuci´on (sg) Sin usar ventanas 6.04 sg 2.82 sg 2.44 sg t=100 y s =20 24.31 sg 12.74 sg 12.31 sg tv=100,sv=20,ta=20 y sa=542.35 sg 19.27 sg 17.68 sg Tabla 6.2: Simulated Annealing con 10000 iteraciones y temperatura 1 Prueba 3: 40000 iteraciones y temperatura 1 =⇒ Configuraci´on usada Media aritm´etica MAD Desviaci´on est´andar muestral Sin aplicar algoritmo de resoluci´on 1868.65 km 948.83 km 1265.18 km Simulated Annealing −→ Distancia tras reordenar (km) Sin usar ventanas 1832.83 km 945.80 km 1222.41 km t=100 y s =20 1537.40 km 803.01 km 905.29 km tv=100,sv=20,ta=20 y sa=51540.18 km 800.00 km 905.18 km Simulated Annealing −→ Eficacia obtenida ( %) Sin usar ventanas 1.19 % 0.10 % 5.24 % t=100 y s =20 12.27 % 8.93 % 14.31 % tv=100,sv=20,ta=20 y sa=512.12 % 8.78 % 14.18 % Simulated Annealing −→ Tiempo de ejecuci´on (sg) Sin usar ventanas 11.35 sg 5.24 sg 4.75 sg t=100 y s =20 100.17 sg 58.18 sg 50.72 sg tv=100,sv=20,ta=20 y sa=5132.18 sg 62.55 sg 55.95 sg Tabla 6.3: Simulated Annealing con 40000 iteraciones y temperatura 1 Ahora, en la Figura 6.1 se muestran una serie de gr´aficas donde se representa el valor de la media aritm´etica obtenida para las distintas pruebas realizadas, teniendo en cuenta cada una de las configuraciones de ventanas consideradas (sin usar ventanas, usando ventanas del mismo tama˜no y solapamiento en la zona del vuelo y en los aeropuertos, as´ı como usando ventanas con distinto tama˜no y solapamiento dependiendo de si se considera la zona del vuelo o de los aeropuertos). La Figura 6.1a se corresponde con la eficacia conseguida (en porcentaje), la Figura 6.1b con la distancia recorrida (en kil´ometros), la Figura 6.1c con la diferencia entre la distancia original con respecto a la obtenida (en kil´ometros) y la Figura 6.1d con el tiempo empleado (en segundos). 75 6.2. Comparativa de los m´etodos de resoluci´on 82 Cap´ıtulo 7 Implementaci´on del Simulated Annealing usando MapReduce Durante este cap´ıtulo se describe c´omo se ha realizado la implementaci´on del algoritmo Simulated Annealing usando el modelo de programaci´on MapReduce. La idea de dicha implementaci´on surge porque, como el propio nombre del trabajo indica, la reconstrucci´on de las trayectorias se iba a hacer desde el principio usando dicho algoritmo. Tras realizar una serie de pruebas en el dashboard creado, los resultados obtenidos s´ı mejoraban los de partida. Por todo ello, se decidi´o implementar el algoritmo Simulated Annealing usando el modelo de programaci´on MapReduce para poder procesar en paralelo grandes conjuntos de datos procedentes de diferentes vuelos, y as´ı, dar una soluci´on escalable a la vez que distribuida al problema planteado en el proyecto llevado a cabo. 7.1. Descripci´on del entorno Para realizar la implementaci´on del algoritmo Simulated Annealing usando el modelo de programaci´on MapReduce se va a usar como entorno Big Data Cloudera. Cloudera CDH (Cloudera Distribution Hadoop) es la plataforma de c´odigo abierto de Cloudera siendo esta la distribuci´on m´as popular de Apache Hadoop (base tecnol´ogica sobre la que se desarrolla Cloudera). Pero, adem´as de incluir el n´ucleo de Hadoop, integra diversos proyectos de la fundaci´on de Apache como HBase, Mahout, Pig, Hive, etc. Hadoop es un framework muy potente y uno de los m´as usados en el contexto tecnol´ogico actual, gracias a su importancia en el desarrollo de proyectos que usan tecnolog´ıas de tipo Big Data ya que ofrece computaci´on fiable, escalable y distribuida, apoy´andose para ello en la t´ecnica de MapReduce y en el sistema distribuido de archivos HDFS. Por lo tanto, Hadoop es capaz de ejecutar programas en MapReduce escritos en Java como es nuestro caso. Dichos programas se caracterizan por su naturaleza paralela, lo cual resulta de gran utilidad para analizar grandes conjuntos de datos usando distintas m´aquinas distribuidas en clusters, f´aciles de escalar. 83 7.1. Descripci´on del entorno En la Figura 7.1 se muestra la arquitectura b´asica de Hadoop. Por un lado, se muestra el sistema de archivo HDFS que se comunica con la infraestructura de programaci´on MapReduce, siendo ´esta la encargada de realizar todas las operaciones y procesamientos distribuidos. Por otro lado, Hive, HBase, Pig, etc. son herramientas que usa MapReduce para realizar operaciones sobre los datos. Figura 7.1: Arquitectura b´asica de Hadoop [21] El procedimiento seguido para la implementaci´on ha sido el siguiente: 1. Instalaci´on de X2Go Client: Como la implementaci´on se ha realizado usando la m´aquina virtual Cloudera, se puede: bien acceder a ella v´ıa ssh o bien usando X2Go Client que es un software de c´odigo abierto que proporciona un escritorio remoto muy visual que facilita el trabajo en Cloudera. Su descarga se puede hacer de forma gratuita en la p´agina web https://wiki.x2go.org/doku.php. Una vez instalado, se requiere realizar una serie de configuraciones para poder usarlo, como son las siguientes: indicar el nombre de la sesi´on, el host, el usuario, el puerto de conexi´on SSH y el tipo de sesi´on usada. 2. Uso de Eclipse Luna yNetBeans 8.2 para la implementaci´on: Primero, se comenz´o programando el algoritmo en NetBeans usando Java y tras ver que su funcionamiento era el esperado, se us´o Eclipse Luna para a˜nadir la funcionalidad asociada usando el modelo de programaci´on MapReduce dentro de la m´aquina virtual de Cloudera. Por un lado, NetBeans 8.2 IDE es un entorno de desarrollo integrado libre, gratuito y multiplataforma que usa el lenguaje de programaci´on Java, y por otro lado, Eclipse Luna es una plataforma de software que consta de un conjunto de herramientas de programaci´on, las cuales son de c´odigo abierto, multiplataforma y que tambi´en usan Java. Antes de detallar c´omo se ha realizado la implementaci´on, conviene explicar las tecnolog´ıas de Apache HDFS y el modelo de programaci´on MapReduce ya que se han usado para su realizaci´on. 84 7.1. Descripci´on del entorno Apache HDFS (Hadoop Distributed File System): Es un framework de software que soporta aplicaciones distribuidas bajo una licencia libre. Es adecuado para aplicaciones que tienen grandes conjuntos de datos y se encarga del almacenamiento distribuido de dichos datos en un determinado cl´uster. De manera interna, un archivo se divide en uno o m´as bloques, donde todos los bloques tienen el mismo tama˜no a excepci´on del ´ultimo y se almacenan en un conjunto de DataNodes (explicado posteriormente). Estos bloques son replicados para evitar posibles fallos. Tanto el tama˜no de los bloques como el n´umero de r´eplicas es configurable, y por lo general el tama˜no suele ser grande, permitiendo reducir el tiempo de acceso asociado a la lectura de los datos. HDFS es compatible con el patr´on “write once read many”, que resulta de gran utilidad para las aplicaciones que escriben datos una sola vez pero los leen una o m´as veces a determinadas velocidades. Luego, lo que se tiene es un archivo que se almacena mediante un determinado n´umero de bloques que son replicados entre los distintos servidores del cl´uster de Hadoop. En la Figura 7.2 se muestra un ejemplo de una r´eplica donde se tienen 5 bloques, cada uno de los cuales son replicados dos veces. Figura 7.2: Replicamiento de bloques [18] HDFS tiene una arquitectura de tipo maestro/esclavo, donde el nodo maestro se conoce como NameNode y el resto como DataNodes. El NameNode es un servidor que se encarga de administrar el espacio de nombres del sistema de archivos (realiza operaciones como abrir, cerrar y renombrar tanto archivos como directorios) y regular el acceso de los clientes a los mismos. Adem´as, asigna los bloques a los DataNodes, los cuales, se encargan de atender las solicitudes de lectura y escritura de los clientes del sistema de archivos, as´ı como crear, eliminar y replicar los bloques seg´un las ´ordenes dadas por el DataNode. Por lo tanto, son los encargados de ejecutar las funciones Map yReduce sobre los datos que se almacenan de manera local en cada uno de los nodos del cl´uster. En resumen, mientras que el NameNode se encarga de saber el estado de los datos almacenados por el cl´uster, los DataNodes se encargan de realizar dicho almacenamiento f´ısico de los datos en el cl´uster asociado. Adem´as, existe otro nodo denominado Jobtracker que agrupa las tareas de MapReduce a nodos espec´ıficos en el cl´uster (suelen ser los que tienen los datos, o al menos los que est´an en el mismo rack). 85 7.1. Descripci´on del entorno En la Figura 7.3 se muestra la arquitectura HDFS comentada con anterioridad. Figura 7.3: Arquitectura HDFS [18] MapReduce: Es un entorno de desarrollo o modelo de programaci´on dise˜nado para procesar grandes cantidades de datos en paralelo dentro de sistemas que se encuentran distribuidos. Se encarga de repartir las tareas entre los diversos nodos del cl´uster. MapReduce no sirve para resolver cualquier tipo de problema, siendo principalmente usado con problemas asociados a grandes cantidades de datos que suelen ejecutarse sobre el sistema de ficheros HDFS. Entre sus principales caracter´ısticas podemos destacar las siguientes: ·Distribuci´on y paralelizaci´on autom´aticas. ·Presenta tolerancia frente a fallos y redundancias. ·Dispone de herramientas de monitorizaci´on. ·Con funcionamiento interno y mantenimiento transparente para los desarrolladores. ·Posee gran escalabilidad horizontal, pues en caso de ser necesario m´as c´omputo de programaci´on, basta con a˜nadir m´as nodos al cl´uster. ·Permite la localizaci´on de los datos mediante el desplazamiento del algoritmo a ellos. El esquema de funcionamiento de MapReduce se puede ver en la Figura 7.4. Como se puede apreciar, existen varias fases. La primera de ellas es la fase del Mapping que consta de un m´etodo (map) que recibe como par´ametros de entrada un par (clave, valor) por cada l´ınea del fichero de entrada. Se encarga de realizar el tratamiento sobre cada uno de esos pares (clave, valor) devolviendo cero o m´as pares (clave, valor) en cada llamada. Tras ello, est´a la fase intermedia del Shuffling &Sort en la que se ordenan los resultados obtenidos del Mapper por la clave y se combinan en una lista aquellos que tienen la misma clave. Finalmente, en la fase del Reducer, se define el m´etodo reduce que, tras recibir las claves y 86 7.1. Descripci´on del entorno los valores asociados a cada una de ellas, realiza las operaciones indicadas emitiendo uno o m´as pares de (clave, valor). Figura 7.4: Esquema de funcionamiento de MapReduce [17] A continuaci´on, se muestra un ejemplo concreto que consiste en obtener el n´umero de veces que aparece cada una de las palabra de un texto dado como entrada. El texto considerado consta de tres l´ıneas diferentes que ser´an procesadas en paralelo. El resultado obtenido en cada una de las distintas fases puede verse en la Figura 7.5. Figura 7.5: Ejemplo WordCount usando MapReduce 87 7.2. Implementaci´on del algoritmo 7.2. Implementaci´on del algoritmo Durante esta secci´on se pretende dar una breve explicaci´on de la implementaci´on realizada del algoritmo Simulated Annealing usando el modelo de programaci´on MapReduce comentado con anterioridad y el lenguaje Java. En el caso concreto de la implementaci´on del Simulated Annealing, el proceso seguido en la primera fase (la fase del Mapper) consiste en lo siguiente: dado un archivo con un conjunto de l´ıneas (cada una de ella est´a asociada a la informaci´on de un cierto mensaje ADS-B), se encarga de procesarlas y agruparlas seg´un el identificador o leg del vuelo. Luego, en la fase del Reducer, una vez obtenidos los datos de cada vuelo, se aplica dicho algoritmo de resoluci´on a cada conjunto de datos obtenido. Tras ello, la salida resultante es uno o m´as ficheros que contienen los mensajes ordenados tras ejecutar el algoritmo para los distintos vuelos considerados, junto con cuatro columnas adicionales: distancia, time nuevo,tag orig ytag ord que se detallar´an a lo largo de las explicaciones posteriores. Para realizar la ejecuci´on del proyecto es necesario introducir una serie de par´ametros de entrada de la forma: fichero entrada fichero salida num iteraciones temperatura ratio enfriamiento tam entorno modo tam vuelo solap vuelo tam aerop solap aerop altura, donde los 7 primeros son obligatorios y los 5 ´ultimos dependen del modo de ejecuci´on elegido. El proyecto creado consta de 5 clases que son: Main.java,Algoritmo.java,Interpreter.java, Mensaje.java ySimulatedAnnealing.java. A continuaci´on se describe cada una de ellas. Main.java: Es la clase principal del proyecto y en ella se implementan los m´etodos map yreduce. Por un lado, en el m´etodo map se lee cada una de las l´ıneas del fichero de entrada y se toquenizan considerando como separador la coma (,). Tras ello, para cada l´ınea se crea una instancia de la clase mensaje con la l´ınea de la cabecera y la l´ınea de datos le´ıda. Finalmente, se env´ıan al collector como datos de salida del mapper diversos pares (clave, valor) donde la clave es el identificador o leg del vuelo y el valor cada instancia de mensaje creada. Por otro lado, en el m´etodo reduce(), primero se recogen los mensajes correspondientes a un determinado valor de leg y se instancia un objeto de la clase mensaje con cada uno de ellos. Todos esos mensajes se guardan en un ArrayList de mensajes con el que se invoca al constructor de la clase Interpreter.java, y tras ello, al m´etodo reordenarMensajes() que se encarga de ordenarlos por timestamp. Despu´es, se aplica el m´etodo Simulated Annealing a dichos mensajes distinguiendo los tres modos de ejecuci´on (sin ventanas, con ventanas del mismo tama˜no, o con ventanas de distinto tama˜no en la zona del aeropuerto y el vuelo). Una vez que se tienen los mensajes reordenados, el m´etodo getArrayDistance() devuelve un vector de distancias cuyas componentes vienen dadas por la distancia existente entre cada punto con respecto al primero. Esto se usa en el m´etodo corregirTimestamps() que recibe la ruta ordenada y el vector de distancias para realizar la correcci´on de los tiempos de aquellos puntos que han sufrido cambios tras la reordenaci´on. Finalmente, se a˜nade al fichero de salida la cabecera dada m´as los campos distancia,time nuevo,tag orig ytag ord que se corresponden respectivamente con la distancia entre cada punto con respecto al primero tras la reordenaci´on, el nuevo tiempo 88 7.2. Implementaci´on del algoritmo interpolado, la posici´on original y la obtenida al aplicar el algoritmo. En el m´etodo est´atico main se crea el trabajo o job y se consideran las distintas opciones de par´ametros de entrada. Tras ello, se define el formato de los ficheros, se llama al m´etodo map yreduce, etc. y se ejecuta el job. En la Figura 7.6 se muestra el esquema de funcionamiento descrito con anterioridad. Como se ve, tras partir de un fichero con mensajes ADS-B no ordenados de distintos vuelos, se obtiene un fichero de mensajes ADS-B ordenados para cada uno de los vuelos considerados (se ordenan seg´un el valor de leg que es el identificador del vuelo). Figura 7.6: L´ogica de funcionamiento Algoritmo.java: Se trata de una clase abstracta que representa un determinado algoritmo de reordenaci´on. En este caso s´olo tenemos uno y no es estrictamente necesaria, pero se ha considerado as´ı porque es m´as general y permite a˜nadir otros algoritmos de forma r´apida y eficaz. En dicha clase se definen un conjunto de variables, unos constructores (para el caso sin ventanas o ventanas del mismo tama˜no, pues basta considerar para el caso sin ventanas un tama˜no de ventana igual al n´umero de datos y solapamiento cero; y para el caso de ventanas con distinto tama˜no en la zona del aeropuerto y en el vuelo), as´ı como una serie de m´etodos: get yset,calcularParametros() que calcula el n´umero de ventanas a considerar as´ı como el l´ımite inferior, el l´ımite superior, el tama˜no de ventana y el solapamiento para cada una de las tres zonas posibles a considerar, initDistanceTable() que calcula la matriz de distancias entre cada par de puntos, createInitialTour() para crear la ruta inicial, getDistance() que calcula la distancia de la ruta actual y si se le pasa como par´ametro una subruta, calcula la distancia de la misma, getArrayDistance() devuelve un array de distancias cuyas coordenadas vienen dadas por la distancia existente entre cada punto con respecto al primero y runAlgorithm para la ejecuci´on del algoritmo. 89 7.2. Implementaci´on del algoritmo Interpreter.java: Dicha clase posee una serie de variables y un constructor que recibe la posici´on de la columna asociada al campo longitud, latitud, altura, velocidad y timestamp en el fichero, as´ı como un ArrayList de mensajes. Tras ello, hay tres m´etodos getCoordinates(),getIds() ygetVelocidades(), que se encargan de obtener las coordenadas (longitud, latitud y altitud), los timestamp y las velocidades de cada punto respectivamente. Luego hay otros m´etodos como: reordenarMensajes() que se encarga de ordenar todos los mensajes del ArrayList por timestamp,estaEnArray() que comprueba si un booleano est´a en un array de booleanos, buscarPuntoBueno() que se encarga de obtener la posici´on del punto bueno anterior o posterior al punto que va a ser interpolado, mean() que calcula la media aritm´etica de un ArrayList dado el ´ındice de inicio y de fin excluyendo los valores nulos y el m´etodo buscarCoincidencias() que recibe como par´ametro de entrada un array con el orden obtenido al aplicar el algoritmo y devuelve un array donde el valor true significa que el dato no ha sido alterado y el valor false que si lo ha sido. Por ´ultimo, el m´etodo corregirTimestamps() se encarga de corregir los tiempos para los puntos alterados tras la reordenaci´on siguiendo el mismo modelo de programaci´on lineal descrito en el Cap´ıtulo 5 usando el entorno de R-Studio. Mensaje.java: Dicha clase es bastante sencilla. Tiene un constructor que recibe el nombre de los campos de la cabecera de un archivo y una l´ınea de datos. Luego se definen una serie de m´etodos get yset, el m´etodo getCoordenadas() que devuelve el valor de las coordenadas de un punto en t´erminos de longitud, latitud y altitud dado el ´ındice de posici´on y el m´etodo toString() que va construyendo las l´ıneas de datos concatenando los distintos valores y usando como separador la coma. SimulatedAnnealing.java: Es la clase donde se implementa el algoritmo Simulated Annealing. Para su ejecuci´on se necesita conocer cuatro par´ametros que son proporcionados por el usuario: temperatura inicial, ratio de enfriamiento, n´umero de iteraciones y tama˜no del entorno de estados vecinos considerado para los distintos estados. Dicha clase, consta de dos constructores que se usar´an en funci´on del modo de ejecuci´on considerado, as´ı como de varios m´etodos. ·getDistance(): Obtiene la distancia de la ruta actual en kil´ometros. ·criterioAcep(): Se corresponde con el criterio de aceptaci´on de estados definido en (4.1). ·randomDouble(): Devuelve un valor aleatorio en [0,1). ·randomInt(): Devuelve un n´umero entero aleatorio en el rango [min, max). ·runAlgorithm(): Implementa el algoritmo Simulated Annealing siguiendo el esquema dado en el Cap´ıtulo 4 y distinguiendo en funci´on de los distintos modos de ejecuci´on posibles. Para ello, primero se calcula el valor de los par´ametros invocando al m´etodo calcularParametros() y, para cada una de las ventanas, se ejecuta el algoritmo teniendo en cuenta cu´al es el l´ımite inferior y superior de cada una de ellas. Tras ello, mientras la temperatura sea menor que 1 se genera un estado aleatorio en el espacio de estados Sy, para el n´umero de iteraciones fijado, se genera otro estado aleatorio en un entorno pr´oximo al estado anterior (dicho entorno es fijado por el usuario). Despu´es, se comprueba si el estado es aceptado o no (se tiene en cuenta el criterio de aceptaci´on y que la nueva 90 7.2. Implementaci´on del algoritmo distancia sea igual o mejor que la anterior). En caso de ser aceptado se intercambian dichos estados, y en otro caso, no se modifica su posici´on. Una vez que acaban todas las iteraciones para un estado se desciende el valor de la temperatura teniendo en cuenta el ratio de enfriamiento. Esto se repite hasta que la temperatura toma un valor menor o igual a 1. En la Figura 7.7 se muestra una imagen de una parte del fichero resultante tras ejecutar el proyecto creado en Java usando MapReduce. En ella, se observan los distintos mensajes ordenados asociados al primero de los vuelos considerados en el fichero de entrada. Figura 7.7: Fichero de salida resultante 91 Bibliograf´ıa [12] Alonso Isla, A., Mart´ ınez Prieto, Miguel A., Breg´ on Breg´ on, A., Garc´ ıa Miranda, I., ´ Alvarez Esteban, Pedro C., D´ ıaz, F. y Gordaliza, P. (2017),Airports: An´alisis de Eficiencia Operacional basado en Trayectorias de Vuelo, URL: https://biblioteca.sistedes.es/submissions/ descargas/2018/JISBD/2018-JISBD-063.pdf. [13] Gesti´ on del tr´ afico a´ ereo (ATM),Gesti´on del tr´afico a´ereo (ATM), URL: https://greatbustardsflight.blogspot.com/2018/06/ gestion-del-trafico-aereo-atm-de-forma.html, 2018. Visitado por ´ultima vez el 8 de Febrero de 2019. [14] Wikipedia,OpenSky Network, URL: https://en.wikipedia.org/wiki/ OpenSky_Network, 2018. Visitado por ´ultima vez el 16 de Febrero de 2019. [15] Lenguaje R,Lenguaje R, URL: https://blog.datatons.com/2016/04/ 08/que-es-lenguaje-programacion-r/, 2018. Visitado por ´ultima vez el 22 de Febrero de 2019. [16] Introducci´ on a Shiny,Introducci´on a Shiny, URL: http: //rstudio-pubs-static.s3.amazonaws.com/21373_ 8af3d3634b97461089c8a76659982915.html, 2014. Visitado por ´ultima vez el 25 de Febrero de 2019. [17] MapReduce,MapReduce, URL: http://hadoopontheroad.blogspot.com/ 2013/02/mapreduce.html, 2013. Visitado por ´ultima vez el 19 de Abril de 2019. [18] Hadoop HDFS,Hadoop HDFS, URL: https://hadoop.apache.org/docs/ r1.2.1/hdfs_design.html#Introduction, 2018. Visitado por ´ultima vez el 19 de Abril de 2019. [19] Kai Lai Chung,Markov Chains, Springer, NewYork, 1960. [20] Isaacson, D. and R. Madsen [1976],Markov Chains, Wiley, New York. [21] Arquitectura de Hadoop,Arquitectura de Hadoop, URL: http://www. diegocalvo.es/hadoop/, 2016. Visitado por ´ultima vez el 1 de Junio de 2019. 98 Ap´endice A Contenido del CD-ROM En esta parte se detalla el contenido del CD-ROM aportado junto con el manual de instalaci´on de cada uno de los programas implementados. El CD-ROM adjunto en la entrega contiene el c´odigo en Java del proyecto realizado usando el modelo de programaci´on MapReduce, el c´odigo fuente del dashboard realizado usando R-Studio, as´ı como una copia en pdf de esta memoria. Para que sea m´as claro, se detalla la estructura de directorios del CD-ROM entregado y el manual de instalaci´on cuando sea necesario: ·MapReduceTrayectoriasSA →Dicha carpeta contiene el proyecto realizado en la m´aquina virtual de Cloudera para implementar el algoritmo de resoluci´on Simulated Annealing usando el modelo de programaci´on MapReduce y el lenguaje Java. Todas las clases .java se encuentran dentro de la carpeta src. En la Figura A.1 se muestra la estructura de directorios del proyecto escalable creado en Java. Figura A.1: Estructura de directorios de la aplicaci´on en Java 99 Para poder ejecutar la implementaci´on escalable realizada se deben cumplir los siguientes requisitos: 1. Disponer de un sistema operativo Cloudera, que integra las librer´ıas de Apache Hadoop. 2. Java JDK 1.7 o superior. 3. IDE Eclipse Luna. Para descargar Cloudera se puede hacer desde la siguiente p´agina web https://es. cloudera.com/. Dicha p´agina web se visualiza en la Figura A.2. Figura A.2: P´agina web de Cloudera ·ProyectoR →Dicha carpeta contiene una carpeta denominada Shiny que tiene: el c´odigo fuente del dashboard realizado en R-Studio usando el lenguaje R (app.R), una carpeta llamada www que tiene las im´agenes e iconos usados en el dashboard, dos ejecutables para los m´etodos de ejecuci´on Lin-Kernighan yConcorde (linkern.exe yconcorde.exe), una carpeta llamada Vuelos que tiene un conjunto de archivos en formato csv donde cada uno de ellos tiene el nombre de un determinado vuelo y otro ficheros requeridos. Luego, dentro de la carpeta ProyectoR, hay un fichero denominado runShinyApp.R que contiene el c´odigo necesario para que el dashboard creado se ejecute directamente desde el CD-ROM sin necesidad de tener que abrir el script creado en R-Studio, as´ı como otros ficheros adicionales. En las Figuras A.3 y A.4 se muestra la estructura de directorios comentada con anterioridad. 100 Figura A.3: Estructura de directorios del dashboard (ProyectoR) Figura A.4: Estructura de directorios del dashboard (Shiny) Por otro lado, el proceso de instalaci´on para ejecutar el dashboard es el siguiente: 1. Descomprimir el zip ProyectoR.zip. 2. Abrir la carpeta ProyectoR y ejecutar el archivo run.bat. 3. Tras ello, se abre un terminal y hay que esperar unos segundos hasta que se abre el dashboard en el navegador que se tenga como predeterminado. 4. Una vez que se acaba de trabajar con la aplicaci´on basta con cerrar la pesta˜na del navegador, lo cual, cierra la sesi´on del terminal abierto. Dicho procedimiento tambi´en se encuentra detallado en el fichero leeme.txt que se encuentra dentro de la carpeta ProyectoR. ·Memoria →Dicha carpeta incluye en formato pdf una copia del presente documento denominado TFG Mar´ıaZorita.pdf. 101