Regime-Calibrated Demand Priors for Ride-Hailing Fleet Dispatch and Repositioning

1. 문제 정의 (Problem Statement)

승차 호출 (Ride-hailing) 플랫폼은 하루에 수백만 건의 승차를 처리하며, 배차 (Dispatch) 및 차량 재배치 (Repositioning) 알고리즘의 효율성은 승객의 대기 시간, 운전자 활용도, 플랫폼 수익에 직접적인 영향을 미칩니다. 주요 과제는 수요의 불확실성입니다.

• 비정상성 (Non-stationarity): 시간대, 요일, 계절, 특수 이벤트 (명절, 행사 등) 에 따라 수요 패턴이 급격히 변합니다.
• 기존 방법의 한계: 대부분의 운영 알고리즘은 수요가 고정되어 있다고 가정하거나, 재학습 비용이 많이 드는 블랙박스 예측 모델 (예: 딥러닝) 에 의존합니다.
• 목표: 학습 없이도 즉각적으로 적응할 수 있으며, 설명 가능하고 결정론적인 (Deterministic) 방식으로 수요를 예측하여 대기 시간을 최소화하는 방법론이 필요합니다.

2. 제안 방법론 (Methodology)

저자들은 "레짐 보정 (Regime-Calibrated)" 접근법을 제안합니다. 이는 과거 데이터를 '수요 레짐 (Demand Regimes)'으로 세분화하고, 현재 상황을 가장 유사한 역사적 사례와 매칭하여 보정된 수요 사전분포 (Calibrated Demand Prior) 를 생성하는 방식입니다. 시스템은 크게 4 단계로 구성됩니다.

A. 데이터 수집 및 레짐 라이브러리 구축

• 데이터: 뉴욕 (NYC) TLC 의 2024 년 1 월 및 6 월 데이터 (약 520 만 건의 승차 기록) 를 활용합니다.
• 세그먼트: 데이터를 4 시간 단위의 블록으로 나누고, 각 블록은 요청률 프로파일, 공간적 기원 - 목적지 (OD) 분포, 이벤트 활동 (서지 발생 등) 으로 특징지어집니다. 총 373 개의 레짐 블록이 라이브러리를 구성합니다.

B. 6 가지 지표 기반 유사도 앙상블 (Similarity Ensemble)

현재 시점의 수요 패턴 (쿼리) 과 라이브러리의 각 레짐을 비교하기 위해 6 가지 지표를 가중 합산하여 유사도를 계산합니다.

1. Kolmogorov–Smirnov (KS): 분포 형태의 차이.
2. Wasserstein-1 (W1): 분포 간의 거리.
3. Feature Distance: 요약 통계량 (평균, 분산, 왜도 등) 의 유클리드 거리.
4. Variance Ratio: 분산 비율.
5. Event Pattern: 서지 (Surge) 이벤트의 강도, 지속 시간, 패턴 유사성.
6. Temporal Proximity: 같은 달, 같은 요일, 같은 시간대 보너스.

• 동작: 가장 유사한 상위 $k$개 (기본값 $k=5$) 의 레짐을 선택합니다.

C. 보정된 수요 사전분포 (Calibrated Demand Prior)

선택된 상위 $k$개 레짐의 수요 패턴을 가중 평균하여 현재 블록의 수요를 예측합니다.

• 가중치: 유사도 점수에 비례하여 할당됩니다.
• 공간적 구조: 선택된 레짐들의 실제 승차/하차 좌표를 풀링 (Pooling) 하여 공간적 상관관계를 보존합니다.
• 보정: 현재 블록의 관측된 요청 수에 맞춰 총량을 조정하여 과대/과소 예측을 방지합니다.

D. LP 기반 선제적 재배치 및 배차

• 재배치 (Repositioning): 보정된 수요 예측을 기반으로, 여유 차량이 많은 구역 (Surplus) 에서 수요가 예상되는 구역 (Deficit) 으로 차량을 이동시키는 최소 비용 수송 문제 (Min-cost Transportation LP) 를 풉니다. 이는 선형 프로그래밍 (Linear Programming) 으로 최적해를 보장합니다.
• 배차 (Dispatch): 대기 중인 요청과 차량을 매칭할 때, 헝가리안 알고리즘 (Hungarian Algorithm) 을 사용하여 배치 (Batch) 단위 (예: 60 초) 로 총 픽업 시간을 최소화합니다.

