Meeting equity requirements in shared micromobility rebalancing: a constrained Markov decision process with a case study in The Hague

기술 요약: 공유 마이크로모빌리티 재배치에서의 형평성 요구사항 충족

문제 정의
공유 마이크로모빌리티 시스템은 차량을 수요가 높고 중심적이며 부유한 지역에 집중시키는 반면, 주변부 및 저소득 지역은 서비스가 부족하게 만듦으로써 도시의 불평등을 재생산하는 경우가 많다. 일반적으로 수익을 극대화하는 표준 재배치 정책은 이러한 "파편화된 도시주의(splintering urbanism)"를 악화시킨다. 도시들이 특정 구역 내 최소 차량 점유율과 같은 형평성 요구사항을 점점 더 많이 부과하고 있지만, 현재의 운영 방식은 이러한 명령을 효율적으로 충족하는 데 어려움을 겪고 있다. 기존의 강화 학습(RL) 접근 방식은 보상 함수에 가중치 페널티를 추가하여 형평성을 통합하려고 시도한다. 그러나 이 방법은 페널티 가중치를 시행착오 방식으로 튜닝하는 것에 의존하며, 특정 규제 임계값(예: 최대 서비스 실패율)이 반드시 충족될 것이라는 직접적인 보장을 제공하지 못하며, 더 엄격한 규칙을 적용할 때의 비용-편익 분석을 명확히 제시하지도 못한다.

방법론
저자들은 차량 재배치 문제를 **제약 마르코프 결정 과정(Constrained Markov Decision Process, CMDP)**으로 재구성할 것을 제안한다. 형평성을 보상 형성(reward shaping)을 통해 암묵적으로 인코딩하는 대신, 이 방법은 형평성을 서비스 실패율(사용자가 차량을 찾지 못하는 비율)에 대한 명시적인 제약 조건으로 취급한다.

• 정식화: 서비스 영역은 중심부에서 주변부까지 단계별로 분류된 카테고리로 나뉜다. 문제는 시간대, 구역 카테고리, 차량 재고를 상태(state)로 포함하는 MDP로 모델링된다. 목표는 장기 보상(재배치 비용 및 차량 페널티 최소화)을 극대화하되, 각 구역 카데고리와 시간대에 대한 기대 서비스 실패율이 도시가 정의한 임계값($r_{max}$)을 초과하지 않아야 한다는 제약을 준수하는 것이다.
• 해결 알고리즘: CMDP는 **요인 분해 라그랑주 Q-러닝(Factorized Lagrangian Q-learning)**을 사용하여 해결된다.
  • 라그랑주 완화(Lagrangian Relaxation): 제약 조건은 각 카테고리와 시간대에 대한 적응형 페널티(이중 변수 $\lambda$)를 도입하여 이중화된다. 이 변수는 서비스 실패에 대한 가격 역할을 하며, 실패가 목표치를 초 exceed하면 증가하고 목표치 아래로 떨어지면 감소한다.
  • 요인 분해(Factorization): 구역 간 수요가 독립적이라는 가정하에, 문제는 하나의 카테고리당 하나의 에이전트가 관리하는 구역별 하위 문제로 분해된다. 동일한 카테고리 내의 모든 구역은 하나의 Q-테이블을 공유하며, 해당 카테고리의 모든 구역으로부터 결합된 경험을 통해 업데이트된다.
  • 프라이멀-듀얼 업데이트(Primal-Dual Updates): 알고리즘은 수정된 보상(기본 보상에서 $\lambda \times$ 실패를 뺀 값)을 최적화하기 위한 Q-값 업데이트(primal)와, 슬라이딩 윈도우를 통해 평균적인 제약 위반을 기반으로 한 이중 변수 업데이트(dual)를 교대로 수행한다.
• 실제 환경 적응: 헤이그(The Hague) 사례 연구를 위해, 저자들은 구역 간 불균등한 용량을 처리할 수 있도록 차량 재고를 점유율(0~1)로 정규화하여 모델을 조정했다. 또한 가중 k-평균 클러스터링을 사용하여 스테이션 위치를 기반으로 서비스 구역을 구성하였고, 국가 여행 조사(ODiN) 및 주소 레지스트리를 사용하여 수요를 추정하였다.

주요 기여

