배달의민족의 인공지능 배차는 어떻게 작동하나

우아한형제들이 2020년 2월 베타 서비스를 출시하여 열심히 밀고 있는 기능이 있으니 ‘인공지능(AI) 추천 배차’다. 우아한형제들의 물류자회사 우아한청년들이 운영하는 배민라이더스의 전업 배달기사 ‘배민라이더’와 파트타임 배달기사 ‘배민커넥터’ 중 희망자가 선택하여 이용할 수 있는 기능이다.

인공지능 추천 배차가 등장하기 전 배민라이더스의 배차 방식은 음식점 인근의 복수 라이더에게 주문을 노출하고 먼저 주문을 잡는 라이더가 수행하는 경쟁배차 방식이었다. 라이더들이 주문을 잡기 위해서 치열하게 경쟁해야 했기 때문에 ‘전투콜’이라고도 불리는 방식이다.

반면, 인공지능 배차는 시스템이 알아서 특정 주문을 라이더에게 추천해준다. A음식점의 주문이 시스템에 노출됐다고 하면 라이더는 해당 주문을 수행하면 된다. A음식점의 배달을 수행하던 중 B음식점의 주문이 추가로 등장했다면 마찬가지로 해당 주문을 수행하면 된다. 그러니까 종전 수동 배차 방식의 결정 주체가 ‘사람’이었다면, 인공지능 배차에서는 ‘기계’로 바뀐다.

몇몇 라이더들에게 AI 추천 배차에 대한 평가를 물어보니 ‘쓸 만하다’는 답변이 돌아왔다. 수동으로 잡는 방식에 비해서 휴대폰을 계속 안 봐도 돼서 편하다는 의견이다. 전투콜이 익숙하지 않은 초보 라이더라면 종전보다 안전하고 편하게 주문을 잡을 수도 있다. 기술 도입으로 인해 배달업의 진입장벽이 낮아지면서 라이더의 업력과 경험이 더 이상 경쟁력이 되지 않는 단계로 넘어가고 있다.

배차에 인공지능이 등장한 이유

우아한형제들이 AI 추천 배차를 도입한 이유는 크게 두 가지다. ‘소비자’와 ‘공급자’ 관점에서 우아한형제들이 해결하고 싶은 문제가 있었다.

먼저 소비자 관점에서 우아한형제들은 인공지능 배차를 통해 날뛰는 ‘배달시간’을 통제하고 싶었다. 통상 오토바이 라이더가 우리가 주문한 치킨집에 방문하여 픽업을 하고 배달을 하기 까지는 20~30분이 채 걸리지 않는다. 그럼에도 불구하고 우리가 주문한 치킨이 대개는 30~40분, 가끔은 1시간이 넘어서 오는 이유는 있다.

첫 번째 이유는 음식점의 한계 생산량 초과다. 할인 이벤트 등으로 치킨집 주문이 폭발했는데, 가게에 튀김기는 하나밖에 없다고 해보자. 조리 시간이 지연되면서 자연히 음식배달 속도는 더 늦어질 수 있다. 물론 이건 배달 단에서 해결할 수 있는 문제는 아니다. 음식점이 주문을 예측해서 인력이나 설비를 추가로 준비해둬야 해결할 수 있다.

AI 주문이 해결하고자 하는 문제는 두 번째 이유에서 나온다. 배달 라이더의 ‘묶음배달’ 행태 때문이다. 배달 라이더들은 배달건당 돈을 받는다. 한정된 시간에 더 많은 돈을 많이 벌기 위해서 최대한 많은 주문을 동시에 수행하고자 한다. 그래서 주문 수행 중에도 여러 건의 주문을 추가로 더 잡는다. 이 때 배달 경로는 배달 라이더들이 현장 상황과 경험을 기반으로 알아서 결정한다. 그러다 보면 첫 번째로 픽업한 음식점의 주문이 맨 마지막에 배달이 되는 상황이 발생하기도 한다.

