Batching 기반 Global Optimization을 통한 전체 ETA 50% 절감

Context

개별 요청마다 최단 거리 드라이버를 매칭하는 Greedy Approach의 한계로 인한 시스템 전체 대기 시간 증가 문제 발생. 국소적 최적화가 전체 시스템의 효율성을 저해하는 Global Optimum 부재 상황 분석.

Technical Solution

• 2~5초 단위의 Batching Window 도입을 통한 다수 요청의 동시 처리 구조 설계
• Bipartite Graph 모델 기반의 Minimum Weight Bipartite Matching 문제로 공식화
• Hungarian Algorithm 적용을 통한 전체 배차 비용(ETA) 최소화 및 Global Optimization 달성
• S2 Cell 기반 필터링에서 H3 Hexagon Index로 전환하여 인접 셀 간 거리 균일성 확보 및 Proximity Search 정확도 향상
• 단순 거리 계산 대신 Routing Service와 DeepETA를 결합한 실제 주행 기반 ETA 산출 로직 적용
• Reinforcement Learning 기반의 MDP 모델을 도입하여 즉각적 매칭 대신 미래 유동성을 고려한 배차 전략 최적화