1. 직접적인 제약 충족: 이 방법은 도시가 직접 최대 서비스 실패율을 지정할 수 있게 하여, 형평성 가중치를 시행착오 방식으로 튜닝할 필요를 없앤다. 알고리즘은 경계값($r_{max}$)을 충족하도록 재배치 전략을 자동으로 조정한다.
2. 비용 투명성: 이 접근 방식은 특정 형평성 목표를 달est하는 데 드는 운영 비용을 정량화한다. 이는 $r_{max}$ 경계가 엄격해질수록 재배치 비용이 증가함을 보여줌으로써, 도시가 정책 도입 전에 더 엄격한 규칙의 비용을 평가할 수 있게 한다.
3. 메트릭 선택: 논문은 지니 계수(Gini index)가 "서비스 하한선(service floor)"을 강제하기에는 부적절하다고 주장한다. 보상 형성이 (비율을 균등화하여) 지니 계수를 줄이는 반면, 제약 기반 접근 방식은 중심 구역의 높은 서비스를 유지하면서 주변부 구역을 개선한다. 이 과정에서 지니 계수가 정체되거나 최악의 경우 실패율이 개선됨에 따라 오히려 약간 상승할 수 있는데, 이는 최악의 경우 실패율이 이 목적에 더 적합한 메트릭임을 시사한다.
4. 실제 적용 가능성: 헤이그 사례 연구는 공개된 데이터(스테이션 피드, 주소 레지스트리, 여행 조사)를 사용하여 훈련된 재배치 전략을 생성할 수 있음을 입증한다.

결과

• 합성 네트워크: 5개 카테고리의 합성 네트워크에서, 이 방법은 모든 구역 카테고리와 시간대에 대해 지정된 실패율 임계값을 성공적으로 충족했다. $r_{max}$가 100%에서 5%로 엄격해짐에 따라 최악의 경우 실패율은 단조 감소했으나, 재배치 비용은 대략 두 배로 증가했다. 중심 구역은 제약의 영향을 받지 않은 반면, 주변 구역은 가용성이 크게 향상되었다.
• 보상 형정과의 비교: 보상 형성 베이스라인과 비교했을 때, 제약 기반 접근 방식은 격차를 좁히기 위해 잘 서비스되는 중심 구역의 서비스를 저하시키지 않았다. 대신, 절대적인 임계값을 충족하기 위해 자원을 소외된 구역에 집중하는 데 집중했다.
• 헤이그 사례 연구: 실제 데이터에 적용했을 때, 시스템은 이미 양호한 성능(제약이 없을 때 최악의 경우 약 2.8%의 실패율)을 보였다. 더 엄격한 경계값으로 테스트했을 때, 모델은 차량 규모와 재배치 작업을 늘림으로써 대응했다. 그러나 가장 엄격한 경계값(0.5% 및 0.75%)에서는 카테고리별 요인 분해(서로 다른 크기의 구역이 하나의 전략을 공유함)로 인해 가장 외곽의 구역들이 임계치를 약간 초과했는데, 이는 계산 효율성과 세밀한 제어 사이의 트레이드오프를 보여준다.

의의 및 주장
저자들은 본 연구가 규제적 형평성 요구사항과 운영 의사결정 사이의 간극을 메운다고 주장한다. 재배치를 CMDP로 프레이밍함으로써, 이 방법은 형평성 목표를 알려진 가격이 있는 계획 입력값으로 변환한다. 이를 통해 도시는 처방적인 입력값(차량 대수) 대신 결과 기반의 규칙(서비스 수준)을 집행할 수 있으며, 이는 국제 교통 포럼(ITF)과 같은 기관의 권고 사항과 일치한다. 논문은 이 접근 방식이 최악의 경우 실패율을 개선하면서도 나머지 네트워크의 효율성을 해치지 않고 소외 지역의 서비스 하한선을 유지할 수 있는 메커니즘을 제공함으로써, UN 지속가능발전목표(SDG) 11.2를 달성하기 위한 실행 가능한 경로를 제시한다고 결론짓는다. 저자들은 현재 모델이 독립적인 수요와 고정된 재배치 시점을 가정하고 있다는 점을 언급하며, 향후 수요 상관관계, 기간 내 재배치, 변화하는 수요 패턴에 대한 온라인 적응 등을 다루는 후속 연구가 필요함을 밝히며 겸허한 태도를 유지했다.