쿠팡 로켓배송의 실시간 물류 경로 최적화 시스템

배경

쿠팡 로켓배송은 주문 후 익일 또는 당일 배송을 약속합니다. 전국 수백 개의 물류센터에서 매일 수백만 건의 주문을 처리하며, 수만 명의 배송 기사에게 최적의 배송 경로를 실시간으로 할당해야 합니다.

도전 과제

NP-Hard 문제인 Vehicle Routing Problem(VRP)을 실시간으로 풀어야 했습니다. 교통 상황, 배송 시간 제약, 차량 적재량, 기사별 담당 구역 등 수많은 제약 조건을 고려하면서도 수 초 내에 최적 경로를 산출해야 했습니다. 또한 주문 취소나 긴급 배송 등 동적 변경에도 대응해야 했습니다.

해결 방안

메타휴리스틱 알고리즘(Large Neighborhood Search)을 기반으로 한 경로 최적화 엔진을 개발했습니다. 실시간 교통 데이터를 반영한 동적 비용 함수를 설계하고, 주문 변경 시 영향받는 경로만 부분 재최적화하는 점진적 접근법을 적용했습니다. GPU 가속으로 대규모 병렬 탐색을 수행합니다.

결과

배송 경로 최적화로 기사당 일일 배송 건수가 20% 증가했습니다. 총 주행 거리 15% 감소, 약속 시간 내 배송 성공률 99.2%를 달성했으며, 경로 산출 시간은 평균 3초 이내입니다.

핵심 인사이트

• 1.Large Neighborhood Search로 실시간 VRP 근사 해법 구현
• 2.점진적 재최적화로 동적 변경 대응 시간 최소화
• 3.실시간 교통 데이터 반영한 동적 비용 함수 설계
• 4.GPU 가속 병렬 탐색으로 대규모 문제 처리