[논문 리뷰] Large-Scale Order Dispatch in On-demand Ride Hailing Platforms - A Learning and Planning Approach

디디추싱 (滴滴出行, Didi Chuxing)

중국판 우버이자 라이드 헤일링 서비스를 제공하는 온디멘드 플랫폼 디디추싱에 대해서 알고 계신가요? 이용해보신 분들은 아주 편리한 서비스 라는 것을 느끼셨을 겁니다. 디디추싱 플랫폼에서는 승객의 호출과 드라이버들을 매칭시켜주는 시스템이 필요합니다. 이와 같은 프로세스를 배차(Order Dispatch)라고 합니다.

고전적인 배차 로직은 주문을 보낸 승객과 가장 가까운 곳에 있는 차량의 드라이버를 매칭 시켜주는 방식입니다. 하지만 디디추싱에서는 특정 지역에서 운전자가 얻을 수 있는 기대이익을 최대화 할 수 있는 배차를 수행하고 있습니다. 단순히 가장 가까운 곳에 있는 승객이 보낸 요청을 드라이버의 스마트폰 상에 띄워주는 것이 아니라, 장기적으로 봤을 때 이윤을 극대화 시킬 수 있는 매칭을 해주는 방식입니다. 이를 위해 디디추싱에서는 Reinforce Learning 의 바탕이 되는 Markov Decision Process을 사용했습니다.

제가 리뷰할 논문은 2018년에 발표된 Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach 이라는 논문 입니다.

1. Introduction

라이드 헤일링시스템은 전통적인 택시 시스템과 비교했을 때 택시기사가 승객을 태우러 돌아다니는 시간과 승객들의 대기 시간을 효과적으로 개선해왔습니다. 본 논문에서는 현대 택시 네트워크의 배차(Order Dispatch) 로직에 초점을 맞추고 있습니다. 이전의 대형 택시 회사에서는 승객을 모실 가장 가까운 운전자를 찾거나 선착순으로 운전자를 매칭 시켜주는 지역에 기반한 greedy methods를 사용해 왔습니다.

이러한 방법은 실행과 관리가 쉽다는 장점이 있지만 공급량 관리 보단 즉각적인 승객의 만족에만 초점이 맞춰진 경향이 있다는 단점이 있습니다. 택시 공급과 승객의 수요 사이에 시공간적인 불일치가 존재하기 때문에 이것은 장기적으로 볼 때 비효율을 초래할 수 있습니다. 논문의 목표는 배차(Order Dispatch)를 장기적인 관점에서 최적화하는 것 입니다. 이는 현재 고객의 수요를 충족시키는 동시에 예상되는 미래 이익 을 최적화 함으로서 가능할 수 있었습니다. 이 논문이 기여한 것은 크게 3가지 입니다.

 

• 즉각적인 이익(Immediate gain)과 기대 이익(Future Gain)을 모두 고려한다.
• 대규모 실시간 시스템에서 Reinforce Learning을 적용한 최초의 사례이다.
• 중국의 주요 도시에서 디디추싱의 매출을 0.5% ~ 5%까지 향상시켰다.

2. Background

논문에서 사용한 배차 알고리즘의 도입 배경을 이해하려면 전통 택시와 우버, 리프트와 같은 온디멘드 플랫폼 기업들의 운행 방식의 차이점을 이해하면 좋습니다. 각각의 운영 방식은 다음과 같습니다.

 

• 전통 택시 : 운전자 - 운전자의 승객 선택 - 매칭 - 운전자 모드 
• 플랫폼 기업 : 플랫폼 - 배차 - 매칭 - 운전자 모드

온디멘드 서비스를 운영하는 기업은 운전자와 승객의 요청 사이에 효과적인 매칭인 배차(Order Dispatch) 가 매우 중요합니다. 디디추싱에서는 이를 효과적으로 관리 하기 위해 택시의 위치 정보를 플랫폼 상에 주기적으로 업로드 했습니다. 승객이 보낸 정보를 플랫폼에서 관리했으며 앞으로 소개할 방법을 통해 승객과 운전자들을 효과적으로 매칭시켜왔습니다. 이를 위해 Markov Decision Process 라는 방식을 사용했습니다. 이에 대해서 잠깐 알아보도록 하겠습니다.

3. Markov Decision Process

강화학습은 Markov Decision Process(MDP)의 문제를 푸는 것이라고 말할 수 있습니다. 우리는 문제를 풀 때 어떤 문제를 풀 것인지 정의해야 하는데요. 강화학습이 푸는 문제들은 모두 MDP로 표현된다. MDP는 Markov Process에 기반합니다. MDP를 이해하려면 Markov Process(Markov Chain)의 개념에 대해 먼저 이해해야 합니다.

3.1 Markov Process

