1. 서 론

기업환경의 변화로 제품의 기획에서부터 생산과 배송에 이르기까지 고객만족은 기업의 목표가 되고 있다. 고객만족은 수요예측과 생산계획, 주문과 배송 등 전체 공급사슬관리를 통해 이루어지고 있는데 이러한 공급사슬에서 물류․배송은 기업의 경쟁력으로 인지되고 있으며, 비용감소를 위한 주요 대상이 되고 있다. 또한 다품종 소량생산의 경향과 온라인 쇼핑 혹은 홈쇼핑의 증가로 물류․배송의 양과 횟수는 급속히 늘어나고 있으며, 기업의 경쟁력 제고를 위해 물류 효율화의 중요성이 더 커지고 있다. 이에 따라 기업들은 물류비 절감을 위해 다양한 수배송방법을 모색하고 있고, 많은 차량경로문제(VRP : Vehicle Routing Problem) 연구들도 이들 환경에 따라 다양하게 이루어지고 있다.

지금까지 환경에 따라 다양하게 연구되어온 VRP는 다음과 같이 분류된다. 차량의 무게제약과 관련한 배송 연구는 CVRP(Capacitated Vehicle Routing Problem) [8, 6], 여러 종류의 차량과 무게제약이 다른 경우의 VRP는 HVRP(Heterogeneous fleet Vehicle Routing Problem)로 부른다. MDVRP(Multiple Depot Vehicle Routing Problem)는 창고가 두 개 이상인 VRP를 다루는 것이며, SDVRP (Split Delivery Vehicle Routing Problem)는 하나의 고객이 여러 차량들에 의해 서비스를 받는 VRP이다. VRPTW (Vehicle Routing Problem with Time Window)는 모든 고객들에게 정해진 시간 구간 내에 배송해야 하는 조건이 있는 VRP이다. VRPDT(Vehicle Routing Problem with Due Time)는 고객이 정해놓은 기간 안에 배송하는 VRP이고, 배송과 수거를 동시에 하는 경우의 문제는 VRPPD (VRP with Pickup and Delivering)이다[7]. VRSP(Vehicle Routing and Scheduling Problem)는 방문순서의 선행관계와 방문시간의 상한과 하한이 주어져 있는 경우이며[10, 2], 시간에 따라 다른 차량통행속도를 반영하여 문제는 TDVRP (Time Dependent Vehicle Routing Problem)이다[11, 5].

VRP에 제약조건이 추가된 이들 연구들은 문제의 복잡성으로 인하여 대부분 발견적 해법을 제시하고 있다. Brandao[4]는 Nearest neighbor, Nearest neighbor plus insert, Giant tour 등의 3가지 방법으로 구한 후, Tabu search에 GENIUS 삽입기법을 적용하여 해를 개선시키는 절차를 반복 수행하여 기존 예제보다 향상된 결과를 얻었다. 반면 초기해를 sweep 알고리즘으로 Giant tour를 구한 후 2-opt로 개선시켜 Dijkstra와 VNS(Variable Neighborhood Search)로 최종해를 구한 Imran 등[1]은 모두 초기해와 개선해 탐색의 두 단계를 거치는 휴리스틱을 소개하고 있다. 이들 해법들은 일차 해를 구한 후, 개선을 하는 두 단계를 거침으로써 해법의 효율성과 전체적(global) 최적해를 동시에 추구하고 있다.

본 연구에서는 대도시에서의 택배배송 차량의 최적 차량경로 탐색을 위한 해법의 개발과 평가에 대한 것을 다루고 있다. 대도시에서는 출퇴근 시간 등의 문제로 시간대에 따라 차량의 이동속도가 달라지는데, 동일한 구간일지라도 차량의 이동속도가 다르면 소요시간이 달라지게 되며 이는 시간대에 따라 구간의 계산상의 거리가 변경되는 매우 복잡한 TSP(Traveling Salesman Problem)로 귀결된다. 이 문제를 풀기 위해 먼저 구역과 시간대에 따른 속도변화를 분석하고, 속도의 변화를 보이지 않는 4가지 시간구간대로 분리한다. 다음은 각 시간구간대에서 일반적인 TSP 해법으로 해를 구하고, 각 구간대의 경로를 연결하여 전체 배송경로를 구한다. 그 후 시간구간 변경구간에 걸쳐있는 배송지들을 중심으로 순서를 변경하여 개선하는 과정을 거쳐 최종해를 구한다.

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

