승무원스케줄링문제 (Crew Scheduling Problem)
한 줄 정의: 항공기 조종사·승무원이나 철도·버스 기사와 같은 운항 인력을, 정해진 운행 일정과 근무 규정을 만족시키면서 각 운행에 배정하는 스케줄링 문제입니다.
쉽게 풀면
항공사는 하루에도 수많은 항공편을 운항하는데, 각 항공편마다 조종사와 승무원이 배정되어야 합니다. 그런데 승무원은 연속 근무시간 제한, 최소 휴식시간, 자격증 요건, 원하는 출발지 복귀 등 여러 규정을 지켜야 합니다. 승무원스케줄링문제는 이런 모든 조건을 만족시키면서, 최소한의 인력과 비용으로 모든 운항을 커버할 수 있는 근무표를 짜는 문제입니다. 간호사스케줄링문제와 비슷하지만, 승무원은 여러 지역을 이동하며 근무한다는 점에서 고려해야 할 조건이 더 복잡한 경우가 많습니다.
왜 중요한가
인건비는 항공사나 운수업체의 주요 비용 항목이기 때문에, 승무원을 얼마나 효율적으로 배치하느냐가 수익성에 직접적인 영향을 미칩니다. 동시에 안전 규정을 반드시 지켜야 하므로, 비용 효율성과 규정 준수를 동시에 만족시켜야 하는 대표적인 대규모 조합최적화 문제로 다루어집니다.
논문에서는 이렇게 쓰입니다
"본 논문은 항공 승무원스케줄링문제를 집합분할(set partitioning) 모형으로 정식화하고, 열 생성 기법을 이용해 대규모 문제를 효율적으로 해결하였다."
대규모 승무원스케줄링문제를 최적화 기법으로 해결한 연구를 설명합니다.
"버스 운수회사의 승무원스케줄링문제에서 최소 휴식시간과 근무 형평성을 동시에 고려하는 다목적 최적화 모형을 제안하였다."
비용뿐 아니라 근무자 간 형평성까지 고려한 스케줄링 모형을 설명하는 문장입니다.
조금 더 깊게 보면
승무원스케줄링문제는 흔히 개별 운항 구간들을 하나의 근무 일정(듀티, duty)으로 묶는 단계와, 여러 듀티를 다시 실제 근무자에게 배정하는 단계로 나누어 접근합니다. 문제의 규모가 매우 크기 때문에 정수계획법과 열 생성(column generation) 기법을 결합한 방법이 대표적으로 연구되어 왔습니다.
주의할 점
안전 규정이 국가나 기관마다 다르게 정해져 있어, 특정 환경에서 개발된 모형을 다른 환경에 그대로 적용하기는 어려울 수 있습니다.