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

컬리가 CC(대형 물류센터)→TC(중간 거점)→고객 2단계 배송에서 TC-권역 할당을 재조정해 배송 소요시간과 물량 불균형을 줄인 조합 최적화 프로젝트를 다룬다. 행정구역·직선거리 기반의 수작업 구획을 OR-Tools 최적화 solver로 대체해, 각 TC가 담당할 권역을 배송 총 소요시간이 최소가 되도록 재배치했다.

핵심 포인트

문제를 Generalized Assignment Problem(GAP)의 special case로 정의: 목적함수는 총 소요시간 최소화, 제약은 TC 물량 상한과 권역당 1개 TC, 결정변수는 할당 여부 0/1이다.
TC 10개·권역 100개면 경우의 수가 10^100로 전수탐색이 불가능해, OR-Tools의 CP-SAT과 SCIP solver를 병렬 실행해 최적해를 구했다.
비슷한 위치 TC끼리 권역이 뒤섞이는 문제를 막으려 각 TC 담당 권역이 뭉치도록 하는 2차 최적화(권역 간 이동거리 최댓값 총합 최소화)를 추가했다.
입력 데이터 품질이 핵심이라, 권역 물량에 배송 난이도(강남 60건/h vs 남양주 30건/h)를 곱해 보정했다.

상세 정리

배경: 1단계 CC→TC는 가까운 TC로 고정, 2단계 TC→권역은 유동적이라 이 할당을 최적화 대상으로 삼았다.
목표: 배송 소요시간 감소와 TC 간 물량 불균형(적체·잉여) 해소 두 가지다.
수리 모형: 파라미터 t_ij(소요시간 물량 가중합)·d_j(권역 물량)·c_i(TC 수용력)로 두고, 목적함수는 할당 소요시간 총합 최소화다.
solver 선택 근거: 실시간이 아니라 해 품질이 중요해 24시간 이상 시간을 줘도 되고, GAP는 NP-hard지만 solver가 수시간 내 최적해를 낸다는 직관에 오픈소스라 부담이 없었다.
solver 특성: CP-SAT은 Constraint Programming과 SAT(제약 전파·백트래킹), SCIP은 선형완화·Branch-and-Bound 정수계획법으로, 문제 구조에 따라 빠른 쪽이 달라 둘을 병렬 실행해 안정적 결과를 얻었다.
권역 재분할: 비슷한 위치 TC는 권역까지 소요시간 차이가 작아 할당이 뒤섞여 관리·기사 이동이 비효율적이라, z_ijk(동시 선택)·w_i(권역 간 최대 이동거리) 변수를 추가해 권역이 뭉치게 유도했다. k-means clustering과 유사하나 물량 제약이 큰 차이다.
입력 데이터 보정: garbage in, garbage out이라 물량에 난이도 가중치를 반영하고, TC 수용력은 차량 공간에 과거 데이터·현장 피드백을 더해 설정했다.
현실 제약: 40분 초과 금지, 특정 기사 선호 권역 같은 조건을 전처리나 제약식으로 추가했다.
실행 결과: 대안1(최적경로)은 배송시간 약 5% 절감·톨게이트 비용 증가, 대안2(무료도로)는 시간을 약간 양보하되 톨비까지 최소화했다.
적용 방식: 모형 실행과 현장 피드백을 상호 보완적으로 반복해야 실제 적용이 가능해 수기 재조정을 병행하고, 재사용하도록 도구화해 신규 TC 후보지 계약·권역 재조정 의사결정에도 확장했다.