Aplicación de recocido simulado para la optimización de procesos de aterrizaje en aeropuertos

Abstract

La capacidad actual de los aeropuertos es insuficiente debido al gran incremento de la demanda del tráfico aéreo en las últimas décadas. Como consecuencia, muchos vuelos no pueden aterrizar o despegar en el horario previsto. Este retraso en los vuelos en aeropuertos congestionados supone una serie de problemas sociales, además de grandes pérdidas económicas. Se trata de un problema complejo que requiere de una gestión óptima de los recursos utilizados. En concreto, se desea asignar un horario y pista de aterrizaje para cada aeronave con destino a cierto aeropuerto para un periodo de tiempo establecido. Debido a la naturaleza combinatoria del problema a resolver, se descarta la utilización de métodos de solución exactos. En esta Tesis Fin de Máster se propone el uso de una metaheurística, el recocido o enfriamiento simulado, para su resolución. Dicha metaheurística de trata de algoritmo de búsqueda trayectorial inspirado en las leyes de la termodinámica que permite la obtención de soluciones subóptimas en tiempos asumibles, evitando quedar atrapado en óptimos locales, inconveniente típico asociado a la utilización de heurísticas. Inicialmente se modeliza matemáticamente el problema de la secuenciación de aterrizajes mediante un problema de optimización lineal. A continuación, adaptamos el recocido o enfriamiento simulado para resolver el problema considerado y ajustamos los parámetros correspondientes. Finalmente, ilustramos el funcionamiento de la metaheurística mediante la utilización de varios ejemplos.---ABSTRACT---The current capacity of airports is becoming insufficient due to growing air transportation demand and a huge increase in air traffic during the last decade. Therefore, some aircrafts cannot land or depart at their preferred target-time. The flight delay at the busy airports causes tremendous economical loss and some social problems. It is a complex problem that requires optimal management of the resources used. The aim is to fix a landing time and strip for each aircraft bound for certain airport in a given time period. Due to the combinatorial nature of the problem to be solved, the use of exact methods is discarded. In this Master’s Final Project we propose the use of a metaheuristic for its resolution, simulated annealing. This is a trayectorial search algorithm inspired in thermodynamics which allows to reach suboptimal solutions in acceptable times, avoiding being trapped in local optima, typical drawback associated with the use of heuristics. The arrival aircraft-sequencing problem is first modeled by means of a linear optimization problem. Then, we adapt simulated annealing to deal with the considered problem and adjust the corresponding parameters and, finally, some examples are provided to illustrate the metaheuristic and to analyze its performance.