0021-01-0036-0004-19.pdf609.7KB

• 1. 서 론
• 2. 문제의 정의 및 수리모형
• 3. 제안해법
• 3.1 초기구역의 분할
• 3.2 초기구역의 경로결정과 초기배송 종료시간계산
• 3.3 최종구역 결정과 최종경로 결정
• 3.3.1 공동구역 배송지 추가 방법
• 3.3.2 최종경로 결정 방법
• 3.3.3 최종경로에 대한 배송 종료시간의 결정
• 4. 실험 및 결과
• 4.1 Sweep알고리즘을 이용한 구역분할과 경로결정
• 4.2 제안해법에 의한 구역분할과 경로결정
• 4.2.1 초기구역분할과 경로결정
• 4.2.2 공동구역 배송지의 추가
• 4.2.3 임의속도에서의 최종구역분할과 경로결정
• 4.2.4 가변속도에서의 최종구역분할과 경로결정
• 5. 실험결과 분석 및 결론
• Acknowledgement

1. 서 론

정보통신의 발달과 함께 인터넷 쇼핑과 같은 새로운 유통경로의 형태는 물류배송의 양과 빈도를 높이고 있다. 또한 빠른 속도로 변화하는 다양한 고객 욕구, 짧은 제품 수명주기와 고객서비스의 중요성은 물류효율성의 중요도가 생산효율성의 중요도를 뛰어넘게 하고 있다. 본 연구는 이러한 물류 효율을 높이기 위해 개별 차량의 경로탐색과 복수 배송차량의 부하할당 문제 즉 구역분할을 다루고 있다. 그 중에서도 대도시의 배송문제를 다루고 있는데 대도시 배송의 주요 특징은 인구가 밀집되어 있어 차량이 많고 그 수에 비해 도로가 부족하다는 것이다. 도로의 부족과 인구의 밀집은 차량의 이동이 많은 번화가에서는 병목현상을 일으키고 번화가가 아닌 곳에서는 같은 시간이라도 도로가 한산하게 되는 차량편중을 일으킨다. 다시 말해 시간과 도로에 따라 다른 차량이동속도와 같은 시간과 도로라 할지라도 차량의 이동방향에 따라 다른 차량이동속도를 보인다. 이렇듯 시간에 따라 동적으로 변하는 이동속도를 고려한 연구인 TDVRP(Timedependent VRP)는 Malandraki와 Daski[7]에 의해 1992년에 소개되었다. 그리고 Haghani와 Jung[4]은 실시간으로 요구되는 서비스와 수요지 간에 다양하게 변하는 배송시간을 가지는 복수차량 문제에 대해 유전자 알고리즘을 적용하여 개선해를 도출하였고, Kuo[6]는 총 이동시간 또는 이동거리의 최소화를 위해 연비를 주요한 지표로 고려하여 차량경로 계획 시 총 연비를 계산하는 방법을 목적으로 하여 이를 SA(simulated annealing) 알고리즘으로 개선하는 방법을 제안하였다. 그리고 Donati 등[2]은 총 이동시간의 최적화를 위해 개선된 ACO(Ant Colony Optimization)를 제안하여 도심에서의 다양한 교통 조건을 동기화하여 시스템으로 구축하였다.

배송구역 분할은 CVRP(Capacitated VRP)와 HVRP(Heterogeneous fleet VRP) 연구에서 주로 다루어지고 있는데 이들 연구에서 많이 사용되는 구역분할 방법은 Gillett과 Miller[3]에 의해 제안된 Sweep알고리즘이다. Sweep알고리즘은 배송지를 좌표평면 상에 표시하고 모든 배송지의 좌표 값을 사용하여 아크탄젠트 값으로 기준 축에 대한 각도를 계산하고 그 각도를 정렬하여 시계방향 또는 반 시계 방향으로 배송지를 차량에 할당하는 구역할당방법이다. 배송지의 위치와 배송요구량 등이 알려져있을 경우 다양한 VRP에 적용시킬 수 있어 많은 연구가 이루어지고 있다. 

