Sabre는 항공사 페어링 최적화에서 승무원 증원을 명시적 변수로 만들었다

항공사 승무원 계획은 두 단계로 진행된다. 먼저 승무원 페어링이 항공편 시간표를 커버하는 익명의 근무 일정을 생성하고, 그다음 그 페어링들이 개별 승무원에게 배정된다. 장거리 항공편은 안전상의 이유로 증원 승무원이 필요하며, 여기에 문제가 있다. 항공편에 필요한 추가 기장이나 부기장의 수는 그 항공편을 커버하는 페어링의 특성에 따라 달라진다. 요구 사항과 일정 선택이 서로 결합되어 있는 것이다. 대부분의 도구는 일반 문제가 매우 어렵기 때문에 증원 요구 사항을 사전에 고정하거나 충족 방식을 제한함으로써 이 결합을 끊는다.

Sabre는 1990년대 중반에 장거리 페어링 최적화기를 개발하면서 반대 경로를 택했다. 최적화기는 여러 유형의 승무원 증원 프로세스를 명시적으로 모델링하고 모든 조종실 승무원의 관련 직급을 동시에 고려한다. 이렇게 만들어진 대규모 모델을 분기 가격법(branch and price)으로 해결한다. 2015년 Interfaces 논문에서 저자들은 20년에 걸친 모델과 알고리즘의 진화를 추적하고 그들의 접근법을 네 가지 전통적 방법과 비교하여, 이것이 일반적인 승무원 증원 문제를 해결하고 항공사에 상당한 승무원 비용 절감을 제공한다는 것을 보여주었다.

왜 효과가 있는가: 증원은 실제 비용이다. 같은 항공편을 페어링 A로 커버하면 추가 승무원 자리가 세 개 필요할 수 있지만 페어링 B로는 한 개만 필요할 수 있으므로, 최적화 전에 요구 사항을 고정하면 비용이 일정에 못 박힌다. 요구 사항을 목적 함수 안에 넣으면 솔버가 전체 네트워크에 걸쳐 가장 저렴한 합법적 조합을 한 번에 선택한다. 절감은 비드 라인의 모든 페어링에 걸쳐 누적되며, 이것이 항공사들이 규칙을 약간 손보는 대신 제품에 비용을 지불한 이유다.

승무원 증원을 최적화 변수로 만들었다

증원 요구 사항은 페어링 선택과 결합되어 있으므로, 이를 사전에 고정하면 솔버가 실행되기도 전에 승무원 비용이 고정된다.

분기 가격법은 확대된 모델을 다룰 수 있게 유지하므로, 증원 상태를 포함한 수백만 개의 후보 페어링이 계속 해결 가능하다.

Sabre는 많은 장거리 항공사에 승무원 페어링 시스템을 판매했으므로, 개선 효과가 한 곳이 아니라 고객 항공사들의 기단 전체에 걸쳐 배가되었다.

20년에 걸친 점진적인 모델 및 알고리즘 작업(1995-2015)이 명시적 정식화를 생산 등급으로 만든 것이다.

제약이 실제로 해에 따라 달라진다면, 그것을 모델 안에 남겨 두어라. '알려진' 매개변수를 사전에 고정하면 수학은 단순해지지만, 솔버가 제거했을 비용이 고정된다.

이 최적화기는 2010년대 중반까지 Sabre의 장거리 페어링 제품 라인에 남아 있었으며, 2015년 Interfaces 논문은 그 모델과 알고리즘의 진화를 기록하고 네 가지 전통적 접근법과 벤치마킹했다. 이 논문은 명시적 증원 정식화를 연구가 아닌 확립된 제품 역량으로 규정하고, 일반 문제가 바로 그 복잡성 때문에 오랫동안 실무에서 건너뛰어졌다고 언급한다.