백엔드
컬리는 물류 최적화 문제를 어떻게 풀고 있을까? - 1부
두줄요약
컬리는 QPS 공정의 생산성을 높이기 위해 바구니 안 고유 상품 수를 줄이는 최적화 문제를 다뤘습니다. 기존 방식 대신 유전 알고리즘을 적용해 10% 이상 개선 가능성을 확인했습니다.
문제 상황
- 컬리 물류센터의 QPS 공정에서 바구니 처리 속도 저하 요인 분석 필요
- 주문 조합에 따라 바구니 안 고유 상품 수가 달라져 전체 생산시간에 영향
- 기존 대각 행렬 기반 주문 묶기 방식의 한계와 최적화 필요성 존재
원인 분석
- QPS가 여러 주문을 작업자에게 분배하는 Open shop scheduling 성격의 NP-Hard 문제
- 해의 경우의 수가 매우 많아 최적 조합 판별이 어려움
- 고유 상품 수가 많을수록 피킹과 분배 동선이 복잡해짐
해결 방법
- 주문 조합 탐색에 유전 알고리즘 적용
- 유사한 주문을 같은 batch에 모아 첫 세대 생성
- 고유 상품 수가 적은 조합을 적합도로 삼아 상위 절반 생존, 교배와 변이 반복
성능/운영 포인트
- 실제 주문 데이터 기준 기존 방식 대비 batch 내 고유 상품 수가 대체로 감소
- 전체적으로 10% 이상 감소 폭 확인
- 실제 운영 적용을 위해 알고리즘 수행 시간과 공정 지연 가능성 고려 필요