Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

기술 요약: rVNS를 통한 공항 지상 조업 운영 할당 및 최적화

문제 정의
본 연구는 공항 지상 조업 운영, 특히 케이터링 서비스의 복잡한 조합 최적화 문제를 다룬다. 핵심 문제는 이질적인 트럭 함대와 다양한 자격 요건 및 적재 패턴을 가진 운전자를 수용하도록 확장된 **다중 운행 용량 제한 차량 경로 및 스케줄링 문제(MTCVRSPTW-MB)**로 모델링된다.

목표는 두 가지이다:

1. 주 목적: 가용 운전자 및 트럭에 할당되는 케이터링 작업(항공기 상차/하차) 수를 최대화한다.
2. 부 목적: 이러한 작업을 수행하는 데 필요한 총 주행 거리를 최소화한다.

문제는 다음과 같은 엄격한 운영 규칙에 의해 제약된다:

• 운전자 제약: 교대 근무 일정, 의무 식사 시간(교대 시작 4~5시간 후 30분간), 특정 항공기 유형 및 항공사에 대한 자격 요건.
• 트럭 제약: 적재 용량 제한, 특정 트럭 유형(14FT, 16FT, 22FT), 그리고 제한된 일일 가용성.
• 작업 제약: 실행 시간 창(Time windows), 트럭/운전자와 특정 항공편/항공사 간의 호환성, 그리고 부피 요구 사항.
• 미션 제약: 동일 미션 내에서 국제선 상차 후 국내선 하차를 금지하는 등의 다중 작업 미션 규칙, 작업 간 충분한 이동 시간 확보, 그리고 모든 미션이 메인 케이터링 유닛에서 시작하고 종료되어야 한다는 규칙.

본 연구는 2023년 3월 샌프란시스코 국제공항(SFO)의 실제 데이터를 활용하며, 여기에는 약 350개의 일일 작업, 80명의 운전자, 40대의 트럭이 포함된다. 핵심 요구 사항은 운영 가능성을 위해 솔루션이 1분 이내에 생성되어야 한다는 점이다.

방법론
저자들은 협력적 축소 변수 이웃 탐색(cooperative reduced Variable Neighborhood Search, rVNS) 메타휴리스틱을 제안한다. 이 접근 방식은 계산 효율성과 솔루션 품질 사이의 균형을 맞추기 위해 전통적인 변수 이웃 탐색(VNS) 및 적응형 대규모 이웃 탐색(ALNS) 대신 선택되었다.

방법론의 주요 구성 요소는 다음과 같다:

1. 축소 VNS (rVNS) 프레임워크:

   • 단계 크기(step sizes)를 변화시키는 클래식 VNS와 달리, rVNS는 고정된 작은 단계 크기를 사용한다.
   • 알고리즘은 현재 솔루션에서 고정된 수($n$)의 작업을 해제하고 이를 무작위로 재할당을 시도하는 해체 및 재구성(deconstruction and reconstruction) 주기를 통해 작동한다.
   • 고정된 단계 크기를 보완하기 위해, 알고-리즘은 스케줄링 문제의 높은 대칭성을 활용한다. 무작위 교환(random swaps)을 통해 "동등한" 솔루션(동일한 점수를 가진 서로 다른 스케줄)을 탐색함으로써, 계산 비용이 많이 드는 큰 단계 없이도 탐색의 다양성을 확보한다.

2. 알고리즘 구조:

   • 분해 (문제 이분법): 일일 스케줄을 운전자의 교대 근무 중첩을 기준으로 두 개의 하위 문제(오전 및 오후)로 나누어 병렬 처리가 가능하도록 한다.
   • 웜 스타트(Warm-Start) 휴리스틱: rVNS는 자격 있는 운전자가 적고 의무 식사 시간이 포함된 작업을 우선시하는 그리디(greedy) 휴리스틱에 의해 생성된 솔루션으로 초기화된다. 이는 탐색이 좋지 않은 지역 최적점(local optimum)에서 시작하는 것을 방지한다.
   • 이중 목적 무작위화: 알고리즘은 목적 함수의 수렴 여부에 따라 두 가지 무작위화 전략을 교대로 사용한다:
     • 주요 초점: 미할당 작업을 위한 공간을 만들기 위해 유사한 시간적 위치를 가진 작업을 해제한다.
     • 부차적 초점: 총 주행 거리에 가장 크게 기여하는 작업을 해제한다.
   • 순서 결정 휴리스틱: 빠른 휴리스틱(알고리즘 3)은 제약 조건을 위반하지 않고 작업이 운전자의 순서에 삽입될 수 있는지 확인하며, 이는 재구성 단계에서 속도를 유지하는 데 매우 중요하다.
   • 협력적 병렬화: 멀티 스타트 전략은 8개의 코어(하위 문제당 4개씩)에서 실행된다. 10초마다 병렬 단위들은 결과를 공유하고 현재 최적의 솔루션에서 다시 시작하여 분산을 줄이고 지역 최적점을 피한다.

