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