2.1 문제의 정의

본 연구에서는 시간의 흐름에 따라 계속해서 변화하는 속도를 반영하는 차량경로문제를 다루고 있다. 본 연구의 차량경로문제의 모형은 하나의 차량이 단일 창고(depot)에서 출발하여 N개의 배송지를 방문하고 다시 창고로 돌아오는 모형으로 배송시간을 최소로 하는 경로를 구하는 것을 목적으로 한다. 다음은 차량경로문제의 모형 구성에 따른 가정이다.

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

(2) 각 배송지의 속도는 시간에 따라 다르며 속도는 미리 알려져 있다.

(3) 같은 배송지사이의 배송시간이라도 시간의 흐름에 따른 속도변화에 따라 배송시간은 달라진다.

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

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

(6) 배송시간은 전달시간을 포함하고 있다.

2.2 수리모형

앞에서 정의한 모형과 가정에 대한 수리모형은 다음과 같다[3].

i : 출발 배송지점

j : 도착 배송지점

N : 전체 배송지의 수

tij : 지점 i에서 j까지의 배송 소요시간

xij : 지점 i에서 j으로의 배송여부

창고를 제외한 배송지점 수는 N이며, i는 출발지점이고 j는 도착지점이다. 그리고 0은 창고이다. 그러므로 tij는 i지점에서 출발하여 j지점으로 가는 차량이동과 전달시간을 포함하여 배송에 소요되는 시간이다. 목적함수와 수식 (4)의 xij는 두 지점 i와 j사이의 차량이동 여부를 나타내는 것으로 이 구간이 선정되었으면 1, 선정되지 않았으면 0이 된다. 수식 (1)과 수식 (2)는 한 지점에서 다른 지점으로 이동되는 구간은 N+1개의 가능한 선택 중 반드시 한 개씩만 선택되도록 하는 제약식이다. 수식 (3)은 전체의 지점에서 다른 지점으로의 이동은 한 개씩은 반드시 선택되도록 하는 제약식이다. 조건 (4)는 동일지점의 이동을 방지하기 위한 제약식이다.

본 연구의 배송문제는 위와 같이 간략화한 수리모형을 만들 수 있으나, 시간대에 따라 차량의 이동속도가 변경되고, 특정구간의 이동속도는 이동순서가 결정되고, 이동을 시작해야 구할 수 있으므로 휴리스틱으로 설계하여 실험 및 수행도 평가를 한다.

3. 해법의 설계

본 연구는 매일 배송품의 개수가 100개 이상인 택배 배송의 배송경로를 결정하는 휴리스틱에 관한 것으로 배송지역과 시간에 따라 속도변화가 있는 VRP를 효율적으로 해결하기 위해 초기해를 구하고 이를 개선하는 2단계 과정을 거쳐 최종해를 구한다. 초기해를 구하고 교체 등의 방법으로 개선과정을 통하여 최종해를 구하는 해법의 경우 초기해의 품질이 최종해의 품질에 미치는 영향이 크다. 좋은 초기해가 반드시 최적해에 도달하는 것은 아니나 VRP와 같은 조합형최적화 문제에서 배송지의 개수가 많은 경우 개선을 위한 교체의 회수를 크게 할 수는 없으므로, 초기해가 거의 최종해가 되기 때문에 좋은 초기해를 구하는 것은 중요해진다. 그러므로 초기해가 최대한 최적해에 근접할 수 있도록 지역과 시간에 따른 속도변화를 반영하면서 해법의 효율성을 유지할 수 있는 범위 내에서 초기해를 구한 후 차량의 이동속도를 4구간으로 단순화하면서 발생할 수 있는 편차를 최소하하기 위해 초기해로 형성된 경로상에서 시간구간대가 변경되는 경계에 있는 배송지들의 배송순서를 변경하는 방법으로 개선하여 최종해를 구한다.

