[Uber Engineering 블로그 리뷰 & 번역 - How Trip Inferences and Machine Learning Optimize Delivery Times on Uber Eats]

 

 

 

지난 포스팅들보다 앞서 블로그에 게재된 내용으로, Uber Eats 에서 ETA, ETD 등을 추정하는 모델에 대한 내용을 설명하는 포스팅이다. 마찬가지로 이번 포스팅 역시 원문에 주관적 해석을 약간 덧붙인 번역문에 가까우니, 영어가 자신있는 분은 원문을 읽는 것을 권장한다.

 

https://eng.uber.com/uber-eats-trip-optimization/

How Trip Inferences and Machine Learning Optimize Delivery Times on Uber Eats

 

---

 

Michelangelo를 사용하는 ML 서비스는 배달 예상시간 추정, 검색 랭킹모델, 검색 자동완성, 개인화 추천 모델 등이 있다. 그 중에서 이번에 소개할 것은 배달 예상시간 추정인데, 주문 전에 음식이 준비되고 배달에 어느정도 시간이 소요될 지 등을 합산해서 유저에게 최종적으로 얼마 정도의 시간이 걸릴 지 예측해서 보여주는 서비스이다. 그리고 음식 배달의 각 단계에서도 Sub-task 로 작은 예측들을 수행한다.

 

ETD(Estimated Time of Delivery)를 예측하는 것은 간단한 일이 아니다. 유저가 주문을 하면 레스토랑에서는 주문 수락을 해야 하고, 현재 몇 개의 주문이 밀려있는지에 따라 일의 복잡도가 높아진다. 또한 라이더 역시 음식이 준비되는 시점에 맞춰 픽업을 가야 하고, 음식을 픽업한 이후에도 문제가 발생한다. 주차 문제가 발생할 수도 있고 고객이 외진 곳에 살 수도 있다. 

 

이러한 예측 문제를 푸는 데 가장 중요한 것은 레스토랑, 유저, 라이더의 위치정보이다. 특히나 라이더가 중요하다. 음식 준비시간은 어느정도 예측이 가능하고, 레스토랑와 유저의 위치는 고정되어있기 때문이다. 그래서 라이더의 주변 통행량, 그리고 주문 수락까지 걸리는 시간 등을 고려해본다면 ETD의 핵심은 라이더이다. 그러나 GPS 데이터 자체가 가지고 있는 노이즈성 때문에 라이더의 위치 기반의 추정 모델을 만드는 것은 큰 어려움이 존재한다. 그래서 우버잇츠에서는 라이더 핸드폰에 장착된 동작 센서 데이터를 활용하여 각 단계를 세분화하는 Trip Status Model을 만들었다고 한다.

 

 

---

 

 

1. Improving time efficiency for delivery-partners and eaters

 

 

아래의 그림에서 보여지는 것 처럼, 일반적으로 라이더는 4개의 행동 상태에 놓인다.

 

 

1) been dispatched : 레스토랑에 주문이 들어온 후, 해당 주문에 라이더가 배차된다.

2) arrived at the restaurant : 라이더가 음식을 픽업하러 레스토랑에 도착한다.

3) is en route to the drop-off location : 주문자의 지역으로 가는 중.

4) arrived at the drop-off location and completed the trip : 주문자의 지역으로 도착해서 배달을 완료한다.

 

그러나 주문 예상시간과 라이더가 실제로 소요하는 시간을 일치시키는 것은 쉬운 일이 아니다. 라이더의 입장은 이렇다고 한다.

 

레스토랑에 도착해도 음식이 전혀 준비되지 않았을 때도 있다.
배차가 밀려 한참을 기다려야 할 때가 있다.
배달 프로세스가 너무 많고 길다.

 

그리고 이를 해결하기 위한 질문들은 다음과 같다.

 