Sweep알고리즘을 사용한 연구들로는 Suthi-karnnarunai[13]는 차량용량 제약이 있는 CVRP에 대해 2-opt를 이용한 Sweep heuristic method를 이용하여 버스 통학 서비스의 최적경로를 결정하는 통합 프로그래밍 모델을 제시하였고, Imran 등[5]은 차량유형이 다양한 HVRP에 대해 비용적인 측면을 고려하여 2-opt를 이용한 Sweep알고리즘을 사용하여 구역할당을 한 후 각 구역의 비용 네트워크에 Dijkstra 알고리즘을 통해 초기해를 도출하고, VNS(Variable Neighborhood Search)을 적용하여 기존의 HVRP 연구들과 결과를 비교하였다. Zhishuo와 Yueting[15]은 CVRP의 개선을 위해 기존의 ACA(ant colony algorithm)를 개선한 SbMACA(Sweep based Multiple Ant Colonies Algorithm)을 제안하여 용량제약을 만족하는 수요지점의 차량할당을 통해 형성된 각 구역 내의 경로들에 대해 2-opt Sweep알고리즘으로 최적경로를 탐색하였고, Venkatesan 등[14]은 PSO(particle swarm optima-zation)를 제안하여 최소거리로 용량을 최대로 하는 차량할당이 이루어지는지를 C-W Saving 알고리즘과 비교하였다. 

구역분할의 또 다른 접근방법은 K-means clustering인데 Chunyu와 Xiaobo[12]는 분배 시스템의 개선을 위해 먼저 K-means 알고리즘을 사용하여 구역을 여러 개로 나눈 다음 전역탐색 기법인 개선된 유전자 알고리즘을 통한 경로 최적화를 제안하는 2단계 알고리즘을 제안하였다. Sergio Barreto 등[1]은 CLRP(capacitated location routing problem)에 대해 창고의 위치를 결정하는 것 뿐만 아니라 분배경로를 최적화하기 위해 용량제약 조건을 토대로 cluster 분석기반해법을 사용하여 각 클러스터를 생성한 후 최적해 알고리즘을 사용하여 경로를 정하고 이를 3-opt local 탐색법을 통해 개선하여 비용을 비교하였다. 

본 연구는 가변적인 차량이동 속도 하에서의 복수차량에 대한 배송부하 할당 그리고 그에 따른 구역분할 문제에 대한 알고리즘을 제안하고 이와 함께 가변적인 차량이동속도가 아닐 때의 본 연구에서 제안하는 복수차량 배송부하 할당 알고리즘의 결과를 비교한다. 

이후에 다루는 내용은 제 2장에서는 본 연구에서 제시하는 문제의 내용을 설명하고 제 3장은 구역분할과 경로결정에 사용된 알고리즘을 설명한다. 제 4장은 이종의 속도환경에서 제시한 알고리즘으로 실험한 내용을 설명하며 제 5장은 실험결과 분석 및 결론을 제시한다. 

2. 문제의 정의 및 수리모형

본 연구에서 다루는 복수차량 배송구역 할당 문제는 시간대와 차량의 이동방향에 따라 다른 차량이동 속도환경에서 각각의 차량이 하나의 창고를 출발하여 각 차량에 할당된 배송지를 방문한 후 다시 창고로 돌아오는 모형이다. 이 배송모형의 목적은 각 차량의 배송지가 합리적으로 할당되도록 전체 배송지를 균형 있게 분할하고 각각의 구역에서는 최적의 차량경로를 탐색하는 것이 목적이다. 이에 대한 평가는 첫 번째는 각 차량의 배송완료 시간이 유사하도록 배송구역이 분할되었는가를 확인하는 것이며, 두 번째는 차량이동속도가 변화가 없는 상황과 차량이동속도가 가변적인 상황인 두 가지 상황에서 제시된 알고리즘을 사용하여 구역분할한 결과를 비교한다. 

본 연구에서 다루는 문제는 배송화물 무게 제약이나 배송 종료시간의 제약은 없다. 다음은 본 연구에서의 모형 구성에 따른 가정이다. 이것은 Moon과 Park[10]에서 정의한 것과 같다. 임의의 두 배송지점을 i와 j라고 하면, 

(1) 창고는 하나만 존재하고, 차량은 두 대 이상 존재한다. 

(2) 각 배송지의 위치는 미리 알려져 있고 각 배송지는 하나의 차량에 의해 한 번만 방문된다. 

(3) 전체 배송지들은 차량의 대수만큼의 구역으로 나뉘어져서 분할되어 각 차량에 분할된 수만큼의 배송지들이 할당된다. 

(4) 각 차량은 창고에서 출발하여 다시 창고로 돌아온다. 

(5) 각 차량의 총 배송시간은 창고에서 출발하여 할당된 모든 배송지를 운행하고 창고로 돌아오는데 걸리는 시간이다. 

(6) 각 배송지 i에서 j까지의 차량이동속도는 시간대에 따라 달라지며 그 속도는 미리 알려져 있다. 

(7) 같은 시간대라도 임의의 배송지 i에서 j까지의 차량 이동속도와 j에서 i까지의 차량이동속도는 다를 수 있으며 그 속도는 미리 알려져 있다. 

