컬리가 상품을 고객에게 빠르게 전달하는 똑똑한 방법

Context

컬리의 배송 시스템은 CC(대형 물류센터)→TC(중간 물류센터)→권역(고객)의 2단계 구조로 운영되며, 기존에는 행정 구역과 직선거리 기반의 수작업 구획 분할로 권역을 할당했다. 이로 인해 실제 배송 소요시간이 최적화되지 않았고, TC별 물량이 수용력 대비 불균형했으며, 할당된 권역들이 지리적으로 흩어져 배송기사의 권역 간 이동 비효율이 발생했다.

Technical Solution

• 문제를 Generalized Assignment Problem(GAP)으로 모델링: 결정변수 y_ij(TC i에 권역 j 할당 여부)의 목적함수(CC→TC→권역 소요시간 총합 최소화)와 제약식(TC별 물량 상한선, 각 권역은 1개 TC만 할당)을 수리 모형으로 정의
• OR-Tools 오픈소스 솔버 도입: Google이 개발한 OR-Tools의 CP-SAT(제약 프로그래밍 + Boolean Satisfiability)과 SCIP(선형완화 + Branch-and-Bound) 두 솔버를 병렬 실행해 NP-hard 문제의 최적해를 도출
• 실제 배송 환경 데이터 반영: 권역별 주문당 배송시간 이력 데이터로 난이도 계수를 산출해 물량 값에 적용, TC별 출차 회차(하루 3회)별 예상 소요시간을 가중합으로 계산
• 권역 응집성 최적화 추가 실행: 한 TC에 할당된 권역들 사이의 최대 이동거리 합을 최소화하는 별도의 조합 최적화 문제를 정의해 지리적으로 흩어진 권역 할당 문제 해결
• 도구화를 통한 재사용성 확보: 물류 운영 부서가 입력 데이터 업데이트, 최적화 범위 설정, 실행 및 결과 분석을 반복 가능하도록 구현

Impact

대안1(최적경로 우선 길찾기)은 기존 방식 대비 배송 소요시간을 약 5% 단축, 대안2(무료도로 우선 길찾기)는 배송 소요시간을 약간 타협하면서 톨게이트 비용을 최소화하고 기존 방식보다 우수한 결과 달성

Key Takeaway

배송·물류 최적화는 현실의 복잡한 변수(도로 상황, 배송 난이도, 차량 수용력 등)를 수리 모형에 완벽하게 담을 수 없으므로, 최적화 알고리즘 실행과 현장 피드백을 반복적으로 수렴하면서 수기 재조정을 거쳐야 실제 도입 가능하다. 또한 단일 목표(시간 최소화)만으로는 부족하며, 권역 응집성 같은 운영 제약을 추가 최적화 문제로 정의하는 다층적 접근이 필요하다.