Sabre convirtió la ampliación de tripulación en una variable explícita en la optimización de emparejamientos de aerolíneas

La planificación de tripulaciones de aerolíneas se ejecuta en dos pasos: la generación de emparejamientos de tripulación produce horarios de trabajo anónimos que cubren el programa de vuelos, y luego esos emparejamientos se asignan a miembros individuales de la tripulación. Los vuelos de largo recorrido necesitan tripulaciones ampliadas por razones de seguridad, y aquí está el problema: cuántos capitanes u oficiales adicionales requiere un vuelo depende de las características del emparejamiento que lo cubre. El requisito y la elección del horario están acoplados. La mayoría de las herramientas rompen ese acoplamiento fijando por adelantado los requisitos de ampliación o restringiendo cómo pueden satisfacerse, porque el problema general es muy difícil.

Sabre desarrolló su optimizador de emparejamientos de largo recorrido a mediados de la década de 1990 y tomó el camino opuesto: el optimizador modela explícitamente muchos tipos de procesos de ampliación de tripulación y considera simultáneamente los rangos relevantes de todos los miembros de la tripulación de cabina de mando. Resuelve el modelo resultante a gran escala con branch and price. En un artículo de Interfaces de 2015, los autores rastrearon dos décadas de evolución del modelo y del algoritmo y compararon su enfoque con cuatro métodos convencionales, mostrando que resuelve el problema general de ampliación de tripulación y genera ahorros significativos en costos de tripulación para las aerolíneas.

Por qué funciona: la ampliación es dinero real. Cubrir el mismo vuelo con el emparejamiento A podría costar tres puestos de tripulación adicionales mientras que el emparejamiento B cuesta uno, así que fijar el requisito antes de optimizar congela el costo dentro del horario. Si se coloca el requisito dentro de la función objetivo, el solver compra la combinación legal más barata en toda la red a la vez. Los ahorros se acumulan en cada emparejamiento de una línea de oferta, y por eso las aerolíneas pagaron por el producto en lugar de por un ajuste de reglas.

Convertir la ampliación de tripulación en una variable de optimización

Los requisitos de ampliación están acoplados a la elección del emparejamiento, así que fijarlos a priori inmoviliza el costo de tripulación antes de que el solver siquiera se ejecute.

Branch and price mantiene tratable el modelo ampliado, de modo que millones de emparejamientos candidatos, incluidos los estados de ampliación, siguen siendo resolubles.

Sabre vendió sistemas de emparejamiento de tripulación a muchas aerolíneas de largo recorrido, así que la mejora se multiplicó en las flotas de los clientes en lugar de quedarse en una sola.

Dos décadas de trabajo incremental en el modelo y el algoritmo (1995-2015) son lo que llevó la formulación explícita a nivel de producción.

Cuando una restricción varía realmente con la solución, déjala dentro del modelo. Fijar por adelantado parámetros "conocidos" simplifica las matemáticas pero inmoviliza el costo que el solver habría eliminado.

El optimizador permaneció en la línea de productos de emparejamiento de largo recorrido de Sabre hasta mediados de la década de 2010, con el artículo de Interfaces de 2015 documentando la evolución de sus modelos y algoritmos y comparándolo con cuatro enfoques convencionales. El artículo presenta la formulación de ampliación explícita como una capacidad de producto consolidada más que como investigación, y señala que el problema general se había omitido durante mucho tiempo en la práctica precisamente por su complejidad.