(8) 각 배송지 i에서 j까지의 차량이동시간은 두 지점 사이의 거리를 미리 알려진 차량의 이동속도로 나누어 계산한다. 

본 연구에서 다루는 모형은 특정구간의 이동속도는 이동순서가 결정되고 이동을 시작한 후 소요시간을 계산하여 어떤 시간대에 특정 구간을 거쳐 가는지가 확정될 때에 그 구간의 속도를 알 수 있게 되는 난이도 높은 조합형최적화 문제의 한 형태이므로 그 해법은 휴리스틱으로 설계하여 실험하고 해법의 수행도를 평가한다. 관련 수리 모형은 복수대의 차량모형이기는 하나 각 단일 배송차량의 구역으로 분할되고 난 이후는 기존의 Moon과 Park[10]의 수리모형을 따르며, 그 경로결정 방법은 제 3.3.2절에서 설명한다. 

3. 제안해법

제시하는 해법은 수정 Sweep알고리즘과 Moon과 Park[10]에서 제시된 경로결정 해법을 사용하며 크게 두 단계로 나누어 볼 수 있다. 첫 번째 단계는 초기구역으로 분할하여 구역에 대한 각 차량의 초기경로를 결정하고 두 번째 단계는 첫 번째 단계에서 결정된 공동구역의 배송지를 첫 번째 단계에서 결정된 초기경로에 추가하는 것이다. 

3.1 초기구역의 분할

초기구역은 두 개의 영역으로 분할한다. 하나는 각 차량에 초기 할당할 배송지가 있는 구역이고 또 하나는 배송 종료시간의 균형을 맞출 수 있도록 하는 공동구역이다. 공동구역을 사용하는 이유는 시간과 이동방향에 따라 다른 차량이동속도 때문에 배송지의 수로 각 차량에 배송구역을 할당할 경우 배송 종료시간이 불균형을 이루기 때문에 공동구역을 이용하여 배송 종료시간의 불균형을 줄이기 위해서이다. 

다음은 구역과 공동구역으로 분할하는 초기구역의 분할 알고리즘이다. 구역과 공동구역 분할은 Sweep알고리즘을 사용하여 나눈다. 이때 창고가 전체 배송지의 가운데있고 차량의 수가 k개이면 k개의 공동구역과 k개의 구역으로 분할한다. 창고가 전체 배송지의 바깥쪽에 위치하면 k-1개의 공동구역과 k개의 구역으로 분할한다. 이 때 공동구역의 배송지 수는 전체 배송지 수의 25%이다. 

단계 1 : 창고의 위치가 전체 배송지의 바깥쪽에 존재할 경우이면 다음 2단계를 사용하고 아니면 단계 1-1로 간다. 

단계 2 : Sweep알고리즘을 사용하여 전체 배송지에서 구역 1의 배송지를 결정한다. 전체 배송지의 수가 n개이고 차량의 수가 k개일 때 구역1의 배송지의 수는 n×0.75/k이다. Sweep알고리즘의 시작의 기준 축과 배송지 포함 방향은 어느 쪽을 사용하여도 된다.

단계 3 : Sweep알고리즘을 사용하여 공동구역 1의 배송지를 결정한다. 이 때 단계 2에서 결정된 배송지 다음 배송지부터 시작하여 배송지를 결정하고 공동구역에 배정될 배송지의 수는 n×0.25/(k-1)이다. 

단계 4 : 단계 3에서 결정된 배송지 다음 배송지부터 시작하여 구역 2의 배송지를 결정한다. Sweep알고리즘을 사용하고 구역 2의 배송지의 수는 n×0.75/k이다. 

단계 5 : 공동구역의 수 k-1, 구역의 수 k개가 만족되지 않았으면 단계 3과 단계 4를 반복하여 실행하고 만족 되었으면 초기구역의 경로결정을 실행한다. 

단계 1-1 : 창고의 위치가 전체 배송지의 안쪽에 존재하는 경우이면 공동구역의 수는 k가 된다. 공동구역의 수가 변경되고 단계 3 공동구역 결정, 단계 2 구역 결정, 단계 5 공동구역 수 k, 구역의 수 k 확인과 k를 만족하지 못할 경우 단계 3, 단계 2 반복의 순서로 단계를 실행한다. 

3.2 초기구역의 경로결정과 초기배송 종료시간계산

