Reconstrucción de trayectorias de aeronaves usando heurísticas de mejora para resolver una versión del problema del viajante (TSP)

Universidad de Valladolid Escuela de Ingeniería Informática de Segovia Trabajo Fin de Grado Grado en Ingeniería Informática de Servicios y Aplicaciones Reconstrucción de trayectorias de aeronaves usando heurísticas de mejora para resolver una versión del problema del viajante (TSP) Alumno: Juan Manuel Velasco Heras Tutores: Anibal Bregón Bregón, Miguel Ángel Martínez Prieto Reconstrucción de trayectorias de aeronaves usando heurísticas de mejora para resolver una versión del problema del viajante (TSP) Juan Manuel Velasco Heras Agradecimientos A Boeing Research and Technology Europe por poner a disposición del proyecto datos e información propia, a mi compañera de estudios y promoción María Zorita Mínguez por su colaboración, a los profesores D. Aníbal Bregón Bregón y D. Miguel Ángel Martínez Prieto por haber aceptado la dirección de este Trabajo Fin de Grado y al profesor D. Pedro César Álvarez Esteban por sus valiosas aportaciones y directrices. Resumen El tráfico aéreo mundial está cada vez más congestionado. Solo en Europa, Eurocontrol pronostica para 2023 un aumento del 14 % en el número de vuelos que transitarán por su espacio aéreo con respecto a 2016, lo que exige una profunda renovación de los sistemas de gestión actuales apostando por tecnologías bigdata. El proyecto AIRPORTS (CIEN, 2015), liderado por Boeing Research & Technology Europe, involucra a la Universidad de Valladolid en esta tarea, abarcando la reconstrucción de trayectorias de aeronaves a partir de los datos de seguimiento obtenidos mediante la nueva tecnología ADS-B (Automatic Dependent Surveillance - Broadcast), que, a pesar de sus ventajas (menores costes, comunicación entre aeronaves, etc), presenta algunos problemas como la desincronización de las señales recibidas por los diferentes receptores terrestres. El presente Trabajo Fin de Grado estudia esta problemática y propone una solución que transforma el supuesto en una variante del conocido problema del viajante (TSP) en la que el nodo inicial y final no coinciden. Se abordan los principales métodos de resolución del TSP profundizando sobre las heurísticas de mejora local. El modelo de solución es analizado y se concluye como satisfactorio al combinarlo con algoritmos como el 2-Opt o el Lin-Kernighan, motivando la implementación escalable de uno de ellos. Se aborda también la posterior corrección de las marcas temporales de los datos de seguimiento. Palabras clave: TSP, ADS-B, ATM, R, MapReduce. Abstract International air traffic is more crowded each day. In Europe, Eurocontrol forecasts for 2023 a rise of 14% in the number of flights moving throught the European air space compared to 2016, requiring to renovate the current management systems with new bigdata technologies. The AIRPORTS project (CIEN, 2015) leaded by Boeing Research & Technology Europe involves University of Valladolid in this task, including the construction of aircrafts trajectories using the Automatic Dependent Surveillance—Broadcast (ADS-B) technology, which, despite its advantages (cheaper, aircrafts inter-communications, etc), it has few time synchronizing problems involving signals received by different receivers. This document aims to solve these problems, modeling the resorted trajectories as a variant of the famous Traveling Salesman Problem (TSP) in which the first and last node are not the same. The main TSP solving algorithms are studied, focusing on the local search heuristics. Since the solution model is proved to be satisfying combined with few algorithms such as 2-Opt or Lin-Kernighan, a scalable implementation of one of them is motivated. Besides, a timestamps correction model for the surveillance data is approached. Keywords: TSP, ADS-B, ATM, R, MapReduce. i ii Índice general Lista de figuras V Lista de tablas IX 1. Introducción 1 1.1. Motivación.................................... 3 1.2. Objetivos .................................... 4 1.3. Organización de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Metodología de trabajo 7 2.1. Entregables del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Ciclo de vida del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3. Herramientas y técnicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3. Gestión del Tráfico Aéreo 13 3.1. Introducción................................... 13 3.2. SESAR...................................... 14 3.3. LossistemasADS................................ 15 3.4. ElproyectoAIRPORTS ............................ 17 3.5. El problema que motiva este trabajo . . . . . . . . . . . . . . . . . . . . . 20 4. El Problema del Viajante 25 4.1. Introducción al problema del viajante . . . . . . . . . . . . . . . . . . . . . 26 4.2. HistoriadelTSP ................................ 30 4.3. Aplicaciones generales del TSP . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4. Algoritmos de resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4.1. Los algoritmos exactos . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4.2. Los algoritmos de aproximación . . . . . . . . . . . . . . . . . . . . 35 4.5. Heurísticas de mejora local . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.5.1. Los algoritmos de la familia k-Opt ................... 38 4.5.2. El algoritmo de Lin-Kernighan . . . . . . . . . . . . . . . . . . . . . 41 4.5.3. AlgoritmoOr-Opt............................ 46 iii Índice de tablas x Capítulo 1 Introducción Desde principios de siglo, el tráfico aéreo mundial viene siendo objeto de un crecimiento constante en su concurrencia [Grushka-Cockayne y De Reyck, 2009]. La gestión del tráfico aéreo, del inglés Air Traffic Management (ATM), pasa a cobrar cada vez más importancia en un entorno en el que el número de agentes es cada vez mayor con el paso del tiempo. A esta dinámica creciente hay que sumarle el aumento de la complejidad de los distintos tipos de actores que intervienen (aeropuertos, aerolíneas, aeronaves, etc) [Alonso Isla et al., 2018], resultando en una demanda en aumento de nuevas tecnologías que se adapten de forma adecuada a las cada vez mayores exigencias del sector. El organismo encargado de la gestión del tráfico aéreo en Europa es Eurocontrol, creado en 1963 por la International Civil Aviation Organization (ICAO) con el fin de constituir una única corporación con responsabilidades sobre todo el espacio aéreo europeo [Grushka-Cockayne y De Reyck, 2009]. En sus inicios, los distintos gobiernos nacionales se negaron a renunciar parcialmente a su soberanía en favor de una gestión comunitaria del tráfico aéreo, derivando en un espacio estructurado en bloques o sectores nacionales que dificulta la gestión del tráfico aéreo. La existencia de estas fronteras estatales, unida a la necesidad de modernizar los sistemas ATM continentales, derivaron en pérdidas estimadas entre 200 y 300 millones de euros anuales con respecto a otras estructuras homólogas, tales como el sistema norteamericano, que parte del proyecto NextGen [Alonso Isla et al., 2018]. Para acabar con esta situación, surge en marzo de 2004 la iniciativa Single European Sky (SES), de la mano de la Comisión Europea [Grushka-Cockayne y De Reyck, 2009], para abordar una reestructuración del espacio aéreo europeo que establezca una nueva división por bloques funcionales (acordes a los flujos del tráfico), dejando atrás el anterior sistema marcado por las fronteras nacionales, así como para modernizar los sistemas de control del tráfico aéreo o Air Traffic Control (ATC). En este afán renovador, se incluye una de las tecnologías de seguimiento del tráfico aéreo más recientes: las Automatic Dependent Surveillance - Broadcast (ADS-B), que 1 Capítulo 1. Introducción suponen un importante paso hacia delante en esta materia. Mientras que su uso se hizo obligatorio en Europa para algunas aeronaves a partir de 2017, en otras regiones geográficas como Australia, la apuesta por estas tecnologías es aun más intensa, siendo en la actualidad de equipamiento obligatorio para todas las aeronaves que atraviesan su espacio aéreo [Álvarez Esteban et al., 2017]. La tecnología ADS-B se caracteriza por utilizar los sistemas de navegación vía satélite oGlobal Navigation Satellite System (GNSS) como método por el que la aeronave obtiene su posición, que envían a través del aire en forma de paquetes que reciben el nombre de señales o mensajes ADS-B [Álvarez Esteban et al., 2017]. Estas comunicaciones son recibidas por una red heterogénea de sensores distribuidos por todo el planeta y conectados con grandes repositorios de datos a los que posteriormente acceden los sistemas ATM. Cuando una señal es recibida por un receptor, éste le asocia una marca temporal otimestamp a fin de poder establecer una ordenación temporal de los mensajes ADS-B asociados a un mismo vuelo o trayectoria. Sin embargo cada mensaje puede llegar a más de un receptor de tierra, cada uno de los cuales le asocia una marca temporal o timestamp de acuerdo con su reloj interno. No hay control de las estaciones que reciben cada mensaje ADS-B, lo que unido al hecho de que los mensajes viajan por el aire pudiendo ocasionarse retrasos, produce que un mismo mensaje recibido por varias estaciones receptoras tenga a su vez distintos valores de timestamp en lugar de tener el mismo. Por tanto, y a pesar de las ventajas de ADS-B, entre las que se encuentran la veracidad de sus datos de geolocalización (al obtener la aeronave su posición a través de una red de satélites de comunicaciones), o su alta frecuencia de comunicaciones (de hasta 2 mensajes ADS-B por segundo), esta tecnología cuenta, por un lado, con la aparición de problemas de escalabilidad en los sistemas ATM, obligando a la consideración de tecnologías bigdata capaces de hacer frente a las altas cargas de procesamiento diarias producidas por la enorme cantidad de datos a tratar. Por otro lado, la tecnología ADS-B cuenta con el problema anterior de alineamiento temporal en los datos. En esta línea, el proyecto AIRPORTS (CIEN, 2015), liderado por Boeing Research & Technology Europe trata las diferentes formas de fusionar los datos de diversas fuentes (receptores) de manera que la reconstrucción de las trayectorias se haga de la forma más fielmente posible a la realidad que representan. Este Trabajo Fin de Grado propone un modelo que permita detectar y corregir estos desordenes producidos a causa de esta problemática a partir del conjunto de mensajes ADS-B procedentes de un vuelo. Esta solución pasa por considerar el problema de encontrar esta reordenación correcta de los mensajes ADS-B de un vuelo como una variante del conocido problema del viajante. Este problema, cuyo nombre procede del inglés Traveling Salesman Problem (TSP) trata la búsqueda de caminos de mínima longitud que permitan visitar una serie de ubicaciones determinadas comenzando y terminando en una de ellas. Para reordenar los mensajes ADS-B asociados a una trayectoria es necesario introducir una pequeña variante 2 1.1. Motivación al problema consistente en buscar caminos con las propiedades anteriores no cerrados, esto es, que comiencen y terminen en diferentes ubicaciones. Como ubicaciones o nodos se consideran las coordenadas geográficas que acompañan a cada mensaje ADS-B. Este modelado del problema requiere de un análisis detallado del problema del viajante a modo de estado del arte, que recoja sus características más importantes así como las diferentes técnicas y métodos que lo abordan. Dada la gran variedad de algoritmos existentes, este trabajo profundizará sobre el funcionamiento y características de un tipo muy conocido de estos métodos, las heurísticas de mejora local, los cuales, dada una primera solución, buscan mejorarla (obtener otra mejor) a través de modificaciones sobre ella que derivan en nuevas soluciones de mejor calidad. La propuesta será analizada y posteriormente implementada de forma escalable, para poder formar parte de la lógica de un gran sistema de gestión del tráfico aéreo, que por tanto admita ejecuciones en paralelo sobre un sistema de altas prestaciones. Además, este trabajo incorpora un modelo de corrección de las marcas temporales asociadas a los mensajes ADS-B de una trayectoria, que, tras haber sido reordenados, existirán inconsistencias entre sus marcas temporales (mensajes con timestamp posterior pueden quedar dispuestos antes que otros con timestamp anterior). En este sentido, se busca la implementación de este modelo para que actúe tras una reordenación reasignando los timestamps de los mensajes de manera que se asemejen lo más fielmente posible al instante temporal en que fueron emitidos. 1.1. Motivación Los nuevos sistemas ATM en Europa han adoptado las nuevas tecnologías de seguimiento ADS-B, que, a pesar de requerir una infraestructura más barata, están desbancando a las tradicionales comunicaciones vía radares secundarios [Martínez Prieto et al., 2017]. Estos nuevos mecanismos de seguimiento se basan, como ya se ha mencionado, en la emisión periódica por parte de una aeronave de señales o mensajes ADS-B conteniendo una serie de datos que permiten el seguimiento del vuelo. Entre ellos se incluyen ubicación actual (en coordenadas geográficas: latitud y longitud), altura, velocidad y callsign (indicador de vuelo) [Álvarez Esteban et al., 2017]. Los mensajes ADS-B son recibidos por distintas redes de receptores, que, como hemos visto, asocian el timestamp conforme a su reloj interno. Posteriormente, los mensajes son almacenados en grandes bases de datos a las que acceden los sistemas ATM para operar con ellos. Entre otras aplicaciones, estos datos permiten la posterior reconstrucción de los trayectos realizados. Para ello, se requiere conocer el orden temporal de los mensajes ADS-B que se corresponden a un mismo vuelo, que a su vez se obtienen por lo general de 3 Capítulo 1. Introducción varias fuentes de datos no sincronizadas. Por tanto, se repercute en el problema temporal descrito anteriormente, generando errores en estas reconstrucciones. Este trabajo tiene como objetivo resolver esta problemática, aumentando así el grado de exactitud de las posteriores reconstrucciones de las trayectorias con respecto a las realizadas realmente, obteniendo datos de longitud de la trayectoria (o distancia recorrida por la aeronave) más próximas a la realidad. Reduciendo las tasas de error en esta materia es posible un control más preciso del espacio aéreo, que entre otras consecuencias tiene el registro y estudio minucioso de los sucesos acontecidos en el espacio aéreo continental, derivando causas y responsabilidades de una forma más efectiva. 1.2. Objetivos El presente Trabajo Fin de Grado estudia, como ya se ha mencionado, los problemas derivados del mal alineamiento temporal de los mensajes ADS-B con el fin de desarrollar una solución que contrarreste sus efectos sobre el procesamiento de los datos por parte de los sistemas de gestión del tráfico aéreo. En esta línea, se identifican los siguientes objetivos a cubrir: OB-1 Desarrollo de una implementación escalable de un algoritmo que permita la reconstrucción de trayectorias de aeronaves a partir del conjunto de mensajes ADS-B asociados. OB-1.1 Formulación de un modelo de reordenación temporal de los mensajes ADS-B que aproxime lo máximo posible el verdadero orden en que son lanzados. OB-1.2 Implementación del modelo teórico que propone el subobjetivo OB-1.1 sobre alguna tecnología escalable que permita su integración a la lógica interna de un sistema de gestión del tráfico aéreo. OB-2 Abordar la corrección de las marcas temporales o timestamp de los mensajes ADS-B asociados a una trayectoria tras haber sido reordenados OB-2.1 Creación de un modelo matemático de corrección de las marcas temporales, dada una reordenación de los mensajes. OB-2.2 Implementar la propuesta que plantea el subobjetivo [OB-2.1], a fin de que pueda ser puesta en práctica sobre trayectorias reales. OB-3 Elaborar un compendio bibliográfico del problema del viajante, enfocando el estudio sobre las heurísticas de mejora local. OB-3.1 Identificar las heurísticas de mejora local más relevantes a fin de ser recogidas y estudiadas en esta memoria. OB-3.2 Analizar el funcionamiento de estos métodos y las técnicas en que se basan. 4 1.3. Organización de la memoria El proyecto a abordar por este trabajo, lleva así asociada una buena labor de investigación, con objeto de encontrar las mejores técnicas y estrategias que sustenten los modelos de reordenación y corrección a desarrollar. Para ello, se requiere analizar de qué manera los algoritmos que resuelven el problema del viajante son aplicables en este contexto en base a su comportamiento, coste computacional, procedimientos que utiliza, etc. Con este objetivo, a lo largo de la memoria se incluyen varias pruebas cuyos resultados serán de utilidad para determinar el nivel de adecuación de las distintas estrategias existentes en diferentes situaciones. 1.3. Organización de la memoria El presente documento se divide en capítulos que tratan diferentes aspectos del proyecto. En primer lugar, se desglosa la metodología de trabajo en el Capítulo 2, donde se identifican los entregables del proyecto (ver Sección 2.1), se listan las fases que componen su ciclo de vida (ver Sección 2.2) y que marcan la estructura posterior de la memoria, y se listan las herramientas y técnicas identificadas (ver Sección 2.3). El Capítulo 3 introduce el contexto que motiva el presente Trabajo Fin de Grado, que involucra la iniciativa de Boeing Resarch & Technology Europe y la colaboración de la Universidad de Valladolid en la construcción de una plataforma bigdata que habilite el estudio de métricas de eficiencia asociadas a la reconstrucción de trayectorias de aeronaves, en el marco del proyecto AIRPORTS, impulsando una renovación en los sistemas de gestión del tráfico aéreo europeo. En el Capítulo 4 se analiza el estado del arte del proyecto. Este esfuerzo abarca los fundamentos teóricos del problema del viajante (TSP), historia, aplicaciones prácticas y algoritmos de resolución, de entre los cuales se analizan en profundidad un tipo especial de ellos, que reciben el nombre de heurísticas de mejora local. Estos algoritmos parten de un camino inicial dado e iteran sobre él realizando modificaciones sucesivas para obtener otros caminos mejores (más cortos). Para ello, cada heurística usa distintas técnicas sobre las que es necesario profundizar y analizar su comportamiento a la hora de ser adaptadas para poder aplicarse a la reordenación de los mensajes ADS-B de una trayectoria. Conviene destacar que, en el contexto de estas reordenaciones, se dispone de un camino inicial dado por el timestamp de los datos de seguimiento. Partiendo de esta ordenación, las heurísticas de mejora local pueden iterar para un nuevo orden que de como resultado una trayectoria reconstruida más corta. A continuación, el Capítulo 5 expone los puntos más destacados del desarrollo de una aplicación destinada a albergar un estudio que permita establecer una primera comparación entre los algoritmos más destacados recogidos previamente en el análisis del estado del arte. No es objeto de esta aplicación implementar los algoritmos, sino el de reutilizar implementaciones libres de los mismos. Se opta por el lenguaje Rpara desarrollar esta aplicación, que cuenta con librerías como TSP ystats que abarcan buena parte de los 5 Capítulo 1. Introducción algoritmos más destacados para resolver el problema del viajante. En la Sección 5.5 se plantea el modelo de corrección de las marcas temporales de los mensajes ADS-B en base a diferentes parámetros incluidos en ellos como la velocidad, altura o geolocalización de la aeronave. Los resultados del estudio que pretende albergar esta aplicación se incluyen en el Capítulo 6. El Capítulo 7 expone las fases posteriores del trabajo, incluyendo la implementación en Java de una de las heurísticas estudiadas en base a su adecuación a la reordenación de los mensajes, así como su integración a una nueva aplicación sobre MapReduce que permita la reordenación simultánea de varias trayectorias y la posterior corrección de las marcas temporales de sus mensajes, a fin de poder ser ejecutada sobre un clúster e integrado a un sistema de gestión del tráfico aéreo. El Capítulo 8 incluye las conclusiones finales del proyecto, así como el trabajo futuro a realizar. 6 Capítulo 2 Metodología de trabajo Una de las primeras tareas de todo proyecto es la elección y posterior configuración de las técnicas, procedimientos y estrategias aplicables a fin de llevar a cabo las diferentes actividades del proyecto. Se desarrolla, a fin de cuentas, una metodología de trabajo orientada a llevar a cabo las labores de investigación previas a las posteriores implementaciones que permitan cubrir los diferentes objetivos del proyecto, que han sido presentados en el Capítulo 1. De esta forma, el presente capítulo expone la metodología planteada para abordar este trabajo, que requiere de una gran labor investigadora, comúnmente caracterizada por el desconocimiento de sus resultados finales, impidiendo así vislumbrar en los instantes iniciales del proyecto el punto final al que se llegará en el marco de este Trabajo Fin de Grado (pensemos que en el caso de resultar inadecuado el presente modelo de reordenación de los mensajes ADS-B en base al TSP, los trabajos posteriores para poner en práctica la propuesta no tendrán sentido). Esta incertidumbre dificulta el establecimiento de una planificación detallada de las actividades en los instantes iniciales o el desarrollo de una línea de base, así como una estimación del esfuerzo del proyecto; tareas imprescindibles en la gestión de cualquier proyecto de desarrollo software. Dados estos obstáculos iniciales, se opta por fijar una metodología en la que los objetivos de cada fase o etapa del proyecto se marquen en función de los resultados obtenidos en las anteriores. A lo largo del proyecto, y especialmente al final de cada etapa, se han ido estableciendo sucesivas reuniones con los tutores que han tenido como objetivo poner en común los resultados obtenidos en la fase previa para, a partir de éstos, establecer los hitos posteriores así como los pasos necesarios para alcanzarlos. 7 Capítulo 2. Metodología de trabajo 2.1. Entregables del proyecto En relación al conjunto de objetivos que se presentan en el Capítulo 1. Se identifican los siguientes entregables para el proyecto: Un compendio bibliográfico del problema del viajante, en línea con el objetivo [OB-3]. Su desarrollo es a su vez una tarea necesaria para poder abordar el objetivo [OB-1]. Se encuentra expuesto en el Capítulo 4 de la presente memoria. Una aplicación que albergue un estudio comparativo de métodos: a raíz del previo análisis del estado del arte. Se identifican una serie de métodos aplicables al problema del viajante, que análogamente, tienen aplicación en la reordenación de los datos de seguimiento de trayectorias de aeronaves. Con el fin de analizar la adecuación de cada uno de ellos a esta problemática, es oportuno llevar a cabo un estudio comparativo que permita encontrar la mejor de estas técnicas. Con este objetivo, se requiere el desarrollo de una aplicación que incluya la creación de un dashboard que ilustre los resultados obtenidos, así como de una lógica interna que soporte las ejecuciones del estudio. Esta memoria dedica el Capítulo 5 a esta aplicación. Un informe de resultados del análisis comparativo anterior que incluya los resultados de una extensa batería de pruebas expresados a través de una serie de métricas globales que permitan extraer de forma sencilla conclusiones acerca de la adecuación de cada algoritmo estudiado a la reordenación de los datos de una trayectoria. Una implementación escalable que aplique el modelo de reordenación de trayectorias y corrección de marcas temporales propuesto: del informe anterior se extraerá la eficacia de cada método. Para este entregable se escogerá el mejor de los algoritmos para ser implementado de manera que aborde la reordenación de trayectorias reales haciendo uso de un modelo de computación paralelizable. En esta línea, y conforme al [OB-1], se estudia el modelo de programación MapReduce, que a través de una serie de librerías en Java, brinda una serie de métodos ejecutables de forma paralela sobre un hardware adecuado como puede ser un cluster formando parte de un sistema gestor del tráfico aéreo. Implementación de un modelo de corrección de timestamps: una vez queda probada la adecuación de la aplicación escalable, es posible abordar, en línea con el objetivo [OB-2], la creación y posterior implementación de un modelo que permita corregir las marcas temporales de los mensajes ADS-B asociados a un vuelo tras haberse ejecutado una reordenación. El objetivo será implementar este modelo en la aplicación escalable como segunda fase del procedimiento de reordenación. Por otro lado, este modelo también se implantará en la aplicación que albergue el estudio comparativo de métodos, pues gracias a sus componentes gráficos será posible analizar su eficacia así como visualizar los resultados de su ejecución. 8 2.2. Ciclo de vida del proyecto Figura 2.1: Gráfico ilustrativo de la metodología desarrollada para llevar a cabo el proyecto de investigación 2.2. Ciclo de vida del proyecto Se puede establecer una clara división temporal del trabajo realizado en torno a las siguientes etapas: 1. Estudio del estado del arte: El proyecto inicialmente requiere la realización de una labor de documentación y estudio del problema del viajante o Traveling Salesman Problem (TSP). En el Capítulo 1, hablábamos de que el problema de la reordenación de los mensajes ADS-B de una trayectoria, objeto de estudio este TFG, puede ser modelado como una variante del problema del viajante en la que el punto inicial y el final de la ruta son distintos. Esto obliga a identificar y analizar los algoritmos más destacados que resuelven el problema del viajante. Son además objeto específico de investigación de este trabajo las heurísticas de mejora local (objetivo [OB-3]), entre las que encontramos los algoritmos k-Opt yLin-Kernighan, que analizaremos en profundidad en la Sección 4.5. Todos los resultados del trabajo realizado en esta fase se hallan recogidos en el Capítulo 4. Este epígrafe conforma el único entregable de esta fase del proyecto. 2. Estudio preliminar del comportamiento de los algoritmos: tras una primera fase de documentación previa acerca del problema del viajante y algunos de los algoritmos más conocidos que lo resuelven, se establece una fase de estudio inicial que tiene como fin obtener unas primeras conclusiones acerca de la adecuación de los algoritmos a la reordenación de trayectorias. Para ello se hizo uso de las librerías TSP ystats de R, que incluyen gran parte de estos algoritmos. Este análisis abarca el estudio del tiempo de ejecución y de la longitud de la ruta encontrada en cada una de las ejecuciones realizadas, todas ellas en condiciones lo más semejantes posibles (mismo ordenador, misma carga del procesador, etc). El objetivo principal de esta etapa es la selección de los dos o tres algoritmos que mejores resultados hayan reportado según los criterios de estudio establecidos (tiempo de ejecución más bajo y longitud de la ruta encontrada más corta). El trabajo realizado a lo largo de esta fase se expone en el Capítulo 5, y los resultados y conclusiones obtenidas, fruto 9 Capítulo 3. Gestión del Tráfico Aéreo iii) proveer datos de seguimiento, similares a los enviados anteriormente vía radar, tanto a controladores en tierra como a otras aeronaves. Aunque los sistemas se encuentran actualmente en un periodo de transición para incorporar la tecnología ADS-B, los equipamientos asociados a la misma son ya obligatorios para algunas aeronaves en Europa desde finales de 2017. Estos vehículos han sido equipados con transmisores de mensajes ADS-B que contienen información acerca de la trayectoria seguida, y que mandan mensajes que comprenden una serie de datos como el código hexadecimal de 24 bits asociado a la aeronave, el código identificativo del vuelo o callsign, datos de geolocalización, altitud o velocidad. La principal ventaja de la tecnología ADS-B es que provee control del tráfico aéreo (ATC) con la posición en tiempo real obtenida mediante el sistema de navegación que, por lo general, es más preciso que el sistema basado en radares. Además, funciona a bajas altitudes y en tierra, por lo que es posible hacer un seguimiento de las maniobras realizadas por el piloto durante el aterrizaje. La infraestructura necesaria para el despliegue de ADS-B queda conformada por dos tipos de componentes: i) ADS-B Out, que emite los datos de la aeronave (e.g. identificación, posición, altitud, velocidad). ii) ADS-B In, que recibe información de utilidad para el piloto, como datos del tráfico, u otra información transmitida mediante el servicio de información sobre previsiones de vuelo o Flight Information Service-Broadcast (FIS-B), como previsiones meteorológicas, restricciones temporales, etc. El despliegue de la tecnología ADS-B requiere a su vez de dos componentes aeronáuticos: un sistema de navegación junto a un enlace de datos con la aeronave, y una estación receptora que obtiene las señales ADS-B. Figura 3.1: Sistemas de geolocalización y seguimiento. A la izquierda, el tradicional método de obtención de la posición de la aeronave vía radar. A la derecha, el uso de tecnologías ADS-B. Fuente: www.adsb.com 16 3.4. El proyecto AIRPORTS En la Figura 3.1 se ilustra el mecanismo de seguimiento que sigue la tecnología ADSB frente al efectuado por sistema de comunicación de la posición vía radar. Mediante el sistema ADS-B, cada aeronave obtiene su geolocalización vía GNSS (Global Navigation Satellite System) a través de una red de satélites de comunicaciones situados en la órbita terrestre. A continuación, la aeronave, una vez ha determinado su posición, la emite en forma de mensaje ADS-B que será recibido por cualquier estación receptora terrestre cercana, que la almacena y procesa. A su vez, otras aeronaves pueden recibir e interpretar los mensajes ADS-B emitidos por otras permitiendo así determinar la distancia a la que se encuentran para, en caso de aproximarse en exceso, desviar su trayectoria evitando posibles colisiones o interferencias. La frecuencia de transmisión de mensajes ADS-B por cada aeronave es de 2 por segundo, lo que resultan en una enorme cantidad de datos asociados a un mismo vuelo que se reciben, almacenan y procesan por los sistemas ATM. Esto hace que la escalabilidad sea un requisito indispensable de estos sistemas, demandando así el uso de tecnologías bigdata que puedan llevar a cabo las operaciones necesarias para procesar tal cantidad de datos. Este hecho es lo que motiva la actual colaboración de la Universidad de Valladolid con Boeing Research and Technology Europe, en la que se establecen varias líneas de investigación que abarcan la construcción de una plataforma bigdata para ATM, que actúe como centro de datos y que englobe los procesos desde la ingesta de datos “en crudo” emitidos por cada vuelo hasta el refinamiento de los mismos que de lugar a información con valor para el usuario final. La descripción de la arquitectura de esta plataforma puede encontrarse en Álvarez Esteban et al. [2017], y a continuación se describe en líneas generales. 3.4. El proyecto AIRPORTS En los últimos años, la optimización aplicada al campo de la gestión del espacio aéreo se ha convertido en un tema de interés especialmente motivado por el aumento continuo del número de vuelos. Esta optimización recae en el análisis de grandes cantidades de datos procedentes de diferentes actores del sistema ATM, lo que convierte este procesamiento en un problema de bigdata en términos de volumen,velocidad yvariedad de los datos. Sin embargo, la industria aeronáutica no dispone de gran influencia para conseguir integrar este tipo de tecnologías como sí que disponen otras como la sanitaria o la financiera [Martínez Prieto et al., 2017]. En este contexto, nace el proyecto AIRPORTS como un consorcio formado por un conjunto de empresas y Organismos Públicos de Investigación (OPI) liderados por Boeing Research and Technology Europe, con el propósito de desarrollar nuevas tecnologías aplicables a la aeronáutica que mejoren la eficiencia en las operaciones de ATM. De esta forma, 17 Capítulo 3. Gestión del Tráfico Aéreo una de las contribuciones más importantes del proyecto es la mejora de estas operaciones aplicando las tecnologías bigdata más recientes. El objetivo principal de AIRPORTS es estudiar cómo los datos de seguimiento procedentes de diferentes proveedores pueden ser combinados con otros datos similares mejorando la calidad (veracidad) y siendo más relevantes como entrada de las herramientas de soporte a la toma de decisiones empleados en los sistemas ATM. Los datos de seguimiento permiten la reconstrucción de las trayectorias de los vuelos desde que la aeronave se dirige a la pista de despegue hasta que se apagan los motores tras haber aterrizado. La continua actualización de la posición de cada aeronave en vuelo supone una fuente de datos clave para este propósito, dotando al sistema de información sobre su posición, altitud o velocidad, que es recogida durante el vuelo. Sin embargo, la gestión correcta de estos datos solo es posible mediante tecnología bigdata, y de hecho, la cantidad de estos datos es mucho mayor cuando se hace uso de tecnologías ADS-B, pues las señales emitidas por cada aeronave son mucho más frecuentes. Más aún, se está acrecentando la extensión del área terrestre sobre la cual son aplicables las tecnologías ADS-B, al estar siendo cubierta por una infraestructura de satélites de comunicaciones. Sin embargo, tal y como hemos comentado en el capítulo introductorio, a día de hoy existe un problema de veracidad en los datos de seguimiento procedentes de ADS-B debido a que el timestamp (marca temporal) del mensaje, es asignado por la estación de destino en el momento en que lo recibe, y no por el sistema emisor cuando lo envía. Esto deriva en errores en la reconstrucción de las trayectorias al poder producirse desórdenes puntuales en los datos de seguimiento (dos mensajes enviados de forma consecutiva pueden llegar a estaciones receptoras en orden inverso al que fueron enviados), que se propagará al procesamiento y análisis de la información del vuelo, incluyendo la posterior reconstrucción de la trayectoria efectuada. En la Figura 3.3 se ilustran dos ejemplos de segmentos de la reconstrucción de dos trayectorias en donde se observan los efectos de esta problemática. La línea roja une los distintos datos de seguimiento por el orden que marca su timestamp. Finalmente, cabe destacar como una de las contribuciones más importantes del proyecto AIRPORTS la creación de un data lake que recibe el nombre de AIRPORTS DL [Martínez Prieto et al., 2017]. Siendo uno de los conceptos más novedosos asociado al bigdata, un data lake permite la ingesta y almacenamiento de datos en crudo (aquellos que aun no han sido procesados por haberse obtenido recientemente) para ser tratados posteriormente. AIRPORTS DL está basado en sistemas de ficheros HDFS (Hadoop Distributed File System) y el modelo de computación MapReduce para trabajar con grandes volúmenes de datos de seguimiento ADS-B procedentes de una gran variedad heterogénea de fuentes de datos aéreos. AIRPORTS DL se compone de los siguientes elementos [Martínez Prieto et al., 2017]: Fuentes de datos: abarca un amplio conjunto de servicios de tiempo real y bases de datos de las cuales AIRPORTS DL obtiene los datos en crudo. 18 3.4. El proyecto AIRPORTS (a) Vuelo Madrid Barajas-Palma de Mayorca (b) Vuelo Madrid BarajasAsturias Figura 3.2: Segmento de dos trayectorias reconstruida con la librería leaflet de Ra partir de las señales ADS-B recibidas Figura 3.3: Arquitectura de AIRPORTS DL. Fuente: Martínez Prieto et al. [2017] 19 Capítulo 3. Gestión del Tráfico Aéreo Ingestión: componente encargado de la extracción de los datos procedentes de cada uno de los proveedores anteriores. Almacenamiento: diseñado de forma escalable y para garantizar la persistencia de grandes ficheros de datos a un bajo coste. Transformación: responsable de la manipulación y transformación de los datos. En estos procesos entra en juego el modelo de computación de MapReduce para llevar a cabo el procesamiento simultáneo de varios conjuntos de datos. Exploración: sirve a modo de interfaz de usuario. Permite analizar, así como visualizar los datos contenidos en el sistema. Producción: lleva a cabo la carga de datos previamente tratados a modo de salida para otros componentes o sistemas fuera de AIRPORTS DL. Governanza: permite la monitorización de los procesos de manipulación de datos, preservando suficiente información para poder trazarlos. Sistema ATM: es externo al data lake pero comunica con él. El data lake procesa los datos que necesita el sistema ATM para llevar a cabo las diferentes operaciones ATM que se le requieren. 3.5. El problema que motiva este trabajo Las tecnologías ADS-B, de reciente aparición, van cobrando cada vez más importancia en el entorno de la gestión del tráfico aéreo a nivel mundial gracias a las mejoras que incorpora en comparación a los sistemas de seguimiento existentes previamente. Entre sus ventajas ya mencionadas está la mayor cantidad de información que es posible enviar por parte de una aeronave durante el vuelo mediante paquetes de información que en este trabajo se denotan por señales o mensajes ADS-B, con una frecuencia de hasta 2 por segundo. Además de aumentar la frecuencia de las comunicaciones, la determinación de la posición vía satélite aumenta la precisión con la que la ubicación es determinada. Sin embargo, y tal y como se menciona en la sección anterior, existe un problema de veracidad en los datos de seguimiento ADS-B derivados de su proceso de comunicación. Esta problemática consiste en una ordenación temporal incorrecta de las señales ADS-B recibidas para ser posteriormente procesadas con respecto al orden en que fueron emitidas. Esto se debe a la producción de alteraciones que afectan al orden de llegada de los mensajes a una determinada fuente de datos, que es donde se asigna el timestamp, o instante temporal a los mensajes. La mayor parte de estos problemas se deben a la falta de sincronización entre redes de sensores distribuidos por todo el planeta. No todos los mensajes correspondientes a un mismo vuelo son recibidos por las mismas estaciones receptoras, y así, dos mensajes 20 3.5. El problema que motiva este trabajo emitidos consecutivamente que son captados por diferentes sensores pueden ver intercambiado su orden de recepción, bien debido a la mayor proximidad del avión al segundo receptor en comparación con el primero, bien porque, aun habiéndose recibido antes el primer mensaje, el timestamp que se asigna al primero es posterior debido a que el reloj interno del sensor que lo captó está más atrasado que el del sensor que captó el segundo mensaje, etc. Estas situaciones se dan más acusadamente en el caso de vuelos de larga distancia o los que atraviesan océanos, cuyas señales son captadas por muchos receptores de múltiples organizaciones a lo largo del vuelo, situados en husos horarios diferentes. De la fusión (merge) de los datos de distintas fuentes pueden producirse a su vez descuadres en el procesamiento. En el caso del data lake AIRPORTS DL, que se describe al final de la sección anterior, son varios los datasets que nutren de datos en crudo al sistema. En la Figura 3.4 se ilustra el alcance que reportan las fuentes de datos de seguimiento más importantes que aportan datos al data lake. (a) Frambuesa (b) ADSBHub (c) OpenSky Figura 3.4: Alcance de las fuentes de datos más importantes que nutren a AIRPORTS DL. Fuente: Martínez Prieto et al. [2017] Nótese que muchos mensajes ADS-B son recibidos por sensores de varias de estas fuentes de datos (como se observa en la Figura 3.5), lo que obliga a llevar a cabo ese proceso de fusión de datos tras ser recibidos por el sistema, con el fin de eliminar duplicados y corregir los datos de timestamp, que presumiblemente serán diferentes en cada mensaje duplicado debido a la no sincronización que se indicó previamente. A partir de esta problemática expuesta, este trabajo plantea una definición formal para el problema de reordenar los mensajes ADS-B asociados a una misma trayectoria, en el Problema 1. Su enunciado, requiere la especificación del concepto de permutación, presente en la Definición 3.1. Definición 3.1 Una permutación πsobre un conjunto N={1,2, ..., n}con n∈Nes una función biyectiva que va de Nen si mismo. Se dice además que πes circular si para todo E(Nno vacío, existe e∈Ede manera que π(e)6∈ E. 21 Capítulo 3. Gestión del Tráfico Aéreo Figura 3.5: Solapamiento de los alcances de las fuentes Frambuesa,OpenSky yADSBHub. Fuente: Martínez Prieto et al. [2017] Problema 1: Problema de reordenación de las trayectorias Se supone un avión que efectúa una trayectoria desde un aeródromo Ahasta otro aeródromo B, enviando nmensajes ADS-B en el transcurso de su realización que son recibidos por diversos receptores y etiquetados con timestamps t1< t2< ... < tn, siendo tiel timestamp que se asocia al mensaje ipara todo 1≤i≤n. Problema: encontrar una permutación circular πsobre {1, ..., n}tal que para cada par de mensajes 1≤i<j≤nse tiene que el mensaje π(i)fue enviado antes que el mensaje π(j). Nótese que, por lo general, cualquier desorden generado (i.e. dos mensajes i, j tales que aunque ise envió antes que jsus respectivos timestamp al recibirse verifican que tj< ti) produce una trayectoria más larga que la realmente recorrida por la aeronave. Es por ello que en la mayoría de los casos (salvo excepciones relativas a maniobras de los pilotos en los aeropuertos esperando permisos desde el control), la solución a este problema coincide con la reordenación de los mensajes que se corresponda con la trayectoria más corta, por lo que parece razonable considerar esta suposición, que nos brinda además la posibilidad de modelar el problema a través del renombrado problema del viajante, sobre el que profundizaremos en el Capítulo 4. 22 3.5. El problema que motiva este trabajo (a) Ruta sin ordenar: 511,99 km (b) Ruta ordenada: 452,95 km Figura 3.6: Segmento de una trayectoria Madrid Barajas-Asturias sobre la que se ha aplicado una reordenación con el algoritmo 2-Opt. Creado con Leaflet La Figura 3.6 (a) ilustra la reconstrucción de un segmento de trayectoria formado a partir de mensajes ADS-B mal ordenados temporalmente. Por su parte, en la Figura 3.6 (b) se observa el mismo segmento tras haberse aplicado una reordenación sobre el conjunto de mensajes ADS-B asociado al vuelo basada en este modelo teórico. Nótese además la enorme reducción que se obtiene en la longitud de la trayectoria realizada. 23 Capítulo 3. Gestión del Tráfico Aéreo 24 Capítulo 4 El Problema del Viajante En el presente capítulo se recogen los fundamentos del ya mencionado problema del viajante. Este problema de optimización combinatoria pertenece a la clase de los problemas NP-difíciles (o NP-hard), que significa que no existe ningún algoritmo en la actualidad que garantice encontrar la solución óptima al mismo de forma computacionalmente razonable (en concreto, con un coste computacional de orden polinomial). Por tanto, será necesaria una máquina con gran capacidad de cómputo para resolver supuestos del problema de tamaño considerable. En la actualidad, son varias las líneas de investigación establecidas a fin de desarrollar algoritmos con las propiedades antes mencionadas, o al menos, mejorar las técnicas ya existentes, algunas de las cuales se vienen utilizando desde hace ya varias décadas. Este capítulo, así como el propio trabajo, se centra, con motivo del Objetivo [OB-3], en una de las corrientes más destacadas en términos de efectividad de los métodos que abarca a la hora de abordar el problema del viajante: las heurísticas de mejora local. Estos algoritmos parten de una ruta que, como veremos a continuación, no es más que un camino que atraviesa una, y sólo una vez, cada uno de los nodos (también llamados ciudades) del grafo de la instancia partiendo y terminando sobre uno de ellos. Esta ruta inicial trata de mejorarse cada iteración realizando sobre ella continuas modificaciones basadas en una serie de técnicas específicas que permiten la obtención de nuevas rutas más cortas. Cada algoritmo implementa sus propias técnicas que lo diferencian del resto. La estructura del capítulo es como sigue. En primer lugar, se define, en la Sección 4.1, el problema del viajante en los términos en que será tratado a lo largo del trabajo. A continuación, en la Sección 4.2, se presentan los detalles históricos más relevantes asociados al TSP. El problema del viajante presenta en la actualidad una gran cantidad de aplicaciones prácticas, algunas de las cuales se describen en la Sección 4.3. El capítulo cierra presentando los algoritmos de resolución del problema más destacados (ver Sección 4.4), centrando el foco sobre las heurísticas de mejora local, cuyo funcionamiento se describe en la Sección 4.5. 25 Capítulo 4. El Problema del Viajante minutos de tiempo de CPU. Más recientemente, destacan los supuestos que el grupo de investigación formado por David Applegate, Robert Bixby, Vasek Chvátal y William Cook logró resolver a través de un algoritmo de creación propia que denominaron Concorde. Mediante este método han obtenido la solución de instancias de tamaño no resuelto hasta entonces, siendo la más reciente una con 85.900 ciudades, en el año 2006 [Cook, 2012]. 4.3. Aplicaciones generales del TSP El TSP es un problema de interés científico debido esencialmente a la complejidad computacional que requiere su resolución. Pero además, es ampliamente estudiado por sus múltiples utilidades prácticas. En realidad, muchos supuestos pueden ser modelados a través del TSP (i.e. planteados como instancias del problema de cuya solución se deriva la del supuesto modelado). Así, existen muchas aplicaciones prácticas del problema del viajante, una de las cuales es la reordenación de los mensajes ADS-B asociados a una trayectoria. Las aplicaciones más claras del TSP, tal y como fue concebido, están ligadas al enrutamiento de vehículos, donde se dispone de un conjunto de ubicaciones que deben ser visitadas por un determinado vehículo recorriendo la menor distancia posible. Pensemos por ejemplo en una compañía con servicio de venta por Internet que debe entregar una serie de paquetes en un conjunto de direcciones prefijadas a través de uno de sus vehículos. Existen otras aplicaciones del problema del viajante entre las que se encuentran las siguientes [Laporte, 1992]: 1. El problema del cableado de ordenador. Algunos sistemas informáticos pueden describirse en términos de módulos que se unen entre sí por medio de cables. Se desea unir todos los módulos (ciudades) por medio de cables (aristas) de mínima longitud y de tal manera que cada módulo quede unido a otros dos. 2. El problema del papel de pared. Se quieren cortar nhojas de un rollo de papel tapiz en el cual se repite un patrón de longitud 1. Para cada hoja i, se denota aiybi como los puntos del patrón donde comienza y finaliza la hoja. Entonces, si se corta la hoja jjusto después que la hoja ise obtiene un desperdicio cij dado por cij =     aj−bisi bi≤aj, 1 + aj−bisi bi> aj. Se pretende por tanto obtener las nhojas del rollo con el menor desperdicio posible. Para definir este problema en términos del TSP se consideran las hojas como ciudades y el gasto de papel de cortar la hoja jjusto después que la hoja icomo cij 32 4.4. Algoritmos de resolución (longitud del camino que une la ciudad icon la ciudad j). A mayores, sería necesario introducir una hoja artificial n+ 1 a modo de unión entre la primera y la última hoja cortadas tal que cij = 0 si i=n+ 1 ój=n+ 1. De esta forma se tendrá que acabar en la ciudad de partida. 3. El problema de la secuenciación de trabajos. Se supone que una máquina debe realizar ntrabajos de forma secuencial y que cij es el tiempo que la máquina invertiría en pasar del trabajo ial trabajo j. Entonces de nuevo, para minimizar el tiempo invertido en cambiar de un trabajo a otro (o change-over time) es posible formular el problema en términos del TSP introduciendo un trabajo artificial de coste 0, de forma análoga al problema anterior. 4. En cristalografía, algunos experimentos consisten en tomar un gran número de medidas sobre cristales a través de un detector. Cada muestra debe montarse en un aparato que debe ser posicionado para poder hacer la medición, invirtiendo tiempo en cambiar la posición del detector desde la que disponía para realizar la última medición hasta la requerida para realizar la actual. Como en los anteriores, añadiendo una ciudad artificial de coste 0 que una la primera muestra con la última obtenemos una instancia del TSP donde las ciudades son las muestras a examinar y el coste de las aristas que las unen es el tiempo invertido por el detector para cambiar su posición. 4.4. Algoritmos de resolución Tal y como se adelanta en la Sección 4.2, los algoritmos que tratan de resolver el TSP se clasifican, según garanticen o no encontrar la solución óptima del problema al ser ejecutados, en algoritmos exactos yalgoritmos de aproximación. En esta sección se mencionan los más importantes de cada uno de estos dos tipos. 4.4.1. Los algoritmos exactos Los algoritmos exactos son aquellos que buscan obtener la solución óptima del problema independientemente del coste computacional requerido. Estos algoritmos aseguran la obtención de la solución óptima, lo que implica un alto coste computacional ligado a las propiedades del TSP. Es por ello que su uso es preferible sobre instancias pequeñas, cuando el tiempo de ejecución de estos algoritmos aun no es desmedido. Dentro de estos algoritmos encontramos el rudimentario ataque por fuerza bruta que prueba todas las permutaciones circulares posibles sobre los nodos del grafo, quedándose con aquella que minimiza la expresión (4.1). La complejidad computacional de este algoritmo es por tanto O(n!) siendo nel número de ciudades de la instancia, asumible sobre 33 Capítulo 4. El Problema del Viajante instancias pequeñas, pero impensable sobre otras más grandes (con n= 20 este número es ya del orden de 2·1018). Una de las familias de algoritmos exactos más exitosas a lo largo de la historia del problema es la de los métodos branch and bound, o de ramificación y acotación, que consisten en dividir la instancia en otras más pequeñas, calculando cotas de la longitud de la ruta más corta de cada parte, y que se obtienen de “relajar”las hipótesis del problema. Tras obtener una solución para cada subinstancia, el algoritmo obtiene la ruta de la instancia principal, que resulta ser una solución óptima. Los algoritmos branch and bound se basan en programación lineal entera, que parte de una formulación del problema a resolver. Para el TSP, Dantzig, Fulkerson y Johnson desarrollaron en 1954 una de las primeras [Lawler et al., 1992], y que consiste en que dada una instancia I= (G, C)donde Ges un grafo de nvértices y C= (cij)1≤i,j≤nes la matriz de costes, se quiere minimizar la expresión X i6=j cijxij con xij ∈Z,para todo i, j en 1≤i, j ≤n(4.3) sujeto a n X j=1 xij = 1, i = 1, ..., n;(4.4) n X i=1 xij = 1, j = 1, ..., n;(4.5) X i,j∈S xij ≤ |S| − 1; (4.6) S⊂V, 2≤ |S| ≤ n−2; (4.7) xij ∈ {0,1}, i, j = 1, . . . , n, i 6=j. (4.8) Es necesario también citar el algoritmo de Held-Karp, que aparece en 1962 de la mano de Michael Held y Richard Karp, y que se basa en programación dinámica [Cook, 2012]. Capaz de encontrar la solución óptima de cualquier instancia del TSP, este algoritmo fija una ciudad como punto de partida, a partir de la cual va construyendo caminos formados por cada vez más vértices y de los cuales va almacenando su longitud. De esta forma, dado un vértice de destino, y un subconjunto de vértices intermedios, el algoritmo halla cual es la forma más corta de recorrer todos los nodos intermedios partiendo desde el primero fijado al comienzo hasta el último señalado. El método itera hasta abarcar todos los vértices. A pesar de garantizar la solución óptima, el coste computacional de este algoritmo es O(n22n)lo que lo inhabilita para ser utilizado sobre instancias grandes. En la actualidad, Concorde es uno de los algoritmos más destacados. Implementado por David Applegate, Robert Bixby, Vasek Chavátal y William Cook, consiste en uno de los desarrollos más recientes del método de ramificación y acotación sobre árboles de 34 4.4. Algoritmos de resolución búsqueda. Este algoritmo, cuyo código está disponible en la red, fue utilizado para obtener la solución óptima a instancias del problema de tamaño record hasta la fecha. Entre ellas se encuentran supuestos de: 3.038 ciudades en 1992, 13.509 en 1998, 24.978 en 2004 y 85.900 en 2006 Cook [2012]. 4.4.2. Los algoritmos de aproximación Por otro lado se encuentran los algoritmos de aproximación, que son aquellos que dan prioridad a un tiempo de ejecución razonable frente a encontrar la solución óptima. Mientras que ejecutar un algoritmo exacto para el problema del viajante puede requerir un coste computacional inasumible para instancias de gran tamaño, un algoritmo de aproximación, aunque no encuentre la solución óptima, es mucho menos complejo computacionalmente, por lo que es posible ejecutarlos sobre instancias de mayor tamaño. Los más sencillos de estos métodos son las heurísticas constructivas, que engloban una serie de métodos cuya mecánica consiste en construir una ruta partiendo de un nodo al que van uniendo sucesivamente ciudades en cada iteración del algoritmo. Algunos de los más destacados son los siguientes [Gutin y Punnen, 2007]: Método de vecinos más próximos (o nearest neighbor): es el método constructivo más simple. Consiste en tomar el conjunto Vde vértices del grafo de una instancia y elegir un nodo v1∈Varbitrario como punto de partida. Para cada iteración i= 2,3, . . . , n, siendo n=|V|, se elige un nuevo nodo vi∈V\{v1, v2, . . . , vi−1} tal que ci−1,i sea el mínimo posible (siendo ci−1,i el coste de la arista (vi−1, vi)), es decir, a cada paso se añade el nodo más cercano, de entre los no escogidos aun, al último añadido. Método de vecinos más próximos iterativo (o repetitive nearest neighbour): variante algo más compleja del método de vecinos más próximos que consiste en comenzar este método desde cada vértice del grafo, eligiendo como ruta la obtenida de menor longitud. Su complejidad computacional por lo general es O(n2). Greedy (codicioso): se comienza ordenando de menor a mayor coste todas las aristas. A continuación, se contruye una ruta, haciendo uso de esta ordenación, comenzando con la arista más corta y añadiendo una nueva arista (v, v0)siempre y cuando vov0no son alcanzados por dos aristas de la ruta en construcción y además la nueva arista no completa un ciclo con menos de nvértices siendo nel número de vértices del grafo de la instancia. Lleva asociado un orden de complejidad O(n2log(n)). Inserción más barata (o cheapest insertion): consiste en insertar, a cada iteración, un nuevo vértice entre dos nodos de la ruta en construcción de la forma que menos incremente su longitud, esto es, si Tm= (v1, v2, . . . , vm−1, vm)es el camino en construcción con m > 1y(vi, vi+1)∈E(Tm)es la arista en el camino actual que minimiza d(vi, vk) + d(vk, vi+1)−d(vi, vi+1), donde des la función distancia (coste) 35 Capítulo 4. El Problema del Viajante entre cada par de vértices del grafo, entonces se obtiene un nuevo camino Tm+1 a partir de Tm, eliminando la arista (vi, vi+1)y añadiendo (vi, vk)y(vk, vi+1)en el lugar que ésta ocupaba, esto es, Tm+1 = (v1, v2, . . . , vi, vk, vi+1, . . . , vm). Inserción más cercana (o nearest insertion): consiste en iniciar el algoritmo con una ciudad y su vecino más próximo. A cada iteración se añade la ciudad no perteneciente a la ruta en construcción cuya distancia con respecto a cualquiera de las ciudades de la ruta en construcción sea mínima. Inserción más lejana (o farthest insertion): como en los anteriores, consiste en comenzar con un nodo y su vecino más cercano. Se itera añadiendo a la ruta en construcción Pel nodo vtal que maximice el valor de m´ın{d(v, v0) : v0∈V(P)},(4.9) donde des la función distancia (coste) entre cada par de vértices del grafo. Inserción arbitraria (o arbitrary insertion): difiere del anterior en que en cada iteración se añade a la ruta un nodo aleatorio no perteneciente a la ruta en construcción. Una de las familias de algoritmos de aproximación más importantes son los búsqueda local, también llamados heurísticas de mejora local, cuyo análisis es objeto de este Trabajo Fin de Grado y que se profundizan en la Sección 4.5). Estos métodos parten de una ruta inicial (solución factible) que van modificando a cada paso para obtener otras rutas más cortas. Se caracterizan por la técnica de modificación que utilicen, que restringe la cantidad de rutas que es posible obtener desde una dada en una sola iteración. Los más conocidos son los algoritmos de la familia k-Opt, que en cada iteración buscan una nueva solución reemplazando karistas de la ruta actual por otras knuevas mediante un procedimiento de modificación que recibe el nombre de k-change (ver Definición 4.8). Los métodos más conocidos de esta familia son el 2-Opt y el 3-Opt. Por otro lado, encontramos una implementación más sofisticada de los algoritmos k-Opt en el algoritmo de Lin-Kernighan, que a diferencia de los anteriores, varía el valor de la ka lo largo de su ejecución con el fin de adaptarse al tipo de modificaciones que resultarán más efectivas a cada instante. Por otro lado, encontramos el algoritmo Or-Opt que basa su procedimiento en la escisión de cadenas de vértices de la ruta actual para unirlas en otra posición. Otros algoritmos de aproximación con aplicación al TSP son los siguientes: Simulated annealing (enfriamiento simulado): se introduce a través de uno de los trabajos de Kirkpatrick, Gelatt y Vecchi en 1983 como método de resolución del TSP con unos resultados bastante prometedores. Mientras que un algoritmo típico de búsqueda local sigue la estrategia hill-climbing, consistente en realizar solo movimientos hacia soluciones “vecinas”(alcanzables en una iteración a través de una técnica de modificación fija) mejores que la actual, el simulated annealing realiza saltos arbitrarios sobre el espacio de estados con una cierta frecuencia a fin de no 36 4.5. Heurísticas de mejora local quedar atrapado en máximos locales. La frecuencia y la distancia de estos saltos va disminuyendo con el paso de las iteraciones (se produce el enfriamiento). Los algoritmos de redes neuronales: basados en el funcionamiento del cerebro humano. Sus componentes básicos son unidades de cómputo simples que reciben el nombre de neuronas artificiales que se comunican entre si a través de una red de conexiones que simulan el procesamiento en paralelo que ocurre en el cerebro humano. Este modelo fue aplicado al TSP por Hopfield y Tank en 1985. Los algoritmos genéticos: trabajan con un conjunto de soluciones del problema. En cada iteración, se eligen las mejores soluciones (selección), las cuales se combinan para obtener otras nuevas (cruce), finalmente se alteran (mutación) y se repite el proceso tomando estas nuevas soluciones como entrada de la siguiente iteración. 4.5. Heurísticas de mejora local En línea con lo expuesto hasta ahora, existe una gran colección de algoritmos aplicables a la resolución del problema del viajante. No obstante, este trabajo se enfoca en un subconjunto de ellos, denominados heurísticas de mejora local. Estos algoritmos destacan por obtener por lo general buenas soluciones requiriendo su ejecución un coste computacional generalmente moderado. En esta sección se ilustran los más importantes. Los algoritmos de búsqueda local oheurísticas de mejora local son considerados en Korte y Vygen [2006] como la técnica más adecuada para obtener buenas soluciones a gran parte de los supuestos del problema del viajante. La mecánica de todas ellas consiste en iniciar su ejecución con una ruta de partida (un ciclo hamiltoniano, también llamado ruta, sobre el grafo de la instancia), obtenida a través de cualquier otra técnica (lo aconsejable es que sea un método constructivo, por su sencillez), e intentar “mejorarla”(encontrar una ruta más corta) mediante la realización de pequeñas modificaciones sobre ella a cada iteración. Es en la forma de realizar esas modificaciones (técnicas de las que hace uso) donde una heurística difiere sobre las demás. Distinguimos dos clases de estos algoritmos en función de los mecanismos de mejora utilizados, de las cuales nos centraremos en la primera de ellas: Algoritmos de intercambio de aristas (EE: edge exchanges): el procedimiento de modificación realizado en estos algoritmos consiste en eliminar a cada iteración un conjunto de aristas de la ruta actual reemplazándolas por otras de manera que formen una nueva ruta. Los métodos de este tipo más conocidos son los de la familia k-Opt o el algoritmo de Lin-Kernighan. Algoritmos de intercambio de cadenas (CE: chain exchanges): en cada iteración, se considera una cadena de vértices de la ruta que son desligados del 37 Capítulo 4. El Problema del Viajante resto. A continuación se vuelven a unir a la ruta en otra posición diferente mediante la eliminación de una arista. Un ejemplo de estos algoritmos es el Or-Opt. 4.5.1. Los algoritmos de la familia k-Opt Dentro de las heurísticas de mejora local, los algoritmos de implementación más sencilla son los de la familia k-Opt. Estos métodos se caracterizan por construir, a cada iteración, una nueva ruta mediante un procedimiento que recibe el nombre de k-change. Se compara la nueva ruta con la ruta actual, y en caso de ser la nueva ruta más corta, sustituyen la ruta actual por la nueva. El procedimiento de modificación k-change, del que hacen uso estos algoritmos, consiste en suprimir karistas de la ruta actual reemplazándolas por otras kdando como resultado una nueva ruta. Esta nueva ruta será considerada solo si es más corta que la anterior. El valor de kes por tanto fijo para cada iteración del algoritmo siendo éste dependiente de la heurística de la familia k-Opt utilizada. Así, para el 2-Opt,k= 2; para el 3-Opt,k= 3; y así sucesivamente. Más formalmente, un k-change viene definido de la forma siguiente: Definición 4.8 Dada una instancia I= (G, C)donde G= (V, E)es un grafo de n vértices, y sea Runa ruta sobre G. Una modificación de Rque da como resultado otra ruta R0sobre Gse dice que es de tipo k-change si a partir de R, dado por R= (v1 1, v1 2, . . . , v1 n1, v2 1, v2 2, . . . , v2 n2, . . . , vk 1, vk 2, . . . , vk nk, v1 1), se obtiene la ruta R0dada por R0= (v1 1, v1 2, . . . , v1 n1, v2 n2, v2 n2−1, . . . , v2 1, v3 n3...,vk−1 1, vk nk, vk nk−1, . . . , vk 1, v1 1). Los algoritmos de la forma k-Opt son muy utilizados en la práctica, al obtener de forma general buenas soluciones a instancias del problema del viajante sin requerir para ello un elevado coste computacional. Sin embargo, el estudio que incluye Englert et al. [2007] permite concluir la existencia de instancias del problema del viajante para las que el algoritmo 2-Opt puede alcanzar una complejidad computacional de orden exponencial, y de la misma forma, en Chandra et al. [1999] se generaliza esta tesis para cualquier algoritmo de la familia k-Opt. En Korte y Vygen [2006] se presentan los algoritmos k-Opt en pseudo-código tal y como se muestra en el Algoritmo 1. 38 4.5. Heurísticas de mejora local Algoritmo 1 Algoritmo k-Opt Entrada: Una instancia del TSP I= (G, C), con G= (V, E). Salida: Una ruta R 1: Sea Runa ruta 2: Sea Sla familia de subconjuntos de E(R)con kelementos 3: para S∈ S y toda ruta R0con E(R0)⊇E(R)\Shacer 4: si P(vi,vj)∈E(R0)ci,j <P(vi,vj)∈E(R)ci,j entonces 5: Asignar R:= R0 6: Sea Sla familia de subconjuntos de E(R)con kelementos 7: fin si 8: fin para 9: devolver R A pesar de hacer uso de una mecánica similar, cada uno de los algoritmos de la familia k-Opt se comportan de distinta forma y por tanto se predispone que alcanzarán soluciones de características diferentes requiriendo para ello distintos órdenes de complejidad en función del valor de kelegido y, por supuesto, del número de vértices de la instancia y la localización de los mismos, esto es, los valores de la matriz de costes asociada. El algoritmo 2-Opt, a cada iteración prueba un 2-change sobre la ruta actual. Un ejemplo de un 2-change se ilustra en la Figura 4.3, donde podemos apreciar que para obtener la nueva ruta simplemente se han suprimido dos aristas (v1, v3)y(v2, v4), que han sido reemplazadas por (v1, v2)y(v3, v4). Las modificaciones de tipo 2-change son las de menor alcance (que afecta a menos aristas de la ruta), pero también las más finas, en cuanto a que permiten mejorar rutas muy próximas a una solución óptima. Esto implica que el algoritmo funcionará peor cuando la ruta actual diste mucho de la solución optima (en cuyo caso es preferible un algoritmo k-Opt con un valor de kmás elevado), pero va mejorando a medida que se aproxima a una solución óptima pues es entonces cuando se requieren modificaciones más pequeñas, y que por tanto afecten a menos aristas. Figura 4.3: Ilustración de un 2-change En la Figura 4.4 se ilustra una modificación de tipo 3-change. En la línea de lo expuesto en el párrafo anterior, un 3-change realiza modificaciones de mayor alcance, pero a su vez menos refinadas que las que puede obtener un 2-change, lo que predispone a este último como menos preferible en caso de disponer de una ruta actual más próxima a la solución óptima en términos de longitud. 39 Capítulo 4. El Problema del Viajante Figura 4.4: Ilustración de un 3-change (a) Ruta actual (b) Ruta mejorada Figura 4.5: Ilustración de un 2-change durante la ejecución del 2-Opt sobre una instancia con 30 ciudades. En negro y amarillo, aristas y nodos afectados respectivamente. Creado con Leaflet Las Figuras 4.5 y 4.6 ilustran una mejora realizada por los algoritmos 2-Opt y3-Opt respectivamente sobre un mismo supuesto del TSP con 30 ciudades situadas en Europa. En conclusión, los algoritmos de la familia k-opt muestran un comportamiento estático, en el sentido de que admiten un solo tipo de modificación que involucra a un número fijo de aristas de la ruta actual, que son eliminadas y reemplazadas por otras nuevas en cada iteración. Sin embargo, como se ha visto, no en todas las situaciones se requieren modificaciones que involucren al mismo número de aristas, sino que en ocasiones será preferible la realización de cambios de mayor alcance mientras que a medida que la longitud de las rutas encontradas va disminuyendo se prefieren cambios más finos. Persiguiendo esto, el algoritmo de Lin-Kernighan propone que estas modificaciones involucren a un número variable de aristas a cada iteración, de manera que sea el propio algoritmo el que se adapte de forma dinámica al alcance de la modificación requerido. 40 4.5. Heurísticas de mejora local (a) Ruta actual (b) Ruta mejorada Figura 4.6: Ilustración de un 3-change durante la ejecución del 3-Opt sobre una instancia con 30 ciudades. En negro y amarillo, aristas y nodos afectados respectivamente. Creado con Leaflet 4.5.2. El algoritmo de Lin-Kernighan Para poder hablar del funcionamiento de este algoritmo es necesario introducir los resultados teóricos que hay debajo del mismo. Nos guiaremos del enfoque dado en Korte y Vygen [2006], que centra su exposición en el concepto de camino alterno. Un camino alterno sobre un grafo puede entenderse como un camino tal que, dada una ruta, el camino alterna aristas de la ruta con aristas no pertenecientes a ésta. Más formalmente, un camino alterno puede definirse de la forma siguiente: Definición 4.9 Sea I= (G, C)una instancia del TSP, con C= (cij )n i,j=1 y sea Runa ruta sobre G. Un camino alterno P= (v1, v2, . . . , v2m+1)sobre Ges aquel que verifica (vi, vi+1)6= (vj, vj+1)para todo 1≤i < j < 2m+ 1, y (vi, vi+1)∈E(R)si, y sólo si ies impar. La ganancia de P viene dada por g(P) = m−1 X i=0 c2i+1,2i+2 −c2i+2,2i+3 Se dice que Pes adecuado si g(v1, v2, . . . , v2i+1)>0para todo i∈ {1, . . . , m}. Notación 4.10 Sean AyBdos conjuntos, se denota por AMBa la diferencia simétrica de los conjuntos AyB. Esto es, AMB= (A\B)∪(B\A). 41 Capítulo 4. El Problema del Viajante (a) Ruta actual (b) Ruta mejorada Figura 4.10: Ilustración de una mejora con longitud de cadena 3 durante la ejecución del algoritmo OrOpt (ver Algoritmo 3) sobre una instancia con 30 ciudades. En negro y naranja la cadena de vértices, y en blanco la arista que se sustituye por la cadena resultante e intentar aproximarla a la solución óptima. Del análisis de ambos códigos se obtiene un coste computacional asociado de orden O(n2), siendo nel número de nodos de la instancia. Entre las ventajas del Or-Opt está su gran flexibilidad, capaz de resolver rápidamente instancias cuya ruta de partida difiere mucho de la solución óptima, así como su reducida complejidad computacional siendo recomendable su aplicación sobre instancias grandes. Como principal desventaja se encuentra la necesaria elección correcta de las longitudes de cadena, pues en caso contrario el algoritmo puede ver altamente reducidas sus prestaciones. La Figura 4.10 muestra una mejora efectuada por el algoritmo Or-Opt. En ella se ilustra en negro (aristas) y naranja (vértices) la cadena de vértices que se escinde para colocarla en la posición en la que situaba la arista señalada en color blanco. Para hacer esto posible desaparecen de la ruta las dos aristas que unían la cadena con los vértices inmediatamente anterior y posterior. Para concluir, la Figura 4.12 ilustra las rutas finales que obtienen los cuatro algoritmos expuestos a lo largo de esta sección al ser ejecutados sobre el mismo supuesto con 30 ciudades y comenzando en la misma ruta de partida (ilustrada en la Figura 4.11). Obsérvese que, en línea con lo ya mencionado, la ruta final del algoritmo 3-Opt se entrecruza consigo misma en la zona de Bélgica, indicando su elevada longitud. Sin embargo el algoritmo no es capaz de mejorarla ya que para romper el entrecruzamiento es necesario eliminar las dos aristas que se cortan entre sí, manteniendo las demás. Esto no es posible con el 3-Opt ya que siempre busca rutas que se obtengan a partir de la eliminación de exactamente 3 aristas de la ruta actual. Esto vemos que no ocurre con el 2-Opt, pues sus modificaciones (denominadas 2-changes) se conciben precisamente para eliminar los entrecruzamientos de la ruta. 48 4.5. Heurísticas de mejora local Figura 4.11: Ruta de partida para la ejecución de los algoritmos de búsqueda local expuestos en esta sección, cuyos resultados finales se ilustran en la Figura 4.12 (a) 2-Opt (b) 3-Opt (c) Lin-Kernighan, p1= 5,p2= 2 (d) Or-Opt, longitudes = (12,6,3,2,2,1,1,1) Figura 4.12: Rutas finales obtenidas de la ejecución de los cuatro algoritmos ilustrados sobre una misma instancia con 30 ciudades y con la misma ruta de partida, que muestra la Figura 4.11 49 Capítulo 4. El Problema del Viajante 50 Capítulo 5 Estudio preliminar de los algoritmos Hasta ahora se han recogido los fundamentos del problema del viajante o Traveling Salesman Problem (TSP), así como los algoritmos más destacados que abordan el problema, a modo de estado del arte del trabajo. Ahora, es objeto del presente capítulo focalizar en el comportamiento de los algoritmos anteriores al ser aplicados a la reordenación de trayectorias aéreas, llevando a cabo un estudio comparativo que permita obtener unas primeras conclusiones sobre su adecuació en este contexto. Por tanto, para esta fase se fijan los siguientes objetivos: Aplicación de los algoritmos a la reordenación de colecciones de trayectorias concretas de diferentes características. Establecimiento de una comparativa entre los resultados obtenidos por los diferentes algoritmos, tras ser ejecutados sobre las mismas trayectorias en las mismas condiciones (mismo ordenador, misma carga del procesador, etc). Desarrollo de una aplicación con interfaz gráfica que permita visualizar la reconstrucción de las rutas sobre un mapa terrestre, así como otras gráficas que aporten al estudio información complementaria. Analizar las formas más adecuadas de llevar a cabo la corrección de los timestamps de los mensajes ADS-B recibidos, de manera que el nuevo orden de éstos sea coherente con el orden real en que fueron enviados por la aeronave. Primeramente, se fijó el lenguaje de programación que podría resultar más adecuado para llevar a cabo el estudio preliminar fijado. Para este caso, se estableció que Rera la mejor opción por su amplia colección de librerías que incluyen la implementación de múltiples algoritmos para resolver distintos problemas complejos, incluido el TSP. 51 Capítulo 5. Estudio preliminar de los algoritmos 5.1. Introducción a R El lenguaje Res un conjunto integrado de programas orientados a la manipulación de datos, cálculo y gráficos. En González y González [2000] se identifican cinco características principales de este lenguaje: Almacenamiento y manipulación efectiva de datos Operadores para cálculo sobre variables indexadas (Array), en particular matrices Una amplia, coherente e integrada colección de herramientas para análisis de datos Posibilidades gráficas para análisis de datos Un lenguaje de programación simple y efectivo que incluye condicionales, ciclos, funciones recursivas y posibilidad de entradas y salidas. Surge a modo de una nueva implementación del lenguaje S, desarrollado en AT&T por Rick Becker, John Chambers y Allan Wilks. Aunque Rno es un lenguaje con aplicación exclusiva al campo de la estadística, es ampliamente utilizado en esta materia. Algunas de estas funcionalidades se encuentran incluidas en el entorno base de Ry otras se acompañan en forma de bibliotecas (packages). Existen ocho bibliotecas incluidas en R, y que reciben el nombre de bibliotecas estándar. Otras muchas, se encuentran disponibles en CRAN a través de Internet. El lenguaje Res orientado a objetos, interpretado y no compilado [Ahumada, 2002], por lo que los comandos escritos se ejecutan directamente sin necesidad de la construcción de ejecutables que los incluyan. Destaca por la simplicidad de su sintaxis, que permite la ejecución de funciones complejas como regresiones lineales a través de comandos sencillos. El amplio conjunto de procedimientos que pueden llevarse a cabo con Rincluyen cálculos sencillos, operaciones vectoriales, generación de sucesiones, gestión de distintas clases de objetos, trabajo con matrices, listas y dataframes, lectura y escritura de archivos con diferentes formatos, así como una gran variedad de cálculos estadísticos. 5.2. Selección de librerías Tras la elección del lenguaje Rcomo medio para desarrollar la aplicación objeto de esta fase del trabajo, se realiza una búsqueda de librerías que incluyan implementaciones de las heurísticas de mejora local más destacadas, así como otros algoritmos aplicables a la resolución del problema del viajante. Así, se descarta la posibilidad de implementar los algoritmos desde cero en esta fase, pues supone un elevado esfuerzo y hay muchas posibilidades de que el algoritmo implementado no satisfaga las expectativas. En esta búsqueda exhaustiva de librerías se identifican las siguientes: 52 5.3. Análisis TSP: la librería TSP, que incluye implementaciones de un gran conjunto de algoritmos destinada a la resolución de instancias del problema del viajante. Estos algoritmos son: 2-Opt,vecinos más próximos,vecinos más próximos repetitivo,inserción más cercana,inserción más barata,inserción más lejana,inserción arbitraria,LinKernighan yConcorde. La descripción de todos estos algoritmos se incluye en la Sección 4.4. stats: la librería stats, de propósito más general, es un optimizador orientado a encontrar el valor mínimo de una función objetivo de un problema, recorriendo el espacio de estados del mismo. Para ello, esta librería recoge una serie de algoritmos de búsqueda informada, entre los que encontramos el Simulated Annealing. A continuación, se requiere encontrar un segundo conjunto de librerías que permitan la elaboración de la interfaz de usuario. Shiny: sostiene el desarrollo de aplicaciones sobre R, proporcionando una API que permite el desarrollo del código tanto del lado cliente como del lado servidor. ShinyDashboards: contiene un conjunto de métodos y funciones que permiten la creación de dashboards y cuadros de mando. Leaflet: permite el renderizado de mapas, así como una serie de funciones para representar distintos elementos sobre éste como puntos, líneas, marcadores, etc. Estos elementos nos proporcionan las herramientas necesarias para poder representar los distintos mensajes ADS-B asociados a una determinada trayectoria, así como unirlos a través de una línea para representar el orden de éstos según su timestamp. Plotly: librería para la elaboración de gráficos estadísticos de diferente tipología. 5.3. Análisis A continuación se incluye el análisis asociado al desarrollo de la aplicación. Una vez queda patente la viabilidad de la aplicación, se identifican las características básicas de la aplicación. Estas son las siguientes: CAR-1 Exploración de los datos: contempla la creación de un dashboard sobre el que puedan visualizarse los datos de los vuelos sobre diferentes formatos (gráficas, mapas, tablas, etc), así como los resultados de ejecutar reordenaciones. CAR-1.1 Ejecutar una reordenación: el sistema debe permitir al usuario ejecutar reordenaciones sobre el vuelo, de entre los almacenados en el sistema, y con el algoritmo, de entre los listados en la Sección 5.2, que elija el usuario. CAR-1.2 Interacción dashboard: engloba aquellas funcionalidades que permiten al usuario manipular el dashboard. 53 Capítulo 5. Estudio preliminar de los algoritmos CAR-1.2.1 Seleccionar vuelo: el sistema debe permitir al usuario seleccionar el vuelo, de entre los almacenados en el sistema, que desea visualizar en el dashboard. CAR-1.2.2 Acotar rango de puntos visualizados: el sistema permitirá al usuario trabajar con un subconjunto de los datos asociados a un vuelo. CAR-1.2.3 Filtrar fuentes de datos: el usuario permitirá al usuario representar y eliminar del dashboard los datos pertenecientes a las fuentes de datos que el usuario elija, así como visualizar la fuente de la que procede cada dato representado. CAR-1.2.4 Visualizar datos mensaje ADS-B: el sistema mostrará al usuario todos los datos que almacene de cada mensaje ADS-B en el sistema, así como filtrar los mensajes de acuerdo a un patrón introducido por el usuario. CAR-2 Pruebas: contempla la realización de baterías de pruebas en las que se ejecuten varias reordenaciones sobre varios vuelos y usando diferentes algoritmos. CAR-2.1 Ejecutar una batería de pruebas: el sistema permitirá al usuario ejecutar varias reordenaciones sobre los vuelos que seleccione y los algoritmos elegidos. CAR-2.2 Descargar resultados: los datos presentados al finalizar una batería de pruebas serán descargables con el fin de poder ser posteriormente conservados. CAR-3 Corrección de timestamps: la aplicación incorporará también un modelo de corrección de los timestamps tras una reordenación, a fin de que la marca temporal de cada mensaje se asemeje lo más fielmente posible al instante temporal en que la aeronave envió verdaderamente el mensaje. CAR-3.1 Visualizar relación distancia recorrida y nuevo timestamp con respecto a la altura: el usuario podrá observar esta relación tras la ejecución de una reordenación [CAR-1.1] con el fin de comprobar cómo se ha llevado a cabo la corrección de los timestamps de los mensajes. De la lista anterior de características, los requisitos de usuario serán aquellas que no tengan subcaracterísticas por debajo de ellas. De estos podemos derivar los distintos requisitos funcionales, que describen la totalidad de la funcionalidad a cubrir. Los requisitos funcionales identificados son los siguientes: RF-01 El sistema ejecutará una reordenación sobre los datos del vuelo que el usuario haya elegido, así como haciendo uso del algoritmo y parámetros que el usuario haya introducido [CAR-1.1]. RF-02 El sistema mostrará un mensaje de error si, al ordenarse una reordenación, alguno de los parámetros introducidos no es válido [CAR-1.1, CAR-2.1]. RF-03 El sistema repintará el dashboard tras finalizar una reordenación para mostrar por pantalla la información asociada a la misma (distancia de la nueva ruta encontrada, 54 5.3. Análisis Figura 5.1: Arbol de características de la aplicación en R puntos cuyo orden haya sido modificado, etc) [CAR-1.1]. RF-04 El sistema leerá todos los ficheros csv de la carpeta Vuelos del proyecto y permitirá al usuario elegir cual de ellos desea que se represente en el dashboard [CAR-1.2.1]. RF-05 El sistema cargará un vuelo en el dashboard tras haber sido seleccionado por el usuario [CAR-1.2.1]. RF-06 El sistema cargará de nuevo el dashboard cada vez que el usuario ordene modificar el rango de puntos a representar [CAR-1.2.2]. RF-07 El sistema hará visible sobre el dashboard la fuente de datos de la que procede cada mensaje ADS-B [CAR-1.2.3]. RF-08 El sistema presentará sobre el dashboard aquellos mensajes ADS-B procedentes de fuentes de datos seleccionadas por el usuario [CAR-1.2.3]. RF-09 El sistema presentará todos los datos asociados a cada mensaje ADS-B de un vuelo elegido [CAR-1.2.4]. RF-10 El sistema mostrará al usuario todos los registros en los que alguno de sus datos se corresponda con el patrón por el que el usuario haya ordenado filtrar [CAR-1.2.4]. RF-11 El sistema permitirá al usuario ordenar la ejecución de una batería de pruebas. RF-12 El sistema presentará tres modos de ejecución de una batería de pruebas: sin ventanas, utilizando un solo tipo de ventana o utilizando dos tipos de ventana para adaptar aeropuertos (ver Subsección 5.4.1) [CAR-2.1]. 55 Capítulo 5. Estudio preliminar de los algoritmos RF-13 El sistema permitirá al usuario elegir varios vuelos de entre aquellos cuyos datos se encuentren en la carpeta Vuelos en formato csv [CAR-2.1]. RF-14 El sistema permitirá al usuario elegir varios algoritmos de entre aquellos citados en la Sección 5.2 [CAR-2.1]. RF-15 El sistema mostrará los datos de las ejecuciones en base a métricas de rendimiento, así como los datos individuales de cada ejecución, que incluyan la longitud de la nueva ruta encontrada y la de partida, el tiempo de ejecución y el porcentaje de mejora que se obtiene sobre la ruta de partida en términos de distancia [CAR-2.1]. RF-16 El sistema permitirá al usuario la descarga de los datos resultantes de la ejecución de una batería de pruebas, entre los que se incluyen las longitudes de las rutas de partida y final, el tiempo de ejecución, y el porcentaje de mejora que se obtiene sobre la ruta de partida en términos de distancia [CAR-2.2]. RF-17 El sistema mostrará por pantalla la información que permita al usuario establecer comparación entre la altura de la aeronave y la distancia recorrida desde el comienzo con respecto al tiempo [CAR-3.1]. 5.4. Desarrollo de la aplicación En esta sección se describen los aspectos fundamentales que caracterizan el desarrollo llevado a cabo de la aplicación objeto de este capítulo. Esta aplicación se caracteriza por la presencia importante de una interfaz gráfica elaborada, que responde a la necesidad de visualizar y obtener las conclusiones arrojadas por el estudio que se pretende llevar a cabo en esta fase del proyecto. Estas conclusiones deben ser claras y precisas de tal manera que sea posible determinar lo más fielmente posible el comportamiento de los distintos algoritmos en estudio, identificando las fortalezas y debilidades de cada uno de ellos. Es por esto, que se opta por la realización de un dashboard, que aloje al mismo tiempo una serie de gráficas y mapas ilustrativos, claves para la obtención de conclusiones. Tal y como se ha mencionado previamente, la interfaz de usuario de la aplicación hace uso de la librería shiny de R, que permite la elaboración de dashboards y aplicaciones de tipo cliente-servidor, proporcionando funciones que permiten el desarrollo de ambas partes. De esta forma, el código de la aplicación queda dividido en dos partes, una parte cliente, que define todos los componentes que forman parte de la interfaz de usuario, así como su distribución, y una parte servidor, que implementa toda la lógica de negocio, así como el acceso a los datos. La parte cliente queda configurada a través de la función shinyUI(), que conforma en su totalidad la capa de presentación. A través de esta función se determinan y distribuyen los distintos componentes que se muestran en pantalla en cada situación. Por defecto, Shiny divide la interfaz de usuario en tres componentes: una cabecera o hea56 5.4. Desarrollo de la aplicación Figura 5.2: Partes de la interfaz de la aplicación der, configurado mediante la función dashboardHeader(), una barra lateral, que puede albergar diferentes opciones a modo de menú, así como botones, sliders u otros componentes; mediante dashboardSidebar(), y una parte central que contenga los diferentes elementos que componen el dashboard, con dashboardBody(). A su vez, es posible añadir componentes adicionales a la estructura, como un pie de página. La Figura 5.2 representa la página de inicio de la aplicación. La barra lateral representa un menú de configuración de los componentes presentes en la parte central. La parte superior de este menú lateral presenta tres widgets que permiten al usuario cambiar la vista de la parte central. El primero de ellos, denotado como mapas, presenta la vista principal (ilustrada en la Figura 5.3), formada por los componentes que componen el dashboard. En la parte superior se encuentra un panel con tres pestañas que permite al usuario visualizar tres componentes distintos. El primero de ellos, y visualizado en la Figura 5.3, es el mapa terrestre sobre el cual se pinta la posición de los mensajes ADSB asociados a un vuelo concreto. El segundo de estos componentes es una gráfica en tres dimensiones que se hacía referencia anteriormente. La tercera es la gráfica que muestra la corrección del timestamp asociado a los mensajes ADS-B tras haber ejecutado una reordenación. En la parte inferior del dashboard se presentan las gráficas de altura frente al timestamp así como de velocidad frente a timestamp. El segundo de los widgets es el que presenta en la parte central una tabla con los datos de mensajes ADS-B asociados a una trayectoria. 57 Capítulo 5. Estudio preliminar de los algoritmos Como hemos visto en el Capítulo 3, los mensajes ADS-B asociados a un vuelo contienen un conjunto de datos necesarios para el seguimiento. Entre ellos se encuentra una marca temporal o timestamp que para cada mensaje representa el instante temporal en que fue recibido por un sensor y que permite establecer un orden en el conjunto de ellos. Sin embargo, como consecuencia de los problemas de alineamiento temporal que presenta la tecnología ADS-B (que se trata en el Capítulo 3), esta ordenación temporal difiere del verdadero orden en que los mensajes son enviados por la aeronave. A lo largo del presente capítulo hemos abordado el problema de reordenación de los mensajes ADS-B asociados a un vuelo mediante la implementación de un modelo que tiene por objeto encontrar esa disposición temporal real de los mensajes ADS-B y que habilita la reconstrucción de la trayectoria seguida por la aeronave tomando en consideración los datos de geolocalización contenidos en estos mensajes. Este desarrollo permite llevar a cabo las reordenaciones anteriores mediante la ejecución de uno de los algoritmos aplicables a resolver supuestos del problema del viajante, problema que, como ya se ha comentado, es la base de este planteamiento teórico. Sin embargo, tras reordenar los mensajes ADS-B de un vuelo se genera una inconsistencia en los datos de seguimiento, pues el nuevo orden de los mensajes no se corresponde con el que resultaría de ordenar ascendentemente sus marcas temporales. Es por ello que es necesario efectuar correcciones sobre el timestamp de ciertos registros de manera que el nuevo orden de los mensajes sea coherente con su timestamp. Este trabajo tiene entre sus aspiraciones abordar este nuevo problema de rectificación o refinamiento de las marcas temporales (en línea con el objetivo [OB-2]), consecuencia del procedimiento de seguimiento que efectúa ADS-B. En primer lugar, se lleva a cabo la creación de un modelo matemático que permita efectuar estas correcciones, así como obtener un nuevo valor de timestamp para cada punto a partir de los datos de los mensajes ADS-B inmediatamente anteriores y posteriores. Dado un vuelo con cierto conjunto de mensajes ADS-B asociado, y una reordenación de estos mensajes, se establece una partición sobre los mensajes de manera que queden divididos en dos subconjuntos en función de si su posición en el orden cambia o no tras la reordenación. Esta división separa los mensajes de la forma siguiente: 1. En el primero de ellos, aquellos mensajes cuya posición antes y después de la reordenación coincide. 2. En el segundo, aquellos mensajes cuya posición antes y después de la reordenación cambia. Así por ejemplo, el mensaje que ocupaba la posición tercera (existen solo dos mensajes con marcas temporales anteriores) antes de reordenar, estará en el primer grupo si tras la reordenación sigue estando en esa posición, y pertenecerá al segundo grupo en caso contrario. Una vez se ejecuta la reordenación, quedan establecidas estas dos categorías de men64 5.5. Modelo de corrección de timestamps sajes, considerando a la primera de ellas como el conjunto de mensajes cuyos datos de timestamp son correctos, de manera que se supone que no han sufrido alteraciones sobre su marca temporal. Estos mensajes se toman como referencia en el modelo a la hora de efectuar las correcciones, y por tanto no se rectifican. Por otro lado, para los mensajes que pertenecen a la segunda categoría se considera que sus marcas temporales no representan fielmente el instante temporal en que se enmarcan, por lo que se establece que deben ser rectificadas. En esta corrección se parte de las marcas temporales de los mensajes pertenecientes al primer grupo más próximos en el orden a cada punto del segundo grupo. El procedimiento de corrección se divide en dos fases. En la primera, se corrigen los puntos primero y último de la ruta en caso de que alguno de ellos pertenezca al segundo grupo. A continuación, la segunda fase consistiría en la corrección del resto de puntos intermedios del segundo grupo. El modelo matemático aplicado a la corrección de cada punto parte de los datos de velocidad y distancia recorrida por la aeronave de los mensajes ADS-B más próximos. Dado cualquier punto del grupo segundo intermedio (que no sea el primero o el último de la ruta tras la reordenación), se localiza el punto bueno anterior y el posterior más cercanos, y de ellos se toman los datos de timestamp,tant, tpos que se consideran correctos (que no necesitan de corrección). A continuación se calcula la velocidad media de la aeronave vant en el segmento de trayectoria que va desde el punto bueno anterior más cercano hasta el punto actual, así como la velocidad media vpos que alcanza en el segmento que va desde el punto actual hasta el punto bueno posterior más próximo. Para obtener estos dos datos es necesario disponer de los datos de velocidad de los mensajes ADS-B que, según el nuevo orden, se encuentran entre los puntos buenos previamente mencionados. Más adelante, en esta sección, veremos la correlación aparente entre velocidad y altura de la aeronave. Esto permite establecer una relación de proporcionalidad entre ambos datos para obtener los datos vant yvpos a partir de la altura, considerando cierta esta correlación. El nuevo timestamp de cada punto dentro del segundo grupo viene dado por la expresión (vposdpos + 1)tant + (vantdant + 1)tpos (vposdpos + 1) + (vantdant + 1) (5.1) donde vpos es la media aritmética de las velocidades de los nmensajes del grupo 1 inmediatamente posteriores al actual, vant es la media aritmética de las velocidades de los nmensajes del grupo 1 inmediatamente anteriores al actual, dpos es la distancia del punto actual con respecto al punto del grupo 1 inmediatamente posterior, 65 Capítulo 5. Estudio preliminar de los algoritmos dant es la distancia del punto actual con respecto al punto del grupo 1 inmediatamente anterior, tant es el timestamp del punto del grupo 1 inmediatamente anterior al actual y tpos es el timestamp del punto del grupo 1 inmediatamente posterior al actual. La constante 1que se suma a cada uno de los pesos evita el caso en que ambos pesos son nulos, en el que el cociente sería igual a cero. La expresión (5.1) no es más que la media ponderada de los timestamps de los puntos del primer grupo anterior y posterior más próximos, donde los pesos dependen de la velocidad media de la aeronave y de la distancia recorrida en el segmento que limitan los dos puntos buenos previos. Este modelo, sin embargo, no funciona cuando no existen puntos buenos en alguno de los dos lados del punto actual, cosa que ocurre cuando alguno de los dos extremos de la ruta son objeto de corrección (son del segundo grupo). Es por ello que se realiza la corrección de estos dos puntos previamente a la corrección de los puntos intermedios, para que, una vez corregidos, pasen a ser considerados como puntos del primer grupo evitando la situación anterior. En el caso de los extremos los datos considerados no cambian: se parte de la velocidad media que alcanza la aeronave en el segmento de trayectoria que va desde el extremo considerado hasta el punto bueno más cercano, así como la distancia recorrida en ese segmento y el timestamp del punto del primer grupo. Así, y considerando un movimiento rectilíneo uniforme, se deriva la marca temporal del extremo considerado a partir de la expresión t0±d v+ 0,1 donde t0es la marca temporal asociada al punto bueno más cercano, ves la velocidad media de la aeronave en el segmento que define el extremo considerado y el punto bueno más próximo y des la longitud del segmento de trayectoria. El operando ±que se considera va en función de si el punto a corregir es el primero o el último: será +para tratar el último punto y −para el primero. Por su parte, la constante 0,1se considera para evitar el caso en que la velocidad media de la aeronave es nula, y por tanto, el cociente igual a cero. Como en el caso anterior, si no se disponen datos de velocidad se supone proporcional a la altura y se obtiene a partir de este dato. Por último añadir que tras corregirse un punto pasa a formar parte de los puntos del primer grupo, por lo que en la corrección de los siguientes puntos, los puntos anteriormente corregidos son buenos a la vista del algoritmo. 66 5.5. Modelo de corrección de timestamps Este modelo de corrección de marcas temporales se encuentra implementado en la aplicación de la que trata este capítulo, a fin de ser puesto en práctica. Tras ejecutar una reordenación, existen dos formas de visualizar sobre la aplicación la reordenación de los timestamps producida. La primera de estas formas es sobre el widget Tabla, donde se muestra una tabla que contiene los datos de los mensajes ADS-B asociados al vuelo. En la tabla que se muestra en esta vista aparecen nuevas columnas que reflejan los resultados de la reordenación y de la corrección de las marcas temporales. Estas columnas son las siguientes: distancia: indica la longitud en kilómetros del camino que recorre todos los puntos de la trayectoria que se encuentran entre el primero y el punto actual en el orden que establece la nueva reordenación. Este valor de longitud se calcula como la suma de la longitud de los segmentos que unen cada punto con el siguiente, a través de la Fórmula de Haversine (7.1). tag_original: Indica la posición que ocupaba cada mensaje antes de la reordenación. tag_ordenado: Indica la posición que ocupa el mensaje tras la reordenación ejecutada. timestamp_ordenado: Indica el nuevo valor de timestamp que se asocia al mensaje tras la reordenación. Por defecto, al acceder a este módulo las filas de la tabla aparecerán ordenadas conforme a la nueva ordenación obtenida, pero el usuario puede, a través de los controles de la tabla, modificar la ordenación de los registros respecto al valor de los mensajes en cualquiera de las columnas. En la Figura 5.8 se observan estos nuevos campos de la tabla. Obsérvese, recuadrado en rojo, como dos puntos cuyo orden se ha intercambiado obtienen nuevos valores de timestamp coherentes con su nueva posición. La segunda forma de comprobar cómo se ha efectuado la corrección de los timestamps se observa en la gráfica que asocia la distancia recorrida por la aeronave (campo distancia anterior) con el nuevo timestamp. A esta componente se accede a través del widget Mapas y la pestaña Distancia vs Tiempo de la componente central. Sobre esta gráfica bidimensional se observa la correlación entre los distintos puntos que componen el vuelo. La Figura 5.9 ilustra lo que se visualiza para un ejemplo concreto. En verde, se representan los puntos “malos”(aquellos que han visto afectada su posición en la ruta al ejecutar la reordenación), cuyo timestamp ha sido modificado, mediante el modelo que representa (5.1). Por otro lado, los puntos en gris representan los puntos “buenos”(que no han cambiado su posición). Éstos mantienen su marca temporal al considerarla el modelo como correcta. En la Figura 5.10 se observa en mayor detalle como se han situado los puntos verdes tras haber sido interpolados, situándose en la línea recta que une los dos puntos grises inmediatamente anterior y posterior al grupo de puntos malos observado, variando su posición en función del valor que tengan en la columna distancia y de la velocidad asociada a los npuntos buenos anteriores y posteriores, como ya hemos comentado. 67 Capítulo 5. Estudio preliminar de los algoritmos Figura 5.8: Ejemplo de corrección de los timestamps tras haber ejecutado una reordenación sobre un vuelo, con los registros ordenados conforme al nuevo orden de los mensajes obtenido Figura 5.9: Ejemplo de corrección de los timestamps tras haber ejecutado una reordenación sobre un vuelo, vista de la gráfica Distancia vs Tiempo del widget Mapas 68 5.5. Modelo de corrección de timestamps Figura 5.10: Ampliación de la gráfica que muestra la Figura 5.9 Figura 5.11: Gráfica Distancia vs Tiempo al representar la altura de cada punto a través de un gradiente de colores Por último, la gráfica anterior puede ilustrar a su vez la relación entre el valor que obtienen los puntos en el campo distancia, su nuevo timestamp y su altura. En la Figura 5.11 se muestra la gráfica de la Figura 5.9 donde, a través de un gradiente de colores, es posible visualizar globalmente la asociación entre la altura de la aeronave y la distancia recorrida con respecto al tiempo. Obsérvese como la pendiente de la gráfica es más acusada cuando los valores de altura son altos (aeronave en vuelo), y menor cuando ésta no es tan elevada (en aeropuertos, despegando o realizando maniobras de aterrizaje). Este hecho se debe a que altura y velocidad de la aeronave son generalmente proporcionales. 69 Capítulo 5. Estudio preliminar de los algoritmos 70 Capítulo 6 Análisis de resultados A lo largo del presente capítulo se presentan los resultados del estudio llevado a cabo a través de la aplicación presentada en el Capítulo 5. Este estudio cuenta con dos fases: en la primera se comparan todos los algoritmos entre sí al ser aplicados a la reordenación de un conjunto de trayectorias reales (ver Sección 6.1), mientras que en la segunda se ejecuta una gran batería de pruebas que incluye 96 vuelos reordenados con el algoritmo 2-Opt a fin de medir su rendimiento (ver Sección 6.2). Ambos estudios han sido realizados junto a María Zorita Mínguez en el marco de una beca de colaboración con el Departamento de Informática. Los vuelos que aparecen de aquí en adelante proceden de datos reales suministrados por Boeing Research & Technology Europe, sin los cuales la realización de este estudio, así como del presente Trabajo Fin de Grado, no habría sido posible. 6.1. Estudio comparativo de los algoritmos de resolución del TSP aplicados a la reordenación de mensajes ADS-B Para elaborar esta primera parte del estudio, se ha tomado como referencia cinco conjuntos de datos procedentes de mensajes ADS-B, cada uno correspondiente a un vuelo concreto. Estos vuelos son los considerados en la breve comparativa que ilustra la eficacia de la técnica de las ventanas de ejecución en la Tabla 5.1. Por otra parte, el sistema informático sobre el que se han ejecutado los algoritmos es un ACER Aspire 5 A515-51G-751G que incluye entre sus características más destacables un sistema operativo Windows 10 Home, procesador Intel Core i7-7500U con velocidad de entre 2.7 GHz a 3.5 GHz y memoria RAM de 8GB. 71 Capítulo 6. Análisis de resultados Figura 6.1: Diagrama de barras: Longitud mejorada (en km) registrada con respecto a la ruta de partida inicial 72 6.1. Estudio comparativo de los algoritmos de resolución del TSP aplicados a la reordenación de mensajes ADS-B Algoritmo IBE04HT IBE04NL IBE0519 IBE05DK RYR9KY_4CA97C de resolución Long Tmp Long Tmp Long Tmp Long Tmp Long Tmp Sin aplicar algoritmo 511,99 - 659,99 - 682,84 - 602,47 - 346.98 - Inserción más cercana 453,22 5,46 588,89 7,24 639,72 5,60 573,73 5,59 300.85 0.78 Inserción más lejana 533,07 5,41 570,51 6,14 600,42 5,97 801,13 4,97 360.63 0.80 Inserción más barata 452,95 3,76 570,42 4,03 600,38 3,89 558,69 3,04 299.99 0.49 Inserción aleatoria 529,76 0,05 576,98 0,05 873,01 0,04 653,8 0,05 330.80 0.02 Vecinos más próximos 518,98 0,05 888,53 0,05 1.227,06 0,05 913,47 0,04 332.44 0.01 Vecinos más próximos repetitivo 453,49 66,22 570,76 67,54 602,57 55,41 558,77 51,36 310.66 6.75 2-Opt 452,95 0,42 570,42 0,63 600,38 0,5 558,69 0,28 299.99 0.03 Lin-Kernighan 452,97 20,85 570,39 18,58 600,38 22,14 558,69 16,97 299.99 3.62 Concorde 452,62 17,37 569,77 20,06 600,26 14,11 558,69 8,40 299.99 2.49 Simulated annealing, 40000 iteraciones 505,91 5,04 657,75 5,08 677,75 5,22 601,86 5,59 340.84 3.65 Simulated annealing, 100000 iteraciones 503,99 12,20 656,83 14,06 664,79 12,56 590,95 11,98 327.98 9.17 Simulated annealing, 1000000 iteraciones 482,97 141,86 611,94 133,66 641,93 120,99 578,84 120,21 309.50 89.64 Tabla 6.1: Comparativa de los algoritmos en longitud de la ruta encontrada (Long) en kilómetros y en tiempo de ejecución (Tmp) en segundos Figura 6.2: Diagrama de barras: Longitud mejorada (en km) registrada con respecto a la ruta de partida inicial obtenida por los métodos no constructivos 73 Capítulo 7. Implementación escalable proceso de adaptación de la aplicación al modelo de programación en MapReduce, en la Sección 7.4. 7.1. Implementación del k-Opt Para implementar el algoritmo se toma como referencia el Algoritmo 1, que se incluye en la Sección 4.5. La implementación en Java se obtendría por tanto realizando iteraciones con un bucle while cuya condición de parada sea cuando no haya ningún k-change por realizar sobre la ruta. Sin embargo, para evitar que en rutas grandes y para un alto valor de kel valor de k-changes a probar sea desmedido, se introduce un atributo int que fije el número total de k-changes que se pueden probar sobre una ruta sin obtener ninguna mejor. De esta forma la condición de parada del bucle se sustituye por deternerse si se sobrepasa el número de k-changes máximo fijado. En cada iteración, el algoritmo prueba una modificación sobre la ruta actual obteniendo una nueva, calcula la longitud de esta nueva ruta y la compara con la actual. En caso de ser más corta sustituye la ruta actual por la nueva y reinicia las variables del bucle. El orden en que se realizan los k-changes es arbitrario. Se generana cada iteración un número aleatorio que indica cual de todos los posibles k-changes se realizará. Para comenzar a iterar, lo primero que es necesario es determinar qué k-changes son posibles de realizar sobre la ruta, para lo cual es necesario imponer una serie de restricciones que permita dar con ellos, así como encontrar un tipo de datos que permita almacenar estos k-changes y eliminarlos una vez que han sido probados. Este tipo, con las características dinámicas requeridas, bien podría ser un ArrayList<int[]>, que permite el acceso aleatorio a cualquiera de sus posiciones, a diferencia de otros tipos estructurados, así como la eliminación de elementos a partir de su posición en la estructura. Por otro lado es necesario especificar las restricciones a tener en cuenta para poder determinar los k-changes. Un k-change debe eliminar karistas determinadas de la ruta y sustituirlas por otras kdeterminadas por aquellas que fueron suprimidas y no puede eliminar dos aristas consecutivas de la ruta (que confluyan en un mismo vértice), pues el k-change daría como resultado un r-change donde 0< r < k (suponiendo como 1-change la modificación que transformaría la ruta en ella misma). Así, por tanto, bastaría con que el ArrayList almacene k−uplas de enteros no negativos donde cada uno de ellos indique una de las aristas a eliminar. De esta forma es necesario numerar todas las aristas de la ruta. Por otro lado se debe imponer la condición de que ninguna k−upla contenga dos números consecutivos, o por la primera y última arista (recordemos que se añade una ciudad artificial que una el primero y el último 80 7.2. Desarrollo de una aplicación en Java que realice reordenaciones a través de la implementación de los métodos k-Opt de los nodos, por lo que las aristas que unen la primera y última ciudad con la ciudad artificial también deben ser tenidas en cuenta como parte de la ruta). Asimismo, para evitar que cada k-change se pruebe más de una vez (ya que, por ejemplo, la 2−upla (n, m)equivaldría a la 2−upla (m, n)en cuanto a que supone eliminar las mismas aristas y por tanto reemplazarlas por las mismas dos aristas) se añade la restricción de que cada par sea de la forma (a, b)donde a < b. En cada iteración, se escoge aleatoriamente el k-change a realizar, generando un número aleatorio que indique la posición del ArrayList de k-changes a considerar. Tras comparar la nueva ruta obtenida con la actual se elimina el k-change probado del ArrayList, para que no vuelva a salir, y prosigue la ejecución. En caso de haber obtener una nueva ruta más corta que la actual se reinicia el ArrayList de k-changes para poder probar todos de nuevo. En el momento en que el ArrayList quede vacío no podrá mejorarse la ruta a través de k-changes lo que desencadena el final de la ejecución del algoritmo. 7.2. Desarrollo de una aplicación en Java que realice reordenaciones a través de la implementación de los métodos k-Opt En el contexto de nuestro problema, una vez se ha llevado a cabo la nueva implementación de los algoritmos k-Opt, se requiere de una aplicación que la contextualice en el marco de la reordenación de trayectorias de aeronaves. El objetivo de este desarrollo es la obtención de una aplicación que, a partir de conjuntos de mensajes ADS-B asociados a un mismo vuelo, sea capaz de reordenarlos haciendo uso de la implementación del algoritmo k-Opt realizada, y genere como salida la nueva reordenación de los datos, así como información complementaria necesaria para conocer la eficacia y eficiencia de la ejecución del algoritmo. Esta aplicación, se desarrolla a modo de prototipo de la implementación escalable que se pretende desarrollar, a fin de estudiar la nueva implementación de los algoritmos k-Opt realizada, y tiene las siguientes características: La aplicación es capaz de leer ficheros csv de una carpeta data_vuelos. Cada uno de estos ficheros contiene registros con los mensajes ADS-B asociados a un vuelo. La aplicación procesa los datos contenidos en cada registro, eliminando aquellos con valores no tratables o con formato incorrecto en aquellos campos necesarios a la hora de realizar la reordenación como son los datos de longitud,latitud otimestamp del mensaje. Una vez se han leído todos los registros de un fichero, y previamente a la reordenación de los mensajes, los registros de la tabla se ordenan ascendentemente por su valor de timestamp 81 Capítulo 7. Implementación escalable Se ejecuta el algoritmo k-Opt, con el valor de kelegido, tras haber procesado la lectura de los datos de un vuelo considerando como ciudades de la instancia del TSP a resolver cada uno de los mensajes ADS-B. Para poder transformar el problema de reordenación de trayectorias en el TSP es además necesaria la introducción de una ciudad artificial que se una a todas las demás a través de aristas cuyo coste o longitud sea 0. La aplicación, antes de comenzar a ejecutar el algoritmo, creará esta nueva ciudad así como la matriz de distancias, calculando la distancia dos a dos entre los mensajes ADS-B a partir de sus coordenadas geográficas (se descarta la altura a modo de simplificación). Este valor se obtiene haciendo uso de la fórmula de la distancia de Haversine que propone obtener el valor de la distancia entre dos puntos sobre la Tierra a través de la expresión 2r·arcsin  v u u tsin2 φ2−φ1 2!+cos(φ1)cos(φ2)sin2 λ2−λ1 2! (7.1) donde φ1es el valor de la latitud del punto 1. λ1es el valor de la longitud del punto 1. φ2es el valor de la latitud del punto 2. λ2es el valor de la longitud del punto 2. res el valor del radio terrestre en la métrica en la que se quiera obtener la distancia (en nuestro caso kilómetros). Su valor es de 6371 kilómetros. La aplicación ejecuta la implementación del k-Opt realizada sobre la nueva instancia del TSP generada a partir de los datos del vuelo, obteniendo como resultado una nueva reordenación de las ciudades. Tras finalizar la ejecución del algoritmo sobre un vuelo, la aplicación elimina la ciudad artificial, obteniendo así la reordenación definitiva de los registros. En este proceso, se localiza la ciudad artificial en la ruta. Las ciudades anexas a esta ciudad artificial en la ruta se corresponderán con el comienzo y el final de la nueva ruta del problema de reordenación de trayectorias. Para determinar cual de las dos ciudades es el inicio o la llegada, se determina tomar como origen aquella que menor timestamp tenga asociado, correspondiéndose entonces la ciudad con mayor timestamp con el final de la trayectoria. La aplicación mide el tiempo que tarda en ejecutarse el algoritmo a modo de determinar la eficiencia de la ejecución, así como la distancia de cada ruta intermedia obtenida durante la ejecución del algoritmo. Esto se hace con el fin de medir la bondad de las mismas y compararlas a través de este valor durante la ejecución. Una vez obtenida la reordenación de los mensajes ADS-B, se genera un nuevo fichero csv que contiene las filas del fichero csv leído previamente a la ejecución, ordenadas 82 7.3. Estudio de rendimiento de la nueva implementación para el 2-Opt en función de la nueva ordenación generada por la ejecución del algoritmo k-Opt. 7.3. Estudio de rendimiento de la nueva implementación para el 2-Opt Una vez finalizada la implementación del programa en Java se requiere analizar el funcionamiento de la nueva implementación de los algoritmos k-Opt, centrándonos en el método 2-Opt (k= 2), en busca de determinar si los resultados obtenidos de su ejecución (sin limitar el número de 2-change realizables sin mejora) son comparables a los obtenidos con la implementación de la librería TSP de R. En caso de obtener resultados similares estaremos en condiciones de afirmar que la implementación es adecuada con el fin de adaptar esta aplicación a la computación paralela. Se realizan tres baterías de pruebas en cada una de las aplicaciones. La primera de ella consiste ejecutar una serie de reordenaciones sobre vuelos de 1000 o más puntos. Frente a los buenos resultados obtenidos en R, en Java, el tiempo de espera supera los dos minutos para cada vuelo, lo que hace el problema intratable. Esto nos indica la imposibilidad de hacer uso de la nueva implementación del 2-Opt sin el uso de la técnica de ventanas de ejecución, a menos que la implementación se hiciese sobre un sistema de altas prestaciones que pudiese hacer frente el alto coste computacional requerido. En la segunda batería se eligen ventanas de tamaño 100 y solapamiento 20, y se miden los resultados obtenidos en longitud de la nueva ruta obtenida y tiempo de ejecución. Los resultados de esta ejecución se ilustran en la Tabla 7.1. Nótese que, la medida de la distancia de la ruta original en las aplicaciones de Ry Java es diferente, debido al distinto orden de precisión del redondeo en la aplicación de la Fórmula de Haversine (7.1). Esta diferencia es notable al aplicarse esta expresión tantas veces como aristas hay en la ruta (que coincide con el número de ciudades menos una), al ser necesario obtener la distancia entre los puntos dos a dos a partir de sus coordenadas geográficas. Teniendo en cuenta la observación del párrafo anterior, parece clara la similitud en tanto a la eficacia de reordenación de la implementación en Java, cuyos resultados en términos de longitud son del orden de los obtenidos por la implementación de la librería TSP de R. Por otro lado, y como era de esperar, la implementación en Java se queda algo atrás en cuanto al tiempo de ejecución, pero las diferencias, al tratarse subinstancias pequeñas, son poco apreciables, y por tanto el coste computacional es razonable. La última batería de pruebas utiliza dos tipos de ventanas: las primeras de tamaño 100 y solapamiento 20 en vuelo, y las segundas de tamaño 25 y solapamiento 5 en aeropuertos, distinguiendo las partes del vuelo por el valor 6.000 de altura. Los resultados de esta prueba se incluyen en la Tabla 7.2. 83 Capítulo 7. Implementación escalable IBE04HT IBE04NL IBE0519 IBE05DK IBE3118 IBE32GP IBE32HV Longitud Original R (km) 511,99 659,99 682,84 602,47 595,88 2622,32 2169,55 Longitud Original Java (km) 511,41 659,25 682,08 601,79 595,2 2619,38 2167,12 Nueva longitud R (km) 452,95 570,42 600,38 558,69 595,82 1924,6 1894,93 Nueva longitud Java (km) 452,55 570,25 599,9 558,15 595,15 1922,96 1892,06 Mejora longitud R ( %) 11,53 % 13,57 % 12,07 % 7,26 % 0,01 % 26,60 % 12,65 % Mejora longitud Java ( %) 11,50 % 13,50 % 12,04 % 7,25 % 0,01 % 26,58 % 12,69 % Tiempo de ejecución R (s) 0,05 0,04 0,01 0,02 0,00 0,02 0,06 Tiempo de ejecución Java (s) 0,09 0,04 0,04 0,04 0,00 0,20 0,10 Tabla 7.1: Comparativa, resultados de la reordenación usando 2-Opt con ventanas únicas de tamaño 100 y solapamiento 20 en las aplicaciones de RyJava IBE04HT IBE04NL IBE0519 IBE05DK IBE3118 IBE32GP IBE32HV Longitud Original R (km) 511,99 659,99 682,84 602,47 595,88 2622,32 2169,55 Longitud Original Java (km) 511.41 659.25 682.08 601.79 595.2 2619.38 2167.12 Nueva longitud R (km) 452.96 570.85 600.38 558.69 595.88 1924.6 1894.93 Nueva longitud Java (km) 452.55 570.25 599.9 558.15 595.2 1922.96 1892.08 Mejora longitud R ( %) 11,53 % 13,50 % 12,07 % 7,26 % 0,00 % 26,60 % 12,65 % Mejora longitud Java ( %) 11,50 % 13,50 % 12,04 % 7,25 % 0,00 % 26,58 % 12,69 % Tiempo de ejecución R (s) 0.02 0,03 0,05 0,00 0,00 0.04 0.08 Tiempo de ejecución Java (s) 0,07 0,06 0,04 0,04 0,00 0,20 0,16 Tabla 7.2: Comparativa, resultados de la reordenación usando 2-Opt con ventanas de tamaño 100 y solapamiento 20 en vuelo y de tamaño 25 y solapamiento 5 en aeropuertos, distinguiendo por altura 6000, en las aplicaciones de RyJava Las diferencias entre los resultados de la tercera batería en relación con los de la 84 7.4. Adaptación a MapReduce segunda son mínimos. En el caso de R, el tiempo de ejecución se reduce levemente mientras que la eficacia de la reordenación disminuye también, aunque de forma inapreciable. Por el contrario, la implementación de Java se mantiene aun más invariante, notando también la adecuación de la implementación a este tipo de ejecución. En conclusión, es posible afirmar la adecuación de la nueva implementación en la reordenación de instancias pequeñas, así como su no recomendable utilización para la reordenación de trayectorias con un gran número de mensajes, a menos que se disponga de un sistema de altas prestaciones. Sin embargo, el obstáculo de disponer de instancias grandes es salvable mediante el uso de la técnica de las ventanas de ejecución que exponíamos en la Subsección 5.4.1, ya que el algoritmo pasa a ejecutarse sobre subinstancias más pequeñas, y por tanto tratables para la nueva implementación del algoritmo. A su vez, como se ha visto, el uso de esta técnica no reduce la eficacia de la reordenación con respecto a la que se obtendría aplicando el algoritmo a la trayectoria completa, haciendo a su vez esta técnica aplicable en la práctica, para la reordenación de trayectorias reales de aeronaves de forma exitosa. 7.4. Adaptación a MapReduce Las pruebas destinadas a verificar el buen funcionamiento de la implementación realizada de los algoritmos k-Opt (concretamente el 2-Opt) en Java concluyen de forma exitosa, al comprobar que a partir de los mismos vuelos, los resultados obtenidos en términos de longitud y de tiempos de ejecución son análogos a los de R. Con todo esto, parece razonable concluir la utilidad de la implementación realizada para su aplicación al problema de reordenación de trayectorias. Sin embargo, no podemos olvidar el entorno en el que nos encontramos. Tal y como se mencionó en el Capítulo 1, la gestión del tráfico aéreo europeo requiere del uso de tecnologías bigdata, capaces de gestionar ingentes cantidades de datos en tiempo real. Esto se debe, por un lado, a la reciente utilización de las tecnologías de seguimiento ADS-B que aumentan la frecuencia de datos emitidos por cada aeronave, y que deben ser procesados por los sistemas ATM. Por otro lado, a la notable subida que prevé Eurocontrol en el número de aeronaves circulando por el espacio aéreo europeo [Eurocontrol, 2017]. Esta situación exige que la implementación anterior expuesta en la Sección 7.2 sea escalable, de forma que pueda ser aplicable a múltiples trayectorias de forma simultanea, esto es, que sea paralelizable sobre un cluster que dote a la implementación de la infrastructura necesaria para poder llevar a cabo este procesamiento de forma escalable, y por tanto, sin perder rendimiento al aumentar de forma ingente el número de datos a procesar. De esta forma se opta por una adaptación de la implementación a MapReduce que, como veremos en la siguiente subsección, permite el procesamiento paralelo de datos abstrayendo al programador de toda la complejidad interna que implica este tipo de computación. 85 Capítulo 7. Implementación escalable 7.4.1. Introducción a MapReduce MapReduce [Dean y Ghemawat, 2008] se define como un modelo de programación e implementación asociada para procesar y generar grandes volúmenes de datos, a través de la especificación de un mapper, o función que procesa pares de la forma clave-valor con el fin de generar un conjunto de pares intermedios clave-valor; y un reducer, o función que combina los valores intermedios asociados a una misma clave. Nace a través de Google, en busca de una implementación que pueda ser ejecutada sobre clusteres de grandes dimensiones así como el desarrollo de aplicaciones altamente escalables y fáciles de desarrollar, abstrayendo a los programadores de la complejidad de la computación paralela y distribuida, y permitiendo así a aquellos sin experiencia en computación distribuida el desarrollo de este tipo de programas. En 2010, nace Hadoop como una implementación OpenSource de este paradigma, y con el que su uso se expande a toda la comunidad informática. Su desarrollo fue llevado a cabo en sus inicios por Yahoo y más tarde pasa a ser realizado por el proyecto Apache. Su inminente expansión se debió a las múltiples aplicaciones reales expresables a través de este paradigma. El modelo de programación que propone MapReduce consiste en considerar como entrada un conjunto de pares clave-valor. Una misma clave usualmente será compartida por varios pares y actúa a modo de clasificador (los pares quedan agrupados por el valor de ésta). Los pares que comparten una misma clave serán procesados conjuntamente. Existen dos funciones principales: Map: toma cada par de datos de entrada clave-valor y produce con ello un conjunto de pares clave-valor intermedios. Estos últimos son agrupados en base a su clave de manera que cada grupo de ellos es la entrada de una ejecución de la función Reduce. Reduce: toma como entrada uno de los subgrupos de pares clave-valor intermedios, resultado de la función Map. En su ejecución, el Reducer tiene como finalidad el procesado de todos los pares recibidos, dando como resultado una información con valor para el usuario, fruto del procesamiento. La salida más típica de esta función suele ser 0 o 1 en función del resultado del procesamiento. El ejemplo más sencillo de aplicación de este modelo de programación, propuesto en Dean y Ghemawat [2008] es el famoso WordCount, que consiste en la lectura de varios textos procedentes de un conjunto de documentos con el fin de obtener el número total de apariciones de cada palabra en los textos. Se propone así una función map que considere como entrada cada uno de los textos. En caso de que estos se encuentren en distintos documentos del sistema, se considera la URL del fichero como clave y el texto contenido como valor. 86 7.4. Adaptación a MapReduce Figura 7.1: Esquema de funcionamiento de MapReduce map(String key, String value): // key: document name // value: document contents for each word w in value: EmitIntermediate(w, "1"); La función Map se ejecuta tantas veces como documentos haya, y en cada una de ellas se recorre el texto, generando para cada palabra del mismo, un par intermedio que toma como clave la propia palabra, y como valor el literal “1”. La librería MapReduce, de forma transparente al programador, agruparía el conjunto total de claves intermedias generadas por las ejecuciones de la función map, generando un tipo de dato que engloba todos los valores asociados a una misma clave, en este caso, todas las apariciones del literal “1”. La función Reduce de este ejemplo tomaría como entrada cada uno de esos pares intermedios, ejecutándose así una vez por cada clave intermedia distinta generada, esto es, una vez por cada palabra distinta en el texto. Para cada palabra se asocia la lista que incluye todos los valores asociados a esa clave. reduce(String key, Iterator values): // key: a word // values: a list of counts int result = 0; for each v in values: result += ParseInt(v); 87 Capítulo 7. Implementación escalable Emit(AsString(result)); Para cada ejecución de la función se produce el procesamiento, en este caso tan simple como contar el número de valores que contiene el iterable, de manera que se obtiene el número de veces que aparece la palabra en los textos. Este valor, así como la palabra asociada, es lo que devuelve la función reduce. Obsérvese que al mismo tiempo, varias ejecuciones de la función Reduce están teniendo lugar, por lo que la aplicabilidad de las implementaciones que hacen uso de esta librería está claramente orientada a su ejecución sobre clusteres donde se procesen simultáneamente varios subconjuntos de datos asociados a diferentes claves. Parece entonces clara la utilidad de este modelo de programación en el contexto del problema de reordenación de los mensajes ADS-B de una trayectoria. Se requiere una implementación capaz de llevar a cabo el procesamiento de un gran número de mensajes ADS-B por unidad de tiempo procedentes de diferentes vuelos que continuamente, y de forma simultanea, emiten datos de su posición que necesariamente han de ser procesados por el sistema en un breve periodo de tiempo. Se requiere a su vez que el sistema sea capaz de reordenar paralelamente las señales ADS-B asociadas a distintos vuelos, de tal manera que se obtenga, a modo de salida, las rutas realmente recorridas por las aeronaves, lo que implica ejecuciones simultaneas del algoritmo k-Opt elegido, una por vuelo a procesar. En la siguiente subsección se analizan los componentes de la nueva implementación así como las peculiaridades asociadas al proceso de adaptación de la anterior implementación en Java. 7.4.2. Implementación escalable en MapReduce A continuación se exponen los detalles de la implementación escalable objeto de exposición en este capítulo, que parte de la implementación previa realizada en Java a modo de prototipo y que alberga la implementación realizada de los métodos k-Opt. Antes de empezar a desarrollar la adaptación es necesario estudiar su viabilidad, pues para su elaboración se requiere disponer de herramientas adecuadas que permitan el desarrollo de implementaciones paralelizables. Se identifican así los siguientes elementos necesarios para esta implementación: Un sistema operativo que soporte Apache Hadoop sobre el que se puedan desarrollar implementaciones paralelizables simulando ejecuciones sobre un cluster. La UVa pone a disposición del proyecto una máquina virtual con el sistema operativo Cloudera donde poder realizar la implementación. 88 7.4. Adaptación a MapReduce Figura 7.2: Análisis de la implementación en MapReduce: diagrama de clases Disponer de accesibilidad a material y contenidos de iniciación al uso del modelo de computación MapReduce al no tener experiencia previa trabajando con él. Con estas necesidades cubiertas se comienza a adaptar la aplicación a MapReduce. Esta aplicación, engloba los objetivos de la anterior aplicación y añade a mayores: ejecución paralelizable de múltiples reordenaciones con los parámetros de ejecución deseados (modo de ejecución, tamaños de ventana, solapamiento, etc). La nueva aplicación, cuyo uso final no prevé la interacción con los usuarios, únicamente incluye la funcionalidad de ejecutar reordenaciones sobre los datos que toma como entrada, posteriormente corregir sus marcas temporales y finalmente generar como salida la nueva ordenación de los mensajes ADS-B de las rutas elegidas. Las clases en que se divide esta aplicación son las siguientes (ver Figura 7.2): Algoritmo: clase abstracta con aquellas propiedades (atributos) y operaciones (métodos) comunes a todos los algoritmos que resuelven instancias del problema del viajante. Diseñada por tanto para que cualquier implementación de un algoritmo de resolución del TSP extienda esta clase. Interpreter: clase que implementa el acceso a datos. Lee los ficheros csv en la carpeta data_vuelos por separado. Para cada registro de los ficheros crea una instancia de la clase Mensaje, donde almacena los valores leídos. A continuación, los mensajes de cada fichero son ordenados ascendentemente por timestamp. KOpt: clase que contiene la implementación de los algoritmos k-Opt. El constructor de esta clase admite un parámetro que permite seleccionar el valor de k, esto es, que algoritmo se ejecutará. Extienden la clase algoritmo al que añade la funcionalidad asociada a la inserción de una ciudad artificial, necesaria para la ejecución de este 89 Capítulo 8. Conclusiones El paso siguiente que da este trabajo, en línea con el [OB-1] consiste en el desarrollo de una implementación escalable en MapReduce que implemente el modelo teórico anterior, de manera que sea paralelizable, condición necesaria para poder ser posteriormente integrada a la lógica interna de un sistema gestor del tráfico aéreo. El esfuerzo llevado a cabo en esta tarea se expone en el Capítulo 7. Como segundo de los objetivos que plantea este Trabajo Fin de Grado [OB-2], se aborda la implementación de un segundo modelo que lleve a cabo el refinamiento o corrección de las marcas temporales de los mensajes ADS-B de una trayectoria recientemente reordenada. La Sección 5.5 presenta la propuesta que hace este trabajo, así como su puesta en práctica en la aplicación en Rque expone el Capítulo 5. Por último, este trabajo aborda la tarea de elaborar un compendio biográfico sobre el problema del viajante, figura central sobre la que se asienta la propuesta de solución del problema de la reordenación de los mensajes ADS-B de un vuelo que trata este trabajo. El Capítulo 4 lo presenta, incluyendo los fundamentos teóricos, así como algunos de los algoritmos más destacados. En línea con el subobjetivo [OB-3.2] se analiza la mecánica de las heurísticas de mejora local más destacadas. 8.2. Aprendizaje personal En este epígrafe recojo unas breves notas sobre la experiencia personal que ha supuesto para mi la realización de este Trabajo Fin de Grado: Llevar a cabo este proyecto ha supuesto para mi una oportunidad para poner en práctica todos los conocimientos que he adquirido a lo largo de la carrera. Especialmente el obtenido en las asignaturas que tratan la Ingeniería del Software así como la programación en el marco de un proyecto. Por otra parte, ha resultado en una oportunidad personal para revisar ciertos lenguajes de programación que he tenido la oportunidad de aprender a lo largo de mi paso por la titulación. Algunos de ellos los he utilizado en repetidas ocasiones como Java, mientras que otros los he requerido menos a lo largo de la carrera, como R. He aprendido un nuevo modelo de programación, gracias al trabajo con MapReduce desde el punto de vista teórico, como práctico a través de la implementación llevada a cabo sobre este esquema. Por último, la redacción de esta memoria me ha ayudado a mejorar mis habilidades con el lenguaje para procesamiento de textos científicos L A TEX. 96 8.3. Líneas de trabajo futuro 8.3. Líneas de trabajo futuro Para poner punto y final a esta memoria, quedan señaladas a continuación una serie de aspectos que han quedado fuera del alcance de este Trabajo Fin de Grado y que definen las futuras actividades a llevar a cabo sobre el proyecto. Integración completa de la implementación escalable sobre la plataforma bigdata de gestión del tráfico aéreo objetivo del proyecto AIRPORTS, a fin de que pase a formar parte de su lógica interna. En este sentido, la aplicación haría su función durante el procesado de los datos de una trayectoria, donde en primer lugar se ejecutaría una reordenación mediante el algoritmo 2-Opt para posteriormente corregir las marcas temporales de los mensajes. Desarrollo completo del componente de acceso a datos de la implementación escalable, así como de la aplicación que alberga el estudio comparativo de los métodos de resolución (ver Capítulo 5). En la actualidad figura un acceso a datos rudimentario que consiste en la lectura de uno o varios ficheros csv de una carpeta prefijada. Los pasos siguientes a llevar a cabo en esta materia consisten en la implementación de un acceso a las bases de datos de las distintas fuentes de datos en crudo. Sobre el punto anterior, la aplicación del Capitulo 5 podría albergar el seguimiento de los vuelos en tiempo real, una vez tenga implementado el acceso a las bases de datos de distintas fuentes como OpenSky oFrambuesa. De esta manera, sería posible la monitorización por parte del usuario a través del dashboard de las distintas trayectorias en directo. Por su parte, el acceso a datos sobre la implementación escalable permitiría el desarrollo de una nueva pieza de la funcionalidad que jugaría un papel fundamental: la corrección en caliente de las desórdenes que se produzcan en los mensajes ADS-B nada más son recibidos por una de las fuentes de datos. Para esto, el sistema podría ejecutar reordenaciones periódicas sobre los últimos mensajes (utilizando la técnica de ventanas para hacer más eficientes las ejecuciones) de la trayectoria en curso, corrigiendo posteriormente las marcas temporales en caso de producirse un error. En cuanto al modelo teórico de que se plantea para la reordenación de los mensajes ADS-B de una trayectoria, el siguiente paso a realizar podría consistir en aumentar su complejidad añadiendo el valor de altitud de la aeronave a la hora de calcular la distancia entre puntos. Esto aumentaría la eficacia del método así como un menor riesgo de error en los casos en que se requieren complejas maniobras de aterrizaje del piloto, y que a veces incluyen rodear el aeropuerto repetidas veces, para los que el modelo actual no se adapta correctamente. Por otro lado, el modelo de corrección de timestamps puede ser mejorado añadiendo nuevos parámetros al modelo como la marca temporal de más puntos o un planteamiento más complejo del modelo que plantee la corrección de los timestamps como 97 Capítulo 8. Conclusiones un problema de optimización. En este sentido, podrían llevarse a cabo técnicas de resolución comunes para este tipo de problemas como la programación lineal. 98 Bibliografía J. Ahumada. Versión en español de R for beginners. Emmanuel Paradis, 2002. A. Alonso Isla, P.C. Alvarez-Esteban, A. Bregón, F. Díaz, I. García Miranda, P. Gordaliza, y M. Martínez-Prieto. Airports: Análisis de eficiencia operacional basado en trayectorias de vuelo. JISBD, 2018. P.C. Álvarez Esteban, A. Bregón, F. Díaz, I. García Miranda, y M. Martínez Prieto. Towards a scalable architecture for flight data management. DATA 2017 - 6th International Conference on Data Science, Technology and Applications, pages 263–268, 2017. G. Babin, S. Deneault, y G. Laporte. Improvements to the or-opt heuristic for the symmetric traveling salesman problem. The Journal of Operational Research Society. Vol. 58, No. 3, pages 402–407, 2007. B. Chandra, H. Karloff, y C. Tovey. New results on the old k-opt algorithm for the traveling salesman problem. SIAM Journal on Computing, 1999. W.J. Cook. In Pursuit of the Traveling Salesman. Princeton University Press, 2012. Jeffrey Dean y Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107–113, 2008. M. Englert, H. Röglin, y B. Vöcking. Worst case and probabilistic analysis of the 2-opt algorithm for the tsp. SODA ’07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1295–1304, 2007. Eurocontrol. Flight movements and service units 2017-2023. Technical report, Eurocontrol, Febrero 2017. Disponible en :https://www.eurocontrol.int/sites/default/files/content/documents/officialdocuments/forecasts/seven-year-flights-service-units-forecast-2017-2023-Feb2017.pdf. A. González y S. González. Versión en español de An introduction to R. R Development Core Team, 2000. Y. Grushka-Cockayne y B. De Reyck. Towards a single european sky. Interfaces, 39: 400–414, 2009. 99 Bibliografía G. Gutin y A. P. Punnen. The Traveling Salesman Problem and its variations. Springer, 2007. B. Juricic, T. Bucak, y I. Francetic. Automatic dependent surveillance (ads). Promet - Traffic - Traffico, 14:111–115, 2002. B. Korte y J. Vygen. Combinatorial Optimization, Theory and Algorithms. Springer, 2006. G. Laporte. The traveling salesman problem: An overview of exact and approximated algorithms. European Journal of Operational Research, 59:231–247, 1992. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, y D.B. Shmoys. The Traveling Salesman Problem. Wiley, 1992. M.A. Martínez Prieto, Bregon A., I. García Miranda, Álvarez Esteban, P.C. Díaz F., y D. Scarlatti. Integrating flight-related information into a (big) data lake. 2017 IEEE/AIAA 36th Digital Avionics Systems Conference (DASC), 2017. 100 Apéndice A Contenido del CD y manuales de las aplicaciones A.1. Contenido del CD El disco en formato CD-R anexo a la presente memoria, adjunta las dos aplicaciones objeto de desarrollo del proyecto. Por un lado, se incluye la aplicación expuesta en el Capítulo 5, que alberga el estudio comparativo de las técnicas de resolución del problema del viajante aplicadas a la reordenación de los datos de seguimiento de trayectorias de aeronaves. El contenido de esta aplicación se encuentra en el archivo comprimido ProyectoR.zip. Por otro lado, se encuentran los ficheros asociados a la implementación escalable en MapReduce del modelo de reordenación y posterior corrección del timestamp de los mensajes planteado en esta memoria. Todos los archivos de esta parte se encuentran en MapReduceTrayectoriasKOpt.zip Figura A.1: Contenido del CD 101 Apéndice A. Contenido del CD y manuales de las aplicaciones El contenido del CD se ilustra en la Figura A.1, donde junto al contenido de los dos programas anteriores se incluye la presente memoria en formato pdf. Por un lado, en el fichero ProyectoR.zip se encuentran los ficheros de la aplicación sobre R, descrita en el Capítulo 5 de la presente memoria. Figura A.2: Contenido de la carpeta ProyectoR La Figura A.2 muestra el contenido de la carpeta del proyecto, la cual contiene otras dos carpetas. Por un lado, la carpeta R-Portable, que incluye los ficheros asociados al lenguaje de programación R, y que permiten la portabilidad de la aplicación sin necesidad de ejecutarse sobre un sistema con Rinstalado. Por otro lado, en shiny se incluyen los ficheros que componen la aplicación (ver Figura A.3). Figura A.3: Contenido de la carpeta shiny La carpeta Vuelos contiene los ficheros csv con los vuelos a los que puede acceder la 102 A.2. Manuales aplicación. Por su parte, las carpetas www y source contienen ficheros secundarios de la aplicación. El código de la aplicación se encuentra en el fichero app.R de shiny. Por su parte, en el fichero MapReduceTrayectoriasKOpt.zip se encuentra la estructura de directorios de la implementación escalable expuesta en el Capítulo 5. La Figura A.4 muestra su contenido. Figura A.4: Estructura de directorios de la implementación escalable Las clases de la aplicación se encuentran en la carpeta src, donde está contenido todo el código de la aplicación. El resto de carpetas y ficheros son secundarios para el funcionamiento de la aplicación. A su vez, el archivo IBE04HT-IBE05DK.csv es un ejemplo de fichero que puede tomarse como entrada para la aplicación. A lo largo de la siguiente sección se exponen los manuales de ambas aplicaciones, incluyendo los manuales de instalación, con las instrucciones básicas de puesta a punto de cada una de ellas. A.2. Manuales En esta sección se incluyen los manuales de usuario y de instalación de las dos aplicaciones presentadas a lo largo de esta memoria. En primer lugar se presentan los manuales de instalación de cada uno de los programas. Posteriormente se presentan los manuales de uso, para los usuarios finales. 103 Apéndice A. Contenido del CD y manuales de las aplicaciones A.2.1. Manuales de instalación A continuación se incluyen las instrucciones básicas para efectuar la instalación de los programas incluidos en el CD. Primero se expone el manual relativo a la aplicación que trata el Capítulo 5, y finalmente la implementación escalable del Capítulo 7. Aplicación que alberga el estudio comparativo La aplicación, desarrollada para estudiar la adecuación de algunos de los más importantes algoritmos de resolución del TSP aplicados a la reordenación de los datos de seguimiento de una trayectoria, no está pensada para ser de uso público, sino restringido al personal del presente proyecto, por lo que la aplicación es de escritorio para ser instalada sobre los ordenadores personales de cada miembro del proyecto. Los requisitos previos para poder ejecutarse la aplicación son: Sistema operativo: Windows Vista,7, 8 o 10. Memoria RAM: un mínimo de 1 GB Para ejecutar el programa, el usuario debe entrar en ProyectoR y hacer doble click sobre el fichero run.bat, que no es más que el ejecutable de la aplicación. Tras esto, se ejecutará un terminal de Windows durante unos segundos (ver Figura A.5) Figura A.5: Terminal desplegado tras ejecutar el fichero run.bat Tras una breve espera se abre el navegador fijado en el sistema como predeterminado con la pantalla inicial de la aplicación, tal y como se muestra en la Figura A.6. 104 A.2. Manuales Figura A.6: Pantalla de inicio de la aplicación Los datos de vuelos con los que trabaja la aplicación proceden de los ficheros csv contenidos en la carpeta ProyectoR/shiny/Vuelos del CD. Al comenzar, la aplicación lee el primero de los ficheros, y va accediendo al resto en función de las necesidades del usuario. Para terminar la ejecución de la aplicación basta con cerrar la pestaña del navegador en que se desplegó la aplicación. Implementación escalable Para poder ejecutar la implementación escalable se han identificado los siguientes requisitos: Disponer de Cloudera, que integra las librerías de Apache Hadoop Java JDK 1.7 o superior IDE Eclipse Luna El sistema operativo Cloudera se puede adquirir desde su sitio web oficial https: //es.cloudera.com/ (ver Figura A.7). 105 Apéndice A. Contenido del CD y manuales de las aplicaciones Figura A.12: Controles en la parte central con widget Mapas seleccionado caso de haberse realizado esta operación. ◦En la gráfica tridimensional (opción “Mapa en 3D”) se permite al usuario mostrar la ordenación de los mensajes ADS-B (representados como puntos), a través de una línea que los une en función de su ordenación temporal. En caso de haber ejecutado una reordenación, el usuario podrá seleccionar la opción de visualizar tanto la reordenación como la ordenación original de los mensajes. ◦En la gráfica de distancia recorrida contra el timestamp (opción “Distancia vs Tiempo”) el usuario puede cambiar la coloración de los puntos. Esta gráfica solo aparece tras haber ejecutado una reordenación, pues el timestamp de los puntos cuyo orden temporal ha cambiado se ha corregido para adaptarlo al nuevo orden. Por defecto se muestran en verde aquellos puntos cuyo timestamp ha sido corregido, y en gris aquellos en que este dato ha permanecido estable, debido a que su orden no ha cambiado. Al accionar el control cambiar coloración los puntos se colorean en función de su altura asociada con un gradiente de colores. •Controles para esconder las gráficas de altura vs. tiempo y velocidad vs. tiempo. En Tabla, los controles están destinados a cambiar las filas de la tabla que se muestran en pantalla [RF-09, RF-10]. Los controles de esta pantalla se ilustran en la Figura A.14, y son los siguientes: 112 A.2. Manuales Figura A.13: Gráficas mostradas al seleccionar cada una de las pestañas del dashboard •Selector número de filas: permite aumentar o disminuir el número de filas de la tabla que se muestran por pantalla. •Campo de filtrado: permite realizar búsquedas sobre la tabla. El usuario introduce un valor y el sistema elimina aquellas filas en que ninguno de los campos 113 Apéndice A. Contenido del CD y manuales de las aplicaciones Figura A.14: Controles en la parte central con widget Tabla seleccionado contengan o se identifiquen con ese valor, de modo que el usuario puede filtrar aquellas filas que no sean de su interés. •Control reordenación por campo: el usuario puede hacer click sobre el nombre de cualquiera de las columnas de la tabla para reordenar las filas en base al valor de ese campo. Para invertir la ordenación (pasar de ser ascendente a descendente o viceversa), basta hacer de nuevo click sobre el nombre de la columna. •Navegación entre registros: cuando no se muestran todas las filas de la tabla, y ésta queda dividida en “páginas”, el usuario puede cambiar de una a otra a través de este control. Estas páginas están indexadas de modo que el usuario podrá seleccionar el número de página que desee para que se muestre por pantalla. En Pruebas se muestra un formulario que permite al usuario seleccionar los parámetros asociados a la prueba a ejecutar [CAR-2]. Los controles de esta parte se muestran en la Figura A.15 y son los siguientes: •Selector múltiple de vuelos: permite al usuario seleccionar los vuelos a considerar para la prueba. Mínimo uno [RF-13]. •Selector múltiple de algoritmos: permite al usuario elegir los algoritmos que se aplicarán para reordenar los vuelos seleccionados en el selector múltiple de vuelos. Cada algoritmo se aplicará una vez a cada vuelo. Al menos un algoritmo 114 A.2. Manuales debe ser seleccionado para poder ejecutar la prueba [RF-14]. •Opciones de ejecución: parámetro principal de la prueba. Permite al usuario elegir el modo de ejecución a aplicar [RF-12]. El usuario podrá elegir entre una ordenación utilizando la técnica divide y vencerás de reordenación presentada en la Subsección 5.4.1), de tamaño fijo o de dos tamaños diferentes para adaptarse a las zonas aeroportuarias del trayecto, o por el contrario, ejecutar la reordenación sin aplicar esta técnica. Si esta última opción no es la elegida, se muestran controles adicionales para configurar los distintos parámetros asociados a las ventanas. Estos controles se muestran en la Figura A.16. Son los siguientes: ◦Campo tamaño ventana en prueba: análogo al control tamaño ventana ejecución del menú lateral. ◦Slider solapamiento en prueba: análogo al control solapamiento entre ventanas de ejecución del menú lateral. ◦Campo altura en prueba: análogo al control campo de altura del menú lateral. ◦Campo tamaño ventana en vuelo: análogo al control tamaño ventana de ejecución del menú lateral al accionar el checkbox adaptar ventanas a aeropuertos. ◦Slider solapamiento en vuelo:análogo al control solapamiento entre ventanas de ejecución del menú lateral al accionar el checkbox adaptar ventanas a aeropuertos. ◦Campo tamaño ventana en aeropuerto: análogo al control tamaño de ventana en aeropuertos del menú lateral. ◦Slider solapamiento en aeropuerto: análogo al control solapamiento entre ventanas en aeropuertos del menú lateral. •Botón ejecución de la prueba: permite al usuario iniciar la batería de pruebas con los parámetros que haya elegido [RF-11]. Al menos debe haberse indicado un vuelo en selector múltiple de vuelos y un algoritmo en selector múltiple de algoritmos para poder ejecutarse la prueba. •Pestaña de resultados: permite al usuario navegar por las diferentes tablas de resultados mostradas tras ejecutar una batería de pruebas. •Botón descargar resultados: permite al usuario descargar el contenido de la tabla seleccionada en el control Pestaña de resultados en formato csv [RF-16]. 115 Apéndice A. Contenido del CD y manuales de las aplicaciones Figura A.15: Controles en la parte central con widget Pruebas seleccionado Figura A.16: Controles adicionales al seleccionar la opción “Utilizar ventanas de un mismo tamaño”, en la parte izquierda, o “Utilizar ventanas de distinto tamaño para aeropuertos”, en la parte derecha, en el control opciones de ejecución 116 A.2. Manuales Principales funciones realizables En esta sección se recogen las funciones más importantes de la aplicación describiéndose el conjunto de acciones realizadas por el usuario para poder llevarse a cabo. La aplicación se construye para estudiar el comportamiento de los distintos algoritmos de resolución del TSP aplicados a la reordenación de trayectorias. Es por tanto la funcionalidad principal de la aplicación la de ejecutar reordenaciones sobre vuelos que seleccione el usuario y utilizando los algoritmos a su elección. Además de la posibilidad de ejecutar una única reordenación sobre una ruta concreta y mostrar sus resultados a través de las diferentes gráficas y mapas que componen el dashboard, el usuario puede ejecutar una batería de pruebas que incluye la posibilidad de ejecutar varios algoritmos sobre uno o varios vuelos determinados, obteniendo resultados que permiten comparar el rendimiento de todas las reordenaciones. Así, se describen a continuación estas dos funcionalidades principales de la aplicación. Ejecutar una reordenación [CAR-1.1] A través de la aplicación, el usuario puede ejecutar una reordenación sobre un vuelo elegido a través de los controles presentes en el menú lateral del widget Mapas. La lista de pasos generales a seguir para llevar a cabo esta función es la siguiente: 1. Accionar la opción Mapas en el control Widgets del menú lateral. 2. Seleccionar el vuelo sobre el que ejecutar la reordenación de entre la lista de vuelos disponibles, en el control Selector de vuelo. 3. Seleccionar el algoritmo que se aplicará al ejecutar la reordenación de la lista de algoritmos disponibles, a través del control Selector de algoritmo. 4. Seleccionar los parámetros asociados a la ejecución de la reordenación mediante los controles Tamaño ventana de ejecución,Solapamiento entre ventanas de ejecución,Adaptar ventanas a aeropuertos y los controles adicionales del menú lateral si proceden. 5. Hacer click sobre el Botón ejecutar reordenación para realizar la reordenación. Como resultado, se redibujan los gráficos del dashboard para mostrar los datos asociados a la nueva ordenación de los mensajes ADS-B de la trayectoria. Ejemplo: realizar una reordenación del vuelo IBE04NL usando el Simulated Annealing apoyado por el algoritmo de inserción más barata para obtener una ruta inicial, aplicando la técnica de uso de ventanas de un único tamaño máximo 130 puntos y solapamiento entre ventanas de 25 puntos. A continuación se lista la secuencia de pasos a seguir, ilustrada en la Figura A.17. 1. Accionar la opción Mapas en el control Widgets (por defecto seleccionada). 2. Seleccionar el vuelo IBE04NL en el control Selector de vuelo. 117 Apéndice A. Contenido del CD y manuales de las aplicaciones Figura A.17: Secuencia de pasos a realizar para llevar a cabo la función Ejecutar una reordenación 3. Seleccionar el algoritmo de reordenación Simulated Annealing a través del control Selector de algoritmo. Una vez hecho esto se mostrarán los controles adicionales asociados a este algoritmo (ver Figura A.10). 4. Seleccionar Inserción más barata en el control Selector de algoritmo de partida. 5. Fijar el valor 130 en el control Tamaño de ventana de ejecución. 6. Fijar el valor 25 en el control Solapamiento entre ventanas de ejecución. 7. Hacer click sobre el Botón ejecutar reordenación. Ejecutar una batería de pruebas [CAR-2.1] Además de la ejecución de una única reordenación, el usuario puede ordenar la ejecución de una batería de reordenaciones aplicadas a varios vuelos que el usuario elija y 118 A.2. Manuales haciendo uso a la carta de los algoritmos de reordenación disponibles en la aplicación. La secuencia de pasos a llevar a cabo para realizar esta función es la siguiente: 1. Accionar la opción Pruebas en el control Widgets del menú lateral. 2. Seleccionar los vuelos sobre los que ejecutar la reordenaciones de entre la lista de vuelos disponibles, en el control Selector múltiple de vuelos. 3. Seleccionar los algoritmos que se desean aplicar a las trayectorias elegidas en el paso anterior, de la lista de algoritmos disponibles, a través del control Selector múltiple de algoritmos. 4. Seleccionar la técnica de reordenación a llevar a cabo en el control Opciones de ejecución. 5. Si procede, seleccionar los parámetros de ejecución en el resto de campos del formulario (ver Figura A.16). 6. Hacer click sobre el Botón ejecución de la prueba para comenzar la batería de reordenaciones. Como resultado, se muestra un nuevo componente en la zona inferior de la parte central de la pantalla que muestra las métricas asociadas a la prueba ejecutada, así como nuevos controles que permiten al usuario navegar entre los distintos datos que se muestran en pantalla. Ejemplo: realizar una batería de pruebas sobre los vuelos IBE04HT e IBE0519 usando los algoritmos 2-Opt e Inserción arbitraria, aplicando la técnica de uso de ventanas de dos tamaños con un máximo de 100 puntos en vuelo y solapamiento entre ventanas de 25 puntos, y un tamaño máximo de 20 puntos en vuelo y 5 puntos de solapamiento. Considerar una altura de 6000 para separar entre un tipo y otro de ventana. A continuación se lista la secuencia de pasos a seguir, ilustrada en la Figura A.18. 1. Accionar la opción Pruebas en el control Widgets (por defecto seleccionada). 2. Seleccionar los vuelos IBE04HT yIBE0519 en el control Selector múltiple de vuelos. 3. Seleccionar los algoritmos 2-Opt eInserción arbitraria en el control Selector múltiple de algoritmos. 4. Seleccionar en el control Opciones de ejecución la casilla “Utilizar ventanas de distinto tamaño para aeropuertos”. A continuación aparecerán los controles adicionales específicos de este tipo de ejecución (ver parte derecha de la Figura A.16). 5. Fijar el valor 6000 en el control Campo altura en prueba. 6. Fijar el valor 100 en el control Campo tamaño ventana en vuelo. 7. Fijar el valor 20 en el control Slider solapamiento en vuelo. 8. Fijar el valor 20 en el control Campo tamaño ventana en aeropuerto. 119 Apéndice A. Contenido del CD y manuales de las aplicaciones 9. Fijar el valor 5 en el control Slider solapamiento en aeropuerto. 10. Hacer click sobre el Botón ejecución de la prueba. Figura A.18: Secuencia de pasos a realizar para llevar a cabo la función Ejecutar una reordenación Implementación escalable En el caso de la implementación escalable, se adjunta un breve manual de usuario con sus posibilidades de uso. La aplicación toma como entrada los parámetros indicados al main() antes de ejecutar. Éstos, se introducen separados por un espacio en blanco y en el orden siguiente: Fichero de entrada (String): ruta del fichero csv de entrada de datos. Directorio de salida (String): ruta donde se colocará el directorio con los resultados de la ejecución. Modo de ejecución (int): determina el uso o no de la técnica de las ventanas de ejecución (ver Subsección 5.4.1) para llevar a cabo la reordenación. Admite tres valores: •0: no se utiliza la técnica de las ventanas de ejecución. Se ejecuta el algoritmo k-Opt una vez por trayectoria. 120 A.2. Manuales •1: se utiliza la técnica de las ventanas de ejecución con un único tamaño máximo y solapamiento. •2: se utiliza la técnica de las ventanas de ejecución con dos tamaños máximo y solapamiento distinguiendo entre aeropuertos y zona central del vuelo. Valor de k (int): algoritmo k-Opt a ejecutar, con k≥2. Ejemplo: con k= 2 se ejecuta el 2-Opt, con k= 3 se ejecuta el 3-Opt, etc. Tolerancia (int): fija el número máximo de k-changes a probar sobre una ruta sin producirse ninguna mejora. Es un entero no negativo, y al introducirse con valor 0 se entiende que no hay límite de k-changes a probar, y por tanto, se prueban todos los posibles. Tamaño en vuelo (int): tamaño máximo de las ventanas que se usarán en la técnica de las ventanas de ejecución si el parámetro modo de ejecución es 1, o en la parte central del vuelo si el parámetro modo de ejecución es 2. Es un entero mayor que 2. Solapamiento en vuelo (int): solapamiento que se aplicará en la técnica de las ventanas de ejecución si el parámetro modo de ejecución es 1, o solo en la parte central del vuelo si el parámetro modo de ejecución es 2. Es un entero no negativo menor que el valor introducido en el parámetro tamaño en vuelo. Tamaño en aeropuertos (int): tamaño máximo de las ventanas que se usarán en la técnica de las ventanas de ejecución en la primera y última parte del vuelo si el parámetro modo de ejecución es 2. Es un entero mayor que 2. Solapamiento en aeropuertos (int): tamaño máximo de las ventanas que se usarán en la técnica de las ventanas de ejecución en la primera y en la última parte del vuelo si el parámetro modo de ejecución es 2. Es un entero no negativo menor que el valor introducido en el parámetro tamaño en aeropuertos. Altura (double): valor de altura que permite dividir la trayectoria en tres partes. El primer punto y el último que superen dicho valor serán los límites de la parte central del vuelo. Al ejecutar la aplicación se lleva a cabo la separación de los registros por su valor de leg, la reordenación de los grupos de mensajes ADS-B resultantes y la posterior corrección de los timestamps. Como salida se obtiene un directorio de resultados en la ruta indicada por el usuario en el parámetro directorio de salida. 121