A Branch-Price-Cut-And-Switch Approach for Optimizing Team Formation and Routing for Airport Baggage Handling Tasks with Stochastic Travel Times

모든 주요 공항의 중심에는 대부분의 여행객은 결코 보지 못하는 복잡하고 중대한 물류적 과제가 자리 잡고 있습니다. 바로 터미널에서 항공기로, 그리고 다시 돌아오는 수하물의 이동입니다. 이 과정은 정밀하게 배치되고, 장비를 갖추고, 활주로를 가로질러 경로가 지정된 지상 조업 팀에 의존합니다. 각 항공편에는 상차 또는 하차를 위한 엄격한 시간 제한이 있으며, 이 마감 시간을 놓치면 연쇄적인 지연, 항공사의 금전적 손실, 그리고 승객의 불만으로 이어질 수 있습니다. 어려움은 지상 조업 인력이 서로 대체 불가능하다는 점 때문에 더욱 가중됩니다. 그들은 하이로더(high-loader)나 컨베이어 벨트와 같은 특정 중장비를 운용할 수 있는 각기 다른 숙련도를 보유하고 있습니다. 또한, 활주로 자체는 주차 구역 간의 이동 시간이 예측 불가능하며, 교차하는 항공기나 국지적인 혼잡으로 인해 속도가 늦춰지는 역동적인 환경입니다. 수십 년 동안 계획가들은 이러한 불확실성의 현실을 고려하지 못한 채 단순화된 가정을 사용하는 경우가 많았으며, 속도의 필요성과 현실 사이의 균형을 맞추기 위해 고군분투해 왔습니다.

뮌헨 공과대학교의 연구진은 이 난제를 해결하기 위해 기존의 정적인 모델을 넘어선 새로운 접근 방식을 개발했습니다. 이동 시간을 고정된 것으로 가정하거나 항상 최악의 시나리오가 발생할 것이라고 가정하는 대신, 그들은 지상 차량의 이동을 알려진 확률을 가진 변수로 취급했습니다. 그들은 어떤 작업자가 팀을 구성할지, 어떤 항공기를 서비스할지, 그리고 어떤 순서로 수행할지를 동시에 결정하면서 지연 가능성까지 고려하는 정교한 알고리즘을 만들었습니다. 이 혁신의 핵심은 "브랜치-프라이스-컷-앤-스위치(Branch-Price-Cut-and-Switch)"라고 불리는 기법입니다. 이 기술을 통해 컴퓨터는 최적의 해답을 찾는 과정에서 전략을 동적으로 변경할 수 있습니다. 우선 인력에 대한 광범하고 단순화된 관점에서 시작하여 빠르게 좋은 옵션들을 찾아내지만, 만약 수학적으로는 타당해 보이지만 실제로는 실행 불가능한 시나리오(예: 작업자가 이동 시간 없이 마법처럼 작업 간에 순간 이동하는 경우)에 직면하면, 오류를 수정하기 위해 즉시 더 상세하고 엄격한 모델로 전환합니다. 이러한 전환 메커니즘은 최종 계획이 단순히 수학적 이상향에 그치지 않고 실행 가능한 현실이 되도록 보장합니다.

연구팀은 주요 유럽 허브 공항에서 생성된 데이터를 사용하여 알고-리즘을 테스트했으며, 시간당 30편의 항공기가 도착하거나 출발하는 최대 2시간의 계획 범위를 시뮬레이션했습니다. 그들은 이 새로운 방식을 기존의 접근 방식들과 비교하였고, 새로운 방식이 더 복잡한 사례들을 최적해(optimality)까지 풀어내며, 최적의 해와 컴퓨터가 찾은 해 사이의 격차를 줄이는 데 훨씬 뛰어난 성능을 보인다는 것을 발견했습니다. 결정적으로, 연구는 불확실성을 명시적으로 계획하는 것이 이를 무시하는 것보다 더 나은 결과를 낳는다는 것을 입증했습니다. 알고리즘에 결정론적 데이터(이동 시간을 평균값이나 최선의 값으로 고정하여 가정함)를 입력했을 때, 생성된 계획은 실제 변동성이 있는 환경에서 테스트되었을 때 서비스 수준 요구 사항을 충족하지 못하는 경우가 많았습니다. 반면, 확률적(stochastic) 이동 시간을 고려하여 생성된 계획은 높은 신뢰도로 항공편을 제때 적재함으로써 일관되게 높은 서비스 수준을 유지했습니다.

가장 눈에 띄는 발견 중 하나는 알고리즘이 효율성과 안전성 사이의 절충안을 어떻게 관리하는가였습니다. 연구진은 잠재적인 지연을 위해 얼마나 많은 인력을 예비로 확보할지 결정하는 특정 통계적 임계값을 사용함으로써, 시스템을 더 보수적이거나 혹은 더 공격적으로 조정할 수 있었습니다. 그들은 최악의 교통 상황을 가정하기보다는 적절한 수준의 주의를 기울여 계획하는 것이, 서비스 수준을 허용 가능한 범위 내로 보장하면서도 가용 인력을 더 효율적으로 사용하는 방법을 찾아냈다는 것을 발견했습니다. 이 접근 방식은 자원을 낭비하지 않으면서도 일정 내에 안전 버퍼를 구축하는 효과를 냈습니다. 또한 본 연구는 단순히 평균 이동 시간을 가정하는 것만으로는 불충분하다는 점을 강조했습니다. 평균값 가정은 최선의 시나리오를 가정하는 것보다는 나은 결과를 냈지만, 여전히 서비스 표준 위반을 빈번하게 초래했습니다. 오직 가능한 모든 이동 시간의 범위와 그 확률을 모델링함으로써만 시스템이 안정적인 서비스 수준을 보장할 수 있었으며, 이는 승객들이 수하물 수취장에서 기다리거나 연결편을 놓치게 만드는 예측 불가능한 지연을 방지할 수 있었습니다.

이 연구의 함의는 활주로 너머까지 확장됩니다. 알고리즘은 추측이나 자원을 유휴 상태로 만드는 과도하게 보수적인 계획에 의존하지 않고도, 복잡하고 불확실한 환경을 위해 매우 효율적이고 견고한 일정을 만드는 것이 가능하다는 것을 증명했습니다. 서로 다른 수학적 모델을 동적으로 전환하고, 실행 가능한 솔루션을 이론적인 솔루션과 분리하기 위해 정확한 방법론을 사용함으로써, 연구진은 불확실성이 존재하는 자원 제약 시스템을 다루는 청사진을 제공했습니다. 그들의 결과는 공항 운영자들이 환경의 예측 불가능성을 무시하려 하기보다 이를 수용함으로써 더 높은 정시성과 더 낮은 비용을 달착할 수 있음을 시사합니다. 본 연구는 이동 시간의 확률적 특성을 명시적으로 고려하는 것이 단순한 이론적 개선이 아니라 현대 공항 운영의 실질적인 필수 요소이며, 가용 인력을 더 효율적으로 활용하는 동시에 수하물 처리 업체에 안정적인 서비스 수준을 보장하는 방법임을 결론짓고 있습니다.