쿠팡이츠는 왜 인하우스 지도 서비스를 만들었을까?

국내 IT 기업은 한국을 넘어 세계를 무대로 할 정도로 뛰어난 기술과 아이디어를 자랑합니다. 이들은 기업 블로그를 통해 이러한 정보를 공개하고 있습니다. 요즘IT는 각 기업의 특색 있고 유익한 콘텐츠를 소개하는 시리즈를 준비했습니다. 이들은 어떻게 사고하고, 어떤 방식으로 일하고 있을까요?

이번 글은 국내 대표 이커머스 기업 ‘쿠팡(Coupang)’이 쿠팡이츠에 인하우스 지도 및 길찾기 서비스를 구축하게 된 배경과 과정을 소개합니다.

3단계의 배달 시간 추정 및 배달 경로 계획으로 음식 배달 속도를 높이다

배달 경로 계획부터 주문 도착 시간 예측까지, 정확한 지도 서비스는 쿠팡이츠 비즈니스에 있어 필수적인 부분입니다. 쿠팡이츠는 타업체의 지도 서비스로 비즈니스를 시작했습니다. 하지만 비즈니스가 성장하면서 지도 기능들의 커스터마이제이션과 UX 개선 요구가 커졌고, 더 높은 수준의 새로운 지도 서비스가 필요해졌습니다.

고객에게 “WOW”한 경험을 제공하기 위해, 저희는 최고 수준의 인하우스(in-house) 지도 서비스를 설계 및 개발하기로 결정했고 곧바로 그 여정을 시작했습니다. 이번 글을 통해 인하우스 지도 서비스의 핵심 구성 요소인 길찾기 서비스가 어떻게 배달 효율을 높이고 수백만 달러의 운영 비용을 절감했는지를 공유드리고자 합니다.

쿠팡이츠의 위치 서비스

고객은 쿠팡이츠 앱에서 메뉴를 고른 후 주소만 입력하면 집 앞까지 음식을 배달 받을 수 있습니다. 하지만 이 매우 짧은 순간에도 이츠는 위치(location) 관련 기술을 활용해 백엔드에서 다음과 같은 복잡한 계산을 수행하고 있습니다:

• 배달 경로 계산. 배달 파트너(Eats Delivery Partner, EDP)가 오토바이, 자동차, 자전거, 도보로 이동한다는 가정 하에 각 운송 수단에 맞는 최적의 배달 경로를 찾습니다.
• 도착 예정 시간(ETA) 계산. 같은 경로라도 교통 상황이나 기상 조건에 따라 ETA가 크게 다를 수 있습니다. 최적의 배달 경로를 결정하기 위해 정확히 ETA를 계산합니다.
• 배달을 위한 최적의 입구 식별.고객이 공원이나 특정 건물로 음식을 주문할 수 있습니다. 저희는 아파트 단지처럼 큰 영역을 관심지역(Area of Interest, AOI)으로 정의합니다. 최적의 배달 경로를 찾는 데 있어 AOI의 최적 진입점을 식별하고 배달 파트너(EDP)를 가장 가까운 입구로 안내하는 작업은 매우 중요합니다.

위의 계산들은 EDP를 위한 최적의 경로를 찾아 음식이 보다 더 효율적으로 배달되는 것을 목표로 하고 있으며, 고객, 판매자, 배달 파트너(EDP) 모두가 윈윈(win-win)할 수 있는 고객 경험(Customer Experience, CX)을 가능케 합니다.

타사 지도 서비스의 한계

타사 지도 서비스로 위에 언급된 유즈 케이스(use case)를 어느 정도까지는 대응할 수 있었지만, 이츠 비즈니스가 급속히 발전하면서 몇 가지 문제와 한계에 직면하게 되었습니다.

• 비효율성. 타사 지도들은 정확한 배달 경로와 ETA를 안정적으로 제공하지 못했습니다. 또한 최적이 아닌 경로 또는 잘못된 관심지점(Point of Interest, POI)에 EDP를 할당하는 경우가 많았습니다.
• 불안정성. 타사 지도들을 사용하면 대기 시간(latency)과 평균 복구 시간(mean time to repair, MTTR)이 길어집니다. 이츠 비즈니스에 있어 지도 서비스는 매우 중요하기 때문에 이러한 불안정한 성능 문제는 고객 경험에 안 좋은 영향을 미쳤습니다.
• 제한된 확장성. 타사 앱들에 대한 의존도 또한 비즈니스 확장성을 제한했습니다. 초당 쿼리 수(queries per second, QPS)에 제한이 있다 보니 증가하는 고객 주문을 신속히 대응할 수 없었습니다.

