HCRide: Harmonizing Passenger Fairness and Driver Preference for Human-Centered Ride-Hailing

기술 요약: HCRide – 승객의 형평성과 운전자의 선호도 조화

문제 정의
본 논문은 플랫폼 수익과 시스템 효율성을 우선시하느라 승객 경험과 운전자 만족도를 소홀히 하는 기존 차량 호출 주문 배차 시스템의 한계를 다룹니다. 구체적으로, 현재의 접근 방식들은 다음과 같은 두 가지 핵심적인 인간 중심적 요소를 자주 간과합니다:

1. 승객 형평성: 기존의 형평성 모델은 지역에 관계없이 절대적인 대기 시간의 동일성을 가정하며, 다양한 시공간적 맥락에 따른 동적인 수급 변동을 무시합니다.
2. 운전자 선호도: 운전자는 특정 지역(예: 집 근처 또는 익숙한 지역)에서 운행하고자 하는 뚜렷한 선호도를 가지고 있으나, 배차 시스템은 종종 이들을 낯설거나 원치 않는 구역으로 배정하여 불만족과 운영 효율 저하를 초래합니다.

저자들은 주문 배차 문제를 **제약된 마르코프 결정 과정(Constrained Markov Decision Process, CMDP)**으로 공식화합니다. 목표는 장기적인 누적 보상(시스템 효율 및 승객 형평성)을 최대화하는 동시에, 누적 비용(운전자 선호도 위반)이 미리 정해진 임계값 미만으로 유지되도록 보장하는 것입니다.

방법론: HCRide 및 Habic
이 CMDP를 해결하기 위해 저자들은 새로운 다중 에이전트 강화 학습 알고리즘인 Harmonization-oriented Actor-Bi-Critic (Habic) 기반의 인간 중심 프레임워크인 HCRide를 제안합니다. 이 시스템은 세 가지 핵심 구성 요소로 구축되었습니다:

1. 시공간적 형평성 및 선호도 모델링:

   • 승객 형평성: 두 단계로 정의됩니다. *지역 내 형평성(Intra-region fairness)*은 동일한 지역과 시간대의 승객들이 유사한 대기 시간을 경험하도록 보장합니다. *지역 간 형평성(Inter-region fairness)*은 대기 시간이 지역 밀도에 따라 자연스럽게 달라질 수 있음을 인정하며, 수급 비율에 기반한 동적인 벤치마크를 설정합니다.
   • 운전자 선호도: 과거 방문 빈도를 사용하여 모델링됩니다. 지역은 긍정(Positive, $H^+$), 중립(Neutral, $H^0$), 부정(Negative, $H^-$) 집단으로 분류됩니다. 운전자를 $H^-$ 지역에 배차할 경우 비용이 발생하며, 그 크기는 운전자의 가장 가까운 선호 지역까지의 거리에 의해 결정됩니다.

2. 다중 에이전트 경쟁 메커니즘:
   거대한 결합 행동 공간(joint action space)을 관리하기 위해, 시스템은 문제를 더 작고 분산된 행동 공간으로 변환합니다. 각 주문에 대해, 특정 범위 내의 제한된 후보 운전자 집단이 작업을 두고 경쟁합니다. 이 메커니즘은 "매칭 특징(matching features)"(운전자 상태와 주문 상태의 결합)을 생성하여, 다양한 선호도를 가진 이질적인 운전자들 사이의 미시적 의사결정을 촉진합니다.

3. Harmonization-oriented Actor-Bi-Critic (Habic) 알고리즘:

   • 동적 액터 네트워크(Dynamic Actor Network): 매칭 특징을 활용하여 최적의 운전자를 선택합니다. 보상 최대화와 제약 조건 충족 사이의 균형을 맞추기 위해 정책 파라미터($\theta$)와 라그랑주 승수($\lambda$)를 교대로 업데이트합니다.
   • 바이-크리틱 네트워크(Bi-Critic Network): 두 개의 평가 네트워크로 구성됩니다. **보상 크리틱(Reward Critic)**은 누적 보상(효율 및 형평성)을 추정하고, **비용 크리틱(Cost Critic)**은 누적 비용(선호도 위반)을 추정합니다. 두 네트워크 모두 안정적인 학습과 수렴을 위해 일반화된 어드밴티지 추정(Generalized Advantage Estimation, GAE)과 근사 정책 최적화(Proximal Policy Optimization, PPO-Clip)를 활용합니다.

주요 기여

1. 새로운 프레임워크: 본 연구는 전체 시스템 효율성을 저해하지 않으면서 승객 형평성과 운전자 선호도를 동시에 최적화하는 인간 중심 차량 호출 배차에 관한 첫 번째 연구를 제시합니다.
2. 데이터 기반 정의: 저자들은 질적 연구와 100만 개 이상의 실제 주문에 대한 양적 분석을 통해 도출된, 시공간을 고려한 형평성 및 운전자 선호도의 공식적 정의를 도입했습니다.
3. 알고리즘 혁신: 동적인 환경에서 제약 최적화 문제를 효과적으로 해결하기 위해 다중 에이전트 경쟁 메커니즘과 Bi-Critic 구조를 통합한 Habic 알고리즘을 개발했습니다.

실험 결과
HCRide 시스템은 두 개의 실제 데이터셋인 심천(주문 107만 건)과 뉴욕시(주문 21.4만 건)를 사용하여 평가되었습니다. 이는 근시적 배차(myopic dispatching), 단일 에이전트 및 다중 에이전트 RL 방법, 그리고 제약 RL 접근법을 포함한 8개의 베이스라인과 비교되었습니다.

최신 기술 수준(state-of-the-art)의 베이스라인 대비 HCRide의 주요 성능 개선 사항은 다음과 같습니다:

• 시스템 효율성: 최신 베이스라인인 Lag-TRPO 대비 평균 승객 대기 시간(APWT)을 2.02%(심천) 및 2.02%(NYC) 감소시켰습니다.
• 승객 형평성: 지역 간 형평성을 5.29%(심천) 및 5.28%(NYC) 개선하였고, 지역 내 형평성을 7.65%(심천) 및 5.39%(NYC) 개선하였습니다.
• 운전자 선호도: 선호도 위반율을 7.77%(심천) 및 10.21%(NYC) 감소시켰습니다.

의의 및 주장
본 논문은 HCRide가 차량 호출 배차에서 상충하는 목표들을 성공적으로 조화시킨다고 주장합니다. 운전자의 선호도를 사후 고려 사항이 아닌 하나의 제약 조건으로 취급하고, 형평성을 절대적 평등이 아닌 시공간적 관점에서 정의함으로써, 시스템은 더욱 균형 잡힌 생태계를 달 구축합니다. 저자들은 이 접근 방식이 승객과 운전자 모두의 사용자 경험을 향상시킬 뿐만 아니라 플랫폼의 운영 효율성을 유지하거나 개선하여, 보다 지속 가능하고 인간 중심적인 차량 호출 서비스를 향한 실행 가능한 경로를 제공한다고 확언합니다.