Planificar en una aerolínea. Optimizar 13 millones de variables

Un aspecto importante a la hora de enfrentarse a un problema es el estudio de complejidad computacional. Este estudio nos ayuda a analizar los recursos y el tiempo necesarios para resolver nuestro problema en función de nuestras condiciones o valores iniciales.

Qué tipo de solución también determinará la dificultad de nuestro problema. ¿Queremos determinar si nuestro problema tiene solución? Además, ¿queremos obtener una posible solución a nuestro problema?, o ¿llegar a una buena solución? O finalmente, ¿queremos la mejor solución de entre todas las posibles?

Esta última alternativa es la optimización. En el Máster en Inteligencia Artificial(VIU) estudiamos diferentes técnicas para llegar a soluciones optimas de diferentes tipos de problemas a través de los Algoritmos de Optimización.

En la resolución de algunos problemas la diferencia entre disponer de una solución y encontrar la mejor solución se traduce en ahorro de dinero, recursos, tiempo o cualquier otra variable a optimizar.

Uno de estos problemas históricos es el de la planificación de la tripulación de una compañía aérea. Se trata de resolver la distribución del personal de tripulación de vuelo y cabina de la compañía aérea para dar servicio a los vuelos comerciales de cada día.

Fuente: leansystems.co

A través de los datos de entrada(todos de los vuelos con sus orígenes, destinos y horarios) el objetivo es proporcionar una asignación sucesiva de personal a dichos vuelos. Por supuesto esta asignación debe ser automatizada y que optimice en lo posible diferentes aspectos como minimizar los costes, tiempos muertos o los días fuera del domicilio del personal .

Adicionalmente deben considerarse restricciones propias de la regulación y seguridad(p.ej. no coincidencias sucesivas con un compañero), restricciones laborales(p.ej. horas de descanso), restricciones comerciales(p.ej idiomas hablados por el personal) o restricciones de preferencias del personal.

A pesar de la aparente simplicidad en el planteamiento, se intuye que el acercamiento al problema va a ser complejo como nos contaba en 1991 Robert E. Bixby, uno de los precursores de las técnicas de optimización.

https://scholarship.rice.edu/bitstream/handle/1911/101715/TR91-11.pdf

En los inicios se utilizaba la computación en este problema como un complemento de ayuda a una tarea manual de un equipo de personas dedicada exclusivamente a obtener soluciones. Fue Robert E. Bixby quien empezó a tratar el problema de manera diferente aplicando técnicas de optimización de Programación Matemática. Trató el problema como un modelo de programación lineal entera-mixta para aplicar algoritmos de optimización. Los problemas de programación lineal entera-mixta son problemas en los que hay que minimizar(o maximizar) una función de varias variable y donde estas variables están sujetas a restricciones. Algunas de estas variables deben tener valores enteros. En su estudio sobre un caso real, Robert E. Bixby planteó un problema que tenía 837 ecuaciones y más de 12,750,000 variables !

No podemos describir aquí los detalles para llegar a soluciones. Como ocurre en estos casos el camino es la división del problema en partes mas asequibles y aplicación de técnicas heurísticas aumentando la eficiencia. Técnicas heurísticas son aquellas que permiten ignorar información del problema a sabiendas que no aportaran mejora en la búsqueda de soluciones con el fin de llegar a estas con menos recursos(o tiempo).

Históricamente estos problemas estaban asociados a la economía o ingeniería pero cada vez son mas los ámbitos en los que la optimización aterriza para encontrar las mejores soluciones a través de la Inteligencia Artificial. Actualmente ya no se discute su utilización en el reclutamiento de para cubrir puestos de trabajo, la publicidad dirigida de acuerdo a nuestro perfil de navegación o determinar el contenido mas adecuado a nuestros gustos(Netflix y Spotify ya lo hacen) como nos muestra Daniel Yankelevich.