인하우스 지도 및 길찾기 서비스

타사 지도 서비스 사용하면서 발생했던 문제들을 극복하기 위해, 저희는 자체적으로 인하우스 지도 서비스를 만들었습니다. 일반적인 지도 서비스가 데이터에 크게 의존하는 것과 같이 저희의 인하우스 지도 서비스는 온라인 서비스 계층, 데이터 계층, 데이터 생산자 계층 이렇게 3개의 계층으로 나뉘어져 있습니다. 또한 저희는 머신 러닝 플랫폼을 활용해 서비스 내 각종 데이터의 정확도를 개선합니다.

인하우스 지도 서비스의 여러 구성 요소들 중 핵심은 바로 경로 계획, ETA 및 거리 계산 등을 담당하는 길찾기 서비스입니다. 저희가 이 길찾기 서비스를 개발하면서 거쳤던 세 개의 주요 단계를 다음 섹션에서 자세히 설명드리겠습니다.

1단계: ETA 계산용 알고리즘 모델 훈련하기

길찾기 서비스 개발의 첫 번째 단계에서, 저희가 중점을 두었던 것은 ETA의 정확도를 향상시킬 수 있는 시스템을 만드는 것이었습니다.

먼저 ETA를 계산하기 위한 라우팅 엔진을 구축했습니다. 하지만 아무것도 없는 상태에서 시작했기 때문에 작업할 데이터가 적었고 결과는 정확하지 않았습니다. 정확성을 향상시키기 위해 EDP 이력 추적 데이터, 배달 수단 유형, 배달 지역 정보 등과 같은 비즈니스 관련 피처(feature)들을 기반으로 알고리즘 모델을 훈련시켰습니다.

통계적으로 봤을 때 알고리즘 모델과 라우팅 엔진이 내놓는 결과는 나쁘지 않았습니다. 하지만 교통량과 같은 실시간 변화를 결과에 반영하지는 못했습니다. 또한 확률 분포 상의 문제로 약간의 좋지 않은 결과가 나오기도 했습니다.

2단계: 데이터 마이닝으로 이동 속도 계산하기

더 나은 ETA 계산 및 경로 계획을 위해, 비즈니스 데이터 기반의 데이터 마이닝(data mining)으로 교통량 이력이 고려된 이동 속도를 생성합니다. 이렇게 마이닝된 이동 속도는 도로 구간 정보와 결부되어, 경로 계획 시 경로 가중치 및 순위를 계산하는 데 사용됩니다.

구간 이동 속도 계산

EDP에서 이동 속도를 얻는 방법에는 두 가지가 있습니다.

• 거리로 계산된 속도. 구간(segment)은 가장 작은 단위의 도로를 가리킵니다. 이동로(track)는 EDP의 배달 경로이고, 이동로 내 통과점(track points)은 특정 구간 내 EDP의 위치 데이터들을 모아 놓은 것입니다. 이동로 내 통과점 둘 사이의 거리와 델타 타임이 업로드됩니다. 속도의 정확도는 EDP 앱을 통해 얻은 델타 타임의 정확도에 따라 달라집니다.
• EDP의 GPS로 업로드된 속도. GPS 속도는 EDP가 양쪽에 높은 건물이 없는 도로를 주행할 때 정확합니다. 그러나 EDP가 고층 건물 사이를 이동하는 경우, GPS 신호가 영향을 받게 되고 이때 업로드된 속도는 정확하지 않습니다.

저희는 위의 두 가지 속도 계산 방법을 조합해, ETA 계산 및 경로 계획에 사용되는 정확한 구간 이동 속도를 얻고 있습니다.

맵 매칭과 노이즈 필터링

정확한 속도 계산을 위해 먼저 맵 매칭(map matching)으로 EDP의 경로를 지도에 매핑합니다. 맵 매칭은 논리적 지리 좌표계를 실제 세계의 도로 구간으로 변환합니다. 맵 매칭은 부정확한 위치 정보는 필터링하고 대상 도로 구간을 찾는 데 도움이 됩니다.

맵 매칭 후, 통과점 밀도(point density)를 사용해 이동로 내 통과점을 추가하거나 필터링하여 속도 계산을 위한 경로를 미리 처리해 놓습니다.

• 두 통과점 사이의 이동 시간이 너무 길면 이동로를 두 개의 하위 이동로로 분할합니다.
• 두 통과점 사이의 이동 시간이 자동차나 오토바이로 이동 시 예상되는 시간보다 너무 짧은 경우, 해당 통과점을 노이즈로 정의하고 제거합니다.
• 이동로 내 통과점이 너무 적으면 이동로를 제거합니다.

