Region Clustering using delvery data
11주차: 음식 픽업하러 산 넘고 강 건널 수 없으니까: 배달 데이터를 활용해 최적의 지역 클러스터링하기
https://www.youtube.com/watch?v=Ub1kL0OB5n8&ab_channel=%EC%9A%B0%EC%95%84%ED%95%9C%ED%85%8C%ED%81%AC
🧭 배달 시스템에서 ‘지역’을 다시 생각하다
배달의민족은 하루 100만 건에 달하는 주문을 처리하며, 이 모든 배달을 적절한 라이더에게 할당하는 복잡한 문제를 다룹니다. 특히 어디서 어디까지를 하나의 지역으로 볼 것인가는 단순한 지리적 개념을 넘어서 성능, 정확도, 효율을 좌우하는 핵심 요소입니다. 이 발표에서는 기존의 정적 지역 분할 방식이 갖는 한계를 극복하기 위해, Word2Vec 기반 공간 임베딩과 클러스터링 기법을 활용해 지역을 재정의한 과정을 자세히 다룹니다.
배차 문제와 분할 정복
10분간 5만건의 주문이 발생하고 5만명의 라이더가 있을 경우
브루트 포스를 한다면 25억건의 배차 연산이 발생한다. 이는 너무나 비효율적이기에 지역을 나누어 배차시스템을 운영해야했다.
🚨 기존 지역 분할의 한계: 균등 분할이 항상 공정하지 않다
초기에는 지도를 일정 크기의 육각형으로 나누는 균등 분할 방식이 사용되었습니다. 이 방식은 모든 지역을 일관성 있게 처리할 수 있어 단순하지만, 다음과 같은 실무적 문제를 유발했습니다.
수요 불균형 문제
서울 강남과 강원 태백은 배달량 자체가 다릅니다. 하지만 동일한 크기로 분할하면, 라이더 수와 배달 건수에 비례한 최적화가 어렵습니다. → 과도한 배차 연산, 지연
지리적 특성 무시
한강, 고속도로, 공원 등 이동을 방해하는 지형지물이 반영되지 않아, 실제론 이어지지 않은 지역을 하나로 묶어 비효율적인 배차를 유발했습니다.
동시성 문제
인접 지역이 동시에 배차를 시작하면, 동일 라이더에게 중복 배차가 발생할 수 있습니다. 이 경우에는 **락(Lock)**으로 제어할 수 있지만, 락은 최적 배차 기회를 줄이므로 시스템 성능 저하의 원인이 됩니다.
H3 라이브러리
Uber가 개발한 지리 정보 격자 시스템으로, 전 세계를 육각형 단위로 나눔.
각 셀은 고유 ID를 가지며 계층 구조(레벨 0~15)로 표현 가능.
문제 정의
지형/상권 고려 불가 → 예: 방이동 먹자골목이 쪼개짐
타이밍/동시성: 인접 지역에 라이더 위치시, 지연/동시 배차 이슈
락은 배차시스템을 비효율적으로 만들 수 있으므로, 이러한 락을 최소화 시키기 위해 보다 근본적인 문제해결이 필요.
무리한 배차: 도시/경계 따라 비효율적 이동 (와일드구스 체이스)
🧪 문제 정의: 왜 ‘데이터 기반’ 재구성이 필요했는가?
기존 방식은 명확한 기준 없이 '지도 위 타일을 깔 듯' 나눴습니다. 하지만 서비스가 커지면서, 지역의 재구성에는 다음과 같은 정량적·정성적 기준이 필요해졌습니다:
라이더 이동 가능성
송파구처럼 라이더들이 일정 지역 안에서만 배달하는 패턴이 많았기에, 실제 라이더의 행동 기반으로 지역을 나눌 필요성이 대두되었습니다.
상권, 도로, 강 등 물리적 경계 반영
사람의 이동과 차량의 이동은 다르며, 배달 특성상 도보 불가능한 영역은 피해야 합니다.
성능을 위한 균등한 ‘문제 크기’ 구성
배차 최적화는 NP-Hard 문제로, 전체 조합을 계산하는 대신 지역 단위로 나누고 줄여야 합니다. 단순한 크기보다, 배달 건수와 라이더 수의 균형이 핵심입니다.
행정동/수작업 분할의 한계: 데이터를 풍부하게 활용하기 어려움
핵심 데이터:
라이더 GPS보다는 "액션(픽업/전달 등) 간 H3 이동 순서"
목표:
자연스러운 이동/빈도 중심, 상권/지리/이동경로 반영
- 라이더 이동이 편한 클러스터
위 그래프를 보면 양끝의 값이 높은 걸 알 수 있다.
이는 송파구에서 배달서빙을 100퍼센트하는 라이더가 있거나, 아예 배달을 하지 않는 라이더가 대부분임을 알 수 있고, 이는 지역을 잘 나누기만 한다면 라이더의 판단대로 주문을 이행할 수 있다고 판단하였다.
지점 간 "오가기가 쉬운지"를 Metric으로 정의
하이라키컬 클러스터링(Hierarchical Clustering): 맥락/관계로 덩어리 묶기
워드투벡(Word2Vec) 임베딩:
단어 대신 H3 셀/action 순서 적용(CBOW/Skip-gram 비교; skip-gram 최적)
임베딩 공간의 거리 → 이동 용이성/실제로 붙어 있는지 표현
데이터 희소성 문제는 skip-gram으로 완화
예시: 잠실-송파구청은 가깝게, 잠실-삼성은 강 건너 멀게
🧠 Word2Vec으로 공간을 벡터화한다는 개념
Word2Vec은 원래 언어모델에서 사용되며, 단어 간 의미적 유사성을 벡터 공간에 투영하는 기술입니다. 여기서는 단어 대신 H3 셀(공간 단위)을 벡터로 표현했습니다.
라이더의 픽업 → 이동 → 배달 로그 데이터를 ‘문장’처럼 보고
각 H3 셀을 ‘단어’처럼 보고
이 순서를 바탕으로 의미적 연결성(이동이 쉬운 지역 vs 어려운 지역)을 학습했습니다
이 방식은 지리적 거리를 벗어나, 실제 이동 빈도와 편의성까지 반영된 실제 행동 기반 임베딩이라는 점에서 매우 혁신적입니다.
🧾 Skip-Gram vs CBOW
Skip-Gram은 “이 단어 주변엔 어떤 단어가 나올까?”를 예측합니다. 이 문맥 기반 추론은 라이더가 "현재 위치에서 다음 액션은 어디서?"를 예측하는 방식과 매우 유사합니다.
Skip-Gram: 주변 단어 예측
CBOW: 주변 단어로 중심 단어 예측
[다중 위치 → 단일 목적지]가 아닌 [단일 위치 → 다중 목적지] 연산을 할 수 있는 Skip-Gram을 선택함
Skip-Gram VS CBOW
🧠라이더의 배차결정 과정
“내가 신천동에 있으니 어느 지역에 가는 것이 가장 효율적일까?”
📉 Infrequent Cell 문제: 드러나지 않는 위험
데이터가 적은 H3 셀은 학습된 벡터가 정확하지 않습니다. 이로 인해 다음과 같은 문제가 발생합니다:
Infrequent Cell: 라이더의 이동/배달 데이터가 거의 기록되지 않은 H3 셀
멀리 떨어진 두 셀이 같은 클러스터로 묶이거나
주요 배달지임에도 누락되거나
특정 셀의 벡터가 주변 맥락과 전혀 무관하게 위치하게 됩니다
이러한 문제는 곧바로 부정확한 배차로 이어질 수 있으므로, 후처리 단계에서 반드시 보완되어야 합니다.
또한, 이 문제는 Skip-gram에서 훨씬 덜 발생했기에 자연스럽게 Skip-gram 모델을 선택
🛠 클러스터링 후처리 및 하이퍼파라미터 조정
🧪 하이퍼파라미터 튜닝
평가 기준: 도로 경계, 상권 연속성, 인구 분포 균일성, shape regularity (예: 너무 뾰족한 모양 피하기, convex)
단일 피트니스 함수로 불가능 → 정성적 평가 병행
🔧 후처리 작업
연속성 보장: 단절 클러스터 병합 또는 제거
스무딩 처리: 뾰족/얇은 지형 최적화
클러스터 중앙 빈 공간 자동 확장: 광진구 사례처럼
비매핑된 외곽 영역 채움: 군포·의왕시 사례, 인접 도시 클러스터에 연결
🛠️ 운영을 위한 보완: 자동화와 수동 개입의 균형
클러스터링만으로는 운영 환경에 적용할 수 없습니다. 대표적인 문제는 다음과 같습니다:
클러스터 내부의 빈 영역
예: 광진구 어린이 대공원처럼 공원·시설물은 데이터가 부족해 누락
경계 지역 왜곡
한강을 사이에 둔 H3 셀은 잘못된 라이더 배차를 유발
신규 지역, 변경 이벤트 대응
클러스터는 주기적으로 재구성되지만, 실무에서는 한 주 만에 상권이 변할 수 있습니다
이러한 문제를 해결하기 위해, Kafka 기반 이벤트 시스템과 Task Queue 기반 순차 처리, 그리고 운영자용 지역 수정 도구(Admin Tool)를 함께 구성하였습니다.
📡 Kafka 이벤트 흐름과 레이스 컨디션 해결
🧨 어떤 상황이 문제인가요?
운영자가 여러 지역을 동시에 수정하는 경우, 예를 들어 “송파구와 강남구 지역 설정을 동시에 바꿈”.
이 이벤트들이 Kafka로 메시지로 전송됨.
Kafka는 기본적으로 이벤트를 Key 기반으로 파티션에 분배해요.
❗ 그런데 문제가 생김!
송파구 이벤트는 A 파티션, 강남구 이벤트는 B 파티션으로 감.
이 파티션들을 각각 다른 서버 인스턴스가 처리할 수 있어요.
그런데 송파구와 강남구는 인접한 지역이잖아요?
→ 서로 겹치는 H3 셀을 다룰 수도 있음.
→ 이걸 각기 다른 서버에서 동시에 처리하면 경합(Race Condition) 발생!
예시)
인스턴스 A는 송파구 확장하면서
H3-123셀을 포함인스턴스 B는 강남구 확장하면서도
H3-123셀을 포함둘 다 모르고
H3-123을 자기 지역에 포함시킴 → 충돌 발생
Kakfa를 통해 이벤트 기반으로 지역의 변경 사항을 동기화 했습니다. 여러 지역이 동시에 변경될 경우, Kafka의 분산 특성상 동시에 여러 인스턴스가 같은 데이터를 수정하는 문제가 발생합니다.
이를 방지하기 위해:
이벤트를 중간 큐(Task Queue)에 모아 순차 처리
동일 TaskId로 파티셔닝하여 단일 인스턴스에서만 처리되도록 구성
병렬 처리도 가능하도록 비인접 지역끼리 그룹화
🧰 수작업 영역: B마트와 지형 특수성 대응
B마트는 ‘물류센터’ 성격의 픽업지로, 주변에 많은 배달이 몰립니다. 하지만 마트가 지역 경계에 위치하면, 한쪽 방향만 배차 우선권을 얻어 배차 편중 문제가 발생합니다. 이 경우엔 운영자가 직접 위치 조정을 통해 해결해야 합니다.
또한 한강, 산, 도로 등은 임베딩 벡터상 연결성이 있지만 실제론 이동 불가능한 지형이므로, 이런 문제는 모델이 아닌 사람이 조정해야 했습니다.
해결방안
지역을 관리하는 Admin을 만들어 미세한 조정이 가능하도록 하여 대응할 수 있었습니다.
🎉 실제 효과: 수치로 입증된 개선
상권 단위 지역 분할
기존 서울 32개 지역 → 클러스터 기반 41개 지역으로 세분화
방이동 상권처럼 분리되던 지역이 하나로 묶여 배차 일관성 증가
부하 분산 효과
배달 밀집 지역은 작게, 외곽은 크게 → 시스템 전체 성능 균형 확보
이동 거리 감소
와일드 구스 체이스 감소 → 특정 광역시에서 평균 픽업 거리 3.7% 개선
수도권 지역 평균 배달 시간 2.6% 감소
Last updated