초기해는 구역분할을 통해서 현재 시간구간에서 가는 것이 다음 시간구간에 가는 것보다 유리한 구역을 결정하게 된다. 이 구역을 중심으로 인접한 구역이면서 시간에 따른 속도변화의 영향을 받지 않는 시간구간에 포함될 구역들을 인접구역결정 알고리즘을 통해 결정하고 그 구역들 내에서 경로를 결정한다. 경로가 결정되면, 결정된 경로들을 모두 연결하여 전체의 배송지역과 전체 배송시간에 따른 경로를 결정한다. 이 경로가 초기해이다. 개선해는 초기해에서 결정된 경로가 지역적(local)최적해에 머무는 것을 방지하기 위해 시간구간에 따라 분할된 구역들 간의 배송지를 주어진 방법들로 교체한다. 그리고 교체된 방법 중 가장 좋은 해를 개선해로 결정한다.

3.1 초기해의 생성

3.1.1 시간구간과 구역분할

초기해 생성 절차를 간략히 설명하면 다음과 같다. 먼저 시간에 따라 속도변화가 있는 시간을 시간구간으로 나누어 사용한다. 시간구간은 Moon과 Park[3]의 4개 시간구간을 사용한다. 4개 시간구간은 10시~12시 59분(3시간), 13시~17시 59분(5시간), 18시~18시 59분(1시간), 19시~19시 59분(1시간)이다. 시간구간은 <Figure 1>과 같이 시간에 따른 속도변화를 4개로 분리된 시간구간으로 반영하면서 하나의 시간구간 안에서는 속도변화가 없는 것으로 하여 해법의 효율성을 높이면서 속도변화를 잘 반영할 수 있도록 한다. <Figure 1>에서는 임의의 속도를 부여하여 시간구간과 속도변화를 설명하는 그림인데 시간구간에 따른 속도변화를 보여주고 있다. 즉 시간구간 10시에서 12시 59분까지는 계속 40km/h로 시간구간 내에서는 속도변화가 없고 13시부터 17시 59분까지 역시 구간 내에서는 60km/h로 속도변화가 없다. 그러나 이들 구간들 사이에는 속도변화가 있는 것이다.

시간구간들 사이에는 속도변화가 있고 배송지역에 따라 속도는 다르므로 현재 시간구간에서 배송하는 것이 가장 유리한 지역부터 배송을 할 수 있도록 배송지역 전체를 구역으로 분할하고 가장 유리한 구역을 선택하는 과정이 해법에 포함되어 있다. 구역분할은 10개로 하게 되는데 이것은 Park과 Moon[9]에서 조사한 내용에 근거한 것으로 택배배송시간은 일반적으로 10시부터 8시까지의 10시간에 맞추어 10개로 구역분할을 한다. 이 구역분할은 속도변화에 따라 현재 시간구간에서 배송지로 선택하는 것이 유리하면서 현재 차량의 위치에서 가까운 배송지를 선택할 수 있도록 한다. 구역분할과 시간구간은 일반적으로 가까운 위치에 있는 배송지를 선택하여서 매 시간에 따른 속도변화를 간과하거나 모든 속도변화를 반영하여 해법의 복잡도를 높이는 문제점을 해결해주는 해법이다.

3.1.2 인접구역과 초기해의 생성

