컬리, OR-Tools 기반 조합 최적화로 배송 권역 재배치… 소요시간 5% 절감

컬리 데이터서비스개발팀은 배송 효율을 높이기 위해 **Cluster Center(CC)**와 Transfer Center(TC), 그리고 최종 배송 권역 간의 연결을 조합 최적화(Combinatorial Optimization) 문제로 정의하고 해결책을 제시했다. 기존 행정구역이나 직선거리 기반 할당은 실제 이동 시간과 불일치하고 TC 간 물량 불균형을 초래하는 한계가 있었다.

최적화 모형 구성

문제는 Google OR-Tools의 CP-SAT와 SCIP solver를 활용해 해결했다. 목적함수는 CC에서 TC를 거쳐 권역으로 이동하는 총 소요시간의 최소화를 목표로 하며, 각 TC의 소화 가능 물량 상한선과 각 권역이 정확히 하나의 TC에 할당되어야 한다는 제약식을 포함한다. 이는 **Generalized Assignment Problem(GAP)**의 특수한 형태로, 경우의 수가 우주 원자 수보다 많아 슈퍼컴퓨터로도 풀기 어려운 NP-hard 문제지만, solver를 통해 실용적인 해를 도출한다.

데이터 보정과 현실 반영

단순 거리 계산이 아닌 실제 배송 난이도를 반영하기 위해 데이터를 보정했다. 예를 들어, 같은 물량이라도 배송 밀집도나 도로 사정에 따라 강남과 남양주의 소요시간이 다르므로, 배송 난이도를 가중치로 적용해 물량($d_j$)을 조정했다. 또한 TC별 출차 시각 이력과 회차별 물량을 고려해 예상 소요시간($t_{ij}$)을 산정하며, 특정 권역의 배송기사 여건이나 40분 이상 소요 제한 등 현장 제약사항을 모형에 추가했다.

권역 재배치와 관리

해결된 할당안에서 위치가 흩어진 권역들을 묶기 위해, TC 내 권역 간 최대 이동 거리를 최소화하는 권역 재분치 단계를 수행했다. 이는 Generalized Assignment Problem의 변형으로, 물량 수용력과 주문량을 동시에 고려한다. 최종 결과는 물류팀이 입력 데이터를 업데이트하고 최적화를 반복 실행할 수 있도록 도구화되었으며, 향후 신규 TC 후보지 검토나 권역 자체 재조정 등 의사결정 지원에 활용될 예정이다.