기술 요약: 서비스 접근성 보장을 갖춘 확장 가능한 차량 호출형 차량 재배치(Rebalancing)

1. 문제 정의

본 논문은 대규모 차량 호출 시스템(예: Uber, Didi Chuxing)에서의 **차량 재배치 문제(vehicle rebalancing problem)**를 다룹니다. 핵심 과제는 차량 공급과 승객 수요 사이의 시공간적 불일치입니다. 기존 방식들은 시스템 전체의 효율성(예: 수익 극대화 또는 대기 시간 최소화)을 최적화하는 데 집중하는 반면, **서비스 접근성(service accessibility)**을 간과하여 수요가 낮은 지역이 소외되는 불평등한 서비스 분포를 초래하는 경우가 많습니다.

이 문제는 다음과 같은 세 가지 주요 난제로 특징지어집니다:

1. 확장성(Scalability): 전통적인 중앙 집중식 강화학습(RL)은 차량 수가 증가함에 따라 "차원의 저주" 문제를 겪습니다. 다중 에이전트 강화학습(MARL)은 차원을 줄여주지만, 비정상성(non-stationarity)과 조정의 복잡성을 유발합니다.
2. 불확실성(Uncertainty): 시스템은 확률적인 수요와 명시적으로 모델링하기 어려운 복잡한 차량-승객 매칭 메커니즘을 포함합니다.
3. 형평성 제약(Equity Constraints): 지리적 영역 전반에 걸쳐 최소한의 서비스 접근성을 보장하는 것은 최적화 문제에 강력한 제약을 추가하며, 이는 표준 강화학습 프레임워크 내에서 처리하기 매우 까다로운 문제입니다.

2. 방법론

저자들은 평균장 강화학습(Mean-Field Reinforcement Learning, MFRL) 접근법을 제안하며, 이를 평균장 제어(Mean-Field Control, MFC) 모델로 보완합니다. 이 프레임워크는 차량 군단을 개별적인 이산 에이전트가 아닌 연속적인 분포로 취급합니다.

2.1 평균장 정식화 (Mean-Field Formulation)

문제는 **제약된 평균장 마르코프 결정 과정(Constrained Mean-Field Markov Decision Process, C-MF-MDP)**으로 정식화됩니다.

• 상태 공간(State Space): 대표 차량의 연속적인 2D 좌표.
• 평균장 분포 ($\mu_t$): 차량 규모 $L \to \infty$일 때의 차량 군단 한계 분포를 나타냅니다.
• 행동(Actions): 연속적인 재배치 확률($p_t$)과 이동 벡터($u_t$).
• 전이(Transitions): 상태 전이는 재배치(repositioning), 매칭(승객 서비스), 순항(cruising)의 세 가지 결과로 분해됩니다. 매칭 확률은 가용 차량 분포와 수요 분포 간의 상호작용에 의해 결정됩니다.

2.2 역학(Dynamics)에 대한 두 가지 접근법

본 논문은 미지의 전이 역학(특히 매칭 프로세스)을 처리하기 위해 두 가지 구별된 방법을 개발했습니다.

1. 평균장 제어 (MFC): **최적 운송(Optimal Transport, OT)**을 사용하여 매칭 프로세스의 폐쇄형 근사(closed-form approximation)를 가정합니다. 매칭은 공급 및 수요 분포 사이의 최소 비용 흐름 문제로 모델링됩니다. 이는 높은 샘플 효율성을 가진 모델 기반 솔루션을 제공합니다.
2. 평균장 강화학습 (MFRL): 에피소드 기반 상호작용을 통해 데이터로부터 매칭 프로세스를 직접 학습합니다. 이진 분류기를 훈련시켜 공급-수요 상태에 따른 매칭 확률을 예측하도록 하며, 이를 상태 전이 함수 근사에 사용합니다.

2.3 접근성 제약 처리

서비스 접근성을 강제하기 위해, 저자들은 가용 차량 분포의 **$\epsilon$-스무딩 가중 차분 엔트로피($\epsilon$-smoothed weighted differential entropy)**에 기반한 제약을 도입합니다.

• 제약 조건: $h_w(\mu_t, \pi_t) \ge C$, 여기서 $C$는 엔트로피의 하한값입니다.
• 메커니즘: 높은 엔트로피는 차량의 균등한 분포를 의미하며, 이는 (강이나 도로 등 운영 불가능한 구역을 제외한) 서비스 영역 전반의 커버리지를 보장합니다.
• 최적화: 제약된 문제는 로그 배리어(log-barrier) 방법을 사용하여 무제약 문제로 변환됩니다. 즉, 보상 함수에 $\lambda \log(h_w - C)$라는 페널티 항을 추가합니다. 이를 통해 훈련 중 정책이 실행 가능한 영역 내에 머물도록 합니다.

