> 뉴스 > 연재/기고
네트워크 시뮬레이션 기반의 수·배송 최적화
CJ대한통운이 제안하는 컨설팅을 통한 물류 혁신 사례
정창윤 박사 | news@klnews.co.kr   2017년 12월 04일 (월) 16:11:45

   
 
[택배 간선네트워크의 특징 및 엔진 구성]

CJ대한통운 택배사업은 당일고객으로부터 집화한 물품을 익일(D+1) 고객에게 배송하기 위해 ‘집화-분류-배송’(Hub&Spoke)방식을 채용하고 있다.
   
   
고객으로부터 집화한 물품은 특정 지역(In-Sub)에서 간선차량에 실어 보내면, 중앙분류센터(Central Hub)나 지역센터(Local Hub)에서 분류하여, 배송을 담당할 특정 지역(Out-Sub)에 분류된 물품을 간선차량에 실어 보낸다. 이를 간선배차라고 부르고 있다. 이러한 간선배차는 Excel 기반의 네트워크 시뮬레이션, 배차 담당자 경험에 의존한 단순 반복적인 배차업무(약 170여명)로 수행된다. 이러한 수작업에 기반 한 배차는 정확도 및 비용절감 측면에서 매우 비효율적인 구조이며, 이를 개선하기 위해 1년간 배차최적화 솔루션을 개발하였다. 배차솔루션은 다음과 같은 특징을 고려하여 개발되었다.

■ 요일 별 물량편차를 고려해야 함
월요일의 경우 주말 인터넷 쇼핑몰 물량이 한꺼번에 출고되기 때문에 물량이 가장 많으며, 일요일로 갈수록 물량이 줄어들어 월요일과 일요일의 물량 차이가 3배 이상이다.

■ Sub – Hub – Sub의 물량 흐름(Hub&Spoke)
택배 네트워크 구조는 대표적으로 Hub&Spoke와 P2P로 나눠지는데, CJ대한통운은 오래전부터 Hub&Spoke를 사용하고 있다.

■ Sub별 대분류코드로 나눠지고, Hub별 처리할 수 있는 대분류코드가 있음
Sub의 위치, 물량규모에 따라 몇 가지의 대분류로 나눠지고, 이를 이용하여 Sub/Hub 상차 시 수작업 분류하는 방식이다.

■ 상차 업무는 수작업 분류 중심으로 현장의 유연성을 최대한 확보함
상차 업무는 자동화하기 어려우며, 앞서 설명한 요일별 물량변화에 대응하기 위해서 수작업 중심으로 진행된다.

■ Sub별 물량 특성을 고려함(소형물량, 일반물량 구분)
Sub별로 물적 특성이 매우 다르다. 집화 지역의 주된 산업에 따라서 소형물량이 많거나 중대형물량이 많아질 수도 있으며, 이는 적재율과 밀접한 관계가 있다.

■ Sub집화 물량을 시간대별로 고려함
집화물량의 Sub입고시간에 따라 차량을 배차여부가 결정된다. 입고시간이 늦은 Sub의 경우 차량배정에 손해를 볼 수 있는 구조가 필요하다. 왜냐하면 집화시간이 빠를수록 Hub의 활용율이 높아지기 때문이다.

Hub&Spoke 네트워크상에서의 간선배차는 주력 차종인 11톤 간선차량의 노선과 적재물량, 일정을 결정하는 문제로 TP(Transportation Problem)를 활용하면 빠른 시간 안에 좋은 답을 얻을 수 있다. TP는 LP(Linear Programming, 선형계획법)와 마찬가지로 실수형 변수만 사용한다. 전형적인 TP모형은 LP에 속하는 모형이지만, 다른 LP와는 달리 무조건 정수해를 보장한다. 이러한 장점으로 인해 일일 4,000여대 차량을 배차하는데 걸리는 시간은 불과 5분 정도의 시간이 소요된다.

   
 
[엔진 절차]

개발된 자동배차 엔진은 다음과 같은 절차로 진행된다.

1. 예측 물량 취합
2. Sub-Hub, Hub-Hub, Hub-Sub, Sub-Sub별 이동거리/비용 산정
3. TP물량 할당
4. 차량별 일정계획 수립

먼저 예측 물량을 각 Sub별로 정리한다. 자동배차의 정확도 향상을 위해서 Sub별 물량 예측은 매우 중요하다. 현재 CJ대한통운의 물량 예측의 정확도는 98%이상으로 취합된 물량을 사용하는데 문제가 없다고 할 수 있다.
다음 프로세스로는 각 거점별 이동거리 및 비용을 산정한다. 대부분의 거점간 거리와 비용은 이미 관리하는 Data가 존재하기 때문에 그대로 사용하면 되지만, 만약 새로운 거점이 생기게 될 경우 즉각적으로 사용할 수 있는 거리산정 로직이 포함되어 있다. Sub-Sub이동거리의 경우 Multi-Pick/Drop에 사용하기 위해서 설정한다.