우아한형제들은 이 문제를 인공지능 배차를 통해 해결하고자 했다. 라이더의 운송수단과 운송수단의 평균 속도, 라이더와 음식점, 음식점과 배송지 사이의 거리, 현재 라이더가 수행하고 있는 배달 건수 등의 데이터를 종합적으로 고려해서 특정 주문을 소비자에게 최적 시간에 배달을 해줄 수 있는 라이더를 인공지능이 찾아주는 형태다.

공급자 관점에서 AI 배차는 라이더들의 안전운행을 가능하게 한다는 의미가 있다. 라이더들이 더 많은 주문을 잡기 위해서 주행 중에도 휴대폰을 보는 경우가 있는데, 이 때문에 주행중 사고가 발생할 수 있다. AI 배차는 라이더가 휴대폰을 보지 않고도 시스템이 적정 주문을 배차하는 구조를 만들었다. 이를 통해 라이더들의 안전 운행에도 도움이 될 수 있다는 게 우아한형제들의 설명이다.

이재일 우아한형제들 딜리버리플랫폼팀 배달플랫폼 개발자는 18일 마무리 된 우아콘2020에서 “고객 관점에서 배달 예정 시간보다 늦게 배달되는 문제, 라이더 관점에서 무리한 배차와 과속으로 인해 예기치 못한 사고로 이어질 확률이 크다는 문제를 인공지능 배차를 통해 풀고자 했다”며 “라이더의 수익을 보존하면서 고객이 주문한 음식을 최대한 빠르게 배달해줄 수 있는 라이더를 찾아 배차를 권유하는 추천 시스템을 만든 것”이라 설명했다.

‘배달 시간’은 비용이다

인공지능 배차를 위해서 필요한 것은 학습을 위한 ‘데이터’다. 우아한형제들이 AI 추천 배차를 위해서 확보한 핵심 데이터는 ‘배달 시간’이다. 주문을 잡은 라이더가 음식점까지 도착하는 데 걸리는 시간, 음식점에서 음식이 나오는 데 걸리는 조리시간, 조리가 끝난 음식을 픽업해서 고객에게 전달하기까지 걸리는 시간 등을 쪼개서 각 경로의 처리 시간을 계산했다. 우아한형제들은 이렇게 취합된 배달 시간을 ‘비용’으로 치환했다. 비용은 적으면 적을수록 좋기 때문에 비용을 줄이는 것을 AI 배차의 목표로 가져갔다.

예컨대 만약 라이더의 운송수단이 오토바이라면 구간별로 오토바이의 평균 속도로 처리할 수 있는 예상 배달 시간을 계산할 수 있다. 배달 시간을 비용으로 치환한다면, 어떤 처리 구간에서 비용이 가장 낮은지 알 수 있다. 이 때 비용이 가장 낮은 구간의 주문을 적절한 라이더에게 추천을 한다면 그것이 최적의 경로라고 할 수 있겠다.

이 때 한 명의 라이더가 한 건의 음식만 배달한다고 가정하면, 시스템으로 배달 시간을 줄일 수 있는 최적 동선을 짜는 것은 그렇게 어렵지 않다. 두 건까지도 그럭저럭 할만하다. 예컨대 라이더가 A음식점의 주문을 받고, 이동 과정에서 B 음식점의 주문을 추가로 받았다고 해보자. 두 음식점에서 음식을 픽업하여 서로 다른 목적지인 (A)와 (B)까지 배달을 한다면 경우의 수는 총 6개가 나온다. 음식점과 목적지 방문 순서대로 경우의 수를 나열하자면 A(A)B(B), AB(A)(B), AB(B)(A), BA(A)(B), BA(B)(A), B(B)A(A)다. 여기까지는 시스템이 충분히 모든 처리시간을 계산해 경우의 수를 따져볼 수 있다.

현실 세계는 쉽지 않다고