가장 지연시간이 긴 레스토랑들의 지연 이유는 무엇인가?
라이더가 식당까지 가는 데 걸리는 시간은 얼마나 되나?
레스토랑은 라이더에게 너무 어려운 픽업 시스템을 가지고 있는가?
라이더 배차는 언제 하는게 가장 좋은가? 음식이 라이더를 기다리고 있는 지, 라이더가 음식을 기다리고 있는 지?
라이더는 배달 자체에 어려움을 겪고 있는가?

 

 

---

 

2. Sensor processing

 

 

앞서 말했듯이 GPS 정보만으로는 무엇인가 추정하기는 어렵다. 그래서 Android activity recognition API를 활용하여 라이더의 다양한 행동정보를 얻어내어 활용한다.

 

 

그리고 이러한 센서 데이터를 염두에 두고 ML 아키텍처를 구성하여 Trip Status Model을 학습한다. 아키텍처는 아래 그림을 참고하자.

 

 

 

---

 

3. Mobile collection

 

 

앞서 말한 안드로이드 API를 이용해 라이더의 모션 타입과 해당 타입의 신뢰도(0~100)의 값을 수집하며, 모델링에 필요한 데이터는 라이더가 온라인 상태일때만 수집한다. 

 

 

 

4. Machine learning

 

 

ML 모델에 사용되는 데이터 레이블셋은 위의 그림과 같다. 이러한 데이터셋을 이용한 Time Series Predict 모델링을 수행한다.

 

 

그리고 위의 그림처럼, 시퀀스 모델은 라이더 행동의 변경점을 찾아낸다. 하지만 이 역시 어느정도는 노이즈가 있는 데이터셋이고, Ground truth data를 충분히 확보하기는 힘들다는 한계 역시 존재한다.

 

 

---

 

 

5. Conditional random fields

 

 

이러한 순차 모델의 특징은, 선후 관계가 연결되어있다는 것이다. 그래서 이전 상태 역시 다음 상태 추론에 매우 중요한 역할을 한다. 예를 들어, 배달중 상태는 픽업중 상태 뒤에 나올 수 밖에 없기 때문이다. 그리고 이 특징들을 활용하기 위해 CRF(Conditional random fields) 알고리즘으로 시계열 모델링을 하였고, 추후 마르코프 체인이나 RNN으로 대체할 수 있는 방법론이라고 할 수 있다.

 

 

 

6. Trip State Model

 

아래의 그림은 ETD 전체 과정에서 Trip State Model을 추가함으로써 새롭게 얻어지는 정보들을 도식화한 것이다.

 

 

모델은 라이더가 각 시점에 대해 어떠한 상태 중 하나에 있을 가능성을 추론한다.

- 식당에 도착한 상황 : 라이더가 식당에 도착했고, 주차장을 찾기 위해 돌아다니고 있을 지도 모른다(한국의 경우 주차할 일은 없겠지만)
- 주차중인 상황 : 주차 후, 걸어서 레스토랑 픽업 지점까지 가는 중인 상황. 역시나 한국에서는 크게 의미 없는 상태일 것이다.
- 레스토랑에서 대기중인 상황 : 도착은 했지만 아직 픽업준비가 완벽하게 되지 않은 상태이다. 이 기간을 잘 분석하면 출발시간, 즉 ETD(Estimated Time of Departure)를 더 잘 추론할 수 있을 것이다.
- 다시 차로 돌아가는 상황 : 역시나 이 상황도 한국에서는 중요하지 않은 상황일 것이다.
- 배달중

 

이러한 상태 추론 모델을 사용하면, 라이더의 대기 및 주차시간을 효율적으로 줄일 수 있다고 한다. 레스토랑이 현재 배차중인 라이더의 상황을 조금 더 디테일하게 파악함으로써, 전체적인 ETA 시간을 예측 하는 데 도움을 주며 동시에 레스토랑의 상태 피쳐(현재 얼마나 바쁜지 등)를 업데이트 할 수 있기 때문이다.