아래의 그림으로 예를 들어보겠습니다. 세 구간의 지도에 EDP의 이동로 내 통과점들이 매핑되어 있습니다. 통과점들 중 원과 타원으로 둘러싸여 있는 것들은 이동 시간이 너무 짧기 때문에 노이즈로 정의되어 제거 대상이 됩니다.

노이즈 필터링(noise filtering) 후 배달 경로의 전체 속도를 계산합니다. 아래에 있는 공식을 자세히 살펴보도록 하겠습니다. 여기서 V는 속도이고, Vxi는 지점 i와 i+1 사이의 거리와 지속 시간으로 계산된 통과점들 사이의 속도입니다. 먼저 Vi의 평균을 구간의 최종 속도로 계산합니다. 그런 다음 Vyj로 표시된 더 많은 속도 데이터를 추가해 Vxi 간의 편차가 완화된 최종 속도를 계산합니다. 저희는 이런 속도들을 활용해 구간 별 소요시간, 최종 이동시간 및 ETA를 도출해냅니다.

3단계: POI를 활용해 최적의 길 찾기

관심지점(POI)이 출입구가 여러 개 있는 대형 아파트 단지(AOI) 내의 특정 건물인 경우, EDP의 배달 시간을 최소화할 수 있는 최적의 경유 지점들을 EDP의 배달 방식을 고려해 결정합니다. 이렇게 목적지 근처에서의 이동 방향들은 이츠의 전체 배달 시나리오에 큰 영향을 미칩니다.

EDP가 자동차로 배달하는 경우, 경로 계획에 EDP가 주차하기에 적합한 곳이 포함된 경로가 포함되어야 합니다. AOI에 하나 이상의 입구가 있다면, 경유 지점들이 POI에 더 가까운 입구로 이어지게끔 경로를 계획해야 합니다. EDP가 대형 공원으로 배달 중인 경우, 공원 내에 POI가 없을 확률이 높아 EDP가 고객에게 가는 경로는 매우 단순해집니다.

정확한 경유 지점들을 찾아내기 위해 다음의 방법들을 사용합니다.

• POI 데이터. 저희는 EDP의 이전 배달 관련 데이터, 위성 사진 데이터 및 기타 데이터를 사용해, EDP를 위한 최상의 경유 지점들을 결정하고 ETA 정확도를 개선하고 있습니다.
• 공간 인덱스. AOI를 작은 셀(cell)로 분할하고 빠르게 쿼리할 수 있도록 셀 단위의 공간 인덱스를 구축했습니다. 아래는 작은 셀로 분할되어 있는 공원입니다. 고객을 작은 셀에 배치하게 되면 해당 셀에 가장 가까운 입구를 EDP의 경유 지점으로 쉽게 결정할 수 있어 배달 시간이 단축됩니다.

성능 및 비용

타사 서비스에서 인하우스 길찾기 서비스로 전환 후 다음과 같은 성과가 있었습니다.

• 길찾기 서비스의 P99 대기시간(latency)이 350ms에서 100ms로 70% 감소했습니다. 이후 이어진 최적화 작업을 통해, P99를 50ms 미만으로 개선했습니다.
• 시스템 확장 시 발생하던 병목 현상이 해결되었습니다. 현재 저희의 길찾기 서비스는 50ms 미만의 P99 대기시간으로 이전보다 10배 더 많은 트래픽을 처리하고 있습니다.
• 엔지니어링 비용이 연간 약 2백만 달러 정도 감소했습니다.
• 총 배달 시간, EDP의 음식 대기 시간, 운영 비용과 같은 비즈니스 지표 모두가 개선되었습니다. 사용자 경험 관련 측정 지표들도 개선되었습니다.

결론

이번 글에서는 쿠팡이츠에서 사용 중인 인하우스 길찾기 서비스에 대해 간략히 소개드렸습니다. 저희 지도 시스템은 복잡하고 많은 하위 시스템들로 구성되어 있으며 여전히 해야 할 일이 많습니다. 저희는 이츠의 성공적인 디자인 혁신과 생산성 향상을 위해 저희의 이 유연한 시스템을 끊임없이 발전시켜 나가고 있으며, 이와 관련해 앞으로도 더 많은 업데이트를 공유드리고자 합니다.

<원문>

쿠팡이츠의 인하우스 지도 서비스 구축하기

요즘IT의 모든 콘텐츠는 저작권법의 보호를 받는 바, 무단 전재와 복사, 배포 등을 금합니다.