컬리는 물류 최적화 문제를 어떻게 풀고 있을까? - 1부

컬리 데이터플랫폼팀이 물류센터 QPS(Quick Picking System) 공정의 생산성을 유전 알고리즘으로 최적화한 과정을 다룬다. 1부는 무엇을 최적화할지 정의하고, 유전 알고리즘을 적용해 과거 데이터로 검증한 결과까지를 정리한다.

핵심 포인트

주문처리는 주문 그룹화 → 피킹 → QPS 분배 3단계인데, 자동화 비중이 높은 QPS를 최적화 대상으로 골랐다.
QPS 생산성을 개별 바구니 처리 속도로 정의하고, 회귀분석으로 바구니 안 고유 상품 수가 가장 영향력 큰 변수임을 찾았다.
문제를 Open-shop scheduling(NP-Hard)으로 치환하고, 최적해 판별이 어려워 유전 알고리즘으로 근사해를 탐색했다.
기존 대각행렬 알고리즘 대비 batch 내 고유 상품 수를 약 10% 이상 줄였고, 결과는 IEEM 2022에 발표 예정이다.

상세 정리

문제 배경: 물류센터 주문처리는 변수가 많아 최적화가 어렵고, 같은 상품을 한 번에 모아 가지러 가는 총량 피킹으로 효율을 높이려는 목적이 있다.
QPS 공정: 작업대에 바구니 도착 → 스캐너 인식 → 상품 스캔 시 넣을 칸(주문) 번호 표시 → 작업자가 해당 칸에 분배하며, 각 칸이 주문 하나다.
지표 정의: 총 바구니 수 등 조건이 같다면 개별 처리 속도 감소가 곧 전체 생산시간 감소이므로 이를 Y로 삼았다.
핵심 변수: 다공선성·내생성 우려 변수를 제외한 회귀분석에서 바구니 안 고유 상품 수가 가장 영향이 컸고, 이 값은 QPS뿐 아니라 앞단 피킹 동선에도 영향을 준다.
목표 재정의: 따라서 바구니 안 고유 상품 수를 줄이는 방향으로 주문 조합을 짜는 것을 최적화 목표로 삼았다.
기존 접근: 주문-상품 행렬을 만들어 대각에 가까운 행렬을 지향하며 행·열을 섞고 인접 주문을 묶어 고유 상품 수를 줄이는 방식이었다.
유전 알고리즘 개념: 해를 유전자, 해집합을 세대로 두고 적합도로 우수 부모를 선택, 교배·변이로 자식 세대를 만들어 세대를 거듭하며 근사 최적해로 수렴시킨다.
속도 대응: 세대를 늘리면 결과는 좋아지지만 수행 시간이 길어져 작업이 지연될 수 있어, 첫 세대를 공들여 만들어 속도와 성능을 함께 잡았다.
적용 방식: 유사 주문이 같은 batch에 담기도록 첫 세대 생성 → 유전자별 고유 상품 수 계산 후 상위 50% 생존 → batch 단위 교배·변이 반복.
결과: 과거 주문 데이터에서 유전 알고리즘이 기존 알고리즘 대비 주문 수 규모와 무관하게 고유 상품 수가 대체로 적어 약 10% 이상 감소했다.
남은 과제: 실제 물류 환경은 변수가 많아 QPS 전후 공정이 맞물려 예상 밖 지연이 생길 수 있어, 2부에서 Digital Twin으로 추가 검증한다.