복잡하고 어려운 음식 배달 과제, 데이터 사이언스로 극복하다
주문 배정, 요금 책정, 도착 예정 시간 등에 예측 모델링과 최적화 기법 적용하기
본 포스트는 영문으로도 제공됩니다.
쿠팡이츠는 2019년 말 한국에서 오픈한 온라인 음식 주문 및 배달 플랫폼입니다. 빠르게 성장한 쿠팡이츠는 론칭 2년을 갓 넘긴 시점에 후발 주자임에도 불구하고 한국 음식 배달 업계의 최강자 수준으로 도약했습니다.
이번 포스트에서 저희는 온라인 음식 배달 서비스를 운영하며 직면했던 주요 데이터 사이언스 문제와 그에 대해 저희가 취한 기술적 해법 몇 가지를 소개하려 합니다.
목차
· 도전 과제
· 주문 배정(OA) 최적화
· 정적/동적 가격 책정
· 도착 예정 시간(ETA)
· 기타 데이터 사이언스 과제
· 마무리
도전 과제
온라인 음식 주문 및 배달은 고객, 판매자, 배달 파트너로 이루어진 삼자 시장에서의 경쟁과 협업이 주가 되는, 복합적인 O2O(온라인-오프라인) 비즈니스입니다. 고객은 음식 수요를 발생시키는 소비자이고, 판매자는 음식의 공급자이며, 배달 파트너는 음식 픽업부터 인도까지 이어지는 주문 이행을 책임집니다. 세 당사자 간의 일반적인 상호 작용 과정은 다음과 같이 이뤄집니다.
쿠팡이츠는 플랫폼으로써 고객, 판매자, 배달 파트너가 음식 주문 및 전달 과정을 완료할 수 있는 매개체 역할을 수행합니다. 배달 측면에서는 크라우드소싱 모델로 운영되는 쿠팡이츠 배달 파트너, 또는 EDP(Eats Delivery Partners)와 협업하고 있습니다. EDP는 주문 배정을 거부할 수 있으며, 플랫폼에 소속되어 있지 않고 배달 프리랜서와 같이 일합니다.
이번 포스트에서는 쿠팡이츠 비즈니스를 운영하며 해결해야했던 음식 배달 및 EDP 관련 과제들을 다뤄보려 합니다. 그중 저희가 해결해야 했던 주요 알고리즘 문제는 다음과 같았습니다.
- 주문 배정(Order Assignment, OA): 빠르고 비용효율적인 각 주문의 픽업/배달이 빠르고 비용효율적으로 이루어지려면 최적의 EDP를 어떻게 배정해야 하는가.
- 가격 책정: 각 주문의 적정 배달 요금은 어떻게 결정하는가.
- 도착 예정 시간(Estimated Time of Arrival, ETA): 음식 조리시간, 이동시간, 그리고 총 배달시간은 어떻게 최대한 정확히 예측하는가.
- 그 외: EDP 공급과 고객의 주문 수요 간의 균형을 어떻게 유지하며, 배달 서비스 품질 유지와 판매자의 최대 주문 전환을 동시에 달성할 수 있는 배달 범위를 어떻게 결정할 것인가.
주문 배정(OA) 최적화
최적의 EDP에게 각 주문을 효율적으로 배정하는 것은 빠른 배달과 양질의 고객 경험(CX)에 있어 핵심적인 요소입니다. 이번 섹션에서는 OA가 왜 쉽지 않은 데이터 사이언스 문제인지 설명하고 OA 관련 도전 과제들을 해결하기 위해 사용했던 접근법을 소개하겠습니다.
OA와 관련해 가장 큰 이슈는 모든 상황이 실시간으로 진행된다는 점입니다. 초 단위로 수많은 계산과 예측을 수행해 주문과 EDP 간 최적의 매칭을 생성해야 합니다. 최고의 고객 경험 제공을 위한 OA 최적화에 있어, 쿠팡이츠의 주 목표는 배달시간 감축, 주문의 롱테일 비율 감소, EDP 수락률의 증가였습니다.
OA 접근 방식
OA에 대한 접근 방식은 보통 두 가지가 있습니다. 경로 기반, 그리고 매칭 기반입니다.
경로 기반 접근 방식은 OA를 운영과학(Operation Research, OR)의 고전적 문제인 차량 경로 문제(Vehicle Routing Problem, VRP)와 동등하게 인식합니다. 이 접근 방식에서는 EDP에 대한 최적의 주문 배정과 각 EDP를 위한 최고의 경로를 동시에 판단하도록 이산 최적화(discrete optimization) 문제를 만듭니다. 경로 기반 접근 방식은 총 이동거리의 최소화나 모든 주문의 배달 소요 예상 시간의 최소화 같은 주어진 제약조건 하에 어떤 목표의 성능을 극대화하는 것이 목표입니다.
하지만 VRP는 일반적으로 효율적인 해결 방법이 없는 NP 난해 문제입니다. 이러한 한계 때문에 음식 배달과 같이 수초 이내에 결정이 이뤄져야 하는 실시간 사례에는 적용하기 어렵습니다.
반면, 매칭 기반 접근 방식은 OA를 EDP와 주문을 매칭하는 문제로 인식합니다. 각 EDP-주문(EDP-order) 쌍에 점수를 매기고, 총 매칭 스코어를 극대화하는 주문 배정을 최적의 결론으로 판단합니다. OA를 VRP로 다루는 경로 기반 접근 방식에 비해 매칭 기반 알고리즘은 연산적으로 더 효율적이며 실시간 사례에 좀 더 적합합니다. 그래서 쿠팡이츠에서는 매칭 기반 접근 방식을 사용합니다.
매칭 기반 OA
이번 섹션에서는 매칭 기반 알고리즘에 대해 좀 더 자세히 알아보겠습니다.
로컬, 그리고 글로벌 배정
매칭 기반 접근 방식은 매칭 문제의 해결 방식에 따라 로컬/글로벌 배정 알고리즘으로도 나눌 수 있습니다.
로컬 배정 알고리즘은 각 주문을 개별적으로 파악하여 가장 인접한 EDP에게 배정하는 그리디(greedy)한 접근 방식입니다. 로컬 배정 알고리즘은 단순하지만, 배달 업무 또는 주문 처리 시 일부 주문에 의해 영향을 받을 수 있으며 결과적으로 최적이 아닌 배달 업무 배정, 적절치 않은 해결 방안을 내놓을 수도 있습니다.
반면, 글로벌 배정 알고리즘은 모든 주문과 EDP를 이분 그래프(bipartite graph)의 양쪽에 있는 노드로 여기고 간선 가중치(edge weight)를 매칭 스코어로 사용합니다. 글로벌 배정에서는 OA를 이분 그래프 매칭 문제로 다뤄 다항 시간 내에 총 매칭 스코어를 극대화하는 전역적인(globally) 최적의 해결 방안을 찾아냅니다. 이러한 이유로 쿠팡이츠에서는 스코어 기반의 글로벌 배정 방식을 선택했습니다.
아래의 그림 2는 로컬 및 글로벌 배정 알고리즘의 차이를 한눈에 볼 수 있는 단순한 예시입니다. 로컬 배정 방식(좌)에서는 주문이 순서대로 처리됩니다. 주문 o1은 EDP d2에게 배정되는데, 이유는 d1보다 o1 위치에 더 가깝기 때문입니다. 이 경우, o2가 d1에게 배정될 수밖에 없고 d1에서 o2까지의 거리가 멀기 때문에 비효율적인 배정이 됩니다. 우측의 글로벌 배정 방식은 이러한 문제를 해결하고 양쪽 주문 모두에 종합적으로 최적인 해결 방안을 풀이하여 o1을 d1에게 배정하고 o2를 d2에게 배정합니다. 매칭 스코어는 픽업 거리를 기준으로 반비례로 산정됩니다. 즉, 거리가 짧을수록 매칭 스코어가 커집니다.
매칭 스코어
매칭 스코어는 매칭 기반 접근 방식에서 주문 배정의 품질 향상을 가능케 하는 핵심 개념입니다. EDP 픽업 거리를 직접적으로 매칭 스코어로 활용하는 것이 가장 직관적일 수 있습니다. 단, 고객 경험 및 EDP 수락률 개선이라는 두 가지 OA 목표를 동시에 달성하기 위해서는 매칭 스코어 산정에 EDP 대기 시간, EDP 선호 사항, 주문 지연 가능성, 신규 고객 선호 사항 등의 요인도 감안해야 합니다. 이러한 요인 및 예측 획득에는 기존 데이터로 트레이닝한 선호도 모델 등의 머신 러닝 모델을 활용하기도 합니다.
구성 요소의 스코어에 더해, 특정 비즈니스 목표를 위한 점수에 서로 다른 가중치를 배정하는 여러 다양한 전략을 설계할 수도 있습니다. 가중치는 오프라인 시뮬레이션, 온라인 실험, 온라인 최적화, 강화학습 등의 방식을 통해 결정할 수 있습니다.
정적/동적 가격 책정
또 다른 음식 배달의 주요 과제로는 각 주문에 대한 적정 배달 요금 결정이 있습니다. 요금 책정에 있어 저희의 주목표는 주문당 비용(Cost per Order, CPO)을 줄이고 배달 효율을 증가시키는 것입니다. 그리고 요금에 영향을 미치는 가장 큰 요인 두 가지는 배달 비용과 EDP 공급 및 고객 수요 간의 균형입니다.
음식 배달 요금은 객관적으로 정량화하기 쉽지 않습니다. 픽업과 전달 지점의 거리와 같이 명백하게 측정할 수 있는 요인을 제외하고는, EDP의 실질 노동 비용은 산정하기 어렵습니다. 노동 비용은 음식 대기 시간, 주문 음식의 총 무게, 특정 음식의 배달 난이도, 고객 목적지 등에 따라 달라지기 때문입니다.
또한, 주문 건수는 일간 변동이 심하기 때문에 수요와 공급 역시 요금 책정에 큰 영향을 미칩니다. 변화하는 EDP 공급과 고객 수요 비율에 따라 요금 역시 동적으로 조정할 필요가 있습니다. 다양한 배달 시나리오를 비용 효율적이고 체계적으로 감안하기 위해 쿠팡이츠에서는 다음 그림과 같은 계층적 가격 책정 시스템을 활용합니다.
가격 책정 시스템
EDP는 각 배달 주문에 대한 건당 보수는 물론, 각자 미션에 따른 인당 보수도 받습니다. 이번 섹션에서는 쿠팡이츠의 가격 책정 시스템이 어떻게 미션과 동적 요금 조정을 기반으로 EDP가 쿠팡이츠 플랫폼에 계속 머무르게끔 동기 부여하는지 설명해 보겠습니다.
정적 가격 책정
미션은 EDP 당 보수와 관련해 활용됩니다. 미션은 EDP가 온라인에 접속하여 활성 상태(active status)를 유지하면 인센티브를 제공하도록 설계되었습니다. EDP는 미션을 통해 일정 시간 내에 일정 주문 건수를 완료하면 보수를 받게 됩니다. 미션 목표는 각기 다른 EDP의 등급과 역량에 맞게 조정됩니다. 미션과 더불어 EDP는 각 주문을 완료할 때마다 기본 배달 요금도 받습니다.
미션 및 기본요금 산정은 오프라인에서 수행되며 비교적 안정적으로 이루어집니다. 이는 정적 가격에 해당하며, 노동 비용이나 지역 내 EDP 인원 등 짧은 기간에 큰 변동이 나타나지 않는 요인들을 기반으로 합니다.
동적 가격 책정
미션이나 기본요금과는 달리 지역 및 태스크 수준 요금은 각종 실시간 요인들에 민감하게 반응하며, 그래서 온라인에서 동적으로 조정해야 합니다. 이런 동적 가격 책정은 풀기 쉽지 않은 엄청난 수준의 데이터 사이언스 과제입니다.
지역 단위의 동적 가격 책정은 선정의(pre-defined)된 연산 규칙에 의해 조정되지만, 이러한 규칙은 수급의 실시간 변화를 반영하지 못합니다. 반면 동적 가격 책정 모델은 실시간 수급 비율을 트래킹하여 공급 부족 시에는 지역의 기본요금을 상향 조정하고, 일반 상황에서는 하향 조정합니다.
단, 실제 실시간 데이터를 사용하면 시스템의 반응이 느려진다는 한계점이 있었습니다. 특히 피크 시간대에는 수요와 공급이 잦은 변동을 보이기 때문이었습니다. 그래서 트래깅 문제를 방지하기 위해 예측 모델을 활용하여 수요 공급의 예상 가치를 산정하여 가격 조정의 효율을 개선했습니다.
지역의 동적 가격 책정은 해당 지역의 대략적인 요금 수준을 결정하지만, 동일 지역의 배달 요금도 태스크 종류에 따라 다르게 책정될 수 있습니다. 각 태스크의 비용과 난이도를 객관적으로 정량화하기는 어렵기 때문에 EDP 주문 응답 데이터를 기반으로 요금 관련 신호를 추출합니다. 동일한 요금 수준에서 EDP는 처리하기 쉬운 태스크는 즉각 수락하고 어려운 태스크는 지연 수락하거나 거부하는 경향을 보입니다.
각기 다른 태스크의 과거 수락률을 기반으로 태스크 난이도에 따른 요금 민감도 모델을 만들어 여러 요금대에 걸친 수락률 변화를 포착했습니다. 쉬운 태스크는 요금에 민감하지 않은 경향을 보이고 수락률이 요금 변화에 따라 크게 변동하지 않습니다. 어려운 태스크는 상대적으로 요금에 민감하며 수락률이 요금 상승에 따라 변동폭이 큽니다. 요금에 둔감한 쉬운 태스크에 대한 요금을 인하하고, 요금에 민감한 어려운 태스크의 요금은 인상함으로써 저희는 태스크 난이도에 따른 공정한 비용을 책정할 수 있었을 뿐 아니라 배달 효율을 유지하면서도 전반적인 주문당 비용(CPO)도 감축할 수 있었습니다.
도착 예정 시간(ETA)
ETA 역시 음식 배달의 고전적인 과제 중 하나입니다. ETA와 관련해서는 두 가지 중요한 이슈가 존재합니다. 음식 조리 시간 예측, 그리고 배달 시간 예측입니다.
정확한 음식 조리 시간은 고객과 EDP 양측 모두에게 중요합니다. 고객의 경우, 과대 예측은 고객의 주문 결정에 영향을 줍니다. EDP 입장에서 과소 예측은 긴 대기 시간으로, 과대 예측은 음식이 식는 결과로 이어질 수 있습니다. 정확한 배달 시간은 고객에게 적절한 수준으로 기대하게 만들고, 참값 대비 편차가 크면 고객을 유지하는데 영향을 미칠 수 있습니다.
정확한 ETA 산출을 위해 저희는 준비 시간 및 배달 시간 예측을 회귀 문제로 풀이했습니다. 즉, 예측 모델을 학습시켜 일련의 입력 특성(features)에 대한 출력값을 예측하도록 했습니다.
음식 조리 ETA
음식 조리 ETA의 경우 각종 음식 카테고리의 과거 조리 시간에 대한 오프라인 통계 데이터, 실시간 조리 시간 근사치 데이터 등이 입력 특성이 됩니다.
표준 회귀는 단일 추정치만을 산출하기 때문에 여러 신뢰 수준의 추정값 연산을 위해 저희는 음식 준비 시간 예측에 분위 회귀분석(quantile regression)도 활용합니다. 이러한 여러 신뢰 수준은 여러 비즈니스 시나리오에 따른 의도적인 과대/과소 예측을 위한 보수적, 또는 공격적인 예측을 산출하는 기반이 됩니다. 예를 들어, 음식 픽업의 지연을 최소화하려고 한다고 합시다. 음식 조리 시간의 과소 예측은 EDP가 업장에 일찍 도착하도록 합니다. 반면, 과대 예측은 EDP의 업장 내 대기 시간을 단축하고 EDP 경험을 향상시킵니다.
배달 ETA
판매자가 주문을 수락하고 음식을 준비하는 동안의 경과 시간을 단순 계산하는 음식 조리 시간 예상과는 달리 배달 시간 예상은 아래 그림과 같이 고객이 주문하는 시점에서부터 주문의 이행을 완료되는 시점까지를 포함하는 멀티홉(multi-hop) 예측 작업입니다.
배달 시간을 예측하는 방법은 보통 두 가지가 있습니다. 상향식(bottom-up) 접근 방식은 분할 정복(divide-and-conquer) 방식으로 일련의 하위 예측 태스크로 분해한 후 하위 태스크의 예측값을 합하여 최종값을 구합니다. 각 하위 태스크는 회귀 문제이며 다음과 같이 개별로 모델링할 수 있습니다.
- 배정 시간 예상: 판매자와 EDP가 주문을 수락하기까지 걸리는 시간입니다.
- 지점 간(point-to-point) 시간 예상: EDP가 픽업을 위해 점포에 도착하기까지의 시간, 그리고 고객 위치로 이동하기까지의 시간을 의미합니다. 지점 간 시간은 EDP가 경로를 이동하는 시간만을 포함하며 판매자 업장 또는 고객이 위치한 건물에 입장한 후의 내부 이동 시간은 포함되지 않습니다.
- 엔드포인트(end-point) 전달 시간 예상: 점포나 고객이 위치한 캠퍼스(단지), 건물 내에서의 경과 시간을 의미합니다. 길가에서 손님을 태우고 내리는 택시와 다르게 음식 배달은 문 앞에서 문 앞으로(Door to door) 배달합니다. 서로 다른 엔드포인트의 전달 시간도 상당한 영향을 미칠 수 있으며, 그러므로 전달 시간 예상에 확실히 반영되어야 합니다.
상향식 접근 방법은 직관적이지만 각 하위 태스크의 정확성에 크게 영향을 받습니다. 각 하위 태스크의 오류가 누적되어 최종 예측의 정확성을 저하할 수 있습니다.
반면, 하향식(top-down) 접근 방법은 전체 프로세스를 블랙박스로 여기고 총체적으로 접근합니다. 단일 회귀 모델을 학습시켜 직접 배달 시간을 예측합니다. 쿠팡이츠에서는 계속 증가 중인 데이터베이스를 기반으로, 최신 머신 러닝 기법을 활용하여 강력한 심층 신경망(deep neural network) 모델을 학습시켜 엔드투엔드(end-to-end) 배달 시간 예측의 복합적인 관계성을 포착하고 있습니다.
기타 데이터 사이언스 과제
음식 배달 관련 과제 중에는 앞서 다룬 알고리즘 과제에 더해 수급의 조정 그리고 배달 범위 설계가 있습니다.
수요 및 공급 조정
앞에서도 언급했듯이 주문은 하루에 균등하게 분포되어 발생하지 않습니다. 주문은 피크 아워, 휴일, 기상 악화 시에 급증하여 EDP 공급 부족이 발생합니다. 불균형한 EDP 수급 상황에서 저희 목표는 수급 비율을 최대한 빠르게 조정하고 중립화하는 것입니다.
앞서 지역 수준의 동적 가격 책정으로 수급 균형을 조정할 수 있다고 설명했습니다. 가격 책정에 더해 긴급한 상황에서 고객 수요를 제한하고 EDP 공급을 활성화하는 다른 여러 조정 수단이 존재합니다. 일례로, 판매자의 배달 범위를 좁히거나 프로모션을 보류할 수 있습니다. 다음 그림에 있는 기타 여러 수단들을 동원할 수도 있습니다.
조정을 위한 트리거 포인트를 파악하기 위해 저희는 연산 규칙을 사용하는 모델보다 더 빠르고 선제적으로 수급 불균형을 알아챌 수 있는 강력한 예측 모델을 구축했습니다. 쿠팡이츠의 예측 모델은 지역 및 시간대와 같은 변수에 따라 유연하게 조정할 수 있습니다.
그리고 예측을 기반으로 수급의 균형이 최적의 상태가 되도록 여러 조정 수단을 적용할 수 있습니다. 이는 보통 다중 목표의 전역 최적화(multi-objective global optimization)를 기반으로 배달 효율을 유지하면서 총 주문 극대화를 도모하거나 반대를 통해 달성하게 됩니다.
배달 범위 설계
판매자 배달 범위는 고객 전환과 배달 품질 모두에 영향을 미칩니다. 범위를 확장하면 고객전환이 감소할 수 있을 뿐더러, 배달 시간도 늘어날 수 있습니다. 합리적인 배달 범위는 전환과 배달 효율의 균형을 염두에 두고 설정되어야 합니다.
배달 범위를 정하는 가장 간단한 방법은 판매자를 기준으로 특정 반경의 원을 그리는 것입니다. 다만, 이동 거리는 도로 및 건물 상태에 따라 크게 달라질 수 있습니다. 또한, 단순히 동그라미를 그리는 것은 여러 복합적인 지리적 건물 및 시설 상황을 반영하지 못합니다. 일례로, 원의 선이 하나의 아파트 단지를 가로지를 수 있습니다. 그러면 1동은 배달 범위에 포함되지만 2동은 포함되지 않게 될 수 있습니다. 이러한 상황은 고객을 혼란스럽게 만듭니다.
이보다 더 정교하고 효과적인 방식은 아래와 같이 동그라미 대신 실제 이동할 거리와 도로망을 반영한 불규칙한 등시선을 사용하는 것입니다. 이렇게 하면 주문량과 잠재적 범위의 배달 특성을 감안한 최적의 범위를 산출할 수 있습니다.
마무리
다른 영역에 비해 온라인 음식 배달의 데이터 사이언스 과제는 한층 특별합니다. 예측 모델링, 최적화 기법 등을 흔히 활용하게 됩니다.
OA, 가격 책정, 수급 균형 재조정과 같은 과제는 최적화와 관련되어 있습니다. 단, 이러한 최적화 문제의 변수는 이전 데이터를 기반으로 학습시킨 복합적인 예측 모델을 통해 파악해야 합니다.
또한, 이러한 문제는 다중 목표의 최적화 문제이기도 합니다. 여러 목표들(고객/EDP 경험, 효율/비용, 평균/롱테일) 간의 균형을 동적으로 찾아가며 다른 영역의 비즈니스 요구사항에도 맞춰 문제를 풀어나가야 합니다.
쿠팡이츠의 복합적인 배달 이슈는 데이터 사이언티스트에게는 새롭고 흥미로운 도전입니다. 복잡한 문제를 최신 최적화 및 예측 모델로 해결하는 프로젝트에 관심이 있는 엔지니어라면 쿠팡의 채용 공고를 한번 확인해 보세요!
