Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

기술 요약: 동적 다중 차량 경로 결정을 위한 보상 밀도 휴리스틱

문제 정의
본 논문은 오리엔티어링 문제(Orienteering Problem, OP)의 요소가 통합된 동적, 온라인 변형 VRP(Vehicle Routing Problem)를 다룬다. 이 정식화에서 함대는 누적 보상을 최대화하기 위해 고정된 시간 범위 내에서 운영된다. 정적 VRP 변형과 달리, 작업이 동적으로 발생(온라인)하므로 지속적인 재계획(replanning)이 필요하다. 이 문제는 차량당 시간 예산 제약을 가지며, 차량은 이동 시간과 서비스 시간의 합이 남은 예산을 초ert지 않을 때만 작업을 할로 할당받을 수 있다. 이러한 구조는 새로운 요청이 발생할 때 밀리초 단위로 할당 결정이 이루어져야 하는 자율 드론 작업 할당 및 도시 택시 배차와 같은 실제 시나리오를 모델링한다.

방법론
저자들은 "보상 밀도 휴리틱"(효율성 휴리스틱이라 명명됨)을 네 가지 구성 휴리스틱 및 세 가지 메타휴리스틱 알고리즘과 비교하여 제안하고 평가한다.

1. 제안된 접근 방식 (효율성 휴리스틱):
   핵심 방법론은 보상 밀도에 기반한 점수 함수이며, 이는 작업의 보상($R$)을 총 시간 비용(이동 시간 $d$ + 서비스 시간 $s$)으로 나눈 비율로 정의된다:
   $$\eta(\tau) = \frac{R(\tau)}{d(v, \tau) + s(\tau)}$$
   두 가지 구현 방식이 테스트된다:

• Greedy-Efficiency: 사용 가능한 각 차량을 순차적으로 가장 높은 점수를 가진 미할당 가능 대상에 할당한다.
• Hungarian-Efficiency: 음의 보상 밀도($-\eta$)를 비용 행렬로 사용하여 할당 문제를 선형 할당 문제(Linear Assignment Problem, LAP)로 정식화하며, 이를 허니가티(Hungarian) 알고리즘을 통해 최적으로 해결한다.

2. 비교 베이스라인:

• 구성 휴리스틱: Greedy-Nearest (거리 최소화), Greedy-Reward (원시 보상 최대화), Hungarian-Time (이동 시간 최소화), 그리고 Hungarian-Reward (LAP를 통한 원시 보상 최대화).
• 메타휴리스틱: 적응형 대규모 이웃 탐색(ALNS), 유전 알고리즘(GA), 그리고 시뮬레이티드 어닐링(SA). 이들은 변화하는 환경에 적응하기 위해 매 재계획 이벤트 시마다 재초기화된다.

3. 실험 설정:
   본 연구는 작업 완료 시 재계획이 트리거되는 이벤트 기반 시뮬레이터를 활용한다. 평가는 두 가지 도메인에서 수행된다:

• 합성 드론 환경: $5000 \times 5000$ 맵에서 50~200개의 타겟을 대상으로 작동하는 12, 20, 50대의 드론.
• 실제 택시 배차: 약 7,600개의 작업(NYC TLC Yellow Cab 2024 데이터셋에서 추출)을 대상으로 120분 동안 작동하는 50대 및 200대의 택시.
  성능은 누적 보상(또는 수익)과 계획 시간(계산 비용)에 의해 측정된다.

주요 결과
실험은 효율성 휴리스틱이 모든 경쟁 방법론에 대해 명확한 파레토 우위(Pareto dominance)를 점함을 입증한다:

• 솔루션 품질: 효율성 휴리스틱(Greedy 및 Hungarian 변형 모두)은 모든 함대 규모와 도메인에 걸쳐 가장 성능이 좋은 메타휴리스틱(ALNS, GA, SA)과 통계적으로 구별할 수 없는 수준의 솔루션 품질을 달성한다. 반면, 단순한 휴리스틱(Greedy-Nearest, Greedy-Reward, Hungarian-Time, Hungarian-Reward)은 일관되게 보상/수익 측면에서 통계적으로 유의미한 결손을 보이며 성능이 저하된다.
• 계산 효율성: 효율성 휴리스틱은 메타휴리스틱보다 2~3 자릿수 적은 계획 시간을 요구한다.
  • 50대 드론 시나리오에서 Hungarian-Efficiency는 약 128ms가 소요된 반면, GA는 약 110만 ms, ALNS는 약 42,654ms, SA는 약 5,247ms가 소요되었다.
  • 200대 택시 시나리오에서 Hungarian-Efficiency는 약 363ms가 소요된 반면, GA는 약 458만 ms가 소요되었다.
• Greedy vs. 전역 최적성: 본 연구는 계산 비용이 더 저렴한 Greedy-Efficiency 방식이 전역 최적인 Hungarian-Efficiency 방식과 통계적으로 동등한 결과를 낸다는 것을 발견했다. 이는 이러한 동적, 고빈도 환경에서 허니가티 알고리즘의 전역 최적성 보장이 실질적인 이득을 거의 제공하지 못함을 시사한다.

의의 및 주장
본 논문은 최적화 기준의 선택(보상 밀도/효율성)이 할당 메커니즘의 정교함보다 더 중요하다고 주장한다.

• 구조적 이점: 효율성 휴리스틱의 성공은 동적 보상 최대화 경로 결정에서, 단순히 원시 보상이나 이동 시간만을 최적화하는 것보다 보상 대비 비용의 비율(효율성)을 최적화하는 것이 함대 차원의 가치 창출을 위한 더 우수한 프록시(proxy)임을 시사한다.
• 실용적 생존 가능성: 메타휴리스틱은 유사한 솔루션 품질 상한에 도달할 수 있음에도 불구하고, 실시간 배차를 불가능하게 만드는 계획 시간을 초래한다. 솔루션이 생성되기 전에 환경이 실질적으로 변해버리는 몇 분 단위의 계획 주기는 라이브 운영에서 "적극적으로 해로운(actively harmful)" 것으로 묘사된다.
• 파레토 우위: 효율성 휴리스틱은 보상 대 계산량의 경계선에서 파레토 우위를 확립하며, 최소한의 계산 오버헤드로 최적에 가까운 성능을 제공한다.

저자들은 실시간 함대 배차를 위해서는 알고리즘의 복잡성보다 목적 함수 설계(특히 보상 밀도 스코어링)가 더 중요하며, 따라서 효율성 휴리스틱이 계획 시간이 제약 조건인 운영 시스템의 강력한 후보라고 결론짓는다. 본 연구는 실험의 시뮬레이션 기반 특성과 수익을 단일 목표로 집중한 점을 한계로 인정하며, 향-연구에서는 다목적 제약 조건과 비정상적(non-stationary) 수요를 탐구해야 한다고 언급한다.