인접구역은 하나의 시간구간에서 가장 유리한 구역이 선정되면 그 구역을 중심으로 인접한 구역들 중 하나의 시간구간에서 유리한 즉 구역점수가 높은 순으로 결정된다. 하나의 시간구간에 포함될 구역의 개수는 하나의 시간구간에 포함된 시간의 수와 동일하다. 하나의 시간구간에 포함될 구역을 인접구역을 통해 생성하는 이유는 하나의 시간대 안에서는 동일한 통행속도를 적용하기 위함이다. 4개의 시간구간에 대응하는 구역들이 인접구역 알고리즘에 의해 선택되면 선택된 구역들에 포함된 노드들로 경로를 결정하면 된다. 각 시간구간 안에서는 속도의 영향을 받지 않으므로 배송지간의 거리로 경로를 결정하는데 본 연구에서는 이전 시간구간에 속한 구역의 중심점과 가장 가까운 배송지를 시작배송지로 하고 이후 시간구간에 속한 구역의 중심점과 가장 가까운 배송지를 마지막배송지로 결정한 후에 시작 배송지와 가장 가까운 배송지를 찾아서 경로를 결정한다.

3.2 개선해

개선해는 초기해의 최종구역분할 내에서 생성된 경로의 부분최적화 문제점을 개선하기 위해서 하나의 시간구간의 구역 내에서 생성된 하나의 경로가 다른 시간구간의 구역 내에서 생성된 경로와 인접하는 부분의 배송지 노드를 교체하는 방법을 사용한다.

3.2.1 구역간 경로 교체이동

하나의 시간구간의 구역에 의해 초기해의 경로가 결정되면 시간에 따른 속도변화를 고려하지 않아도 되기 때문에 해의 효율은 높일 수 있으나 지역적인 해에 빠지게 된다. 이러한 지역적 최적해 문제점을 개선하기 위해 하나의 시간구간에 속한 구역과 다음 시간구간에 속한 구역이 만나는 부분에 있는 배송지 노드를 교환하는 방법을 사용한다. 즉 하나의 시간구간의 마지막 배송지 n과 그 다음 시간 구간의 시작 배송지를 교체한다. 또 마지막 배송지의 앞 배송지 즉, n-1번째 배송지와 다음시간구간의 시작 배송지를 교체이동 한다. 이 방법은 구역분할과 시간구간에 의해 나뉘어져 있어서 배송시간을 줄여줄 수 있는 보다 가까운 배송지와의 교체를 가능하게 한다.

3.3 제안해법의 순서도

<Figure 5>는 본 연구에서 제안하는 해법의 순서도이다. 왼쪽은 초기해 생성단계이고 오른쪽은 개선하는 단계이다.

4. 실험 및 결과분석

본 연구의 실험은 무작위로 위치를 발생시킨 20개의 배송지 노드를 대상으로 하였다. 실험에 사용된 속도는 10개의 구역에 60km/h를 넘지 않는 범위에서 부여하였으며 구역 내의 배송지들은 부여된 속도를 중심으로 60%~ 140%내에서 무작위로 속도가 부여되었다. 실험은 두 가지로 설계하였는데 창고의 위치에 따른 영향을 분석하기 위한 것과 다른 하나는 10개 구역에 지정한 속도 값의 변화에 대한 영향 분석을 위한 것이다.

4.1 실험의 설계 및 결과

창고의 위치를 달리하여 한 실험과 구역별속도를 달리한 두 실험은 모두 먼저 본 연구에서 제안한 해법으로 경로를 구하였다. 제안해법에서는 해법의 탐색효율성을 위해 10개의 시간치를 4가지 시간 구간치로 변경하여 탐색하므로 구해진 경로는 다시 한 시간 간격의 속도변화 자료를 적용하여 그에 따른 배송시간을 실제 배송소요시간을 계산하였다. 그리고 각 실험과 같은 조건으로 임의로 발생시킨 408가지의 다른 배송경로들에 대해 10개 시간치에 대한 배송 소요시간을 계산하여 제시된 해법의 경로 결과치와 비교하였다.

4.1.1 창고의 위치에 따른 경로와 배송시간

