Estado Del Arte Para La Resolución Del Problema De Aircraft Landing Scheduling Problem - Inteligencia Artificial

Inteligencia Artificial
Estado del Arte: Problema Aircraft Landing Scheduling Problem
C´sar Flores, Angelina Mansilla e 10 de junio de 2012

Evaluaci´n o
Resumen (5 %): Introducci´n (5 %): o Definici´n del Problema (10 %): o Estado del Arte (35 %): Modelo Matem´tico (20 %): a Conclusiones (20 %): Bibliograf´ (5 %): ıa Nota Final (100):
Resumen En este documento se describir´ el problemallamado Aircraft Landing Scheduling Proa blem (Tambi´n conocido como Aircraft Arrival and Departure), y el Estado del arte del e mismo, en el cual se presentar´n diversas maneras de representaci´n y resoluci´n con divera o o sas t´cnicas. En este problema, el controlador de trafico a´reo tiene que calcular el tiempo e e de aterrizaje para cada avi´n que solicite ocupar la pista, y tiene que intentarminimizar o los costos, considerando un numero de restricciones duras. Los costos est´n asociados al a diferencial de tiempo que demora el avi´n en aterrizar en las pistas, en comparaci´n a su o o tiempo preferido de aterrizaje, y las restricciones se refieren al manejo de las ventanas de tiempo con las que cuenta un avi´n para aterrizar en la pista que requiere para hacerlo. o

1

1.Introducci´n o

Existen muchos factores que han hecho que la congesti´n del espacio a´reo haya aumentado o e significativamente en las ultimas d´cadas, tales como la reducci´n de costos de los pasajes de ´ e o avi´n y una mayor seguridad en el transporte, que han tra´ como consecuencia la disponibilidad o ıdo del viaje a´reo al p´blico masivo y global. Esto ha hecho que se haya complejizado de manera e udr´stica el control y coordinaci´n entre los aviones que circulan diariamente. En la figura 1 que a o se muestra a continuaci´n nos ayuda a dimensionar este fen´meno. o o

Figura 1: Tr´fico en EEUU en una ma˜ana de Febrero del 2010 a n Una de las tareas cr´ ıticas que se debe considerar en la coordinaci´n y control, es el aterrizaje o de estos aviones en los aeropuertos disponibles, considerandoque cada avi´n para aterrizar o necesita una pista de aterrizaje de uso exclusivo mientras dura este proceso. Tarea que se ha vuelto un problema para las torres de control de cada aeropuerto debido a lo mencionado con anterioridad. Esto ha llevado a la comunidad cient´ ıfica a tratar de resolverlo con t´cnicas e computacionales debido a su complejidad y la necesidad de obtener soluciones en tiemporeal. Es por esto que se expondr´ en este documento una definici´n del problema que incluya a o los factores m´s importantes y una recopilaci´n de aproximaciones para su resoluci´n, lo que a o o permitir´ adentrarse en la definici´n de un modelo matem´tico. a o a Se espera que el trabajo presentado en este documento fije las bases para la proposici´n de o un algoritmo y su implementaci´n. o

22.

Definici´n del Problema o

En esta secci´n, se definir´ con detalle el problema de Aircraft Landing Scheduling Problem, o a que para su simplificaci´n consideraremos solamente el caso est´tico, que a diferencia del caso o a din´mico, la informaci´n de los aviones que soliciten alguna pista del aeropuerto para aterrizar a o en una ventana de tiempo acotada no cambia, en contraposici´n a ircalculando en tiempo real o los aviones que van entrando en el rango del radar del aeropuerto o la torre de control (horizonte)

2.1.

Aircraft Landing Scheduling Problem

Cuando un avi´n entra dentro del horizonte del radar del control de tr´fico a´reo en un o a e aeropuerto, el avi´n necesita que el control le asigne un tiempo t en el cual tiene que aterrizar, o adem´s de asignarle una pistade aterrizaje en la cual pueda realizar la tarea. a El tiempo de aterrizaje debe estar dentro de una ventana de tiempo especificada, y limitada por una cota inferior y una cota superior, siendo estos tiempos distintos para cada avi´n que o este dentro del horizonte. La cota inferior representa el tiempo m´s temprano en el cual el avi´n a o puede aterrizar si lo hiciera a su m´xima velocidad. La...