가게에 치킨 주문이 들어왔다. 배달까지 예상시간은 약 40분. 배달할 라이더(배달대행기사)를 찾는 게 급선무다. 근처에는 세 명의 라이더가 있다. 1번 라이더는 배달 중이다. 목적지엔 거의 도착했다. 2번 라이더는 배달이 없지만 치킨집과는 먼 거리에 있다. 3번 라이더는 가게와 가까이 있지만 두 건의 배달이 밀려 있다. 어느 라이더가 치킨을 배달해야 할까? 대개 ‘콜(배차)’을 빨리 잡은 라이더가 치킨을 배달하지만, 배달앱 ‘배달의민족(운영사 우아한형제들)’은 올해 2월부터 배민 라이더스·배민커넥터 등을 대상으로 인공지능(AI) 추천 배차제를 시범 도입했다. 주문이 들어오면 알고리즘이 적절한 라이더를 골라 배차를 띄우는 식이다.
16일 이재일 우아한형제들 딜리버리플랫폼팀 개발자는 우아한형제들 주최로 열린 온라인 개발자 행사 ‘우아한테크콘서트(이하 우아콘)’에서 ‘겉바속촉 치킨의 골든타임을 지키기 위해 배민이 하는 일’을 주제로 AI 추천 배차 알고리즘을 설계한 방법과 이 과정에서 생긴 개발상의 고민들을 공유했다. (※ 참고하면 좋은 링크 <배달아~ 배달 가는길 알려줘!(2019)>, 이재일, 우아한형제들 기술 블로그)
치킨을 배달할 라이더를 찾아라
배민의 추천 배차 알고리즘은 1단계 비용, 2단계 경로 선택, 3단계 라이더 선정, 4단계 거리 계산 등으로 이루어져 있다.
먼저 1단계에서 말하는 비용은 라이더가 가게까지 도착하는 시간, 음식이 나오는 시간, 라이더가 이를 픽업하고 손님에게 배달하기까지 걸리는 시간을 통칭한다. 초과시간이 늘어나면 비용도 함께 증가하는 식이다. 단 건으로 배달을 수행하면 경로는 단순하다. 그러나 배민 라이더는 복수 건의 배달을 수행할 수 있다. 동시처리해야 하는 배달 건수가 증가할수록 연산은 복잡해진다.
이재일 개발자는 “비 오는 날, 라이더는 적고 배달은 많고 동시처리 숫자가 늘어나면 (이는) 라이더 수급에 실패한 안 좋은 현상이지만 (플랫폼은) 비용을 계산해야 한다”며 “한 명의 라이더가 하나의 배달을 추가할 때마다 최적의 경로를 선택해야 한다. 이때 모든 라이더의 비용을 동시 계산해야 하는데 이 많은 연산을 최적화하는 방법이 필요하다”고 말했다.
배민은 이 같은 기하급수적 연산을 처리하는 해법으로 ‘탐욕 알고리즘(Greedy Algorithm)’을 택했다. 탐욕 알고리즘이란 매 순간마다 최적으로 여겨지는 답을 선택해 최종 결론을 만들어내는 방식을 뜻한다. 기존 정한 최적의 배달 경로에서 새롭게 추가되는 배달이 있을 경우 이를 사이사이에 추가해 처리하도록 하고, 기존 비용과 새 배달로 추가된 비용의 증분 값이 가장 적은 라이더를 고르게끔 알고리즘을 설계했다는 설명이다.
배달 경로 설계 시 도로 사정을 고려한 거리 계산도 중요하다고 그는 강조했다. 이재일 개발자는 “단순히 직선만 그으면 라이더가 산을 넘는 일이 생길 수 있다”면서도 “장소에서 장소로 거리와 소요시간을 구하는 서비스는 존재하지만, 우리가 처한 환경은 막대한 연산을 해야 하는 환경임을 고려해야 한다”고 말했다.
배민은 ‘OSRM(Open Source Route Machine, https://github.com/Project-OSRM/osrm-backend)’이라는 오픈소스 도구를 사용했다. 운송 유형별 최적의 경로를 제공하는 알고리즘을 구현한 길찾기 프로젝트다. 다운로드해 서버에 직접 설치할 수 있다. 여기에 국내 오픈 스트리트 데이터를 내려 받고, OSRM REST API를 사용해 총 거리와 수행시간 등의 정보를 즉시 응답 받을 수 있도록 했다. 또, 시간 단축을 위해 모든 면적을 동일한 블록으로 나눠 경우의 수를 계산하기 쉽게 만들었다. 여기엔 우버의 h3(공간 라이브러리)를 사용했다. 정확한 실거리 대신 근사값을 구했고, 미리 계산된 정보를 서버에 둔 뒤 클라이언트가 비동기 호출로 처리하도록 해 속도를 높였다.
이재일 개발자는 “양질의 치킨 배달을 위해 우리가 할 수 있는 많은 일을 시도했다. 라이더가 하나 혹은 여러 개의 배달을 할 수 있는, 가능한한 모든 경로를 계산하고 최적의 경로를 예측하게 했다”며 “(추천 배차 알고리즘에) 쓰인 기술은 특별한 게 없다. 하나하나 적절한 대안을 마련해서 문제를 해결했다”고 말했다. 이어 “‘은 탄환’ 같은 기술은 사실 없다고 생각한다. 이보다 더 좋은 개선방법은 얼마든지 많이 있지만 작은 문제를 조금씩 해결해 큰 문제를 해결하는 방법을 소개할 수 있어 좋았다”고 말했다.