하지만 현실 세계가 이처럼 쉽게 돌아가지 않는다. 대표적인 문제는 ‘묶음배달’에서 나왔다. 라이더들은 1~2건씩만 배달을 하는 경우가 많지 않다. 현실 세계의 배달 라이더는 3~5건 이상의 묶음배달을 하기도 한다.

라이더의 숫자 또한 ‘한 명’이 아니다. 한 지역에서도 수많은 라이더들이 활동을 하고 있다. 라이더는 대부분이 특수형태 근로자로 자유롭게 일자리에 나오기에 공급은 매일매일 바뀐다. 마찬가지로 수요인 음식점에서 발생하는 주문 또한 매일매일 바뀐다. 예를 들어서 요즘 같이 춥거나 눈이 오는 날이면 자연스럽게 공급은 떨어질 수 있다. 음식 주문은 역으로 악천후 상황에서 튀어 오를 수 있다.

요컨대 시장에 나온 복수 라이더들을 고려해서 최저 비용의 주문건을 매칭해야 인공지능 추천 배차는 작동할 수 있다. 하지만 이렇게 기하급수적으로 숫자가 증가하는 상황에서 시스템이 빠른 연산을 하는 것은 쉽지 않다. n개의 지점을 방문하는 최소 비용의 경로를 찾는 문제인 ‘TSP(Traveling Salesman Problem)이 경영과학계에서 풀 수 없는 NP Hard 문제로 분류된 이유가 여기 있다. 경우의 수가 지수적으로 증가하여 시스템이 감당하지 못한다.

이 개발자는 “우리 플랫폼은 라이더가 부족하고, 더 많은 배달 주문이 들어오는 상황에서도 비용을 계산할 수 있어야 했다. 가능한 비용이 높지 않은 라이더를 찾아야 한다면, 주문을 많이 들고 있지 않은 여러 라이더의 비용도 계산해야 했다는 것”이라며 “그런데 모든 비용을 계산하기에는 경우의 수가 기하급수적으로 늘어난다. 이런 많은 연산을 어떻게 최적화할 수 있을지 고민했고, 많은 시행착오 끝에 한 방법을 찾았다”고 말했다.

최적의 근사치를 구하라

우아한형제들이 문제를 해결하기 위해 택한 방법은 ‘탐욕 알고리즘(Greedy Algorithm)’이다. 탐욕 알고리즘은 ‘최적의 해’, 정답을 구하는 방법이 아니다. 여러 경로에서 그 순간 최적이라고 생각되는 방법을 계속해서 수집해서 최종적으로 ‘정답의 근사치’에 도달하는 방법이다.

우아한형제들은 복잡한 현실 세계의 모든 경우의 수를 시스템으로 계산하는 것은 어렵다고 판단해서 근사값을 추적하는 방향으로 AI 추천배차를 설계했다. 탐욕 알고리즘을 통해 AI 배차의 부분 최적화를 꾸준히 한다면 종국에는 전체 최적화에 ‘가까워’ 질 수 있을 것이라 본 게 우아한형제들의 생각이다.

그 방법은 이렇다. 먼저 한 건의 배달에 있어 최적 경로의 숫자를 구한다. 다음으로 이 최적 경로에 새로운 배달 주문이 추가되는 상황을 가정해서 최적의 숫자를 구한다. 만약 또 다시 새로운 배달 주문이 들어온다면 이 상황에서 다시 최적의 숫자를 구하는 행위를 반복한다. 우아한형제들은 탐욕 알고리즘을 기반으로 ‘n개의 배달을 수행하는 최적의 경로’는 ‘n-1개의 배달을 수행하는 최적의 경로 중 하나의 배달(n번째)을 사이사이에 처리할 수 있는 모든 경로중 최적의 경로’와 같다는 공식을 도출했다.