3. 주요 기여

본 논문은 다음과 같은 기여를 주장합니다:

• 강화학습에 접근성 통합 최초 시도: 저자들이 아는 바로는, 확률적 전이와 비정상적 수요 하에서 RL 기반 차량 재배치에 서비스 접근성 제약을 통합한 첫 번째 연구입니다.
• 연속 공간 확장성: 기존의 구역 단위 이산 방식과 달리, 제안된 MFC 및 MFRL 모델은 연속 공간에서 작동하며, 차량 규모가 변하더라도 재학습 없이 수만 대의 차량까지 확장 가능합니다.
• 효율성-형평성 파레토 프런트(Efficiency-Equity Pareto Front): 이 접근법은 효율성(이용률, 이행률)과 형평성(접근성) 사이의 트레이드오프를 성공적으로 탐색하며, 벤치마크 모델들을 능가합니다.
• 강건성(Robustness): 제안된 모델은 가우시안 노이즈, 시간적 순열, 갑작스러운 수요 충격 등 다양한 수요 변화에 대해 강건함을 입증했습니다.

4. 실험 결과

방법론은 **중국 선전(Shenzhen)**의 실제 택시 궤적 데이터(차량 18,000대, 6시간 피크 타임)를 사용하여 평가되었습니다.

4.1 계산 효율성

• 훈련: MFC 훈련에는 약 40분이 소요되었고, MFRL 훈련에는 약 26분이 소요되었습니다.
• 추론(Inference): MFC와 MFRL 모두 GPU 상에서 18,000대의 차량에 대한 재배치 정책을 생성하는 데 0.001분 미만(1초 미만)이 소요되었습니다.
• 비교: 이는 추론에 12~19분이 소요되는 CPU 기반 선형 계획법(LP) 벤치마크보다 현저히 빠릅니다.

4.2 성능 지표

• 접근성 vs. 효율성: 접근성 제약($p$)이 엄격해질수록 접근 가능한 구역의 비율은 증가했으나, 이용률 및 서비스율과 같은 지표는 약간 감소했습니다. 그러나 그 감소 폭은 미미했습니다(예: 상당한 접근성 이득을 위해 이용률 손실은 5% 미만). 이는 주요 효율성을 희생하지 않고도 높은 형평성을 달고할 수 있음을 나타냅니다.
• 벤치마크 비교: MFC와 MFRL 모두 서비스 이행, 이용률, 픽업 거리 측면에서 "재배치 없음(No Rebalancing)", "정적 LP(Static LP)", "동적 LP(Dynamic LP)" 정책보다 우수한 성능을 보였습니다. 일반적으로 MFRL이 MFC보다 약간 더 나은 성능(최대 5% 차이)을 보였으나, 훈련 시 계산 비용은 더 높았습니다.
• 충격에 대한 강건성: 가상의 수요 충격(예: 저수요 구역에 5,200건의 요청이 급증하는 상황) 발생 시, 제안된 정책은 70%에서 85% 사이의 서비스율을 유지한 반면, 벤치마크(LP 및 재배치 없음)는 요청의 40% 이상을 처리하지 못했습니다. 접근성 제약은 이러한 예측 불가능한 시나리오에서 서비스를 유지하는 데 결정적인 역할을 했습니다.

5. 의의 및 주장

본 논문은 자신의 연구를 확장 가능하고 형평성 있는 도시 모빌리티 관리를 향한 중요한 진전으로 규정합니다.

• 확장성: 평균장 근사를 활용함으로써 차량 규모가 변해도 모델을 재학습할 필요가 없으며, 이는 대도시 규모의 배포에 적합합니다.
• 형평성: 단순한 수익 중심 최적화를 넘어, 수학적으로 최소 수준의 서비스 접근성을 보장함으로써 차량 호출 서비스의 "공정성" 비판에 대응합니다.
• 실용성: 1초 미만의 추론 시간은 이 접근법이 실시간 배포가 가능함을 시사하며, 전통적인 최적화 방법보다 시장 변화에 더 빠르게 대응할 수 있습니다.

저자들은 현재 모델이 완전한 드라이버 준수를 가정하고(인간 행동 무시) 시간 이산화를 사용한다는 점을 언급하며 한계를 인정했습니다. 향후 연구로는 다중 플랫폼 경쟁, 더 세밀한 로컬 제약 조건, 그리고 자율주행 차량 군단의 통합 등을 제시했습니다.