제 3.1절 초기구역의 분할에서 구역과 공동구역의 배송지가 결정되었으면 각 구역의 초기차량경로를 결정한다. 초기 차량경로는 Moon과 Park[10]에서 제시된 경로결정 알고리즘으로 매 시간마다 이동방향에 따라 달라지는 차량이동속도를 4개 시간대의 속도구간[9]으로 간략하여 시간과 이동방향에 따라 달라지는 차량이동속도를 반영하여 최선의 차량경로를 탐색하는 휴리스틱 해법이다. 초기구역에 대한 차량경로가 결정되었으면 이에 대한 초기배송 종료시간을 계산하게 된다. 초기배송 종료시간의 계산은 한 시간 간격의 속도정보를 이용하여 계산된다. 이는 현재 매해 조사되는 대도시의 차량이동속도이므로 가장 현실적인 값이 된다. 한 시간 간격의 속도정보를 이용하여 차량경로에 대한 배송시간을 계산한다는 것은 탐색된 경로를 실시간 정보에 의해 배송 종료시간을 예측하는 것을 의미한다. 따라서 초기구역 분할에서 결정된 k개 구역에서 각 차량의 배송 종료시간이 균형을 이루었는지 불균형을 이루었는지 실제속도변화를 통해 확인한다. 그리고 k개 구역의 각 차량의 배송 종료시간은 비율로 계산한다. 

3.3 최종구역 결정과 최종경로 결정

초기구역과 초기경로 결정 그리고 초기배송 종료시간 계산에 따라 공동구역의 배송지를 각 구역으로 추가시킨다.

3.3.1 공동구역 배송지 추가 방법

공동구역의 배송지를 각 구역에 추가시키는 절차는 다음과 같다. 

단계 1 : 앞 단계의 초기구역 분할에서 결정된 경로의 배송 종료시간의 비율에 의해 구역 1, 2, …, k에 추가해야 할 배송지의 수를 결정한다. 배송 종료시간이 짧은 구역에 다음의 식을 이용해 추가해야 할 배송지의 수를 결정한다. 

T : 하나의 배송지에 배송하는 평균시간
N_i : 공동구역에서 각 구역 I로 추가해야할 배송지 수
T_max : 가장 긴 배송 종료시간
T_i : 구역i의 배송 종료시간
x_i : 구역i의 배송지 수
i : 구역 번호, 1, 2, 3, …, k
k : 분할된 구역의 갯수 

단계 2 : 배송 종료시간이 짧은 구역에 위의 식으로 추가해야 할 배송지의 수를 결정한 후 나머지 공동구역 배송지 수를 구역 수만큼 나누어서 다시 추가할 배송지의 수를 결정한다. 

단계 3 : 공동구역의 모든 배송지 중에서 구역 1, 2, …, k에 있는 배송지와 가장 짧은 거리에 있는 배송지를 탐색한다. 

단계 4 : 가장 짧은 거리의 공동구역 배송지와 구역번호를 확인하여 그 구역에 추가해야 하는 배송지의 수를 넘지 않으면 그 구역에 가장 짧은 거리의 공동구역 배송지를 추가한다. 만일 추가해야 하는 배송지의 수를 넘으면 그 구역은 제외하고 다시 단계 3으로 가서 가장 짧은 거리의 공동구역 배송지를 탐색한다. 

단계 5 : 공동구역의 모든 배송지가 각 구역에 추가되었는지 확인한다. 모두 추가되지 않았다면 단계 3로 가서 모두 추가될 때까지 반복하고 모두 추가되었으면 알고리즘을 종료한다. 이때 하나의 공동구역 배송지가 어떤 구역에 추가되었다면 단계 2로 가서 다시 남은 배송지를 추가할 때 이전에 추가된 공동구역 배송지는 결정된 구역의 배송지로 취급되어 거리계산에 포함된다. 

3.3.2 최종경로 결정 방법

최종경로 결정은 공동구역 배송지를 각 구역에 추가하면서 이루어진다. 3.3.1의 공동구역 배송지 추가 알고리즘에서 단계 2와 단계 3을 거쳐 하나의 공동구역의 배송지가 구역 1, 2, …, k 중 하나의 구역에 추가되는 것이 확정되었다면 최종경로 결정 알고리즘에 의해 공동구역 배송지가 경로에 추가되고 이때 최종경로 결정 알고리즘이 사용된다. 최종경로 결정 알고리즘은 Moon과 Park[10]에서 제시되었다. 

단계 1 : 공동구역 배송지 i와 구역의 배송지 l이 가장 짧은 거리로 탐색되었다면 i와 l은 연결한다. 이때 l은 이미 구역에서 결정된 경로가 존재하므로 l로 들어가는 배송지 k와 l에서 나가는 배송지 m이 존재한다. 즉 이전에 결정된 결로는 k-l-m의 순서이다. 그리고 새로운 배송지 i가 배송지 l과 연결되어야 한다. K는 들어오는 배송지 m은 나가는 배송지로 결정되어 있고, i-l사이에는 방향이 결정되지 않고 연결되는 것만 결정되어 있다. 