이 개발자는 “우리는 여러 라이더가 현재 처리중인 배달 비용을 계산할 수 있고, 그 결과를 하나의 수식으로 표현해서 가장 비용이 낮은 라이더를 찾을 수 있게 됐다”며 “이전 상태의 비용값과 신규 배달에 추가될 비용값 사이의 증분이 가장 적은 라이더가 우리의 유한한 자원을 가장 적게 소모하는 최적의 해라 생각한다. 매번 이렇게 최소 비용을 소모하는 방식으로 라이더를 찾는다면, 결국 전체 배차에서도 최소 비용을 소모하는 형태로 귀결될 것으로 예상했다”고 말했다.

연산속도를 늘리는 방법

AI 인공지능 배차를 구현하기 위한 또 다른 숙제도 있었다. 우아한형제들은 AI 배차를 최적화하기 위한 ‘거리 데이터’로 직선거리를 사용한다. 그러니까 라이더의 현위치부터 음식점까지의 거리, 음식점에서 고객이 음식을 받는 목적지까지의 거리를 지도상 직선으로 표기한 값을 사용하는 것이다.

당연히 현실 세계의 라이더가 드론은 아니기 때문에 목적지까지 거리를 ‘직선’으로 관통할 수는 없다. 막다른 길이 있거나 오토바이나 자전거가 지나지 못하는 도로가 있다면 돌아가야 한다. 자연스레 시스템상 직선거리는 라이더의 이동거리와는 다를 수밖에 없다.

우아한형제들이 이런 한계에도 불구하고 ‘직선거리’를 인공지능 배차에 사용한 이유는 있다. 현실 세계의 배달 경로를 그대로 데이터화해 분석한다면 시스템에서 막대한 연산 시간이 소요됐기 때문이다. 이 개발자에 따르면 실거리를 기반으로 계산을 했을 때, 수십분이 지나도 연산 결과가 나오지 않는 것을 확인할 수 있었다.

하지만 직선거리를 기반으로 계산하더라도 정도가 다를 뿐이지 오래 걸리는 것은 매한가지였다. 원활한 인공지능 배차를 위해서는 ‘연산 속도’를 끌어올리기 위한 방법이 필요했다.

고민 끝에 우아한형제들이 택한 방법은 ‘사전 연산’이다. 아주 정확한 숫자가 아니더라도 실측에 가까운 도로 기반 거리 데이터를 미리 계산하여 연산 속도를 크게 올릴 수 있을 것이라 판단했다. 우아한형제들은 과거 수개월의 주문 데이터를 주문이 발생한 위치와 매칭하여 지도 위에 그렸다. 서비스 가능 지역에서 총 8만개의 블록이 도출됐다. 이 정도로 쪼개진 블록이라면 발생할 수 있는 경우의 수를 미리 파악하여 계산할 수 있겠다는 판단이 섰다. 그 결과가 현재 배민라이더스에 적용된 AI 추천배차(BETA)다.

우아한형제들의 AI 추천배차는 여러 제약 조건들로 인해 정답을 구하는 것이 어려운 상황에서, ‘부분 최적화’를 반복해서 전체 최적화에 가까운 답을 찾아갔다. 여기 특별히 거창한 최신 기술이 들어간 것은 아니다. 크고 어려운 문제를 해결하기 위해서 작은 단계부터 조금씩 대안을 만들었던 과정이 모여서 지금의 AI 추천배차가 나올 수 있었다는 설명이다. 이재일 개발자의 말로 마무리 한다.

“(우아콘2020에 참여한 분들에게) 끝으로 전달하고 싶은 것은 어떤 은탄환 같은 기술은 사실 없다는 겁니다. AI 배차에 사용한 기술 중 그렇게 특별한 것은 없고, 우리가 선택한 것보다 좋은 개선 방법은 얼마든지 있습니다. 그보다 어떤 작은 문제를 조금씩 해결해 나가면서 마침내 큰 문제를 풀 수 있었던 사례를 여러분에게 소개할 수 있어서 좋았습니다”

글. 바이라인네트워크

<엄지용 기자> drake@byline.network