배달앱 총알배송의 비밀은 '수학적 최적화'

최적의 '묶음 배송' 방법 찾아라
LG CNS '최적화 그랜드 챌린지'
대한산업공학회와 공동 개최
제조·물류·금융·통신·항공·철도 등
대부분 산업에서 최적화 수요 늘어
KAIST·서울대 등 32개 대학팀
카카오·GS칼텍스 등 8개 직장인팀
예선 통과…10개팀 뽑아 결선

LG CNS 직원들이 ‘최적화 그랜드 챌린지 2024’ 경연대회를 소개하고 있다. /LG CNS 제공

스마트폰 시대의 가장 큰 수혜자 중 하나인 배달 앱. 배달 앱 운영업체들은 동시다발로 일어나는 배달 주문을 어떻게 처리할까. 주문하는 고객으로선 자신의 주문 한 개만 생각하고 최대한 빠른 배송을 원하지만, 배달을 총괄하는 입장에선 보통 복잡한 일이 아니다. 무수한 소비자의 주문과 배달 음식을 만들 저마다의 음식점, 그리고 대기 중이거나 운행 중인 라이더를 최적으로 조합해야 하기 때문이다. 조합은 가짓수가 약간만 늘어나도 기하급수적으로 증가한다.

지리적으로 가까운 배송지와 음식점을 적절히 묶어 라이더에게 복수의 주문을 배당하는 것을 묶음 배송 기술이라고 한다. 이 기술이 있어야 배송 시간을 최대한 줄일 수 있다. 묶음 배송은 수리과학적으로 최적화한 알고리즘이 필요하다.

LG그룹의 정보기술(IT) 서비스 기업으로 국내 산업의 디지털 전환(DX)을 선도하고 있는 LG CNS는 올해 대한산업공학회 창립 50주년을 맞아 이 학회와 함께 ‘최적화 그랜드 챌린지 2024’를 열고 있다. 이 대회 주제가 ‘묶음 배송 최적화:묶어라, 보내라, 싸게 빠르게’다.

올해 처음 마련된 이 대회엔 국내 주요 대학(원)생, 대기업 직원 등으로 구성된 378개 팀, 827명이 참가했다. 지난 6월 24일부터 이달 7일까지 열린 예선 결과 40개 팀이 통과했다. KAIST, 서울대 등 대학 32개 팀과 카카오, GS칼텍스, LG디스플레이 등에서 참가한 직장인 8개 팀이 예선을 넘었다.

묶음 배송이 중요한 이유는 어떻게 주문을 조합하느냐에 따라 배송 시간이 달라지고, 그에 따라 라이더에게 지급하는 비용이 달라지기 때문이다. 배달 앱을 운영하는 기업으로서는 묶음 배송을 통해 비용 최소화, 이윤 극대화를 추구할 수 있다. 배달의민족 앱을 운영하는 기업 우아한형제들이 이번 대회 후원사로 참여한 이유다.

참가 팀은 여러 고객이 동시에 음식을 주문할 때 도보, 오토바이, 차량 등을 매칭해 가장 빠르게 음식을 배달할 수 있는 최적의 묶음 배송 알고리즘을 구현해야 한다. 묶음 배송은 여러 제약 조건하에서 최적화를 통해 이뤄진다. 수학적으로 보면 명쾌하다. 목적함수(배송비)를 최소화하는 것이다. 예선에서 제시된 주문 개수는 300개. 참가한 팀들은 300개의 주문을 ‘최선으로’ 나눠 묶는 조합 알고리즘을 코딩해 수시로 올렸다. LG CNS는 각 팀이 개발한 알고리즘에 대한 점수와 순위를 매일 대회 홈페이지 리더보드에 공개하고 있다.

행사 자문단으로 참여하고 있는 대학 교수들과 LG CNS 내부 전문가들이 함께 개발한 평가 모델로 이들 알고리즘 순위를 매긴다. 이 모델은 참가자들이 제시한 알고리즘이 1분 내 최적으로 음식을 배달할 수 있는 조합을 찾는지를 따진다. 알고리즘이 최적 조합을 찾는 시간이 1분을 넘으면 그 알고리즘은 쓸모가 없는 것으로 간주해 탈락시킨다.

예선을 통과한 40개 팀은 이달 12일부터 다음달 11일까지 본선에서 실력을 다시 겨룬다. 본선에서는 묶어야 할 주문이 1000개로 세 배 이상 늘어난다. 본선을 넘은 10개 팀은 10월 16일까지 결선을 치른다. 결선에선 주문이 수천 개 이상이다.

LG CNS는 수학적 최적화로 산업을 선도하고 있는 국내 유일한 기업이다. 제조, 물류, 금융, 통신, 항공, 철도 등 다양한 분야 기업이 의뢰한 비즈니스 난제를 수학적 최적화로 해결해준다. LG CNS는 ‘최적화컨설팅 담당’이란 특화 조직을 두고 규모를 매년 확장하고 있다.

LG CNS는 수학적 최적화 관련 인재 육성에도 앞장서고 있다. 지난 7~9일 전국 산업공학도가 모여 교류하는 ‘필드 캠프’ 연례 행사가 대전 KAIST에서 열리도록 지원했다. 수학적 최적화 관련 전문가 강연과 함께 학생들이 이론을 바탕으로 최적화 실무 경험을 쌓는 기회를 제공했다. 장민용 LG CNS D&A 사업부장은 “이번 최적화 그랜드 챌린지 행사가 미래 신산업 활성화를 위한 촉매가 되길 기대한다”고 말했다.

이해성 기자 ihs@hankyung.com