Análisis del problema de rotación de aviones para una compañía mediana

Equation Chapter 1 Section 1 Trabajo Fin de Máster Máster Universitario en Ingeniería Aeronáutica Análisis del problema de rotación de aviones para una compañía mediana Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Autor: Tomás Sánchez Sánchez Tutor: José María del Castillo Granados Dep. Ingeniería y Ciencia de los materiales y del Transporte Escuela Técnica Superior de Ingeniería Sevilla, 201 8 iii Trabajo Fin de Máster Máster Universitario en Ingeniería Aeronáutica Anáisis del problema de rotación de aviones para una compañía mediana Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Autor: Tomás Sánchez Sánchez Tutor: José María del Castillo Granados Profesor titular Dep. de Ingeniería y Ciencia de los materiales y del Transporte Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 v Trabajo Fin de Máster: Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Autor: Tomás Sánchez Sánchez Tutor: José María del Castillo El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2018 El Secretario del Tribunal vii Agradecimientos Agradecerselo a mis padres y a mi hermano que han estado ahí siempre que lo he necesitado. Este es el principio de una nueva etapa de mi vida, conseguido con esfuerzo y trabajo. Agradecer también a José María del Castillo la oportunidad de profundizar en el mundo del transporte aéreo, así como la ayuda recibida en su realización. Gracias por todo. ix Resumen El objetivo del presente trabajo es mostrar un algoritmo de resolución del método ‘Aircraft Routing’. Es decir, la finalidad es obtener las rotaciones que realizarán los aviones de una determinada compañía para poder realizar todos los vuelos programados sin repetir ninguno, optimizando las funciones objetivo que sean requeridas. Además, se mostrarán ejemplos con empresas y horarios reales. Finalmente, se realizarán retrasos y adelantos en los horarios de los vuelos para observar el efecto que estos tendrían en las rotaciones obtenidas, y las posibles mejoras que estos acarrearían. xvii ÍNDICE DE FIGURAS Figura 1: Obtención de datos, referencia [1] 1 Figura 2: Diagrama de conexión entre aeropuertos 2 Figura 3:Rotación de 1 día 3 Figura 4:Rotación de 2 días 3 Figura 5: Posición sectorial de Canaryfly, 2017, [8] 7 Figura 6: Posición nacional Volotea, 2017, [7] 8 Figura 7: Ejemplo de sistema con B = 2 y C = 6 12 Figura 8: Nombres en hojas de Excel 13 Figura 9: Acción de importar datos en Matlab 14 Figura 10: Selección de datos para importarlos a Matlab. 14 Figura 11: Código ejecutable de datos de importación 15 Figura 12: Importancia de T en las rotaciones, ejemplo 15 Figura 13: Ejemplo de dos salidas posibles frente a 3 totales 16 Figura 14: Ejemplo de combinaciones entre aeropuertos 17 Figura 15: Algoritmo de emparejamientos 18 Figura 16: Ejemplo 1 de rutas Canaryfly 20 Figura 17: Ejemplo 2 rutas Canaryfly 21 Figura 18: Ejemplo 3 rutas Canaryfly 21 Figura 19: Ejemplo 4 rutas Canaryfly 22 Figura 20: Ejemplo 1 rutas Volotea, día 13 23 Figura 21: Ejemplo 2 rutas Volotea, día 13 23 Figura 22: Ejemplo 3 rutas Volotea, día 13 24 Figura 23: Ejemplo1 rutas Volotea, día 14 24 Figura 24: Ejemplo 2 rutas volotea, día 14 25 Figura 25: Ejemplo 1 rutas Volotea, día 15 25 Figura 26: Ejemplo 1 rutas Volotea, día 16 26 Figura 27: Aparición de vuelos en todas las rotaciones, Canaryfly 29 Figura 28: Aparición de vuelos en rotaciones, día 1 (13 noviembre), Volotea 30 Figura 29: Aparición de vuelos en rotaciones día 2 (14 noviembre), Volotea 31 Figura 30: Aparición de vuelos en rotaciones, día 3 (15 noviembre), Volotea 31 Figura 31: Aparición de vuelos en rotaciones día 4 (16 noviembre), Volotea 32 Figura 32: Rotaciones de 2 días. 33 Figura 33: Aparición de vuelos en rotaciones de 2 días, día 1(13 noviembre), Volotea 34 Figura 34: Aparición de vuelos en rotaciones de 2 días, día 2(14 noviembre), Volotea 35 Figura 35: Aparición de vuelos en rotaciones de 2 días, día 3(15 noviembre), Volotea 35 Figura 36: Aparición de vuelos en rotaciones de 2 días, día 4(16 noviembre), Volotea 36 Figura 37: Vuelos no realizados por ninguna rotación en combinaciones de 2 días, Volotea 36 Figura 38: Solución mostrada en la Tabla 7 42 Figura 39: Rotaciones Canaryfly sobre el mapa de Gran Canarias 42 Figura 40: Avión 1 y 4, Volotea sobre el mapa real, día 13 51 Figura 41: Avión 2 y 8, Volotea sobre el mapa real, día 13 52 Figura 42: Avión 1, Volotea sobre el mapa real, día 15-16 52 Figura 43: Combinaciones nuevas con T’ de valor 10 minutos, Canaryfly. 54 Figura 44: Combinaciones nuevas con T’ igual a 10 minutos, día 13, Volotea 55 Figura 45: Diagrama de flujo, etapas del algoritmo 58 Figura 46: Histograma, probabilidad de encontrar una rotación óptima entre el total, Volotea 59 Figura 47: Histograma, probabilidad de encontrar una rotación óptima entre el total, Canaryfly,F3 60 Figura 48: Histograma, probabilidad de encontrar una rotación óptima entre el total, Canaryfly, F2 61 Figura 49: Horarios de llegada, Canaryfly 67 Figura 50: horarios de salida, Canaryfly 68 xix Notación A Compañía de estudio B Nº de aeropuertos M Nomenclatura de un aeropuerto de salida N Nomenclatura de un aeropuerto de destino E Nomenclatura de un aeropuerto de destino,2 C Nº de vuelos entre aeropuertos i Nodo de salida j Nodo de llegada l Segundo nodo de llegada k Día de estudio S Matriz de salidas LL Matriz de llegadas CMmax Nº de asignaciones de un aeropuerto α Vector de salidas-llegada perteneciente a un nodo con más de una asignación T Tiempo de estancia en tierra LLR Matriz de rotación de llegada formado por dos nodos SR Matriz de rotación de salida formado por dos nodos LLF Matriz de rotación completa de llegada SF Matriz de rotación completa de salida RF Matriz de rotación completa a Nodos de asignación principal b Nodos de asignación secundaria LC Vector de posicionamiento de cambio de asignaciones CC Vector de valor de los nodos cambiados de asignación β Nodo de salida fijo γ Nodo de llegada fijo F Posición en el vector de rotación del último nodo de la rotación F Función objetivo RT Matriz de rotaciones con duración concreta kR Días de duración de la rotación de estudio X Variable de decisión, si se realiza o no una rotación en concreto r Nº de rotaciones total RI Matriz de restricciones de desigualdad P Nº de aviones disponible RD Matriz de restricciones de igualdad W Peso de la función objetivo 1 1 INTRODUCCIÓN n la industria del transporte aéreo, cobra especial importancia la mejora de los procesos, de cara a optimizar el movimiento de aeronaves por el espacio aéreo así como dar un servicio lo más eficiente posible al cliente. Por ello, a lo largo de los años se han desarrollados diversos métodos que permiten encontrar la solución que mejor se adapta a las necesidades de cada empresa, según los intereses de cada una. En el presente trabajo, se va a desarrollar el método de Aircraft Routing, se desglosará paso a paso mostrando como implementarlo en un software, en este caso Matlab. Además, se aportarán casos reales para poder entender con mayor facilidad el proceso seguido y el alcance del método. El método de Aircraft Routing se puede subdividir en los apartados expuestos a continuación, a partir de los cuales se desgranarán las diversas ecuaciones matemáticas usadas para obtener un resultado satisfactorio. 1. Obtención de datos. Para poder realizar el problema primero será necesario obtener datos reales de las salidas y llegadas de diversos vuelos correspondientes a una aerolínea en concreto. Siendo estrictos esto no pertenece al método de Aircraft Routing, sino que una vez se tienen la información de los vuelos, entonces puede empezarse a operar con dichos datos. Figura 1: Obtención de datos, referencia [1] E Introducción 2 2. Cálculo de rotaciones. Una vez conocidos los vuelos, se deberá ver si la concatenación de estos es posible. En caso afirmativo, se buscarán todas las combinaciones viables. Como resultado se tendrán todas las trayectorias reales posibles que puede realizar una aeronave con los horarios de la compañía de estudio. En la Figura 2 se muestra un ejemplo de conexión en un sistema de aeropuertos (A, B, C, D, E, …), donde habrá que tener en cuenta los horarios de los vuelos. E A B D AB DA C Figura 2: Diagrama de conexión entre aeropuertos 3. Selección de rotaciones según criterios impuestos por la empresa. Cada compañía ‘repite’ las rotaciones cada cierto número de días (1,2, 3…). Esto quiere decir que en el caso de que las rotaciones se repitan cada 2 días, por ejemplo, de todas las rotaciones calculadas en el apartado anterior, sólo se mantendrán aquellas cuyo destino final en la noche del día 2 sea el mismo que el origen de la mañana del día 1. El concepto ‘repite’ no es del todo exacto, pues la compañía puede, y de hecho es una práctica habitual, cambiar los horarios y los vuelos según el día y las necesidades. Lo que quiere decir es que una rotación de un día, la aeronave iniciará el día en un aeropuerto A y terminará el día, pasará la noche, en el mismo aeropuerto A. Para rotaciones de dos días, como ya se ha mencionado, la noche intermendia la pasará en un aeropuerto distinto del original. Las rotaciones de tres días, suelen ser combinación de las rotaciones de uno y dos días concatenadas. 4. Agrupación de rotaciones. Una vez se ha hecho una criba acerca de las combinaciones que satisfacen los requisitos de la empresa de estudio es necesario ver qué rotaciones, combinándolas entre sí permiten completar el mapa de vuelos, es decir, que conjunto de rotaciones permiten realizar todos los vuelos sin que se repita ninguno. Se obtendrán varias posibles combinaciones y todas son soluciones al problema. 3 3 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla BA C A DÍA 1; ROTACIÓN DE 1 DÍA El avión pasa la noche en A, SIEMPRE Figura 3:Rotación de 1 día ADA E H DÍA 1 DÍA 2 El avión pasa la noche en E Figura 4:Rotación de 2 días 5. Optimizar el resultado. Este apartado puede tener varias soluciones. Todo depende de lo que se quiera optimizar. Un objetivo puede ser que la empresa tenga ciertos aeropuertos base en los que prefiera que sus empleados pasen la noche, en lugar de en otros que sólo son escalas. Pues se asignarán diversas ponderaciones a cada rotación para ver de todas las combinaciones de rotaciones posibles, cuál mejora la solución al problema. Puede darse el caso de que halla más de un objetivo en cuestión. En dicho caso se obtendrá el máximo absoluto de la solución, o lo que es lo mismo, una solución que maximice (o minimice, según corresponda) el conjunto y no sólo una variable del problema. Tanto el apartado 4 como el 5 se harán de forma conjunta mediante el uso de métodos de programación lineal. 6. Proposición de mejora. Por último, se tiene un algoritmo que permite variar los horarios de los vuelos un determinado periodo de tiempo (se entiende que relativamente corto) y observar que cambios se producen en las posibles combinaciones de los vuelos. O sea, aconsejar posibles cambios que mejoren las posibilidades existentes de cara al futuro. 5 2 ESTADO DEL ARTE Como punto de partida se ha realizado un estudio de los procedimientos usados a día de hoy en este campo, así como los algoritmos más utilizados. Esto permitirá tener una visión global del problema al que nos enfrentamos en este trabajo y poder abordarlo con mayor criterio. Sin embargo, la intención no es emular otro algoritmo ya existente sino adquirir los conocimientos suficientes como para poder realizar un algoritmo propio de resolución del método de Aircraft Routing. La optimización de las rutas seguidas por las aeronaves de una compañía es un problema a la par importante y complejo, de manera que existen multitud de artículos versando sobre este tema. El objetivo de todos ellos es, con distintos métodos, obtener aquellas soluciones que sean óptimas en el menor tiempo posible de computación. Es importante entender que cuando una aeronave se queda en tierra durante más tiempo del necesario para repostar y dar entrada y salida a los pasajeros, es debido a que en el mismo se están realizando tareas de mantenimiento. En ( [2], [3]) , explica como este mantenimiento debe estar de acuerdo con la normativa de la FAA donde se distinguen comprobaciones de la aeronave mayores y menores, según la exhaustividad de las mismas. Aquellas que sean mayores requieren de mayor dedicación y obligan a la aeronave a permanecer en tierra más tiempo. El primero de estos chequeos suele hacer alrededor de una vez a la semana (66 horas de vuelo). A la hora de imponer horarios de vuelo habrá que tener en cuenta la restricción del mantenimiento, que obligará a mantener en tierra aviones, lo que supone pérdida de beneficios a la compañía, pues el objetivo es que un avión en concreto esté en vuelo el mayor tiempo posible. Para determinar el método de Aircraft Routing, al partir de unos horarios ya definidos, se supone que la compañía ha realizado un estudio previo para poder cumplir con dichos requisitos. Sin embargo, al igual que se plantea en ( [2], [3]), pueden existir tareas de mantenimiento no programadas. Por ejemplo, un impacto de pájaro que obliga a la aerolínea a mantener durante unos minutos extra a la aeronave. O incluso, sin necesidad de que sea un mantenimiento, puede haber retrasos debido a que los slots no se estén cumpliendo en un aeropuerto en concreto. Esto producirá un cambio en los vuelos en cadena, y en mayor medida si se trata de ‘Hubs’. Para ello, habrá que dimiensionar el sistema para que, aún habiendo ciertos retrasos, estos no se propaguen de manera incontrolada. Esto se consigue aumentando el tiempo T que tarda un avión entre su aterrizaje y el posterior despegue. Aquellas ventanas de despegue donde dicho tiempo T sea menor, podrán verse afectadas en mayor medida, aunque pueden disiparse si en una rotación en concreto existen tiempos mayores en otros vuelos posteriores que permitan acumular dicho retraso y no impactar en el desarrollo normal de la aerolínea. Este tiempo T contempla la bajada de pasajeros,la subida de los mismos así como las tareas de mantenimiento prevuelo que hay que cumplir para asegurar que todos los sistemas están a punto y no hay ningún defecto que impida la operatividad de la aeronave en cuestión. En [3] se muestra como en la función objetivo, a minimizar, se pueden usar parámetros a priori desconocidos que penalizan los retrasos. En el algoritmo de este trabajo se ha realizado un enfoque parecido jugando con el valor T. Cuanto mayor es dicho parámetro T globalmente en cada rotación, menor será la probabilidad de retrasos en los vuelos indicados. Como se indica en [4], en torno a un 30% de los vuelos que requieren un mayor tiempo de mantienimiento por motivos meteorológicos y de colas, se vieron retrasados en el tiempo, y hasta un 10% por más de un cuarto de hora, lo que quiere decir que controlar dicho tiempo T no es sencillo y fijarlo requiere de un estudio intensivo del sistema para comprobar como se puede propagar el retraso, sobre todo si los pasajeros necesitan hacer trasbordo en algún lugar. De ahí que si se puede conseguir que las rotaciones contemplen vuelos que permitan realizar todos sin necesidad de realizar trasbordos, o al menos, realizando el menor número de ellos, mejor. Para evitar estos retrasos, la mejor manera es añadir ‘buffers’ a aquellos vuelos que se conocen por experiencia que suelen sufrir más veces retrasos, así se aportará mayor estabilidad al sistema y sobre todo, se mejorará el servicio al cliente pues el principal objetivo es atraer a pasajeros que quieran volar en la compañía en concreto no solo una vez, sino cada vez que hagan uso del transporte aéreo. Obtención de datos 12 11:00 10:54 16:45 12:30 15:15 9:24 M N Figura 7: Ejemplo de sistema con B = 2 y C = 6 Si representamos un esquema general de la forma que adquirirán las matrices, se obtendrá el resultado mostrado en la ecuación (3-1). (4–1) Cuando no existe ningún vuelo entre los aeropuertos (i, j), al lugar de la matriz definido por la pareja se le dará un valor nulo (0). De antemano se puede inferir que cuando i = j, el valor será nulo pues no existen vuelos de M a M, un aeropuerto no puede operar consigo mismo. Demos el siguiente paso, recordemos que puede existir más de una salida y llegada entre M y N, o lo que es lo mismo, LLMN y SMN, tal y como la hemos definido, no es única, sino que poseería más de un valor. Por ello, se debe retomar la definición de nodo. Por simplicidad se usarán sólo los nodos de salida, pero se puede realizar el mismo desarrollo con los de llegada. Si se estudian los nodos obtenidos para un sólo aeropuerto M, se tienen la siguiente lista (M1-1, M1-2, …, M1-C1; Mi1, Mi2, …, Mi-Ci; MB1, MB2, …, MB-CB). Como se puede observar el número de nodos total (CM) de salida vendrá dada por la expresión (3-2). Donde 𝐶 representa el número de vuelos que habrá en una unidad horaria entre dos aeropuertos M y N. 𝐶  =  𝐶      (4–2) Si se observan las matrices de llegadas y salidas, cada fila de esta contendrá B-1 nodos como máximo (no B pues un aeropuerto no puede operar consigo mismo como ya se expuso anteriormente), con la salvedad de que por cada fila sólo puede haber un nodo asociado al par llegada-salida (M, N). Esto quiere decir que el número de filas necesarias para poder expresar los CM nodos es igual al máximo de Ci. El número de valores asignados a un aeropuerto M será entonces el dado por la expresión, Max (C1, C2, …, Ci, …, CB), así para cada aeropuerto. Sea CM-max al número de valores asignados al aeropuerto M, donde M=1, 2, …, B, entonces el tamaño real de las matrices de llegada y salida será el mostrado en (3-3), recordemos que son matrices cuadradas para cada unidad horaria k. Al ser una expresión matricial, se generarán nodos que realmente no existen, no todas las combinaciones (i, j) tienen vuelos, y por ello esos huecos se rellenarán con ceros (0). Se trata de matrices tridimensionales si lo que se requiere es el estudio de más de una unidad horaria. 13 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla (4–3) (4–4) En esta definición hay que matizar algunos detalles importantes. Supongamos un aeropuerto M que tiene asignados un conjunto de valores debido a que existe más de un vuelo diaria entre el mismo y otro aeropuerto del sistema. Aunque las salidas asociadas a cada fila sean distintas, pues ya se ha dicho que el objetivo de esta formulación es la repetición de vuelos entre un mismo origen y destino en la unidad horaria seleccionada, las llegadas deben ser las mismas. En definitiva, aunque sean valores distintos, todos están asociados al mismo aeropuerto, de manera que las llegadas a un nodo determinado deben ser las mismas. Si los valores de llegadas fueran distintos significaría que no se están contemplando las mismas llegadas para un mismo aeropuerto, y eso es una incongruencia. Esto implica que habrá cierta repetitividad en los datos, necesaria para que la formulación sea correcta. La formulación final se muestra en (3-5) donde α1 y α2 son vectores que indican la igualdad en las columnas correspondientes a un mismo aeropuerto. Se recalca que, aunque las columnas sean iguales, las filas deben ser distintas, pues ese es el objetivo final de la asignación múltiple de valores a un aeropuerto M. Cabe destacar que las matrices LL y S son tridimensionales, pues lo que se muestra aquí no es más que los horarios de vuelos para una unidad horaria determinada. La tercera dimensión contempla las unidades horarias que el usuario estime oportuno, es decir, la variable D designa el número de unidades horarias empleadas en el estudio. (4–5) 4.4. Caso práctico: Canaryfly y Volotea Una vez se ha definido la forma de ordenar los horarios de vuelos y designar a los aeropuertos de operación, se mostrará un caso real para su aplicación. Es en la pagina principal de las compañías donde se debe realizar la recopilación de datos, mostrándolos en Excel siguiendo las indicaciones dadas en apartados anteriores y por ello se pretende dar ejemplo por medio de Canaryfly para conocer en mayor medida el procedimiento. Ya se definió la empresa Canaryfly en apartados anteriores, (2.1). Los datos de vuelos se obtuvieron de la web de la empresa. Para organizar dichos datos de forma fácil, se realizará por medio de Excel, como ya se ha mencionado. El estudio se va a realizar para el mes de octubre de 2017 donde Canaryfly oferta los mismos horarios de vuelos para cada día del mes. De esta forma, las matrices S y LL serán más fáciles de montar pues la dimensión D es idéntica para cada unidad horaria, donde se ha escogido como unidad horaria 24 horas por simplicidad. Se recomienda ver los anexos donde se muestra cómo quedaría la matriz en Excel. Sin embargo, hay un matiz, y es que Matlab opera mucho mejor con decimales que en horas. Para ello Excel posee formulación a partir de la cual se puede pasar los minutos a decimal. Para ello, y con el objetivo de evitar confusiones, se muestra paso a paso como se ha hecho uso del archivo. 1. En un archivo Excel en blanco, se crean dos hojas distintas por cada unidad horaria que se pretenda estudiar. El nombre asignado a cada hoja es indiferente, por simplicidad se le asigna el del día de estudio y si está en decimal o en minutos. Figura 8: Nombres en hojas de Excel 2. En la hoja donde queramos indicar los horarios en minutos, se escriben las matrices LL y S en minutos Obtención de datos 14 tal y como se indica en los anexos. 3. En la hoja donde queramos indicar los horarios en decimales, se deberá tener especial cuidado en hacer coincidir las celdas de las matrices S y LL con las mismas matrices en minutos. Si no se hace así no ocurrirá nada, pero la posibilidad de inducirnos a error es muy elevada. Conviene ser metódicos para evitar posibles fallos. Una vez creado el marco de las matrices hay que rellenarlas con los datos correspondientes, en este caso sólo hay que transformar los datos en minutos a decimal. Si lo hemos hecho correctamente, los horarios de salida comenzarían en la celda B2. En dicha celda hay que escribir la formula indicada en (3-6). Es importante saber que 'S-LL(HORA)' cambia según el nombre que se le asigne a la hoja del apartado 2, es decir, la hoja con los horarios en minutos. (4–6) 4. Una vez están los datos en decimal, habrá que exportarlos a Matlab. Para ello, los datos serán guardados como una matriz numérica, pues se trata de horarios de vuelos. Además, se generará un Script para poder importarlos cuantas veces sea necesario en el caso de que se quiera modificar el Excel en algún momento durante el proceso. Figura 9: Acción de importar datos en Matlab Figura 10: Selección de datos para importarlos a Matlab. Matlab automáticamente generará las líneas de código correspondientes. En la Figura 11 se muestra como sería el código para importar los datos correspondientes a los horarios de llegadas para el día 15 de noviembre de 2017 para la compañía Volotea. Se resalta en rojo el lugar donde se indica las filas y columnas afectadas. Se podrá cambiar dichos valores según añadamos más filas y columnas al archivo de datos. Los puntos suspensivos indicarían la ruta del archivo en el ordenador, se ha eliminado para mayor claridad en la imagen. 15 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Figura 11: Código ejecutable de datos de importación Una vez se ha realizado para todas las llegadas y salidas, estas se unirán en una única matriz LL y S con la tercera dimensión correspondiente a las unidades horarias de estudio. 15 5 CÁLCULO DE ROTACIONES na vez se tienen los datos de llegadas y salidas podemos comenzar a operar con ellos. El primer objetivo del proceso es conocer las combinaciones que se pueden realizar entre vuelos sin que halla interferencias en los horarios. Como datos de entrada, sólo se requieren los horarios de salidas y llegadas obtenidos en el apartado anterior, (apartado 2, anexos), así como el tiempo que debe transcurrir desde que una aeronave aterriza hasta que despega. Esta última variable (T), cobra especial importancia pues es un dato que imponer y que dependerá de cada compañía. T puede variar según la empresa y según el tamaño de aeronave, y su valor puede determinar un cambio en las combinaciones posibles, de manera que es un valor para tener en cuenta. LLEGADA 17:00 SALIDA 17:25 Tiempo entre LLEGADA-SALIDA : 25 mins T< 25 mins OK T> 25 mins X Figura 12: Importancia de T en las rotaciones, ejemplo 5.1. Emparejamiento de vuelos En primera instancia, sólo visualizando las matrices de llegadas y salidas ya se conocen los pares origen-destino posibles en el problema. Aquellas celdas que posean un valor distinto a cero son una pareja posible. Sin embargo, hay que ir algo más allá. A continuación, lo que se buscarán son tríos de vuelos concatenados de manera que se puedan dividir en dos parejas, una de origen y otra de destino. Imaginemos que la combinación (3-7-15) es posible, donde 3,7,15 son los valores asignados a diversos aeropuertos de nuestro estudio. En tal caso tendremos la pareja de orígenes (3,7) y la pareja de destinos (7,15). Ahora bien, cómo se obtienen todas las parejas posibles mediante un algoritmo matemático. Sean dos aeropuertos M y N, donde entre M y N existe al menos un vuelo con su horario de salida y de llegada definido por la celda (i, j, k) tanto en S como en LL, donde k sólo refleja la unidad horaria en la que nos encontramos (si se trata de 24 h y k posee un valor de 3 significa que estamos en el tercer día de estudio, recordemos que las matrices LL y S eran tridimensionales). Habrá que buscar todas aquellas salidas que una vez haya aterrizado el vuelo entre M y N, tengan un horario de salida que supere el tiempo T desde la llegada del vuelo. Para poder evaluar todas las salidas posibles desde N se hará uso de la variable l que barrerá toda la columna correspondiente al aeropuerto N en cuestión (en el caso de que el aeropuerto tenga asignado más de un valor no ocurre nada pues no debemos olvidar que todas las columnas correspondientes a ese aeropuerto poseen los mismos horarios). Si este estudio no lo realizamos para la combinación M y N, sino para al sistema completo nos queda la expresión indicada en (4-1). Para programarlo no hay más que realizar cuatro bucles concatenados empezando por k, i, j, y finalmente l. Es importante saber que se debe cumplir que LL(i, j, k) ≠0, pues si fuera nulo podría ocurrir (de hecho ocurre) que la desigualdad se cumpla, pero es un error pensar que pueda ser una combinación posible pues si el valor de la celda de llegada es nulo significa que no existe tal llegada. (5–1) Si la desigualdad (4-1) se cumple, significa que la pareja (i, j) serán dos aeropuertos de origen y (j, l) serán dos aeropuertos de llegada. U Cálculo de rotaciones 16 16 LLEGADA N 17:00 SALIDA N 17:25 SALIDA N 17:10 SALIDA N 19:05 T=20 mins Figura 13: Ejemplo de dos salidas posibles frente a 3 totales Para poder almacenar toda la información relativa a rotaciones, es decir, las parejas origen destino posibles, habrá que usar variables al efecto, que se llamarán LLR y SR. Estas variables se inicializarán como conjuntos vacíos e irán aumentando de tamaño conforme se encuentren pares (i, j) y (j, l) que cumplan con los criterios de unión. 𝐿𝐿𝑅 =  𝑖  , 𝑗  𝑖  , 𝑗  … …  (5–2) 𝑆𝑅 =  𝑗  , 𝑙  𝑗  , 𝑙  … …  (5–3) El caso mostrado en la Figura 14 enseña como existirían para el par de valores i=5 y j=1, cuatro pares de rotaciones salida-llegada, o lo que es lo mismo, cuatro rutas formadas por tres aeropuertos. 𝑆𝑅 =  5 , 1 5 , 1 5 , 1 5 , 1  (5–4) 𝐿𝐿𝑅 =  1 , 3 1 , 4 1 , 6 1 , 7  (5–5) 17 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Posibles rutas l a partir de j=1 i=5 j=7 j=1 j=3 l=4 l=3 l=6 l=7 Figura 14: Ejemplo de combinaciones entre aeropuertos 5.2. Agrupación de emparejamientos Una vez agrupadas todas las opciones posibles habrá que combinarlas entre sí para obtener las secuencias más largas viables. Las iteraciones se realizarán para cada unidad horaria de forma independiente, esto quiere decir que la primera operación será un bucle en k, donde k irá desde 1 hasta D. Para poder llevar a cabo el algoritmo se hará uso de otras variables como LLF y SF. Inicialmente estas variables se les dará el valor del conjunto vacío, y se irán actualizando a medida que avancemos en el bucle. Se parten de los resultados obtenidos para SR y LLR. A priori sabemos que las columnas tienen un tamaño de 2, recordemos que eran emparejamientos, pero el objetivo es ir agrandando dichos emparejamientos de forma que se obtengan todas las rotaciones al completo. Para ello habrá que iterar, se indica el algoritmo seguido a continuación. Para poder iterar es necesario conocer el tamaño tanto de LLF y SF en cada iteración, que denominaremos (I,J). J indicará el tamaño de las rotaciones mientras que I muestra el número de rotaciones en el sistema. Ahora comienza la búsqueda de parejas que encajen entre sí. Para ello hacemos uso de dos índices (m, m2) que irán aumentando de valor desde 1 hasta I, es decir, hasta el tamaño de la matriz donde se han guardado los emparejamientos posibles. El objetivo es ver que parejas se pueden combinar para formar conjuntos más grandes. La variable m indica el emparejamiento que se está estudiando y la variable m2 indica la pareja con la que se está comparando. Si m = m2 entonces no se debe realizar comparativa alguna pues se trata de la misma rotación. Para visualizar mejor el proceso supongamos que tenemos dos pares de salidas y llegadas para una unidad horaria k en concreto. Donde βx indica un valor asignado a un aeropuerto de salida, y γx es idéntico, pero para aeropuertos de llegada. 𝑆𝑅 ( 𝑚 ) = [ 𝛽 (   ) , 𝛽 (   ) ] (5–6) 𝑆𝑅 ( 𝑚  ) = [ 𝛽 (    ) , 𝛽 (    ) ] (5–7) 𝐿𝐿𝑅 ( 𝑚 ) = [ 𝛾 (   ) , 𝛾 (   ) ] (5–8) Cálculo de rotaciones 18 18 𝐿𝐿𝑅 ( 𝑚  ) = [ 𝛾 (    ) , 𝛾 (    ) ] (5–9) En este caso se tiene que para que ambas rotaciones se pueden concatenar, se debe cumplir la ecuación (4-10). Es decir, cuando tenemos dos rotaciones formadas por tres aeropuertos, el aeropuerto final debe coincidir con el inicial de la otra rotación de comparación. 𝛽 (   ) = 𝛽 (    ) (5–10) 𝛾 (   ) = 𝛾 (    ) (5–11) Figura 15: Algoritmo de emparejamientos De esta forma se obtendría una rotación de 4 aeropuertos, o lo que es lo mismo, SF y LLF serán tríos de aeropuertos. 𝑆𝐹 ( 𝒆𝒏𝒅 + 1 , : ) = [ 𝛽 (   ) , 𝛽 (   ) , 𝛽 (    ) ] (5–12) 𝐿𝐿𝐹 ( 𝒆𝒏𝒅 + 1 , : ) = [ 𝛾 (   ) , 𝛾 (   ) , 𝛾 (    ) ] (5–13) La expresión ‘end +1’ implica que SF y LLF tendrán más rotaciones, y que cuando se encuentra una nueva esta se añadirá a las ya existentes, end indica la última fila. Los dos puntos indica que se trata de una columna entera y no un elemento en concreto. Además, se debe tener en cuenta que, a pesar de haber encontrado una nueva combinación más larga, no hay que descartar la combinación LLR(m) que estábamos estudiando pues, aunque sea una combinación más corta, para los intereses de una compañía no se puede saber a priori que es más beneficioso. Es decir, habrá que guardar en la variable LLF dicho valor. Al tratarse de una combinación más corta, y almacenarla en una matriz de mayor tamaño, a la combinación se le añadirá un cero al final. 𝑆𝐹 ( 𝒆𝒏𝒅 + 1 , : ) = [ 𝛽 (   ) , 𝛽 (   ) , 0 ] (5–14) 𝐿𝐿𝐹 ( 𝒆𝒏𝒅 + 1 , : ) = [ 𝛾 (   ) , 𝛾 (   ) , 0 ] (5–15) La rotación m2 no se incluye porque es la rotación de comparación, no de estudio, m barrerá todas las rotaciones existentes en LLR y SR. En el caso de que una vez realizado el barrido en m2 no haya ninguna combinación posible, no se hará acción alguna pues ya se ha almacenado la combinación m según (4-14, 4-15), es decir, esa combinación no puede concatenarse con ninguna otra. Este proceso se realizará para cada combinación, es decir, se habrá realizado un barrido completo a m. Sin embargo, una vez terminado de realizar dicho bucle, hay que saber si todavía pueden 𝛽 (   ) 𝛽 (   ) 𝛾 (   ) 𝛽 (    ) 𝛾 () 𝛽 (    ) 𝛾 (    ) 𝛾 () 19 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla realizarse más uniones entre combinaciones, pues solo tenemos hasta 4 aeropuertos, pero puede haber más. Para ello se hará uso de un bucle 'while', por medio del cual 'mientras' haya alguna combinación cuyo último valor sea distinto de cero, 0, significará que puede seguir combinándose. No debe olvidarse que, por medio del algoritmo realizado, siempre que una rotación no tiene combinaciones posibles se le añade un cero al final. Esto quiere decir que al final se debe acabar con un sistema de r rotaciones posibles o filas, y t+1 columnas, siendo t el tamaño de la combinación más larga. Haciendo referencia a la ecuación (4-12, 4-13), se puede ver como por cada vuelta que se de en el bucle 'while' el tamaño de las rotaciones máximo que se encontrará será de 3,4,6,10, ... Esto se debe a que siempre se comparan los dos últimos elementos de LLF y SF para m y los dos primeros para m2, y son el resto de los elementos los que difieren entre rotaciones concatenadas. Destacar que se usaran variables auxiliares para LLF y SF pues al inicio de cada bucle estas se reinician para almacenar las nuevas rotaciones. Aquellas rotaciones con un cero al final se seguirán rellenando de ceros para evitar problemas en las dimensiones de las matrices. Finalmente, teniendo en cuenta que se realiza un estudio separado para cada unidad horaria, habrá que cuadrar las matrices obtenidas cada día de manera que se rellenarán de ceros las filas y columnas necesarias para que todos tengan las mismas medidas y así obtener una matriz única y evitar el uso de k matrices diferenciadas. El hecho de que halla filas y columnas nulas de más no es inconveniente, y se usa sencillamente para evitar errores en la lectura del código porque las dimensiones matriciales no sean consistentes. Es decir se obtendrá una matriz final LLF(r, t+1, k) y SF(r, t+1, k) tridimensional. Tanto LLF como SF se unirán en una única matriz RF donde se almacenarán las rutas al completo y no sólo los nodos de salida y llegada. Esto no es más que sumar a SF el último valor de LLF que no sea nulo, y así se tendrá un conocimiento completo del total de las rotaciones posibles. 5.3. Eliminación de combinaciones repetidas Debido a la numeración seguida habrá ciertas combinaciones que salgan repetidas. Cuando un determinado aeropuerto tiene más de un valor asignado, esto se debe a que el número de salidas que tiene dicho aeropuerto no se pueden representar por medio de un único valor y por ello se asignaba más de uno al mismo aeropuerto. Sin embargo, como ya se vió, cuando el aeropuerto es el de destino, el tener más de un valor asignado lo único que aporta es la repetición de datos pues los horarios de llegada a un aeropuerto deben ser los mismos para todos sus valores asignados. En el caso de que el aeropuerto en cuestión sea un nodo intermedio, es decir, tenga un nodo anterior y otro posterior no es ningún inconveniente pues ese era el objetivo de la asignación múltiple de un aeropuerto, cada valor está asociado a un vuelo en concreto. Sin embargo, cuando el aeropuerto en cuestión es el último nodo de la rotación, es un nodo de sólo destino (en esa unidad horaria, en la siguiente será de sólo origen). Al ser un nodo de sólo destino, si el aeropuerto en cuestión tiene varios valores asignados, aparecerán combinaciones repetidas. Para ver mejor el por qué se expone un ejemplo. Supongamos un aeropuerto M que tiene asignados los valores 6,17,18, por ejemplo. Imaginemos una rotación posible del sistema,(4-16).Las tres combinaciones son posibles siguiendo el algoritmo descrito, sin embargo, son totalmente redundantes pues los valores 17 y 18 como último nodo no aportan información que permita generar una rotación nueva. Por ello, deberán ser eliminados, reduciendo considerablemente en algunos casos el número de rotaciones totales. Para evitar posibles errores en el tamaño de las matrices resultantes, las filas de rotaciones que deban ser eliminadas se rellenarán de ceros. [ 4 15 28 6 ] , [ 4 15 28 17 ] , [ 4 15 28 18 ] (5–16) 5.4. Aplicación a casos reales Los datos de entrada para poder realizar este apartado 4 son el tiempo entre llegadas y salidas para una aeronave (T), así como los horarios de los vuelos. Cálculo de rotaciones 26 26 Figura 26: Ejemplo 1 rutas Volotea, día 16 27 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla 6 DURACIÓN DE ROTACIONES na vez se han obtenido todas las rotaciones posibles para cada unidad horaria de estudio, es necesario escoger aquellas combinaciones que permitan resolver el problema según criterios impuestos por la compañía. Toda empresa suele operar de forma que los vuelos se repiten cada cierto tiempo, o lo que es lo mismo, partiendo de un aeropuerto de origen un día por la mañana y acabar tras un periodo de tiempo (un día, dos días, tres días, …) como destino final el mismo aeropuerto al final del ciclo. 6.1. Ciclo real y equivalente Hay que recordar que el estudio se realiza para cada unidad horaria por separado, sin embargo, una unidad horaria puede representar desde un día hasta varios días, en este caso representerán un día. De esta forma, la duración mínima de las rotaciones será una unidad horaria, según el tramo real que esta represente. Esto quiere decir que sólo se podrán obtener rotaciones proporcionales a la unidad horaria. Es decir, si la unidad horaria es de 48 horas, no se podrán conseguir rotaciones de 3 días, pues representan 72 horas que es 3/2 de la unidad horaria establecida. 6.2. Cambio de asignación Cuando un aeropuerto tiene más de un vuelo diario hacia un mismo destino, se le asigna más de un valor para poder definir todos los vuelos de manera inequívoca. Sin embargo, el hecho de que dos rotaciones tengan como valor inicial y final números distintos no quiere decir que se traten de aeropuertos distintos. Supongamos que el aeropuerto M tiene asignados los valores 6,17,18. En ese caso, todas las rotaciones que empiecen por 6,17,18, independientemente de los vuelos que contemplen, tienen el mismo origen. Para poder operar de forma congruente y que no haya problemas habrá que transformar dicha numeración. Como se ha indicado, los únicos nodos que interesan en este momento son el primero y el último en cada rotación. Sin embargo, el último nodo ya fue estudiado en apartados anteriores para evitar la repetición de rotaciones y no deberá ser reasignado. Todos los primeros nodos de todas las rotaciones deben ser estudiados para que, en el caso de un aeropuerto con más de una asignación posible, estos valores se transformen todos en un mismo valor, en el ejemplo anterior sería 6. Pero claro está, se deberán guardar los valores originales pues estos dan información acerca del nodo (recordemos que el valor 17 o 18 nos indicaban que se trataba de la fila 17 o 18 de la matriz de salidas y llegadas). A continuación, se muestra matemáticamente como se resuelve este paso. En primera instancia se introducen los valores de aquellos aeropuertos que tienen más de una asignación. Para ello introducimos una variable llamada a y otra b. Estos vectores deben tener el mismo tamaño y lo que indican es que para cada elemento en b correspondiente a un aeropuerto, hay otro elemento en a en la misma posición que indica el valor de asignación principal de dicho aeropuerto. Para Canaryfly (5-3, 5-4) y Volotea (5-1, 5-2) se tendrán los siguientes vectores. Los valores de Canaryfly son más repetitivos debido a la alta afluencia de vuelos entre los mismos aeropuertos que lleva a asignar múltiples valores a un solo aeropuerto. 𝑎  = [ 18 , 20 , 22 , 42 , 46 ] (6–1) 𝑏  = [ 19 , 21 , 23 , 43 , 47 ] (6–2) 𝑎  = [ 2 , 2 , 2 , 3 , 3 , 4 , 4 , 4 , 5 , 5 , 5 , 6 , 6 , 6 ] (6–3) 𝑏  = [ 7 , 8 , 20 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 ] (6–4) A continuación, se realiza un barrido para cada unidad horaria desde 1 hasta I, siendo I el número total de rotaciones. Si el elemento número uno de la rotación coincide con cualquiera de los valores en b, cuyos U Duración de rotaciones 28 28 componenetes se leen con el subíndice j, deberá ser sustituido por el valor correspondiente de a. Si 𝑅𝐹 ( 𝑖 , 1 , 𝑘 ) = 𝑏 ( 𝑗 ) 𝑖 = 1 , … , 𝐼 ; 𝑘 = 1 , … , 𝐷 (6–5) Entonces 𝑅𝐹 ( 𝑖 , 1 , 𝑘 ) = 𝑎 ( 𝑗 ) (6–6) Para no perder la información de los valores de b habrá que guardar que rotaciones han sufrido cambios para revertir los valores al final del proceso. Para ello se hace uso de una nueva variable llamada LC y CC, donde se guardarán las posiciones donde se han realizado los cambios y el número eliminado y añadido, respectivamente. Estas variables se irán actualizando de manera que todas las rotaciones que sufran cambios queden guardadas para posteriormente devolverlas a su estado inicial. 𝐿𝐶 ( 𝑒𝑛𝑑 + 1 ) = [ 𝑖 , 𝑘 ] (6–7) 𝐶𝐶 ( 𝑒𝑛𝑑 + 1 ) = [ 𝑏 ( 𝑗 ) , 𝑎 ( 𝑗 ) ] (6–8) Una vez realizados los cambios se puede proceder a realizar el estudio. 6.3. Rotaciones de 1 día Hay compañías, normalmente de tamaño reducido, que pueden y realizan los vuelos de manera que el aeropuerto de origen al inicio de un día es el mismo que el aeropuerto de destino al final de dicho día. En sí las rotaciones pueden ser distintas cada día, pero el lugar de origen y destino es el mismo al final del día. En este caso bastará con realizar un estudio por separado para cada unidad horaria, y escoger sólo las rotaciones que cumplen con el criterio indicado. De esta forma las posibilidades reales son inferiores al montante total de rotaciones posibles. Si se realiza dicho proceso de forma matemática, para ello habrá que evaluar las rotaciones. Habrá que tener en cuenta que, para evitar problemas de evaluación en Matlab, si una rotación tiene un tamaño inferior a la rotación mayor del sistema, entonces se habrá rellenado de ceros. Es decir, el último nodo de la rotación no tiene por qué coincidir con el último elemento de la fila. Puede ocurrir que la rotación sea la indicada en la ecuación (5-10), donde los ceros no son más que para evitar problemas de dimensiones y no aportan información. Cabe destacar que el símbolo ':' indica que se está evaluando la fila al completo. En este caso lo que interesa es el primer y el quinto nodo de la rotación pues como ya se ha dicho y se reitera, los ceros no aportan información. Para ello habrá que evaluar cada fila y escoger el valor F tal que el nodo correspondiente a dicha posición sea distinto a cero, pero el nodo correspondiente a F+1 sea nulo, ecuación (5-9). 𝐹 / 𝑅𝐹 ( 𝑖 , 𝐹 , 𝑘 ) ≠ 0 & 𝑅 𝐹 ( 𝑖 , 𝐹 + 1 , 𝑘 ) = 0 ; 𝑖 = 1 , … , 𝐼 ; 𝑘 = 1 , … , 𝐷 (6–9) 𝑅𝐹 ( 𝑖 , : , 𝑘 ) = [ 2 , 4 , 3 , 11 , 7 , 9 , 2 , 0 , 0 , 0 ] → 𝐹 = 7 (6–10) Una vez se ha calculado F se comprueba que se cumplen los requisitos para rotaciones de un día. 𝑅𝐹 ( 𝑖 , 1 , 𝑘 ) = 𝑅𝐹 ( 𝑖 , 𝐹 , 𝑘 ) ; 𝑖 = 1 , … , 𝐼 ; 𝑘 = 1 , … , 𝐷 (6–11) En caso afirmativo, se guardará la rotación y se seguirá en el bucle i hasta obtener todas las rotaciones que cumplen con el criterio. Una vez halla concluido el bucle, habrá que devolver los valores de inicio a sus asignaciones reales, es decir, habrá que hacer uso de las variables LC y CC. 6.4. Casos prácticos, rotaciones de 1 día 6.4.1. Canaryfly Canaryfly cumple la condición de ser una empresa de tamaño pequeño y además todos los días tiene los mismos horarios, de forma que la solución más probable es el uso de rotaciones de un día. Usando como dato de partida 29 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla los resultados obtenidos en RF escogemos aquellos cuyo aeropuerto de origen y de destino sea el mismo, siendo el resultado de 4273 rotaciones. Puede parecer un resultado elevado, pero las condiciones geográficas de operación de Canaryfly llevan a este fenómeno. Canaryfly opera todos sus vuelos, llegando hasta los 38, en horarios que suelen bajar de 1 hora de duración. Además, sólo opera en las Canarias, islas muy próximas entre sí lo que permite poder realizar diversas combinaciones. Para determinar cuales son las rutas más limitantes y las que poseen numerosas combinaciones, se representa un diagrama con las veces que aparece cada vuelo en las rotaciones. El mínimo numero de veces que aparece una rotación es 84 veces, y se trata de la combinación de 12 a 2, de Gran Canaria a Tenerife Norte. 84 veces es un número muy elevado, y evidencia el hecho de que Canaryfly tiene unas condiciones que, aunque sea una compañía pequeña, el número de rotaciones es muy grande. En la Figura 27 se evidencia como existen vuelos que se llevan a cabo un menor número de veces. Aquellas que aparecen nulas no son vuelos, se corresponden con los valores nulos de la matriz, es decir, que no existen vuelos entre dichos nodos. Lo que representa esta gráfica es el número de veces que se repite un determinado vuelo entre todas las rotaciones posibles. El eje ‘asignación de nodos’ hace referencia a los nodos de salida de un determinado vuelo (filas de la matriz S, LL), mientras que el eje ‘Aeropuertos’ hace referencia a los nodos de llegada (columnas de la matriz S, LL). Como se puede ver, el eje ‘Aeropuertos’ es más corto y porque se han eliminado aquellos nodos de llegada redundantes. Recordemos que cuando a un aeropuerto se le asigna más de un número, este sólo aporta información en la salida, pero no en la llegada. De esta forma en la posición (15,4) hay un valor de 123, lo que quiere decir que el vuelo de 15 hacia 4 se repite 123 veces en todas las rotaciones estudiadas. Figura 27: Aparición de vuelos en todas las rotaciones, Canaryfly 6.4.2. Volotea Aunque existen soluciones al caso de rotaciones de 1 día, y en conjunto no pueden resolver el problema al completo será de interés realizar el estudio en conjunto con rotaciones de dos días. Esto se debe a que Volotea es una empresa de considerable tamaño donde los vuelos no son diarios, sino que varían según convenga y es posible dar una solución para rotaciones diarias y no diarias en conjunto. Por ello, los resultados obtenidos se presentan a continuación. Se realiza el estudio para cuatro días de la semana Duración de rotaciones 30 30 (de lunes a jueves), por lo cual se obtendrá una matriz tridimensional (4 días) donde el máximo número de combinaciones es de 173, y se dan el lunes, donde el número de vuelos es considerablemente superior al del resto de días laborales (esxceptuando el viernes). Al igual que se hizo para Canaryfly, observaremos cuales son las rutas limitantes, partiendo de la base de que existirán rutas que no se alcanzarán a realizar por medio de estas rotaciones. Figura 28: Aparición de vuelos en rotaciones, día 1 (13 noviembre), Volotea Para el caso de Volotea, ocurre exáctamente igual. La diferencia estriba en que la asignación de valores para los aeropuertos prácticamente es una relación uno a uno, de manera que ambos ejes son similares. Al final, lo que quieren representar estas gráficas son el número de veces que se repite un determinado vuelo entre todas las rotaciones encontradas. Aquellos puntos de la matriz donde no hay nada, no tiene que implicar que no se realice el vuelo. Se puede tratar de combinaciones inexistentes, ceros en las matrices de salida y llegada. Estas gráficas son útilies pues permiten ver que vuelos serán más limitantes pues existen menos rotaciones que las realizan, o dicho de otra manera, que vuelos fijan más el sistema y obligan a realizar determinadas combinaciones. Por otro lado, aquellas columnas de maor tamaño, son los vuelos que se realizan un mayor número de veces, es decir, exiten multitud de rotaciones que tienen en cuenta dicho vuelo. Al final la gráfica lo que quiere mostrar es que aquellas columnas de mayor tamaño limitan menos el problema pero lo dejan más abierto, con mayor número de posibilidades mientras que las columnas más chicas son aquellas que restringen el problema y hacen que sea más sencillo buscar la solución correcta. Para el caso de Canaryfly, como se pudo ver, todos los vuelos se realizaban en multitud de rotaciones, lo que quiere decir que ninguna rotación en concreto fijaba el sistema y quedaba todo abierto, con la posibilidad de obtener optimizaciones en el sistema mayores que para Volotea, que tiene fijado gran parte de sus vuelos a muy pocas rotaciones posibles. Esto se debe, a que Volotea opera en un espacio mayor, lo que impide poder combinar con todos y cada uno de sus aeropuertos. 31 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Figura 29: Aparición de vuelos en rotaciones día 2 (14 noviembre), Volotea Figura 30: Aparición de vuelos en rotaciones, día 3 (15 noviembre), Volotea Duración de rotaciones 32 32 Figura 31: Aparición de vuelos en rotaciones día 4 (16 noviembre), Volotea Todos los vuelos se pueden llevar a cabo por medio de rotaciones diarias. Sin embargo, es interesante comparar que solución sería óptima. Si usar rotaciones de 1 día o 2 días, o una combinación de ambas. Este estudio se puede realizar y aportará información extra que permita alcanzar la solución que mejor se adapte al sistema. Como se verá más adelante, los días 13 y 14 las rotaciones de 1 día serán las óptimas mientras que los días 15 y 16 una combinación de todas será la mejor opción. Bien es cierto que se podría resolver con rotaciones de un día solamente, pero no aportaría información extra del estudio hecho con Canaryfly, y de esta forma se alcanzan nuevas soluciones y conclusiones. 6.5. Rotaciones de 2 días En este caso habrá que estudiar los días por parejas. De esta manera habrá que concatenar las rotaciones de dos días de forma que el aeropuerto de origen al inicio del día 1 sea el mismo que el aeropuerto de destino al final del día 2. La aeronave deberá pasar noche en algún aeropuerto del sistema, y en principio no se imponen restricciones al respecto. A continuación, se pretende explicar matemáticamente el algoritmo a partir del cual se lleva a cabo dicho procedimiento. Se supone que tenemos I rotaciones para el día 1 de estudio (día k) y J para el día 2 (día k+1), y que I≠J, ya que todos los días tengan las mismas rotaciones es poco probable. Habrá que ver si se pueden combinar entre sí dichas combinaciones. Para ello se realizará un barrido en i desde la rotación primera hasta la I del día 1. Cada i corresponde a una rotación del día 1. Para poder comparar con las rotaciones del día 2 se hará un segundo barrido en j desde 1 hasta J. Para que ambas rotaciones se puedan combinar se debe cumplir lo indicado en la ecuación (5-12, 5-13, 5-14). Donde F indica el último valor de la rotación de estudio, es decir, si una rotación está compuesta por cuatro nodos F tendrá un valor de 4. Es importante entender esto pues hay que recordar que RF tiene las dimensiones de la rotación más grande para evitar errores dimensionales y por ello F no tiene por qué ser el número de columnas total de esta matriz pues puede resultar que en alguna fila dicho valor sea un cero, o lo que es lo mismo, no sea un nodo y no estemos realizando el estudio correctamente. Los ceros se escribían para cuadrar las matrices, pero no aportaban información adicional. La tercera ecuación (5-14) indica que, si el aeropuerto de origen y de destino en el día uno son el mismo, no valdrá como opción pues eso sería dar uso de 33 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla las rotaciones de un día, obtenidas en la sección anterior. F posee sobíndice pues dependerá de la rotación de estudio y del día. 𝑅𝐹 ( 𝑖 , 1 , 𝑘 ) = 𝑅𝐹  𝑗 , 𝐹  ,    , 𝑘 + 1  ; 𝑖 = 1 , … , 𝐼 ; 𝑗 = 1 , … , 𝐽 ; 𝑘 = 1 , … , 𝐷 (6–12) 𝑅𝐹  𝑖 , 𝐹  ,  , 𝑘  = 𝑅𝐹 ( 𝑗 , 1 , 𝑘 + 1 ) (6–13) 𝑅𝐹 ( 𝑖 , 1 , 𝑘 ) ≠ 𝑅𝐹 ( 𝑖 , 𝐹  ,  , 𝑘 ) (6–14) En el caso afirmativo de que se cumplan dichos requisitos, habrá que guardar dichas rotaciones. Al tratarse de rotaciones de dos días, habrá que agrupar las rotaciones de forma coherente. Para ello, se hará uso de una nueva variable RT, donde se guardarán las rotaciones que cumplen el criterio de búsqueda. La rotación i correspondiente al día k y la rotación j correspondiente al día k+1 están concatenadas, de forma que generan una única rotación de dos días. Para indicar que forman una rotación deberán ser guardadas en la misma fila indicando que se trata de dos días distintos, para ello se añadirá un valor nulo entre ambas cadenas. 𝑅𝑇 ( 𝑒𝑛𝑑 + 1 ) = [ 𝑅𝐹  𝑖 , 1 : 𝐹  ,  , 𝑘  , 0 , 𝑅𝐹  𝑗 , 1 : 𝐹  ,    , 𝑘 + 1  ] (6–15) Al igual que en RF después será necesario añadir ceros al final de cada fila para que la matriz RT no tenga problemas de dimensiones. A B C A = C A ≠ B ______ B ≠ C ... ... Figura 32: Rotaciones de 2 días. 6.6. Caso práctico, rotaciones de 2 días 6.6.1. Canaryfly Se llevó a cabo el estudio para Canaryfly y se obtuvieron una cantidad de combinaciones posibles excesivamente elevada. Esto se debe a las condiciones expuestas anteriormente, y es que, al operar en un espacio tan reducido, esto permite aumentar las combinaciones entre vuelos. Al ser todos los horarios idénticos diariamente, nos lleva a concluir que Canaryfly opera con rotaciones de 1 día, realizar el estudio para 2 días llevaría un tiempo elevado y no aportaría información relevante, pues se existe la posibilidad de reducir el periodo de las rotaciones para que la tripulación duerma siempre en el mismo sitio. Duración de rotaciones 34 34 6.6.2. Volotea Para el caso de Volotea se llegó a la conclusión de que para obtener soluciones era necesario combinar rotaciones de 1 y 2 días, pues con sólo rotaciones de 2 días no se llegaba a una solución que englobara todos los vuelos. En apartados anteriores ya se indicó los resultados obtenidos para rotaciones de 1 día, se presentan los resultados para rotaciones de 2 días. Si se suman las soluciones obtenidas para 1 día y 2 días el problema queda completamente definido, si bien algunos vuelos sólo son realizados por una rotación en concreto, lo que llevará a que dichas rotaciones deben formar parte de la solución. Cabe destacar que, con las rotaciones de dos días, se alcanza a realizar un menor número de vuelos el lunes 13 que, con rotaciones de 1 día, esto se debe a la escasa cantidad de vuelos que se llevan a cabo el martes 14, sin ningún parecido con los realizados el lunes. Esto imposibilita llegar a una solución viable con rotaciones de dos días, pero en conjunto con rotaciones de un día puede ocurrir que las soluciones sean óptimas, en lugar de sólo usar un tipo de rotaciones. El tipo de rotación puede depender de la aeronave en concreto y no tiene por qué ser todo el sistema con el mismo tipo de rotaciones, sino que se da una mayor flexibilidad para adaptar los vuelos a la realidad y así ajustar los resultados lo más posible. Destacar que el día 15 de noviembre sí se realizan todos los vuelos con las rotaciones de dos días, pero como el día 16 no se llegan a realizar todos los vuelos, también harán falta rotaciones de un día para completar el sistema. Figura 33: Aparición de vuelos en rotaciones de 2 días, día 1(13 noviembre), Volotea 35 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Figura 34: Aparición de vuelos en rotaciones de 2 días, día 2(14 noviembre), Volotea Figura 35: Aparición de vuelos en rotaciones de 2 días, día 3(15 noviembre), Volotea Combinación de rotaciones 42 42 Figura 38: Solución mostrada en la Tabla 7 Si representamos el resultado de manera más visual, misma información que la Figura 38, donde las imágenes superiores representan los aviones 1 y 2 de izquierda a derecha y las inferiores los aviones 3 y 4. Los números indican el número de vuelo en la rotación en concreto. Si existen varios valores, como por ejemplo (1,2,3,4) significa que el primer, segundo, tercer y cuarto vuelo son entre esos dos destinos en concreto. Figura 39: Rotaciones Canaryfly sobre el mapa de Gran Canarias 43 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Como se puede ver la mayoría de aviones operan entre un conjunto de islas determinado realizando ida y vuelta sin parar. Esto hace que el sistema sea eficiente pues cada aeronave está especializada en una ruta en concreto, y también la tripulación. Sin embargo, a la hora de realizar trasbordo esto hace que los pasajeros deban abandonar el vuelo y coger otro avión si el objetivo es realizar el enlace con una isla determinada. 7.2.2. Volotea Para Volotea hay que recordar que, aunque existían soluciones para rotaciones de 1 día, pero no para rotaciones de 2 días, si se combinaban entre sí, se podía obtener una solución al sistema al completo. Al igual que para Canaryfly, se hará el estudio para las distintas funciones objetivo que han sido propuestas. Si se obtienen las soluciones relativas a usar el menor número de aviones posibles, se obtienen que para los días 13 y 14 con 19 aviones se podrían realizar los vuelos mientras que para los días 15 y 16 se podrían realizar todos los vuelos con 16 aviones. Si la compañía tiene 27 aviones en su flota es debido a que es una empresa que opera principalmente en temporadas turísticas y los vuelos invernales se ven reducidos sustancialmente, siendo el momento de realizar el mantenimiento de la mayoría de sus aeronaves. Tabla 8: Combinaciones para días 13,14, menor número de aviones posible, Volotea Aviones Rotaciones Avión 1 46 22 46 20 47 22 19 42 18 43 23 46 Avión 2 22 42 16 43 23 20 17 40 17 20 22 Avión 3 20 22 20 18 21 22 47 22 20 Avión 4 18 15 18 23 46 22 43 18 Avión 5 41 18 42 46 43 18 41 Avión 6 42 18 41 19 42 Avión 7 2 13 2 1 4 1 2 Avión 8 38 32 38 30 35 30 38 Avión 9 44 32 44 9 44 Avión 10 45 27 38 27 45 Avión 11 45 35 33 35 45 Avión 12 46 16 18 16 46 Avión 13 45 37 45 24 45 Avión 14 44 27 34 27 44 Avión 15 41 16 41 Avión 16 39 22 39 Avión 17 42 23 42 Avión 18 41 3 1 3 41 Combinación de rotaciones 44 44 Avión 19 2 6 2 Tabla 9: Combinaciones para días 15,16, menor número de aviones posible, Volotea Aviones Rotaciones Avión 1 20 18 15 18 20 22 20 18 21 23 20 Avión 2 42 16 43 18 42 46 42 22 42 Avión 3 46 22 47 22 20 22 46 21 46 Avión 4 18 43 23 42 16 43 18 Avión 5 42 18 16 46 47 22 19 42 Avión 6 46 16 18 41 18 23 46 Avión 7 41 19 42 18 41 Avión 8 32 38 31 38 32 Avión 9 23 46 22 Avión 10 38 32 38 Avión 11 44 32 44 Avión 12 45 35 45 Avión 13 2 11 2 1 4 1 2 Avión 14 45 41 45 35 45 Avión 15 41 16 41 Avión 16 44 32 44 Habrá que comprobar si existe conexión entre las rotaciones de los días 13, 14 y los días 15, 16. En este caso no es totalmente necesario pues la compañía posee más aviones, pero si es recomendable para que exista continuidad en los vuelos. Se puede ver como los vuelos están concatenados, salvo para el vuelo 16 (día 13) y el vuelo 8 (días 15 y 16). Es decir, para el total de los cuatro días se necesitarán en total 20 aviones como mínimo, de un total de 27 que es la flota. Como ya se ha mencionado, esto se debe a que en invierno el número de vuelos disminuye considerablemente con respecto a las campañas turísticas. Tabla 10: Combinación entre rotaciones de días distintos F1, Volotea Días 13, 14 Días 15, 16 Avión 3 Avión 1 45 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Avión 6, Avión 17 Avión 2 Avión 1, Avión 12 Avión 3 Avión 4 Avión 4 Avión 6, Avión 17 Avión 5 Avión 1, Avión 12 Avión 6 Avion 5, Avión 18 Avión 7 - Avión 8 Avión 2 Avión 9 Avión 8 Avión 10 Avión 9, Avión 14 Avión 11 Avión 10, Avión 11, Avión 13 Avión 12 Avión 7, Avión 19 Avión 13 Avión 10, Avión 11, Avión 13 Avión 14 Avión 5, Avión 15, Avión 18 Avión 15 Avión 9, Avión 14 Avión 16 Avión 16 - Si se realiza un estudio para obtener la solución con el menor número de noches posibles fuera de los aeropuertos base, se obtiene que es necesario usar los 28 aviones de la flota. Esto era predecible, pues cuantos más aviones, más pequeñas son las rotaciones y permiten controlar mejor los aeropuertos de origen y destino. Tabla 11: Combinación para los días 13, 14, menor número de noches fuera de los aeropuertos base, Volotea Aviones Rotaciones Avión 1 2 13 2 1 4 1 2 Avión 2 46 22 47 22 18 23 46 Avión 3 20 22 20 18 20 Avión 4 38 30 35 30 38 Avión 5 41 18 15 18 41 Avión 6 42 16 43 19 42 Avión 7 42 22 43 19 42 Avión 8 44 27 34 27 44 Combinación de rotaciones 46 46 Avión 9 44 32 44 9 44 Avión 10 45 27 38 27 45 Avión 11 45 35 33 35 45 Avión 12 45 37 45 24 45 Avión 13 46 16 18 16 46 Avión 14 21 23 20 Avión 15 38 32 38 Avión 16 39 22 39 Avión 17 41 16 41 Avión 18 42 22 42 Avión 19 42 46 42 Avión 20 46 20 46 Avión 21 42 18 43 22 43 19 42 Avión 22 20 17 40 17 20 Avión 23 41 3 1 3 41 Avión 24 2 6 2 Avión 25 20 22 20 Avión 26 41 18 41 Avión 27 46 22 46 Avión 28 47 23 46 Tabla 12: Combinación para los días 15, 16, menor número de noches fuera de los aeropuertos base, Volotea Aviones Rotaciones Avión 1 42 18 16 47 23 46 22 47 22 19 42 Avión 2 46 16 18 23 46 Avión 3 18 42 43 18 Avión 4 20 18 15 18 20 Avión 5 20 22 20 47 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Avión 6 32 38 32 Avión 7 41 18 41 Avión 8 42 16 42 Avión 9 43 19 42 Avión 10 43 23 42 Avión 11 44 32 44 Avión 12 45 35 45 Avión 13 46 22 46 Avión 14 20 22 20 18 21 23 20 Avión 15 2 11 2 1 2 Avión 16 1 4 1 Avión 17 32 38 32 Avión 18 38 31 38 Avión 19 41 16 41 Avión 20 41 18 41 Avión 21 42 16 42 Avión 22 42 18 42 Avión 23 42 22 42 Avión 24 42 46 42 Avión 25 44 32 44 Avión 26 45 35 45 Avión 27 45 41 45 Avión 28 46 21 46 Si realizamos la comparativa de las rotaciones que se concatenan en los distintos días, se obtienen los resultados mostrados en (Tabla 13). A pesar de que para cada jornada con 28 es suficiente, al unir las dos combinaciones se torna imposible realizar el problema. Es decir, habrá que buscar soluciones con menor número de rotaciones, es decir, aviones, pues sino se resolverá el problema a trozos, pero no de manera general. Es por ello, que se resolverá el problema para un óptimo intermedio, con w de valor ½ y dos funciones objetivo. F1 será usar el mínimo número de aviones posible y F2 será pasar fuera de los aeropuertos base el menor número de noches posible. Combinación de rotaciones 48 48 Tabla 13: Combinación entre rotaciones de días distintos F2, Volotea Días 13, 14 Días 15, 16 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 1 Avión 2, Avión 13, Avión 20, Avión 27, Avión 28 Avión 2 - Avión 3 Avión 3, Avión 14, Avión 22 Avión 4 Avión 3, Avión 14, Avión 22 Avión 5 - Avión 6 Avion 5, Avión 17, Avión 23, Avión 26 Avión 7 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 8 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 9 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 10 Avión 8, Avión 9 Avión 11 Avión 10, Avión 11, Avión 12 Avión 12 Avión 2, Avión 13, Avión 20, Avión 27, Avión 28 Avión 13 Avión 3, Avión 14, Avión 22 Avión 14 Avión 1, Avión 24 Avión 15 - Avión 16 - Avión 17 Avión 4, Avión 15 Avión 18 Avion 5, Avión 17, Avión 23, Avión 26 Avión 19 Avion 5, Avión 17, Avión 23, Avión 26 Avión 20 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 21 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 22 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 23 Avión 6, Avión 7, Avión 18, Avión 19, Avión 21 Avión 24 Avión 8, Avión 9 Avión 25 Avión 10, Avión 11, Avión 12 Avión 26 49 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Avión 10, Avión 11, Avión 12 Avión 27 Avión 2, Avión 13, Avión 20, Avión 27, Avión 28 Avión 28 Tabla 14: Combinación para los días 13, 14, combinación F1 y F2, Volotea Aviones Rotaciones Avión 1 46 22 46 20 47 22 18 23 46 Avión 2 2 13 2 1 4 1 2 Avión 3 20 22 20 18 21 23 20 Avión 4 38 32 38 30 35 30 38 Avión 5 42 18 42 46 43 19 42 Avión 6 42 22 42 16 43 23 42 Avión 7 41 18 15 18 41 Avión 8 44 27 34 27 44 Avión 9 44 32 44 9 44 Avión 10 45 27 38 27 45 Avión 11 45 35 33 35 45 Avión 12 45 37 45 24 45 Avión 13 46 16 18 16 46 Avión 14 39 32 39 Avión 15 41 16 41 Avión 16 20 17 40 17 20 22 20 Avión 17 42 18 43 22 43 19 42 Avión 18 41 3 1 3 41 Avión 19 46 22 47 23 46 Avión 20 2 6 2 Avión 21 41 18 41 Combinación de rotaciones 50 50 Tabla 15: Combinación para los días 15, 16, combinación F1 y F2, Volotea Aviones Rotaciones Avión 1 42 18 16 47 23 46 22 47 22 19 42 Avión 2 46 16 18 20 22 20 22 20 18 23 46 Avión 3 20 18 15 19 42 18 21 23 20 Avión 4 42 16 43 18 42 46 42 22 42 Avión 5 18 43 23 42 16 43 18 Avión 6 32 38 32 Avión 7 41 18 41 Avión 8 44 32 44 Avión 9 45 35 45 Avión 10 46 22 46 Avión 11 2 11 2 1 4 1 2 Avión 12 45 41 45 35 45 Avión 13 32 38 32 Avión 14 38 31 38 Avión 15 41 16 41 Avión 16 41 18 41 Avión 17 44 32 44 Avión 18 46 21 46 Si se realiza de nuevo una comparativa de las rotaciones que se pueden concatenar se observan las combinaciones de aviones entre los distintos días, lo que permitirá tener conocimiento del número de aviones total necesarios para el estudio. Tabla 16: Combinación entre rotaciones de días distintos F2 y F1, Volotea Días 13, 14 Días 15, 16 Avión 5, Avión 6, Avión 17 Avión 1 Avión 1, Avión 13, Avión 19 Avión 2 51 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Avión 3, Avión 16 Avión 3 Avión 5, Avión 6, Avión 17 Avión 4 - Avión 5 - Avión 6 Avion 7, Avión 15, Avión 18, Avión 21 Avión 7 Avión 8, Avión 9 Avión 8 Avión 10, Avión 11, Avión 12 Avión 9 Avión 1, Avión 13, Avión 19 Avión 10 Avión 20 Avión 11 Avión 10, Avión 11, Avión 12 Avión 12 - Avión 13 Avión 4 Avión 14 Avion 7, Avión 15, Avión 18, Avión 21 Avión 15 Avion 7, Avión 15, Avión 18, Avión 21 Avión 16 Avión 8, Avión 9 Avión 17 Avión 1, Avión 13, Avión 19 Avión 18 En total en los 4 días de estudio y como solución óptima, se obtuvo que son necesarios 24 aviones de 28 totales para poder realizar el total de vuelos. A continuación se muestran sobre el mapa real algunos de los vuelos para entender no sólo numéricamente hacia donde va sino el lugar exacto. Como se aprecia, la mayoría de los vuelos opera en una región determinada no muy amplia. En línea discontínua se muestran los vuelos realizados en el segundo día de la rotación, en el caso de que esta dure más de un día. Figura 40: Avión 1 y 4, Volotea sobre el mapa real, día 13 Conclusiones 58 58 de maniobra en caso de que algún avión quede inoperativo. De ahí que se puedean realizar todos los vuelos con menos aviones de los que cuenta la flota, pues aparte de tener que realizar mantenimientos de larga duración, que reduce la flota real en algunos aviones, deben existir aviones en condiciones operativas en caso de que sea necesaria la sustitución de alguna aeronave. Para Canaryfly, se vió como a pesar de no tener una gran flota, si había un número de vuelos diarios considerable. Esto se debía a la proximidad de operación. El principal inconveniente era no ya el calculo de las rotaciones, sino la combinación entre ellas, pues las posibilidades eran muchas y variadas. Había rotaciones que variaban en un vuelo exclusivamente, puediendo obtener más de una solución óptima plausible. A pesar de ello, si se buscaba la solución óptima para varios objetivos, había una combinación que resaltaba por encima de todas. Figura 45: Diagrama de flujo, etapas del algoritmo En definitiva, el algoritmo permite visualizar todos y cada uno de los resultados al final de cada fase, así como consultar los tiempos entre despegues y aterrizajes para así poder comprobar como de limitante es una combinación. Es decir, cada una de las fases muestra resultados que pueden ser útiles para entender el proceso seguido así como las limitaciones que se pueden encontrar en fases futuras debido a resultados previos que impiden determinadas condiciones, es decir, puede ser que se quiera pasar noche en un determinado lugar optimizando el número de aviones, y no se obtengan soluciones para la flota real. Eso se puede ver ya en fases tempranas del proceso cuando no existen muchas combinaciones que hagan noche en dicho lugar. Bien es cierto que se ha hecho un estudio para cuatro días de vuelos. Pero esto no es un inconveniente, pues el algoritmo es escalable. Se ha diseñado para poder paralelizar tareas. Cada fase descrita en la Figura 41, debe ser lineal con la anterior, es decir, debe haberse terminado el proceso precedente para empezar con la siguiente. Sin embargo, dentro de cada fase, suponiendo que es una caja negra, se puede dividir el estudio y calcular todo usando toda la potencia disponible, en este caso hasta 3 núcleos. Esto agiliza los resultados y podría aumentar la velocidad en caso de disponer de mayor capacidad. Esta paralelización se puede realizar gracias a que en el proceso 3 del diagrama de flujo, cuando se parte de los pares de vuelos concatenados, se comienza con un vuelo en concreto comparado con el resto y así para cada una de las combinaciones. Bien pues cada par de vuelos comparado original del procedimiento se puede paralelizar y obtener resultados de forma independiente. Al final del proceso se deberán unir todos esos resultados en una única matriz con la que poder operar en apartados sucesivos. Lo que quiere decir que se puede ahorrar tiempo de procesado mediante estos procedimientos. En cualquier caso, para rotaciones de dos días, aunque mejora el rendimiento del algoritmo no es necesario pues el tiempo de ejecución no resulta problemático a la hora de sacar resultados. Por último, recalcar que los programas realizados para llevar a cabo los algoritmos se han ido perfeccionando a lo largo del trabajo, mejorando su tiempo de ejecución y puliendo líneas de código innecesarias. Operar con Matlab matrices de n dimensiones tiene sus ventajas e inconvenientes. Matlab, al ser un programa de resolución numérica realiza cálculos muy rápido permitiendo así una ejecución veloz de los resultados. Sin embargo, los vectores de los que debe estar formada la matriz deben ser de igual tamaño o habrá problemas de guardado en las variables. Esto se podría evitar por medio del uso de ‘arrays’ pero el tiempo de realización de cálculos aumentaría pues serían tratados los números como caracteres. De ahí que el empleo de lenguajes de programación como Python puedan ser de ayuda para mejorar los tiempos de ejecución si el estudio se realiza para compañías de gran tamaño y periodos de tiempo elevado. Aún así, el uso eficiente que Matlab realiza de Datos de partida: HORARIOS SALIDAS-LLEGADAS Resultados: Solución final OPTIMIZACIÓN Concatenación de vuelos Relación 1-1 Rotación ORIGEN-DESTINO díaria Combinación de rotaciónes 59 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla los cálculos numéricos hacen que sea un gran motor de procesado para tareas como ‘Aircraft Routing’ ya que con el simple hecho de asociar valores enteros a los aeropuertos, se puede obtener resultados óptimos evitando el uso de ‘strings’, que suelen ralentizar pues hay que comparar letra a letra si se trata del mismo aeropuerto o no. En definitiva, el método de ‘Aircraft Routing’ permite ahorrar costes de cara a las aerolíneas por medio de la potencia de cálculo usando software específico para obtener las rotaciones más convenientes según los intereses. Además permite ver que nuevos vuelos pueden crearse viendo aquellas ventanas de despegue más libres y con mayor combinatoria. Ese estudio resulta beneficioso pues si se quieren abrir nuevas rutas, dichos vuelos deberán pertenencer a una rotación en concreto, y para ello saber que rotaciones permitirán con mayor facilidad incorporar dicho vuelo, o al menos, aportar mayor número de rotaciones que puedan realizar el vuelo en cuestión para así, a la hora de optimizar, tener un resultado deseable y no empeorar con respecto a las combinaciones posteriores a los nuevos vuelos. Para poder comparar las ventajas del algoritmo de forma cuantitativa, frente a resolver el problema manualmente, se presenta un histograma de la empresa Volotea con todas las rotaciones y los valores de la función objetivo para todas ellas. Cuanto mayor es el valor de la función objetivo, mejor es el sistema. Si se realizase manualmente una rotación, podría obtenerse cualquiera de las que el algoritmo ha obtenido. La probabilidad de obtener una rotación que maximice el sistema (valor de la función objetivo de 2) es de 7.3%. Sin embargo, la probabilidad de obtener una rotación de valor negativo de función objetivo es de un 54.7%, más de la mitad de las veces. Lo que quiere decir que la probabilidad de encontrar una rotación ‘mala’ es 8 veces superior a encontrar una rotación óptima para los intereses de la compañía. Esto sin tener en cuenta el ahorro de tiempo pues el algoritmo minimiza el proceso operacional a pesar de calcular todas las opciones posibles. Hay que tener en cuenta que el número de aviones hace que la función tome valores negativos o nulos pues habrá que minimizarlo, mientras que los valores positivos son de la función objetivo de pasar noche en determinados aeropuertos, que habrá que maximizar. Figura 46: Histograma, probabilidad de encontrar una rotación óptima entre el total, Volotea Conclusiones 60 60 De esta forma concluimos que la ventaja operacional del algoritmo es elevada pues permite obtener siempre la opción correcta entre el total en un periodo corto de tiempo. Por ello, este tipo de problema se ha hecho tan popular en las compañías aéreas, intentando optimizar lo máximo posible para así reducir gastos. Función objetivo 1 Función Objetivo 2 Función Objetivo 1+2 Volotea 19 24 20 Número de noches en base 20 32 24 Número de aviones Para el caso de Canaryfly se llegó a la conclusión que había una solución que era óptima para todos los resultados, siendo esta la misma. Calculemos como de buena es esta solución frente al total. La figura 47 refleja la desviación frente a la media de horas de vuelo que debe realizar cada avión en el caso de que fuesen 4 aviones los utilizados. Figura 47: Histograma, probabilidad de encontrar una rotación óptima entre el total, Canaryfly,F3 Función objetivo 1 Función Objetivo 2 Función Objetivo 3 Función Objetivo 1+2+3 Canaryfly 4 4 4 4 Número de noches en base 4 4 4 4 Número de aviones 61 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla 3.75 3.75 3.75 3.75 Desviación de horas media Figura 48: Histograma, probabilidad de encontrar una rotación óptima entre el total, Canaryfly, F2 Conclusiones 62 62 63 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla REFERENCIAS [1] Canaryfly, «Página oficial del la compañía aérea 'Canaryfly',» 2018. [En línea]. Available: https://www.canaryfly.es/. [2] C. Jeenanunta, B. Kasemsontitum y T. Noichawee, «A multicommodity flow approach for aircraft routing and maintenance problem,» 2011 IEEE International Conference on Quality and Reliability, 14- 17 Sept. 2011. [3] M. Sarhani, O. Ezzinbi, A. El Afia y Y. Benadada, «Particle swarm optimization with a mutation operator for solving the preventive aircraft maintenance routing problem,» 2016 3rd International Conference on Logistics Operations Management (GOL), 23-25 May 2016. [4] M. Ben Ahmed, F. Zeghal Mansour y M. Haouari, «A PSO Approach for Robust Aircraft Routing,» 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 6- 9 Dec. 2015. [5] P. A. Vela, A. E. Vela y G. Ogunmakin, «Topologically based decision supp ort tools for aircraft routing,» 29th Digital Avionics Systems Conference. [6] K. Roy y C. J. Tomlin, «Solving the aircraft routing problem using network flow algorithms,» Proceedings of the 2007 American Control Conference, New York City, USA, July 11-13, 2007. [7] M. De-yi y Z. Zongxian, «The integrated model of airline fleet assignment and aircraft routing based on flight cycle,» 2010 International Conference on Management Science & Engineering, November 24- 26, 2010. [8] S. Baromand, M. Nekouie y K. Navaie, «Optimal Distributed Fuzzy Control Strategy for Aircraft Routing and,» IV International Congress on Ultra Modern Telecommunications and Control Systems 2012, 3- 5 Oct. 2012. [9] Volotea, «Página oficial de la compañía aérea 'Volotea',» 2018. [En línea]. Available: http://www.volotea.com/es/. [10] M. Barzagan, Airline operations and scheduling, Ashgate, 2004. [11] J. M. d. C. Granados y L. M. R. Pérez, Aplicación de la programación lineal al transporte aéreo, Complementos de Transporte aéreo, 1º de MUIA. [12] Mathworks, «Página de soporte de productos de Matlab,» [En línea]. Available: https://es.mathworks.com/help/optim/ug/linprog.html. [13] Mathworks, «Página de soporte de productos de Matlab,» [En línea]. Available: https://es.mathworks.com/help/optim/ug/intlinprog.html. [14] Economista. [En línea]. Available: http://ranking-empresas.eleconomista.es/VOLOTEA.html. [15] Economista. [En línea]. Available: http://ranking-empresas.eleconomista.es/CANARY-FLY.html. Referencias 64 64 65 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla ÍNDICE DE CONCEPTOS A319: Avión comercial de pasajeros basado en el diseño del A320, de corto o medio alcance. Su fabricante es Airbus. Asignación: Valor numérico asociado a un aeropuerto. No tiene por qué ser único, permite definir los nodos de forma unívoca. ATR72-500: Avión comercial de pasajeros propulsado por dos motores turbohélices. Suele ser usado como avión de línea regional, la empresa fabricante es ATR. B717: Avión comercial de pasajeros de corto y medio alcance. Su fabricante es Boing. Ciclo de tiempo: Toda rotación debe tener un principio y un final. En este caso puede empezar y terminar el mismo día, donde el aeropuerto inicial y final de la rotación debe ser el mismo. Puede ocurrir que sea de dos días la duración de la rotación, y ocurriría lo mismo con el aeropuerto final e inicial. El ciclo de tiempo de la rotación puede ser tan amplio como la compañía operadora estime oportuno. Combinación: Conjunto de rotaciones que permiten resolver un sistema con una función objetivo y unas restricciones concretas. Flota: Conjunto de aviones de los que dispone una compañía aérea. Función objetivo: Para optimizar un sistema habrá que declarar un objetivo prioritario que se pretenda cumplir en la realidad, y después expresarlo de forma matemática por medio de una función a maximizar o minimizar. Nodo: Todo vuelo tiene un aeropuerto de salida y otro de llegada, cada aeropuerto es un nodo del vuelo. Existen dos nodos por vuelo. Pesos: Cuando una función objetivo no es única, se debe ponderar según la importancia de esta con respecto al resto. Restricciones: Condiciones que debe cumplir un sistema de ecuaciones para adecuarse a unas pautas dadas por el caso real. Pueden ser ecuaciones de igualdad o desigualdad, en el caso de que no se pueda superar un determinado valor. Rotación: Combinación de vuelos realizados por una aeronave en concreto. Ruta: Rotación. SIMPLEX: Método de programación lineal que permite resolver problemas con dichas condiciones de manera rápida por medio de algoritmos hechos al efecto. En este trabajo se ha usado para la resolución de problemas de programación lineal binaria. String: Conjunto de caracteres que forman una palabra. En computación, para reconocer la palabra hay que guardarlo letra a letra, mientras que los números son elementos únicos con los que es más rápido operar. Tiempo de espera: Todo avión debe permanecer en tierra un tiempo mínimo antes de despegar, habrá que bajar a los pasajeros, el equipaje, realizar repostaje y tareas de puesta a punto. Además, habrá que esperar que la pista este disponible según slots. No todos los vuelos tienen los mismos tiempos de espera, pero si se puede suponer un tiempo mínimo general por compañía. Índice de Conceptos 66 66 67 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Anexos Figura 49: Horarios de llegada, Canaryfly Índice de Conceptos 74 74 Salida Llegada Horario de salida Horario de llegada Catania Génova 16:40 18:35 Catania Venecia 18:10 20:00 Catania Verona 9:20 11:10 Catania Verona 20:55 22:45 Génova Catania 14:35 16:15 Génova Nápoles 7:00 8:20 Génova Nápoles 19:00 20:20 Génova Palermo 15:05 16:35 Nápoles Catania 16:45 17:50 Nápoles Génova 9:00 10:20 Nápoles Génova 20:45 22:05 Nápoles Verona 19:45 21:05 Nápoles Palermo 9:25 10:25 Nápoles Palermo 19:55 20:55 Caen Toulouse 17:00 18:35 Estrasburgo Toulouse 17:30 19:00 Estrasburgo Burdeos 19:25 20:55 Montpellier Nantes 18:50 20:15 Toulouse Caen 15:10 16:35 Toulouse Estrasburgo 19:25 20:55 Venecia Bari 15:00 16:20 Venecia Catania 16:00 17:45 Venecia Nantes 14:25 16:40 Verona Palermo 14:00 15:35 Verona Bari 15:00 16:20 Verona Catania 7:15 8:55 Verona Catania 18:50 20:30 75 Formato de Publicación de la Escuela Técnica Superior de Ingeniería de Sevilla Salida Llegada Horario de salida Horario de llegada Verona Nápoles 18:00 19:20 Burdeos Estrasburgo 17:10 18:45 Nantes Montpellier 17:05 18:25 Nantes Venecia 12:00 14:00 Palermo Génova 13:10 14:40 Palermo Nápoles 8:00 9:00 Palermo Nápoles 15:20 16:20 Palermo Verona 16:00 17:35