• 확률 가정: 시간이 진행 함에 따라 상태가 확률적으로 변화하는 과정. 어떤 확률 분포를 따르는 random variable이 discrete한 time interval 마다 값을 생성해 내는 것을 의미 합니다.
• Markov Process: time interval이 discrete하고 state가 이전 state에만 영향을 받는 확률 과정을 의미합니다. 아래의 그림이 이를 잘 표현하고 있습니다. 아래의 그림은 학생의 일과에 대한 Markov Process 입니다. 

  

  학생 일과에 대한 Markov Pricess

• Transition: 한 State에서 다른 State로 이동하는 것을 의미합니다. 한 state에서 다른 state로 이동할 확률 들의 합은 1 입니다. 즉, SNS라는 state에서 다시 SNS로 이동할 확률은 0.9 이고, Class 1 으로 이동할 확률은 0.1 이라고 할 수 있습니다.
• Terminal state란 다른 state로의 이동이 없는 마지막 state를 의미합니다. 위 그림에서는 sleep이 Terminal state가 되겠네요.
• stationary distribution: 무한대의 시간이 지나고 나면 Terminal state로 수렴하는 것을 의미합니다.

3.2 Markov Reward Process

Markov Reward Process란 Markov Process에 Reward 개념을 추가한 것을 의미합니다. 각 state별로 reward 개념이 적용되어 각 state의 가치를 정량화시킬 수 있습니다.

• Reward: Markov Process는 각 state별 transition 확률이 주어져 있을 뿐, 이 state에서 다음 state로 가는 것이 얼마나 가치 있는지는 알 수 없습니다. 이를 정량화 한 개념이 Reward 입니다.

 

3.3 Markov Decision Process

Markov Decision Process란 Markov Reward Process에 Action 개념이 추가된 것을 의미합니다.

• Action: state에서 agent가 취할 수 있는 행동을 의미합니다. MRP에서 state가 변한다는 것은 transition probability에 따른 임의의 변화입니다. 하지만 MDP에서는 state에서 action을 함으로써 state가 변하게 됩니다. 아래 그림은 디디추싱이 배차를 할 때 사용한 MDP Definition 입니다.

4. Learning

디디추싱의 배차 방식은 Learning과 Planning으로 나뉩니다.

 

• Learning : 과거 데이터를 통해 Markov Decesion Process를 학습시켰습니다. 이를 통해 기대이익을 정량화
• Planning : 승객과 운전자 사이의 실시간 매칭은 Decision-Making Problem in Multi-Agent Systems으로 공식화 되며 global optimum을 찾기 위해 Combinatorial Optimization을 사용

4.1 Problem Statement

디디추싱에서는 agent와 environment들을 어떻게 설정했을까요?

• Agent: 각각의 독립적인 운전자들을 Agent로 모델링 했습니다.
• State: 운전자의 state를 시간과 지역의 Cartesian Product로 정의했습니다.
• Action: 2개의 action이 있습니다.
  • serving: 운전자에게 특정 주문을 할당하는 것입니다. 이 경우 운전자가 지정된 장소에 가서 승객을 태운 다음 승객을 목적지로 보냅니다. 그리고 해당 호출에 대한 reward를 받습니다.
  • idle: 운전자가 한 시간 내에 어떤 승객 과도 매칭이 되지 않는 상황을 의미합니다.
• Reward: 운전자가 승객으로 부터 받는 가격으로 정의됩니다.
• Goal: GMV(Gross Merchandise Volume)를 maximize 하는 것입니다. 즉, 운전자들이 승객으로 받을 수 있는 매출을 최대화 시키는 것입니다.
• State-Value-function: 현재 state에서 미래에 받을 것이라 기대하는 reward의 합을 의미합니다.
• Q-function: 현재 state에서 이 action을 선택했을 때 미래에 받을 것이라 기대하는 reward의 합을 의미합니다.
• Policy: MDP와 같은 순차적 행동 결정문제에서 구해야할 답을 의미합니다. 즉, 모든 state에서 agent가 어떤 행동을 해야 하는지 정해놓은 것을 의미합니다.

4.2 Policy Evaluation

