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

컬리나 물류 업계에선 최적화 분야의 문제를 자주 풀게 됩니다. 대표적인 스타트업인 컬리에선 물류 최적화를 어떻게 푸는지 글이 나와 공유드립니다. 저도 최적화 문제를 풀었던 경험이 있어서 흥미롭게 봤고, 과정을 잘 정리해주셨네요! 2부도 있답니다 ✨️ 추천드리고 싶은 분 - 최적화 분야에 관심이 있는 분(Operation Research 등) - 유전 알고리즘에 대해 궁금하신 분 내용 퀵 요약 - 물류 센터가 돌아가는 과정 : 그룹화 - 피킹 - 분배 - 포장 - 배송 - 주문처리 과정 중 QPS(Quick Picking System)에 집중 - 실시간으로 분배하는 핵심 공정 최적화를 위한 문제 정의 - QPS 장비 : 스테이션에 바구니 도착, 작업 지시, 상품 분배, 바구니 처리 완료로 작업이 진행 - QPS 생산성 : 개별 바구니 처리 속도(Y) - 개별 처리 속도의 감소 => 전체 생산 시간의 감소 - X : 바구니 안의 총 상품 수, 바구니 안의 고유 상품 수, 바구니 진입 시점의 스테이션 내 부하, 작업자의 숙련도 등급에 따라 결과가 다른 것을 회귀분석을 통해 알 수 있었음 - 바구니 안 고유한 상품 수가 적다면 => 이동의 수가 적기 때문에 최적화를 하기로 함 최적화 방법 - Open Shop Scheduling의 문제로 치환할 수 있음 - QPS는 서로 다른 주문이 작업에게 할당되며, 총 생산 시간을 줄이기 위한 최적의 할당 시나리오를 찾음 - 해의 개수가 굉장히 많은 NP Hard 문제 - 최적해를 찾기 어려운 문제기 때문에 계산 비용을 지불해 최적에 가까운 대안을 찾는 알고리즘을 찾았고, 유전 알고리즘을 발견하고 적용 - 최적해임을 확신하기 어려운 단점이 있지만, 간편하교 효율적으로 나은 대안을 찾을 수 있음 유전 알고리즘 - 세대를 거치면서 평가하고, 도태되고, 교배, 증식, 변이하느 ㄴ과정을 거치는 알고리즘 - 문제의 다양한 해 : 유전자, 해의 집합 : 세대 - 임의 함수로 계산된 적합도 기준으로 부모 유전자를 선택해 교배, 변이를 적용 - 속도와 성능을 모두 잡아야 함 - 같은 batch 안에 유사한 주문이 담기도록 신경쓰며 첫 세대를 생성 결과 - 전체적으로 10% 이상 감소