3. 목적 함수:
   전체 목적 함수 $F$는 작업 할당을 우선시한 후 주행 거리 감소, 마지막으로 미션 효율성을 고려하는 가중 합계이다:
   $$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$$
   여기서 $a_i$는 미할당 작업을, $x_i$와 $y_i$는 이동 거리를, $e_i$는 미션 시작 횟수를 나타낸다.

주요 결과
본 연구는 제안된 rVNS를 그리디 휴리스틱(Greedy Heuristic) 및 메타휴리스틱(Matheuristic)([1]에서 이미 개발됨)과 두 가지 데이터셋(S1: 적고 제약이 많은 작업; S2: 많고 제약이 적은 작업)을 사용하여 비교한다.

• 작업 할당: rVNS는 이전 방법들을 크게 능가한다. 그리디 및 메타휴리스틱 방식이 약 80~89%의 작업을 할당한 반면, rVNS는 두 데이터셋 모두에서 **99.0% ~ 99.8%**의 할당률을 달로 달성했다.
• 주행 거리 감소: rVNS는 메타휴리스틱과 비교했을 때 S1 데이터셋에서는 약 30%, **S2 데이터셋에서는 약 20%**의 총 함대 주행 거리를 줄였다.
• 안정성 및 수렴성:
  • 병렬화된 rVNS는 순차적 버전보다 더 높은 일관성을 보였으며, 주행 거리의 표준 편차가 순차적 방식의 46%에 비해 23%로 나타났다.
  • 수렴 속도: 작은 데이터셋(S1)의 경우, 주요 목적(작업 수)은 빠르게 수렴(~1초 이내)했으나, 주행 거리 최적화는 1분까지 계속 개선되었다. 더 큰 데이터셋(S2)의 경우, 주요 목적은 ~10초 만에 수렴했으며, 1분 이후에는 수익 체감(diminishing returns)이 나타났다.
• 실행 시간: 모든 솔루션은 요구되는 1분의 시간 창 내에 생성되었다(오버헤드를 포함하여 구체적으로 약 55~60초).

의의 및 주장
본 논문은 rVNS 메타휴리틱이 기존의 정확한(exact) 방식 및 휴리스틱 베이스라인을 능가하는 견고하고 유연한 솔루션을 제공한다고 주장한다. 이 연구의 주요 의의는 다음과 같다:

1. 운영 가능성: 실시간 배차에 필요한 엄격한 1분의 시간 내에 고도로 제약된 다중 목적 문제를 해결한다.
2. 이중 최적화: 작업 완료 극대화와 운영 비용(주행 거리) 최소화 사이의 균형을 성공적으로 맞추었으며, 이는 이전 연구에서 완전히 최적화되지 못한 부분이다.
3. 유연성: 저자들은 알고리즘 구조가 전기 차량 충전 또는 다중 데포(multi-depot) 운영과 같은 새로운 제약 조건이나 목적을 통합할 수 있다고 언급한다.
4. 실제 적용: 본 연구는 알고리즘이 기존 모델보다 실제 데이터(슬라이딩 타임 윈도우 및 이질적 함대 포함)의 복잡성을 더 잘 처리할 수 있음을 입증하며, 지상 조업사가 매일 수백 개의 작업을 자동으로 할당하는 데 사용할 수 있는 도구를 제공한다.

저자들은 알고리즘이 전역 최적해(global optimum)를 보장하지는 않지만, 속도와 품질 모두에서 기존 방법보다 우수한 솔루션으로 지속적으로 수렴한다는 점을 인정하며 절대적 최적성에 대해서는 신중한 태도를 유지한다. 또한 지연된 작업이 동적으로 재스케줄링되어야 하는 실시간 재할당 시나리오에 대한 향후 적용 가능성을 강조한다.