창고의 위치는 <Figure 6>과 <Table 1>에 나타나 있는 것처럼 배송지들의 외곽과 가운데로 하여 실험하였다. 이때의 구역별 속도는 실험 2_1의 속도와 같이 45, 50, 40, 50, 55, 20, 60, 25, 35, 40이다. 실험 1_1의 경우 해법으로 탐색한 경로의 배송시간은 220.75이며 임의경로 408개의 배송시간의 평균은 381.09이다. 모든 경우 탐색경로가 우수함을 보이고 있다. 실험 1_2부터 1_6은 모두 창고의 위치를 달리하여 해법으로 각 경로를 도출하였고 이들 실험에 각각에 대해 408개의 임의경로를 도출하여 이들에 대한 배송시간을 계산하여 평균한 값이다. 가능경로의 모집단에 대한 탐색해의 비교 분석은 4.2에서 다룬다.

4.1.2 구역별 속도에 따른 경로와 배송시간

구역별 속도는 임의속도를 각 구역의 속도 자료로 하여 해법의 배송경로를 탐색하였다. 실험의 구역별 속도는 <Figure 7>의 번호 대로 속도를 부여한 것이다. 예를 들어 <Table 1>의 실험 2_1의 구역별 속도는 <Figure 7>의 1부터 10까지의 구역순서대로 45 50 40 50 55 20 60 25 35 40의 속도를 부여한 것이다. 각 구역에는 그 구역에 속한 노드가 있는데 이들 노드들의 속도는 이들 구역별 속도를 기준으로 60~140% 내에서 임의로 적용된다.

<Table 1>의 2_3의 실험 결과를 살펴보면 창고와 가까운 구역의 속도가 낮을수록 해법 경로의 배송시간과 무작위 경로의 평균 배송시간과의 편차가 크다. 이는 본 해법이 다음 배송지를 현재 위치와 가까운 곳을 찾기보다는 시간대에 따른 속도변화를 계산하여 다음 배송지를 선택하는 해법이기 때문이다. 이와 같이 시간대에 따라 차량의 속도에 차이가 발생하는 대도시에서 소요시간을 짧게 할 수 있는 경로를 탐색하는데 도움이 될 것으로 평가된다.

4.2 수행도 평가

정부에서 조사하여 제공하는 차량통행속도 자료와 같이 본 연구에서 설정한 1시간 간격으로 속도가 변경되는 경우에 대해 수행도 비교를 할 수 있는 타당한 해법이 없으므로 다음과 같은 평가 방법을 사용한다. 먼저 경로를 설정해야 하는 대상지에 대해 임의로 경로를 설정하고 소요시간을 평가한다. 물론 최적해는 임의로 형성된 경로중의 하나일 것이다. 20개 배송지의 경우 20!개의 다른 경로가 있을 수 있다. 이중에서 임의로 100개의 경로를 발생시켜 소요시간을 계산한 후 평균과 표준편자를 구하여 모집단 20!개를 잘 대변할 수 있는 임의경로의 개수를 구한다. 이렇게 필요한 임의경로의 개수대로 생성하여 소요시간을 계산하고, 소요시간치들의 집단에 대해 적합도 검정을 한다. 정규분포를 따르는 것으로 인정이 되면 이 집단의 평균값과 표준편차를 사용하여 본 연구에서 제안하는 해법으로 구한 최종해가 모집단에 대해 어느 수준의 값인지를 평가하는 방법을 사용한다.

수행도 평가는 본 해법의 최종해로 탐색된 경로에 대한 배송시간과 임의경로 408개에 대한 배송시간을 비교하였다. 임의경로의 수를 408개로 한 이유는 임의 생성한 100개 경로에 대한 일차실험 결과로 필요한 자료의 크기를 계산한 결과이다. 필요한 자료의 수를 계산한 식은 다음과 같다. 임의생성 경로집단의 평균 소요시간이 모집단 평균 소요시간의 ±1% 내에 포함되기를 95.4%의 신뢰도로 하기 위해 Z는 2, 는 0.01로 하였다.

: 자료의 크기

: 신뢰계수, 2 사용

: 표준편차

: 평균

: 평균오차율, 0.01 사용