단계 2 : k와 l의 연결은 끊어지고, l과 m의 연결도 끊어지고 k는 시작, m은 종료의 방향만 남는다. i와 l은 연결된 상태이다. 이 때, k-i-l-m의 거리와 kl-i-m의 거리를 비교하여 짧은 연결을 선택한다. 

제 3.3.1절의 공동구역 배송지 추가 알고리즘과 제 3.3.2절의 최종경로 결정 알고리즘을 반복하여 모든 공동구역 배송지가 구역으로 포함되면 최종구역이 결정되고 최종경로가 결정된다. 

3.3.3 최종경로에 대한 배송 종료시간의 결정

최종구역과 최종경로가 결정되었으면 각 구역의 최종경로에 대한 배송 종료시간을 계산하고 각 구역의 배송종료시간의 비율을 확인한다. 각 배송 종료시간의 결정은 제 3.2절의 초기배송 종료시간과 같은 방법을 사용한다. 

4. 실험 및 결과

본 연구의 실험은 구역을 분할하고 각 구역의 차량경로를 결정하여 각 구역의 결정된 차량경로에 대해 배송종료시간을 계산하는 것이다. 실험에 사용된 총 배송지의 수는 80개, 차량은 두 대, 창고는 하나이며 그 위치는 전체 배송지 중앙에 위치하는 경우와 전체 배송지 바깥쪽에 위치하는 몇 가지 경우에 대하여 실험하였다. 그리고 차량이동속도는 시간에 따라 가변적이며 도로와 차량 이동방향에 대해서도 가변적인데 이와 같은 차량이동속도를 크게 두 가지로 나누어 실험하였다. 차량이동속도는 임의로 발생시킨 즉 같은 분포로 발생시킨 속도에서 실험한 것과 시간과 구간에 따라 다르게 속도를 발생시킨 경우에 대해서 실험하였다.

실험은 크게 두 단계로 이루어진다. 첫 번째는 Sweep알고리즘을 이용하여 80개의 배송지를 두 개의 구역으로 나누는 실험이다. 두 번째는 제안한 알고리즘을 이용하여 같은 배송지와 창고로 두 개의 구역으로 나누는 실험이다. 그리고 두 번째 실험은 다시 시간과 배송구간에 따라 다른 속도인 가변속도에서의 제안한 알고리즘으로 구역분할 하는 것과 균일한 분포로 임의로 발생시킨 속도에서의 제안한 알고리즘으로 구역분할 하는 두 가지로 실험한다. 창고위치와 배송지의 종류는 5가지로 <Table 1>의 실험 1-1과 실험 2-1, 실험 1-2와 실험 2-2, 실험 1-3과 실험 2-3, 실험 1-4와 실험 2-4, 실험 1-5와 실험 2-5는 같은 창고위치와 배송지위치에 대해 다른 속도정보로 실험한 것이다. 그리고 실험 1-1~실험 1-5는 각각 다른 창고위치와 다른 배송지에 대해 실험하였다. 

<Table 1> Comparisons of Required Delivery Completion Times

다음의 제 4.1절과 제 4.2절은 실험내용을 설명한 것으로<Table 1>의 실험 1-2와 실험 2-2에 대한 결과값으로 설명한다. 

4.1 Sweep알고리즘을 이용한 구역분할과 경로결정

<Figure 1>은 Sweep알고리즘으로 실험한 결과이며, 실험 1-2의 <Figure 4>와 실험 2-2의 <Figure 5>는 <Figure 1>과 같은 창고위치와 배송지 위치에서 실험된 것이다. Sweep알고리즘은 위치정보만 필요하고 속도정보는 필요하지 않은 알고리즘이므로 속도에 관한 값은 없다. <Figure 1>창고의 위치는 x = 0, y = 25로 왼쪽 상단에 위치해 있다. 

<Figure 1> Delivery Assignment by Sweep Algorithm and Delivery Routes

