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

컬리가 물류센터 QPS 공정의 주문 그룹화 문제를 유전 알고리즘으로 풀어 바구니당 고유 상품 수를 10% 이상 감소

2022년 10월 13일8분intermediate

AI 요약

Context

QPS(Quick Picking System)에서 주문을 바구니에 담을 때 고유한 상품 수가 많으면 작업자의 처리 시간이 증가한다. 기존의 대각 행렬 정렬 알고리즘은 주문 조합 최적화에 한계가 있어 더 나은 대안이 필요했다.

최적화 목표 재정의: 회귀분석을 통해 바구니 처리 속도에 가장 영향을 미치는 변수를 '바구니 안의 고유한 상품 수'로 파악
Open shop scheduling 문제로 치환: 주문(job)을 작업자(machine)에 할당하는 과정을 조합 최적화 문제로 모델링
유전 알고리즘(Genetic Algorithm) 도입: 적합도 함수로 고유 상품 수를 최소화하는 유전자(주문 조합)를 선택하고, 교배·변이 연산자를 반복 적용
초기 세대 품질 향상: 유사한 주문들을 같은 batch에 배치하여 첫 세대부터 우월한 유전자 확보, 알고리즘 수행 시간 단축
평가 메커니즘: 각 세대에서 고유 상품 수가 작은 상위 50%만 생존시키는 선택압(selection pressure) 적용

유전 알고리즘이 기존 대각 행렬 알고리즘 대비 약 10% 이상 고유 상품 수를 감소시켰다.

NP-Hard 조합 최적화 문제는 완전해를 보장하는 대신 계산 비용을 제한하면서 근사해를 빠르게 구하는 휴리스틱 알고리즘(유전 알고리즘)으로 접근하되, 초기 상태를 도메인 지식으로 최적화하면 수렴 속도와 해의 품질을 동시에 개선할 수 있다.

실천 포인트

물류·배송 시스템에서 주문 그룹화, 배차 최적화 등 조합 문제를 다룰 때 유전 알고리즘을 적용하되, 첫 세대 생성 시 휴리스틱(예: 상품 유사도 기반 사전 정렬)을 적용하면 안정적인 수렴과 실시간 성능 요구사항을 동시에 만족시킬 수 있다.

태그