실험 1_1부터 2_3까지의 각 실험에 대해서 모두 408개씩 필요한 것은 아니나 편의상 모두 같은 개수의 임의경로를 발생시켰다. 각 실험과 같은 창고와 구역별속도, 배송지간 거리, 한 시간별 배송지간 속도로 경로에 대한 배송시간을 계산하였다.

<Figure 8>은 ExpertFit 실험 2_4의 408개 임의경로가 가지는 배송시간들이 정규분포를 따른다는 것을 보여준다. <Figure 9>는 Minitab의 히스토그램으로 실험 2_4는 평균 532.92, 표준편차 47.24로 정규분포를 따른다. 실험2_4의 408개 임의경로 배송시간과 해법의 배송시간을 비교하여 보면 해법에서 도출된 경로의 배송시간은 300.49로 Z = 4.92로 최상위 값에 속한다. 실험 2_4 이외의 모든 실험도 408개 임의경로의 배송시간은 정규분포를 따르며 해법에서 도출된 경로의 배송시간은 Z값이 4.5에서 6사이 값으로 20!개의 가능한 모집단 경로들 중에서 매우 짧은 배송 소요시간을 가지는 경로임을 보여주고 있다.

<Table 2>는 각 실험사례 문제당 408개씩의 임의 경로들을 발생시켜 현실과 같이 매 시간 변화하는 속도자료에 넣어 소요되는 배송시간들을 계산한 결과값과 제안해법으로 탐색한 결과값의 비교분석 표이다. 표에는 제안한 해법으로 탐색한 최종해에 대해 배송에 소요되는 시간치의 계산값과 20!개의 가능한 경로들이 나타낼 배송소요시간 분포를 파악하기 위해 각 경우 408개씩의 임의로 생성한 경로들에 대해 평가한 배송소요시간들의 평균치, 표준편차, 최소값과 최대값이 나와 있다.

408개의 임의로 생성된 경로들이 보여주는 소요시간치의 평균과 표준편차값은 20!개 전체가 보여줄 모집단에 대한 유추를 가능하게 한다. 제안해법으로 탐색한 경로의 소요시간치는 모집단 전체로 볼 때 어느 정도 수준의 값인가를 알기 위해 Z값을 계산하여 표의 마지막에 두었다. Z값은 각 Case마다 표의 Suggested heuristic 값과 Randomly generate route의 Mean 값의 차이를 표준편차값인 Std.Dev.로 나눈 것이다. 평균 -4.971로 모집단에서도 아주 작은 값을 보이는 위치에 속하는 것이라는 것을 알 수 있다.

5. 결 론

본 연구에서의 제안한 해법은 창고와 가까운 구역의 속도가 상대적으로 낮을 때 비교적 좋은 결과 값을 보였다. 이는 시간에 따라 부분적으로 차량통행속도의 감소가 일어나고 이로 인해 정체현상이 일어나는 도로 환경에서 단순히 다음 배송지를 가까운 경로로 선택하는 것과는 달리 속도변화에 대한 예측을 하고 이를 고려하여 현재 시간구간에서 이동하는 것이 좋은 구역을 선택하여 배송시간을 단축시켜주는 경로를 찾아준다는 것을 말해준다. 그러므로 차량통행속도가 시간에 따라 변화하는 대도시에서의 배송 효율을 증대시켜 주어 배송기업에게는 물류비를 줄여주고, 배송관련 고객 서비스를 높여주며 기업의 경쟁력을 증대시켜 줄 것이다.

본 연구에서는 동일한 차량이동 속도를 보이는 시간대의 개수를 4개로 설정하였다. 그러나 분류하는 시간변화의 기준에 따라 3개구간 혹은 5개구간으로도 설정이 가능할 수 있다. 5개로 분할시 1시간구간으로 변화하는 현실의 교통자료에 가까워지므로 보다 양질의 초기해를 구할 수 있을 것이나 해법의 계산량이 증가할 것이다. 반면 3개로 하면 반대의 현상이 나타날 것이므로 추후 구역분할의 개수와 초기해, 최종해의 품질에 관한 연구가 필요하겠다.

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(2012-0004582).