Sweep알고리즘을 사용하여 y축으로 시작하여 시계반대방향으로 배송지를 추가하며 두 대의 차량에 각각 40개의 배송지를 할당한다. 각각 40개의 배송지를 할당한 결과는 <Figure 1>과 같으며 이렇게 두 개의 구역으로 나눈 배송지를 Moon과 Park[10]에서 제시된 경로결정 알고리즘으로 경로를 결정한다. 결정된 1구역 경로는 0 - 58 - 49 - 68 - 24 - 11 - 72 - 12 - 9 - 60 - 66 - 25 - 27 - 18 - 23 - 31 - 8 - 80 - 75 - 50 - 67 - 38 - 7 - 36 - 52 - 4 - 30 - 14 - 3 - 29 - 59 - 5 - 6 - 34 - 78 - 10 - 45 - 64 - 54 - 16 - 20 - 0이다. 그리고 2구역 경로는 0 - 35 - 43 - 74 - 55 - 42 - 19 - 39 - 63 - 51 - 15 - 71 - 2 - 40 - 69 - 17 - 56 - 61 - 47 - 41 - 13 - 73 - 46 - 70 - 76 - 53 - 57 - 79 - 77 - 1 - 65 - 22 - 62 - 21 - 37 - 44 - 26 - 48 - 28 - 32 - 33 - 0이다. 이렇게 결정된 경로를 실험 1-2와 실험 2-2의 매 시간 변경 속도로 배송 종료시간을 계산하면 실험 1-2의 속도에서 Sweep알고리즘을 이용하여 분할한 1구역 배송 종료시간은 263.14분이고 2구역의 배송 종료시간은 252.47분으로 두 개 구역의 배송이 모두 마쳐지는 배송 종료시간은 더 늦은 배송 종료시간인 263.14분이 된다. 실험 2-2의 속도에서 Sweep알고리즘을 이용하여 분할한 1구역의 배송 종료시간은 213.96분이고 2구역의 배송 종료시간은 402.46분이고 두 개 구역의 배송 종료시간은 402.46분이 된다. 

4.2 제안해법에 의한 구역분할과 경로결정

제안해법에서 구역분할은 수정 Sweep알고리즘을 사용한 초기구역분할, 경로결정과 공동구역의 배송지를 각 구역으로 추가하여 최종구역, 최종 경로를 결정하는 두 단계로 나뉜다. 

4.2.1 초기구역분할과 경로결정

수정 Sweep알고리즘을 이용한 초기구역분할은 창고의 위치에 따라 분할되는 개수가 달라진다. 창고의 위치가 배송지의 가운데 위치하는 경우는 차량이 두 대일 경우 두 개의 구역과 두 개의 공동구역으로 나뉘며 창고의 위치가 배송지 바깥쪽에 위치하는 경우는 두 개의 구역과 하나의 공동구역으로 나뉜다. 실험 1-2과 실험 2-2의 창고의 위치는 배송지 바깥쪽에 위치함으로 y축으로부터 시작하여 구역 1, 공동구역, 구역 2의 순서로 나뉘어진다. 그리고 전체 배송지 80개의 25%는 20개이므로 20개의 배송지가 공동구역에 속하게 되어 구역 1에 30개 배송지, 공동구역에 20개 배송지 그리고 구역 2에 30개의 배송지로 각 분할된다. 분할된 구역 1과 구역 2의 배송지는 Moon과 Park[10]에서 제시된 경로결정 해법으로 경로를 결정한다. <Figure 2>는 분할된 구역 1, 공동구역 그리고 구역 2를 보여준다. 

<Figure 2> Initial Delivery Assignment with Common Area and Delivery Routes

구역 1과 구역 2의 배송지는 다시 경로결정 알고리즘에 의해 경로가 결정되는데 구역 1의 경로는 0 - 58 - 49 - 68 - 24 - 11 - 12 - 9 - 60 - 66 - 25 - 75 - 50 - 67 - 38 - 7 - 36 - 52 - 4 - 30 - 59 - 5 - 6 - 34 - 78 - 10 - 45 - 64 - 54 - 16 - 20 - 0이며 구역 2의 경로는 0 - 35 - 43 - 74 - 55 - 42 - 19 - 39 - 63 - 51 - 15 - 71 - 2 - 40 - 69 - 17 - 56 - 61 - 47 - 77 - 1 - 65 - 22 - 62 - 37 - 44 - 26 - 48 - 28 - 32 - 33 - 0이다. 그리고 실험 1-2 속도에 의한 구역 1의 배송 종료시간은 199.33분이고 구역 2의 배송 종료시간은 219.5분이다. 배송 종료시간의 비율은 0.91:1로 먼저 1구역에 추가할 공동구역 배송지의 수는 3장에서 언급한 계산식에 의해 2개이며 공동구역 배송지의 수 20개에서 2개를 뺀 18개의 배송지를 두 구역에 나누면 각각 9개씩의 배송지를 추가해야 한다. 즉 1구역에는 2+9 = 12개의 공동구역 배송지를 추가해야 하며, 2구역에는 9개의 공동구역 배송지를 추가하면 된다. 실험 2-2의 속도로 배송 종료시간을 계산하면 구역1은 157.27분이고 구역 2는 387.99분이다. 그리고 그 비율은 0.40:1이고 추가해야 할 배송지를 계산하면 구역1에 25개이다. 그런데 공동구역 배송지는 20개이므로 공동구역 배송지 20개 모두를 구역 1에 추가하면 된다. 