MDP definition에 정의하여 과거 데이터들의 transaction pairs를 serving actions, idle actions을 포함하는 (s, a, s', r) 으로 구성할 수 있습니다. 이는 s라는 state에 있는 운전자가 a라는 action을 통해 s'라는 state로 transition이 일어났으며 이에 따라 r만큼의 reward를 받았다고 해석할 수 있습니다. Learning step은 모든 state에서 얻을 수 있는 기대 이익을 계산하는 과정 state-value-function을 구하는 과정입니다. 간단한 예시를 들어보겠습니다. (모든 action은 serving으로 간주하겠습니다.)

state-value는 현재 state에서 미래에 받을 것으로 기대하는 reward들의 합을 의미한다고 했습니다.

• 먼저 위 그림에서 D, E는 Terminal state이기 때문에 state-value가 0입니다.
• B에서의 state-value는 D에서 발생하는 state-value인 0원에 B에서 D로 손님을 태울 때 받을 수 있는 기대이익인 10,000원을 더한 10,000 입니다.
• C역시 B와 같은 이유로 8,000 입니다.
• A의 경우 약간 복잡한데요, 먼저 B, C의 state-value인 10,000과 8,000에 각각으로 이동하는 기대이익을 더해줘야 합니다. 그래서 결국 21,800이라는 state-value를 구할 수 있습니다. 위 식에서 분모가 5인 이유는 기대 이익이기 때문에 해당 state에서 발생할 수 있는 전체 transition의 횟수 (5 = 2+3) 로 나눠줘야 합니다.

위 과정을 거치면 state-value table을 만들 수 있습니다.

5. Planning

planning 단계에서는 학습된 state-value functions을 입력으로 사용하며 실시간으로 운전자와 주문 사이에 최종적인 매칭. 즉, 배차를 수행합니다. 배차가 이루어지는 방식은 사실 간단합니다. 앞서 Q-Function이란, 현재 state에서 이 action을 선택했을 때 미래에 받을 것이라 기대하는 reward의 합이라고 말씀드렸는데요. Q-Function을 구하고 지금 선택할 수 있는 행동 중에 Q-Function이 가장 높은 쪽으로 배차를 해주는 것 입니다.

만약 S라는 곳에 운전자가 있었다고 합시다. A로 향하는 승객의 호출과 G로 향하는 승객의 호출이 있다고 합시다. 이 경우는 G로 가는 것이 reward를 최대화 할 수 있기 때문에 G로 향하는 승객과 매칭을 시켜주는 것이 플랫폼의 전체 기대이익을 최대화할 수 있는 방법입니다.

5.1 Advantage Function Trick

기존의 방식이라면 아래 그림의 왼쪽 처럼 운전자와 승객의 호출 사이에 모든 경우의 edge를 고려하여 연산을 진행해야 합니다. 하지만, 본 논문에서는 알고리즘의 computational complexity 를 줄이기 위해 default action을 모두 제거하는 function trick을 사용했습니다. (default action 이란 운전자가 아무것도 하지 않고 배차도 요청되지 않은 상태를 의미합니다.)

6. Conclusion

지금까지 디디추싱에서 운전자와 승객을 매칭해주는 배차(Order Dispatch) 방법에 대해서 알아보았습니다. 개별 드라이버들을 매출을 최대화 하는 방향으로 움직이게 함으로서 플랫폼 전체의 매출을 최대화 하는 방법이 매우 대단한 것 같습니다. 본 포스팅에서는 쉬운 이해를 위해 최대한 간략하게 전반적인 과정을 설명했는데요. 사실 Markov Decision Process 을 학습시키기 위해선 state-value-function 와 q function 을 구할 때 ETA(예상 도착 시간)와 예상 매출 을 함께 고려해야 합니다. 또한 미래에 발생하는 가치를 현재에 반영하기 위해선 적절한 가격으로 할인을 해줘야하는데 이를 위해서는 discount factor 를 정하고 각각의 기대 이익을 시간에 비례하여 적절하게 할인해줘야 합니다. (연금의 현재 가치를 계산하는 방식과 유사합니다.)

7. 느낀점

디디추싱은 전 세계를 대표하는 모빌리티 기업답게 서비스 플랫폼에서 발생하는 데이터를 실제 매출을 발생시킬 수 있는 방향으로 활용한다는 점이 매우 인상적이었습니다. 대부분의 모빌리티 플랫폼 기업들은 자율주행차 연구를 함께 진행하고 있습니다. 디디추싱도 관련된 활발한 연구와 사업들을 진행하고 있는데요. 이와 같은 연구 및 성과는 나중에 자율주행차가 등장했을 때도 엄청난 위력을 발휘할 것 같습니다.

모빌리티 데이터는 공부하면 할 수록 정말 활용할만한 곳이 많고 미래가치가 충분한 연구분야이기 때문에 더욱 재밌는 것 같습니다. Order Dispatch 이외에도 Dynamic Pricing, ETA, Spatio-Temporal Prediction, Traffic Estimation and Forecasting, Scheduling Optimization 등등 정말 수 많은 분야에서 데이터가 활용되고 있는데요. 제 블로그에 관련된 내용들을 차근차근 업로드 해볼 예정입니다.

Reference

• Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach
• Markov Decision Process 에 대한 좋은 자료가 담긴 블로그 입니다.
• Reinforce Learning 에 대한 전반적인 내용을 담고 있는 slide share 자료 입니다.