음식 픽업하러 산 넘고 강 건널 수 없으니까: 배달 데이터를 활용해 최적의 지역 클러스터링하기 #우아콘2024 #우아한형제들

우아한테크·woowacon-2024 ·2024년·

#geospatial-clustering#word2vec#hierarchical-clustering#h3-indexing#dispatch-optimization#machine-learning-operations

AI 요약

균일한 H3 격자로 배차 지역을 나누며 생긴 상권 단절, 지역별 처리량 편차, race condition, 먼 rider를 끌어오는 wild-goose-chase를 배달 이동 데이터 기반 clustering으로 개선한 사례다. 이동 sequence를 공간 embedding으로 바꿔 자연 경계와 상권을 반영한 지역을 만든 과정을 다룬다.

핵심 포인트

10분에 배달 5만·rider 5만이면 조합이 최대 25억 건이라 배차는 먼저 지역을 나눠 분할 정복하는데, 전국을 같은 크기 육각형으로 나누니 밀도가 다른 강남과 강원도를 같은 문제 크기로 취급해 성능·품질이 불균일해지고 먹자골목이 잘리거나 강·도로 때문에 가까운 rider가 후보에서 빠지는 문제 발생
익명 rider가 pickup·delivery한 H3 cell 순서를 문장의 단어처럼 보고 Word2Vec skip-gram으로 학습해 자주 연속 방문되는 cell을 vector 공간에서 가깝게 만들고 hierarchical clustering + 지리 후처리(자연 경계·singleton·비연결 cluster 정리)를 적용
Data scientist가 S3에 둔 cluster를 server가 Athena로 읽고 서비스 지역과 합쳐 빈 H3까지 채우며, 지역 변경은 Kafka로 반영하고 인접 race condition은 동일 task key로 한 partition에 모음 — 서울을 육각형 32개에서 cluster 41개로 바꿔 지방 광역시 평균 pickup 거리 3.7%, 수도권 평균 배달 시간 2.6% 감소

왜 읽나균일 격자 분할의 한계를 겪는 지리 기반 시스템 설계자에게 이동 데이터 embedding + clustering으로 도메인 경계를 학습시키는 접근을 보여준다.

챕터별 상세

011:41 – 4:37

25억 배차 후보를 지역으로 분할 정복하기

10분 동안 배달 5만 건과 rider 5만 명이 존재하면 단순 조합은 최대 25억 건이 되므로, 배차 system은 먼저 지역을 고르고 후보 생성·제약 제거·비용 계산·최적 조합 선택을 수행한다. 초기에는 전국을 같은 크기의 육각형으로 나눠 빈틈과 구현 복잡도를 줄였지만, 주문 밀도가 다른 강남과 강원도를 같은 문제 크기로 취급해 지역별 처리 성능과 배차 품질이 불균일해졌다.

Uber H3의 동일 크기 cell은 먹자골목을 반으로 자르거나 강·큰 도로를 한 지역에 넣어 가까운 rider를 후보에서 제외하고, 지역별 최적화 종료 시점 차이로 한 rider에게 두 배달을 동시에 추천하는 race condition을 만들었다. 주문이 몰린 큰 지역에서는 지연 배달을 처리하려고 먼 rider까지 끌어오는 wild-goose-chase가 발생해, 이동하기 쉬운 cell은 묶고 자연 경계·상권·처리량을 반영하는 data-driven 지역이 필요했다.

GPS 대신 익명 rider가 pickup·delivery를 수행한 H3 cell의 순서를 문장의 단어처럼 보고 Word2Vec으로 학습해, 자주 연속해서 방문되는 cell이 vector 공간에서도 가까워지도록 만들었다. 희소 지역을 더 잘 다루는 skip-gram embedding과 hierarchical clustering을 선택하고, 강·산·도로·상권 경계와 지나치게 길거나 뾰족한 모양을 정성 평가하며 singleton·비연결 cluster와 뒤바뀐 인접 cell을 후처리했다.

Data scientist가 S3에 둔 cluster를 server가 Athena로 읽고 서비스 가능 지역과 합쳐, 데이터가 적은 공원·도시 외곽의 빈 H3도 주변 생활권에 맞게 채워 전체 배달 지역을 빠짐없이 cover했다. 서비스 지역 변경 event는 Kafka로 반영하고 인접 지역의 race condition은 동일 task key로 한 partition에 모으며, 신규 지역은 행정동 기반으로 임시 생성하고 비마트·한강 경계 같은 예외는 admin에서 미세 조정했다.

서울을 고정 육각형 32개로 나누던 방식에서 배달·rider 밀도와 상권을 반영한 cluster 41개로 바꿔 방이동 같은 하나의 상권을 같은 지역에 묶고, 중심지는 작게 외곽은 크게 나눠 10분당 주문량 분포를 더 균일하게 만들었다. 자연 지형을 돌아가는 배차도 줄어 wild-goose-chase가 두드러진 지방 광역시의 평균 pickup 거리는 3.7%, 수도권의 평균 배달 시간은 2.6% 감소했다.