4.2.2 공동구역 배송지의 추가

제 4.2.1절에서 추가할 배송지의 수가 결정되었으면 공동구역 배송지를 추가한다. <Figure 3>는 <Figure 2>의 공동구역에 있는 27번 배송지와 인접한 부분을 확대한 그림이다. 

<Figure 3> Addition of Delivery Points in Common Area to the Initial Delivery Route

<Figure 3>의 첫 번째 그림에서 공동구역의 모든 배송지와 구역 1과 구역 2의 배송지의 거리를 모두 계산하여 공동구역 27번 배송지와 구역 1의 25번 배송지가 가장 짧은 거리일 경우 27번 배송지와 25번 배송지를 연결하고 Park과 Moon[11]에서 제시하였던 방법으로 25번 이전 배송지인 66번 배송지와 25번 이후 배송지인 75번 배송지를 연결한다. 연결한 후의 구역 1의 경로는 66 - 26 - 27 - 75가 된다. 27번 배송지가 구역 1에 추가된 후 공동구역 배송지는 한 개 줄고 구역 1의 배송지는 하나 늘어났다. 다시 나머지 공동구역 배송지와 구역 1과 구역 2의 배송지의 거리를 모두 비교하여 가장 짧은 거리를 비교하면 구역1의 27번 배송지와 공동구역 18번 배송지가 가장 짧은 거리이다. 다시 이들을 연결하면 25 - 27 - 18 - 75로 18번 배송지가 구역 1에 추가된다. 다시 공동구역 배송지와 각 구역의 배송지 간의 거리를 비교하여 가장 짧은 배송지를 찾아서 각 구역에 추가한다. 모든 공동구역 배송지가 각 구역에 추가되었다면 그 때의 구역분할이 최종 구역분할이 된다. 

4.2.3 임의속도에서의 최종구역분할과 경로결정

제 4.2.3절에서의 공동구역 배송지들이 각 구역에 모두 추가되었으면 최종 구역분할이 이루어진다. 그리고 이 때의 구역 1과 구역 2의 경로는 최종 경로가 된다. 그런데 제 4.2.1절에서의 초기구역분할과 경로가 결정되고 나면 공동구역 배송지중 구역 1과 구역 2에 추가되어야 할 배송지의 수가 매시간 속도에 의한 배송 종료시간 계산에 의해 결정된다. 즉 속도환경에 따라 각 구역에 추가해야 할 배송지의 수가 달라지는 것이다. 실험 1-2는 일정한 분포로 임의 발생시킨 속도에 대한 것으로 구역 1에 추가해야 할 배송지의 수는 11개, 구역 2에 추가해야 할 배송지의 수는 9개이다. 추가해야 할 배송지의 수에 알맞게 제 4.2.2절의 배송지 추가 방법으로 추가해나가면 <Figure 4>의 최종구역과 경로가 결정된다. 

<Figure 4> Final Assignments with Random Vehicle Speed Problem

최종 결정된 구역 1의 경로는 0 - 58 - 49 - 68 - 24 - 1 - 1 - 72 - 12 - 9 - 60 - 66 - 25 - 27 - 18 - 23 - 31 - 8 - 80 - 75 - 50 - 67 - 38 - 7 - 36 - 52 - 4 - 30 - 3 - 13 - 41 - 29 - 59 - 5 - 6 - 34 - 78 - 10 - 45 - 64 - 54 - 16 - 20 - 0 이고 2구역의 경로는 0 - 35 - 43 - 74 - 55 - 42 - 19 - 39 - 63 - 51 - 15 - 71 - 2 - 40 - 69 - 17 - 56 - 61 - 47 - 46 - 73 - 70 - 76 - 14 - 53 - 57 - 79 - 77 - 1 - 65 - 22 - 62 - 21 - 37 - 44 - 26 - 48 - 28 - 32 - 33 - 0이다. 이 두 구역의 배송 종료시간을 계산하면 구역 1은 277.06분, 구역 2는 261.97분이다. 즉 임의 속도에서의 최종배송 종료시간은 277.06분으로 임의속도에서 Sweep알고리즘으로 구역 분할하여 배송 종료한 시간인 263.14분보다 13.92분이 늘어났다. 임의속도에서는 Sweep알고리즘의 사용이 적절할 것으로 보인다. 

4.2.4 가변속도에서의 최종구역분할과 경로결정