TP를 활용하여 각각의 Sub-Hub간 물량을 배정한다. TP는 앞서 설명한 것과 같이 빠른 속도로 전체 비용을 최소화 할 수 있는 물량 할당 결과를 보장한다. 아래 <그림3>이 TP 모형이다. i는 출발지 인덱스이며, j는 목적지 인덱스이다. c_ij는 출발지 i에서 목적지 j까지의 비용이다. 목적함수는 전체 수송비용의 최소화를 나타낸다. 첫 번째 제약은 출발지 i의 전체 물량에 대한 제약이며, 두 번째 제약은 목적지 j의 Capa.를 넘을 수 없다는 것을 의미한다.
   
 

이렇게 해서 x_ij값(각각의 Sub-Hub물량)을 결정하면 TP 절차가 마무리된다.

마지막으로 TP로 할당된 물량을 차량단위로 나누는 과정이다. <그림4>처럼 21시에 5,000Box가 집화되고, 차량별 적재량이 1,800Box라면 총 3대의 차량이 배차되게 된다. Hub-Sub간 물량 배정은 따로 TP를 활용하지 않으며, 차량별 물량 배정과정에 따라 순차적으로 진행되어 모든 배차절차를 마치게 된다.

   
 
[개발과정에서의 시사점]

배차결과를 처음 운영자에게 공유했을 때 대략적으로는 매우 훌륭하다라는 반응을 얻을 수 있었다. 하지만, Sub별 세부 배차계획을 살펴보면서 이해하기 어렵다는 의견이 대부분이었다. 문제는 현재 운영자가 주로 사용하는 노선이 TP에 의해 결정된 노선과 차이가 있었기 때문이었다. 기존의 수작업으로 진행되던 배차는 부분만을 고려하여 결과를 도출하기 때문에 전체 최적화된 TP결과는 기존 운영자들이 이해하는데 어려움이 있을 수 있다. 특히, 물량이 적은 소형 Sub의 경우 배차가 진행되지 않거나, 거리가 먼 Hub로 배차될 수 있기 때문에 이점에 대해서 실사용에 부담을 느끼는 경우가 많을 수밖에 없다. 대부분의 운영자들은 모든 Sub에 대해서 배차 형평성을 보장하면서 배차를 진행하지만, TP를 활용한 배차는 형평성보다 최소 비용이 더 중요하기 때문에 이러한 부분에서도 이질감을 느끼게 된다. TP 결과를 최대한 활용하여 배차하는데 합의하기까지 추가적인 설명과정이 더 필요할 것이라 판단된다. 앞으로 이러한 프로젝트 진행 시 운영자에게 설명하고 설득하는 과정은 매우 중요하며, 꼭 필요한 과정으로 인식할 수 있어야 할 것이다. 수작업 배차의 경우 특정 노선에 Hub간 셔틀을 활용하고 싶어 하지만, TP의 경우 셔틀은 기본적으로 전체비용을 높이기 때문에 고려되지 않는 경우가 대부분이다. 셔틀을 무조건 배정되도록 모형을 수정하게 되면 TP 모형의 해법으로는 풀 수 없게 되며, 이렇게 모형을 구성하면 빠른 시간에 해답을 얻을 수 없다. 초기에 일일 자동배차를 위해 개발된 엔진은 속도가 최우선이었기 때문에 TP 모형을 사용할 수밖에 없었다. 고정간선의 경우에도 사용자는 정말 필요해서 선 할당해둔 고정간선 노선이 TP 결과에는 비효율로 판정되어 사용되지 않는 경우도 있었다. 배차엔진은 이러한 비효율 노선을 즉각적으로 판별할 수 있게 한다. 앞으로 엔진 결과에 따라 고정간선 노선을 빈번하게 수정해야 할 수도 있지만, 결국 총비용을 절감하고, 차량 관리수준을 높일 수 있을 것으로 기대된다.

ⓒ 물류신문(http://www.klnews.co.kr) 무단전재 및 재배포금지 | 저작권문의  
정창윤 박사의 다른기사 보기
전체기사의견(0)  
 
   * 200자까지 쓰실 수 있습니다. (현재 0 byte/최대 400byte)
   * 욕설등 인신공격성 글은 삭제 합니다. [운영원칙]
전체기사의견(0)
인기기사
‘KG택배 지고, 드림 뜨고’, 신
‘택배서비스 발전방안’ 발표, 택배시
볼보트럭, 물류 패러다임 전환할 핵심
택배요금 인상 불가피, 물류업종 비중
창간 20주년 특별기획 3. Part
신문사소개기사제보광고문의불편신고개인정보취급방침이메일무단수집거부청소년보호정책
(우:04157) 서울특별시 마포구 마포대로 63-8 삼창프라자빌딩 210 (주) 물류신문사  |  대표전화 : 02-749-5445  |  팩스 : 02-749-5456
등록번호 : 서울특별시 아00052  |  등록연월일 : 2005년 9월 12일  |  발행인 : 장대용  |  편집인 : 김성우  |  청소년보호책임자 : 김성우
Copyright © 2017 물류신문. All rights reserved. Mail to news@klnews.co.kr