A Sabre tornou o aumento de tripulação uma variável explícita na otimização de pareamento de tripulações de companhias aéreas

O planejamento de tripulações de companhias aéreas ocorre em duas etapas: o pareamento de tripulações gera escalas de trabalho anônimas que cobrem a malha de voos e, em seguida, esses pareamentos são atribuídos a tripulantes individuais. Voos de longa distância exigem tripulações reforçadas por razões de segurança, e aí está o problema: quantos capitães ou oficiais extras um voo requer depende das características do pareamento que o cobre. A exigência e a escolha da escala estão acopladas. A maioria das ferramentas rompe esse acoplamento fixando previamente os requisitos de aumento de tripulação ou restringindo a forma como podem ser satisfeitos, porque o problema geral é muito difícil.

A Sabre desenvolveu seu otimizador de pareamento de longa distância em meados da década de 1990 e seguiu o caminho oposto: o otimizador modela explicitamente muitos tipos de processos de aumento de tripulação e considera simultaneamente as patentes relevantes de todos os tripulantes de cabine de comando. Ele resolve o modelo de grande escala resultante com branch and price. Em um artigo da Interfaces de 2015, os autores traçaram duas décadas de evolução do modelo e do algoritmo e compararam sua abordagem com quatro métodos convencionais, mostrando que ela resolve o problema geral de aumento de tripulação e proporciona economias significativas de custos de tripulação às companhias aéreas.

Por que funciona: o aumento de tripulação custa caro de verdade. Cobrir o mesmo voo com o pareamento A pode custar três posições extras de tripulação, enquanto o pareamento B custa uma, de modo que fixar o requisito antes da otimização congela o custo na escala. Coloque o requisito dentro da função objetivo e o solucionador escolhe a combinação legal mais barata em toda a malha de uma só vez. As economias se acumulam em cada pareamento de uma escala de trabalho, e é por isso que as companhias aéreas pagaram pelo produto em vez de por um ajuste de regra.

Tornar o aumento de tripulação uma variável de otimização

Os requisitos de aumento de tripulação estão acoplados à escolha do pareamento, de modo que fixá-los a priori congela o custo de tripulação antes mesmo de o solucionador ser executado.

O branch and price mantém o modelo ampliado tratável, de modo que milhões de pareamentos candidatos, incluindo estados de aumento de tripulação, permanecem solucionáveis.

A Sabre vendeu sistemas de pareamento de tripulações para muitas companhias aéreas de longa distância, de modo que a melhoria se multiplicou pelas frotas dos clientes em vez de ficar restrita a uma só.

Duas décadas de trabalho incremental no modelo e no algoritmo (1995-2015) foram o que tornou a formulação explícita adequada para produção.

Quando uma restrição varia de fato com a solução, deixe-a dentro do modelo. Fixar parâmetros "conhecidos" de antemão simplifica a matemática, mas congela o custo que o solucionador teria eliminado.

O otimizador permaneceu na linha de produtos de pareamento de longa distância da Sabre até meados da década de 2010, com o artigo da Interfaces de 2015 documentando a evolução de seus modelos e algoritmos e comparando-o com quatro abordagens convencionais. O artigo enquadra a formulação de aumento explícito como capacidade de produto consolidada, e não como pesquisa, e observa que o problema geral havia sido há muito tempo deixado de lado na prática justamente por sua complexidade.