제 4.2.3절과 같은 방법으로 제 4.2.1절에서 초기구역과 경로가 결정되면 시간과 구간에 따라 다른 속도가 부여된 가변속도에서 각 구역에 추가해야 할 배송지의 수를 계산하면 제 4.2.3절과 달리 구역 1에 20개의 공동구역 배송지를 모두 추가해야 한다. 

공동구역 배송지 모두를 제 4.2.2절의 방법으로 모두 추가하면 구역 1의 경로는 0 - 58 - 49 - 68 - 24 - 11 - 72 - 12 - 9 - 60 - 66 - 25 - 75 - 50 - 67 - 38 - 7 - 36 - 52 - 4 - 14 - 53 - 80 - 8 - 31 - 23 - 27 - 18 - 21 - 79 - 57 - 46 - 13 - 41 - 73 - 70 - 76 - 30 - 3 - 29 - 59 - 5 - 6 - 34 - 78 - 10 - 45 - 64 - 54 - 16 - 20 - 0이며, 구역 2의 경로는 0 - 35 - 43 - 74 - 55 - 42 - 19 - 39 - 63 - 51 - 15 - 71 - 2 - 40 - 69 - 17 - 56 - 61 - 47 - 77 - 1 - 65 - 22 - 62 - 37 - 44 - 26 - 48 - 28 - 32 - 33 - 0가 된다. 그리고 이 두 구역의 배송 종료시간을 가변속도에서 계산하면 구역 1은 278.05분, 구역 2는 387.99분으로 가변속도에서의 최종배송 종료시간은 387.99분이 된다. 이것을 Sweep알고리즘으로 구역 분할하여 배송 종료한 시간인 402.46분과 비교하면 14.47분이 줄었다. 따라서 가변속도 하에서의 제시한 알고리즘의 사용은 적합한 것으로 보인다. 

<Figure 5> Final Assignments with Various Vehicle Speed Problem

5. 실험결과 분석 및 결론

<Table 1>에서 “Sweep algorithm”은 Sweep알고리즘을 사용하여 구역분할을 하고 경로를 결정하여 주어진 속도하에서 각 구역의 배송 종료시간을 계산한 후, 그 값들 중에서 배송 종료시간이 긴 것을 표시한 것이다. “Suggested heuristic”은 제시한 알고리즘을 사용하여 구역분할하고 경로를 결정하여 주어진 속도 하에서 각 구역의 배송 종료시간을 계산하여 그 값들 중에서 배송 종료시간이 긴 것을 표시한 것이다. 속도는 임의속도와 가변속도로 나뉘고 Sweep알고리즘과 제시한 알고리즘의 최종배송 종료시간의 차이가 “Differences”에 입력되어 있다. 배송 종료시간의 단위는 분이다. 

<Table 1>의 값을 살펴보면 임의속도에서의 제시한 알고리즘은 Sweep알고리즘에 비해 일반적으로 최종 배송 종료시간이 짧다. 그러나 때로 Sweep알고리즘을 사용한 최종 배송 종료시간이 짧은 경우도 있다. 이와는 달리 가변속도에서의 제시한 알고리즘은 Sweep알고리즘을 사용한 경우에 비해 최종배송 종료시간이 항상 짧다. 즉 제시한 알고리즘은 같은 분포로 임의속도에서 보다 시간과 구간별로 다른 속도인 경우에 더 나은 성능을 보인다는 것이다. 이것은 본 연구에서 제시한 알고리즘은 시간과 구간별로 속도차이가 많이 나는 대도시의 배송에 적합한 해법이라는 것을 말해준다. 

<Table 1>의 값의 해법들간의 최종배송시간의 차이는 최대 41.43분 정도이다. 즉 제시한 알고리즘을 사용하였을 경우 Sweep알고리즘을 사용한 경우에 비해 최종배송 시간의 단축은 41.43분이라는 것이다. 이것은 크지 않은 값이나 실험의 배송지의 수가 80개이고 배송 종료시간이 최소 166.32분에서 최대 402.46분인 것을 고려하면 실제한 구역의 배송지의 수가 100개에서 120개이고 실제 한 구역의 배송시간이 600분 이상인 것으로 환산하면 최종배송 종료시간을 최대 120분 정도할 수 있다는 것을 말해준다.

추가적인 연구는 적절한 공동구역의 크기에 관한 것으로 공통구역의 크기는 배송구역별로 배송지 사이를 이동하는 차량의 속도 편차와 매우 밀접한 관계를 가지고 있기 때문에 다양한 차량속도를 적용한 문제들에 대한 실험을 통한 분석연구가 필요하겠다. 

Acknowledgement

This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology(NRF-2011-0013252).