[이재우]“치킨 왔습니다” 배민이 말하는 추천 배차 알고리즘

# 배달의 민족
한국에서 살면, 치킨을 한 번이라도 먹어본 사람이면 배달의 민족앱을 모를 수 없다. 배달의 민족에서는 16일 이재일 우아한형제들 딜리버리플랫폼팀 개발자는 우아한형제들 주최로 열린 온라인 개발자 행사 ‘우아한테크콘서트(이하 우아콘)’에서 ‘겉바속촉 치킨의 골든타임을 지키기 위해 배민이 하는 일’을 주제로 AI 추천 배차 알고리즘을 설계한 방법과 이 과정에서 생긴 개발상의 고민들을 공유했다.


# 배민 배차 알고리즘
배민의 추천 배차 알고리즘은 여러단계로 나뉘어 볼 수 있다. 먼저 1단계 비용, 2단계 경로 선택, 3단계 라이더 선정, 4단계 거리 계산 등으로 이루어져 있다.

먼저 1단계에서 말하는 비용은 배민 라이더가 가게까지 도착하는 시간 + 음식이 준비되는 시간 + 배민 라이더가 이를 픽업하고 손님에게 배달하기까지 걸리는 시간을 의미한다. 초과시간이 늘어나면 비용도 함께 증가하는 방식이다. 단 한 건으로 배달을 수행하면 경로는 쉽게 경로를 찾을 수 있다. 그러나 배민 라이더는 복수 건의 배달을 수행할 수 있기 때문에, 동시처리해야 하는 배달 건수가 증가할수록 알고리즘 연산은 복잡해진다.

이재일 개발자는 “비 오는 날, 라이더는 적고 배달은 많고 동시처리 숫자가 늘어나면 (이는) 라이더 수급에 실패한 안 좋은 현상이지만 (플랫폼은) 비용을 계산해야 한다”며 “한 명의 라이더가 하나의 배달을 추가할 때마다 최적의 경로를 선택해야 한다. 이때 모든 라이더의 비용을 동시 계산해야 하는데 이 많은 연산을 최적화하는 방법이 필요하다”고 말했다.


# 기하급수적 연산처리를 위한 탐욕 알고리즘
탐욕 알고리즘(Greedy Algorithm)이란 매 순간마다 최적으로 여겨지는 답을 선택해 최종 결론을 만들어내는 방식을 뜻한다. 기존 정한 최적의 배달 경로에서 새롭게 추가되는 배달이 있을 경우 이를 사이사이에 추가해 처리하도록 하고, 기존 비용과 새 배달로 추가된 비용의 증분 값이 가장 적은 라이더를 고르게끔 알고리즘을 설계했다는 설명이다.

배달 경로 설계 시 도로 사정을 고려한 거리 계산도 중요하다고 그는 강조했다. 이재일 개발자는 “단순히 직선만 그으면 라이더가 산을 넘는 일이 생길 수 있다”면서도 “장소에서 장소로 거리와 소요시간을 구하는 서비스는 존재하지만, 우리가 처한 환경은 막대한 연산을 해야 하는 환경임을 고려해야 한다”고 말했다.

# 길찾기 알고리즘
배민은 ‘OSRM(Open Source Route Machine, https://github.com/Project-OSRM/osrm-backend)’이라는 오픈소스 도구를 사용했다. 운송 유형별 최적의 경로를 제공하는 알고리즘을 구현한 길찾기 프로젝트다. 다운로드해 서버에 직접 설치할 수 있고, 여기에 국내 오픈 스트리트 데이터를 내려 받고, OSRM REST API를 사용해 총 거리와 수행시간 등의 정보를 즉시 응답 받을 수 있도록 했다. 또, 시간 단축을 위해 모든 면적을 동일한 블록으로 나눠 경우의 수를 계산하기 쉽게 만들었다. 여기엔 우버의 h3(공간 라이브러리)를 사용했다. 정확한 실거리 대신 근사값을 구했고, 미리 계산된 정보를 서버에 둔 뒤 클라이언트가 비동기 호출로 처리하도록 해 속도를 높였다.

# 특별한 알고리즘?
이재일 개발자는 “양질의 치킨 배달을 위해 우리가 할 수 있는 많은 일을 시도했다. 라이더가 하나 혹은 여러 개의 배달을 할 수 있는, 가능한한 모든 경로를 계산하고 최적의 경로를 예측하게 했다”며 “(추천 배차 알고리즘에) 쓰인 기술은 특별한 게 없다. 하나하나 적절한 대안을 마련해서 문제를 해결했다”고 말했다. 이어 “‘은 탄환’ 같은 기술은 사실 없다고 생각한다. 이보다 더 좋은 개선방법은 얼마든지 많이 있지만 작은 문제를 조금씩 해결해 큰 문제를 해결하는 방법을 소개할 수 있어 좋았다”고 말했다. 작은 문제 부터 생각할 수 있는 능력이 꼭 필요한듯 하다. DP의 중요성이 다시금 느껴진다.