3. 주요 기여 (Key Contributions)

1. 학습 불필요한 레짐 보정 기법: 블랙박스 예측 모델 대신 역사적 유사 패턴을 기반으로 한 결정론적이고 설명 가능한 수요 사전분포를 제시했습니다.
2. 선제적 재배치를 위한 LP 최적화: 보정된 수요 예측을 활용하여 차량 재배치를 최적화하는 선형 프로그래밍 모델을 설계하고, 이론적으로 최적성과 민감도를 증명했습니다.
3. 도시 간 전이 및 강건성 검증: 뉴욕 (NYC) 에서 학습된 레짐 라이브러리를 재학습 없이 시카고 (Chicago) 데이터에 적용하여 유효성을 입증했습니다. 또한, 차량 대수 변화 (0.5 배~2 배) 에 따른 강건성을 검증했습니다.

4. 실험 결과 (Results)

뉴욕 TLC 데이터를 기반으로 8 가지 다양한 시나리오 (겨울/여름, 평일/주말/명절, 아침/저녁/심야) 에서 평가되었습니다.

• 대기 시간 감소: 평균 승객 대기 시간이 31.1% 감소했습니다 (95% 신뢰구간: [26.5%, 36.6%]).
  • 통계적 유의성: Friedman 검정 ($\chi^2 = 80.0, p = 4.25 \times 10^{-18}$) 및 Nemenyi 사후 검정을 통해 모든 비교 그룹 간 유의미한 차이가 확인되었습니다.
  • 효과 크기 (Cohen's d): 시나리오별로 7.5~29.9 로 매우 큽니다.
• 꼬리 (Tail) 성능 개선: 대기 시간이 긴 승객 (P95) 의 대기 시간은 37.6% 감소했습니다.
• 공정성 향상: 대기 시간의 지니 계수 (Gini Coefficient) 가 0.441 에서 0.409 로 개선되어 (상대적 7.3% 감소), 서비스 불평등이 완화되었습니다.
• 성분 분석:
  • 보정 (Calibration) 만으로도 대기 시간이 16.9% 감소.
  • 여기에 LP 재배치를 추가하면 추가 15.5% 감소 (합산 효과 약 29.8%).
• 도시 간 전이 (Cross-City Transfer): 뉴욕 모델로 시카고를 테스트했을 때 평균 23.3% 의 대기 시간 감소 효과를 보였습니다.
• 계산 효율성: 4 시간 시뮬레이션당 약 2.7 초 (Apple M 시리즈 CPU) 로 실행 가능하며, 기존 배차 방식 대비 오버헤드는 약 10% 수준입니다.

5. 의의 및 결론 (Significance)

• 실용성: 복잡한 딥러닝 모델의 학습 비용과 재학습 필요성 없이, 즉시 적용 가능한 경량화된 솔루션을 제공합니다.
• 설명 가능성: "왜 이 차량을 이 지역으로 보냈는가?"에 대해 유사한 과거 패턴과 수학적 최적화 근거로 명확히 설명할 수 있습니다.
• 강건성: 특수 이벤트 (명절, 금요일 밤 등) 와 같은 변동성이 큰 상황에서 기존 방법보다 훨씬 큰 개선 효과를 보였습니다.
• 한계 및 향후 과제: 현재는 맨해튼 중심의 데이터와 단순화된 라우팅 (Haversine) 을 사용하며, 차량 공유 (Pooling) 나 동적 가격 책정 (Surge Pricing) 은 고려하지 않았습니다. 또한, 유사도 앙상블의 가중치 자동 최적화 필요성이 제기되었습니다.

이 논문은 데이터 기반의 통계적 유사성 매칭과 최적화 기법을 결합하여, 실시간 승차 호출 시스템의 효율성을 획기적으로 높일 수 있는 새로운 패러다임을 제시했습니다.