36-3-09 문기주, 박성미71-.pdf1.04MB

1. 서 론

 대도시에서의 차량이동에는 출퇴근시간이나 교통사고, 잘못된 도로설계, 상업지역 등과 같은 이유로 정체 시간대 혹은 정체구간들이 나타나게 된다. 이러한 정체에는 시간의 흐름이나 이동방향, 위치와 같이 규칙적인 정체가 있고, 사고와 같이 예측할 수 없는 정체가 있다. 일반적으로 VRP(vehicle routing problem)관련 연구에서는 배송지점들 간의 차량이동에 소요되는 시간은 이동방향에 관계없이 동일한 속도를 가정한 경로탐색 해법들을 개발하고 있다. 그러나 차량의 정체는 이동하는 시간대와 이동하는 방향에 따라 큰 차이를 보이고 있기 때문에 차량의 정체를 고려하지 않고 단순히 거리를 바탕으로 소요시간을 산출하여 최단시간을 탐색하는 해법을 설계하면 현실과는 동떨어진 결과를 도출하게 된다. 예를 들어 두 개의 배송지점 사이를 이동할 때 차량정체 등의 영향으로 이동방향에 따라 소요시간이 각각 다르게 나타나게 되는데, 이러한 점을 무시하고 동일한 소요시간으로 가정하고 탐색하는 배송경로 해법의 경우 도출된 결과는 현실에서는 효율적인 배송경로가 아니며 활용성도 없는 결과물이 된다.

 따라서 본 연구에서는 대도시에서의 배송의 경우 출퇴근시간이나 번화가나 주요한 상가주변으로 규칙적으로 반복하여 발생하는 정체를 반영한 배송경로 탐색해법을 설계하고자 한다. 즉 차량이동 시간대와 이동방향에 따라 각각 다른 차량의 이동속도를 가질 때 효율적인 배송경로 탐색해법을 개발하고자 한다.

 시간에 따라 달라지는 속도나 이동시간이 달라지는 TDVRP (Time Dependent Vehicle Routing Problem)문제에는 다음과 같은 연구들이 있다. 1992년에 Malandraki와 Daskin[9]은 시간 변화에 따라 두 지점 간 이동시간이 변하는 차량경로문제를 다루었고 Hill[3]은 특정시간에 고객이 위치한 지점에서 평균차량속도를 추정하는 모형을 제시하였다. 1996년에 Malandraki와 Dial[9]은 임의로 발생되는 TSP 문제에 대한 휴리스틱 해법을 제안하였다. 2001년에는 Jung과 Haghani [6]가 복수차량의 시간대 별 경로문제를 유전자 알고리즘을 사용하여 풀어냈으며 2003년에 Kenyon과 Morton[7]은 지정된 시간 전에 서비스를 완료하기 위한 확률을 극대화시키기 위해 경로 시간을 최소화하는 확률을 추정하는 모형을 제안하였고 Ichoua[4]는 FIFO으로 가중치가 주어진 지체시간과 총 경로시간을 최소화하는 병렬 타부서치 해법을 제안하였다.

 2005년에 Haghani와 Jung[2]은 유전자 알고리즘을 이용하여 복수 차량의 시간대 별 경로문제를 고려하였다. 2008년에 Donati[1]는 시간변화에 따른 각 고객 사이의 시간에 따른 최단 경로를 탐색하기 위한 Multiple Ant Colony system을 이용한 Ant Colony 메타휴리스틱을 제시하였다. 2009년에는 Jabali 등[5]이 FIFO 원칙을 만족하기 위해 실제 데이터를 기반으로 한 속도를 함수로 변환하는 경로문제를 다루었으며, Kuo 등[8]은 시간에 따른 주행 속도에 따라 최적화된 차량 할당 및 차량 경로 문제를 해결하기 위해 non-passing 타부서치 휴리스틱을 제안하였다.

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

2.1 문제의 정의

 본 연구에서 다루는 문제는 차량의 이동 시간대와  이동방향에 따라 변화하는 차량의 이동속도를 반영한 VRP이다. <Figure 1>은 본 연구에서 다루는 속도 변화의 예시이며 차량이 i에서 j방향으로 이동하면 이동거리를 D_ij라 표시하고 반대방향으로 이동하면 D_ji라고 표시한다. 두 지점 i와 j구간의 시간대에 따른 차량의 이동속도 변화를 그래프로 표시하였다. 좌측 그래프를 보면 차량의 이동속도는 같은 i에서 j구간을 이동하더라도 10시부터 10시 59분까지 이동한다면 시속 60km, 11시부터 17시 59분까지는 시속 80km, 18시부터 18시 59분까지는 시속 50km, 19시부터 19시 59분까지는 시속 30km로 다르게 적용되어야 함을 나타내고 있다. 이 그래프의 11시부터 17시 59분까지의 이동속도는 시속 80km로 i에서 j방향으로 이동하는 차량 속도이다. 그리고 우측 그래프의 같은 시간대에 차량이동속도는 시속 40km로 나타나 있는데 이것은 j에서 i방향으로 이동하는 차량의 속도를 나타낸다.

<Figure 1> Vehicle Moving Speed Examples

 이와 같은 <Figure 1>에서의 차량이동속도를 따를 때 해당구간의 차량이동시간은 <Figure 2>에 나와있다. D_ij와 D_ji의 거리는 40km로 동일하기 때문에 그래프에 표시된 이동시간들은 <Figure 1>의 그래프에 나와있는 속도를 거리에 나누어 차량이동에 소요되는 시간으로 환산한 것이다. 이 그래프들은 차량이 이동하는 시간대와 방향에 따라 차량의 속도는 다르며 또한 차량이동 소요시간이 달라짐을 보여준다. 만일 11시부터 17시 59분까지의 시간대에 i에서 j로 이동한다면 1시간이 소요되지만 j에서 i로 이동한다면 1시간 30분이 소요된다. 이러한 차량이동소요시간의 차이는 어떤 시간대에 어떤 방향으로 가는 가에 따라 총 배송시간이 달라질 수 있음을 보여주고 있다.

<Figure 2> Vehicle Moving Time Examples

2.2 수리모형

 본 연구에서는 동일한 구간이라도 이동방향에 따라 다른 즉 왕복비대칭의 차량이동 소요시간을 보이며, 또한 시간대별로 차량의 이동속도가 달라지는 TDVRP 형태의 문제를 다룬다. 또한 단일의 창고 및 단일의 배송차량 모형으로 창고를 출발하여 모든 배송지를 방문한 후 다시 창고로 돌아오는 모형이다. 이 TDVRP 모형의 목적은 배송완료 시간이 최소가 되는 경로를 구하는 것에 있다. 배송화물의 무게에 관련된 제약이나 배송에 관련된 시간적인 제약은 없다. 본 연구에서의 모형 구성에 따른 가정이다.

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

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

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

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

 (5) 차량과 창고는 각각 하나만 존재한다.

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

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

 (8) 차량이 창고로 들어오는 마지막 시간대에 해당하는 속도가 그 이후에도 지속된다.

 이상과 같이 정의한 모형과 가정에 대한 수리모형 Moon과 Park[12]에서 정의한 것과 같으며, 그 내용은 다음과 같다.

 본 연구에서 고려하는 차량의 이동방향과 시간대에 따라 바뀌는 차량의 이동속도를 고려하는 모형을 수리모형으로 완벽하게 표현하거나 풀 수 없기 때문에 다음과 같이 간략화한 수리모형으로 정의한다. 그러나 본 연구에서 다루는 모형은 특정구간의 이동속도는 이동순서가 결정되고 이동을 시작한 후 소요시간을 계산해야 알 수 있게 되는 매우 높은 난이도의 조합형최적화 문제의 한가지 형태이다. 그러므로 실제 해법은 제한된 시간 내에 유효성 높은 해를 찾을 수 있어야 하므로 휴리스틱으로 설계하여 실험하고 해법의 수행도를 평가한다.

 i : 출발배송지점
 j : 도착배송지점
 N : 전체 배송지의 수
 t_ij : 지점 i에서 j까지의 배송소요시간
 x_ij지점 i에서 j으로의 배송여부

 창고(depot)를 제외한 배송지점 수는 N이며, i는 출발지점이고 j는 도착지점이다. 그리고 0은 창고이다. 그러므로 t_ij는 i지점에서 출발하여 j지점으로 가는 차량이동과 전달시간을 포함하여 배송에 소요되는 시간이다. 목적함수와 식 (4)의 x_ij는 두 지점 i와 j사이의 차량이동 여부를 나타내는 것으로 이 구간이 선정되었으면 1, 선정되지 않았으면 0이 된다.

 식 (1)과 식 (2)는 한 지점에서 다른 지점으로 이동되는 구간은 N+1개의 가능한 선택 중 반드시 한 개씩만 선택되도록 하는 제약식이다. 식 (3)은 전체의 지점에서 다른 지점으로의 이동은 한 개씩은 반드시 선택되도록 하는 제약식이다. 조건 식 (4)는 동일지점의 이동을 방지하기 위한 제약식이다[12].

3. 왕복비대칭가변속도 VRP 해법

 시간대와 이동방향 속도변화를 반영하는 알고리즘은 다음의 순서로 이루어져 있다.

<Figure 3> Flowchart For The Suggested Heuristic

 효율적인 해법의 설계를 위해 한 대의 배송차량이 오전 10시에서 저녁 8시까지 10시간 동안 배송을 한다고 가정하였으며 Moon과 Park[11]의 차량통행속도의 분석과 재구성방법에 따라 배송시간은 10시~12시 59분, 13시~17시 59분, 18시~18시 59분, 19시~20시까지의 4개의 시간구간으로 분할하였다.

 이들 4개의 각 시간대에서 이동할 가장 좋은 구역을 선택하는 방법은 Park과 Moon[13]의 구역분할 방법에 따른다. 이 방법은 하나의 시간대에서 가장 좋은 구역을 선택할 때 다음 시간대에서 각 노드별 이동시간과 현재 시간대에서 각 노드별 이동시간의 차이의 합을 구하여 그 값이 가장 큰 것을 현재 시간대에서 이동하기에 가장 적절한 구역으로 선택한다.

 <Figure 3>의 제안 해법은 앞선 연구들의 4개의 시간구간으로 분할하는 것과 하나의 시간대에서 가장 좋은 구역을 선택방법을 적용한다. 알고리즘에서 이동방향에 따른 속도를 반영하는 방법은 창고에서 출발하는 방향의 속도로 1번 시간대의 구역을 선택하고 그 다음은 4번 시간대에서 창고로 들어올 때 가장 좋은 구역을 선택하는 것이다. 이렇게 하면 창고에서 나가는 방향의 속도와 들어오는 방향의 속도가 반영되면서 시간대에 따라 가장 좋은 구역을 선택하게 된다. 4번 시간대에서 창고로 들어올 때의 속도로 계산하여 가장 좋은 구역이 선택되었다면 그 다음은 2번 시간대에서 1번 시간대의 선택된 구역에서 나가는 방향의 속도로 계산하여 가장 좋은 구역을 선택한다. 그 다음은 마지막으로 3번 시간대에서 4번 시간대의 선택된 구역으로 들어오는 방향의 속도로 계산하여 가장 좋은 구역을 선택한다.

 <Figure 4>는 1번 시간대에서 창고로부터 나가는 방향의 속도로 각 구역 값을 계산하여 7번 구역이 선택되었음을 보여준다. 1번 시간대에 해당되는 구역은 총 3개로 <Figure 5>와 같이 구역선택 알고리즘에 의해 1번 시간대에는 2, 7, 8번의 구역이 선택되었다. 다음은 4번 시간대에서 이전에 선택된 2, 7, 8번의 구역을 제외한 나머지 구역 중 창고로 들어오는 방향의 속도로 계산하여 가장 좋은 값을 가진 구역을 선택한다. <Figure 5>의 4번째 시간대에서 선택된 구역은 6번이며, 4번째 시간대는 하나의 구역만 선택하면 되므로 6번만 선택한다.

<Figure 4> Zone Selection From Depot To Begin Delivery

<Figure 5> Zone Selection Coming Back Direction To Depot

 같은 방법으로 2, 6, 7, 8구역을 제외한 나머지 구역 중 2번 시간대에서 가장 좋은 구역을 선택하고 1번, 2번, 4번 시간대에서 선택된 구역을 제외하고 3번 시간대에서 가장 좋은 구역을 선택한다. 모든 구역이 선택되었으면 1-2-3-4시간대의 각 구역 안에서 경로를 선택하고 Moon과 Park[12]의 경로결정방법을 사용하여 각 시간대에 알맞은 구역에서의 경로로 초기해와 개선해를 생성하여 경로를 결정한다.

4. 실험 및 결과

 설계된 해법의 유효성을 입증하기 위해 크게 2가지로 나누어 실험을 수행한다. 첫 번째 실험은 이동방향에 따라 동일한 차량이동 속도를 가정한 왕복대칭해법과 이동방향에 따라 다른 차량이동 속도를 반영한 왕복비대칭해법으로 구역을 할당하고 그 결과를 비교한다. 왕복비대칭의 경우가 왕복대칭의 경우에 비교하여 구역할당에서 어떤 차이를 나타내는지 확인하는 데 목적을 둔 것이다. 두 번째 실험은 4개 시간구간과 양방향 차량통행속도를 반영한 왕복비대칭 경우의 차량경로 탐색해법을 적용하여 경로를 탐색하고, 이 경로가 12개 시간구간의 왕복비대칭 차량통행속도 문제에 대한 배송소요시간을 계산한다.

 탐색된 배송경로의 평가는 동일한 조건에서 배송경로를 탐색할 수 있도록 개발된 해법이 없으므로 타 해법들과 그 수행도를 비교 분석할 수는 없다. 따라서 제안 해법으로 탐색한 경로가 어느 정도 수준의 해인지를 평가해보는 간접적인 방법을 사용하기로 한다. 이를 위해 먼저 실행 가능한 모든 탐색경로로 구성된 모집단의 소요시간들에 대한 유추를 하기 위해 모집단을 대변하기에 충분한 개수의 배송경로를 임의로 생성하여 소요시간을 평가해 본다. 다음은 임의 생성된 배송경로들의 소요 시간치가 정규분포를 따르고 있음을 보인 후 평균값과 표준편차 값을 구하고, 제안 해법이 찾아낸 배송경로의 값이 이 통계치에서 어느 수준의 값인지를 확인하여 평가하는 방법을 사용한다.

4.1 구역할당 비교실험

 실험에 사용되는 배송지는 0.1~15km의 범위 안에서 각 배송지 사이의 거리가 무작위로 발생되며 배송지의 수는 창고를 제외하고 40개로 배송시간 10시간 내에 모두 배송할 수 있는 거리와 배송지수이다. <Figure 6>은 실험에 사용된 임의로 생성된 40개의 배송지이며 이 배송지를 Park과 Moon[13]의 시간대에 따른 속도변화를 적용한 구역분할 방법을 사용하여 분할하였으나 10시간 동안의 배송시간을 고려하여 10개의 구역분할 방법을 사용하였다.

<Figure 6> Zone Division For A Depot And Delivery Nodes

 구역할당 결과를 비교해보면 Moon과 Park[12]의 해법 즉 왕복대칭해법을 사용한 <Figure 7>의 경우에는 창고인 0노드와 1번 시간대와 4번 시간대의 구역은 떨어져 있다. 이에 비해 <Figure 8>의 왕복비대칭해법을 사용하여 이동방향별 속도를 반영한 경우는 1번 시간대는 창고노드를 포함하고 있고 4번 시간대의 구역은 창고노드와 인접하여 할당되어 있다. 이것은 각 시간대에 따라 가장 좋은 구역을 선정하되 창고노드에서 출발하고 창고노드로 도착하는 시간대를 함께 고려함으로써 마지막 시간대인 4번 시간대에서는 의미 없이 남게 되는 구역만이 할당되는 결과를 방지해준다.

<Figure 7> Zone Division For Symmetric Heuristic

<Figure 8> Zone Division For Unsymmetric Heuristic

4.2 왕복비대칭해법 경로의 배송시간 실험

4.2.1 실험의 설계 및 평가방법

 실험은 앞서 <Figure 6>에서 주어진 하나의 창고노드와 배송지노드 40개에 대해 제 3장에서 설명한 왕복비대칭해법을 이용하여 경로를 결정하고 이의 배송시간을 12개의 시간구간에 대한 이동방향에 따라 다른 차량통행속도로 구한다. 그런데 본 연구의 이동방향에 따라 다른 차량통행속도를 반영한 알고리즘의 수행도 비교를 할 수 있는 알맞은 해법이 없으므로 다음과 같은 평가 방법을 사용한다.

 먼저 임의로 경로를 설정하고 배송시간을 계산한다. 40개 배송지의 경우 40!개의 다른 경로가 있을 수 있으며 최적해는 임의로 형성된 경로 중의 하나가 될 것이다. 이 중에서 임의로 50개의 경로를 발생시켜 배송시간을 계산한 후 평균과 표준편차를 구하여 모집단 40!개를 잘 대변할 수 있는 임의경로의 개수를 계산한다. 계산된 개수만큼 임의경로를 생성하여 배송시간을 계산하고, 배송시간 값들의 집단에 대해 적합도 검정을 하여 정규분포를 따르는 것으로 인정이 되면 이 집단의 평균값과 표준편차를 사용하여 본 연구에서 제안하는 왕복비대칭해법으로 구한 경로가 모집단에서 어느 수준의 값인지를 평가하는 방법을 사용한다.

 <Table 1>의 배송시간은 4개의 시간대로 간편화한 속도와 노드간 이동방향에 따라 다른 속도를 반영한 왕복비대칭해법으로 작성한 해법에서 생성된 하나의 경로와 임의로 발생시킨 412개의 경로에 대해 간편화한 속도가 아닌 실제에 가까운 매시간마다 다른 속도와 노드간 이동방향에 따라 다른 속도로 각각의 경로에 대해 배송시간을 계산한 값이다. 임의로 생성된 경로는 412개이므로 이들 경로들에 대한 배송속도는 평균값으로 표기한다. 그리고 같은 배송지에 대해서도 4가지의 다른 위치의 창고노드로 실험함으로써 각각 다른 위치의 창고노드인 경우에도 해법의 결과가 유효한지 확인한다.

<Table 1> Experiment Design And Results

4.2.2 수행도 평가

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

 n : 자료의 크기
 z : 신뢰계수, 2사용
 σ : 표준편차
 μ : 평균
 α : 평균오차율, 0.01사용
 n =  

 실험 1부터 4까지의 각 실험에 대해서 모두 412개씩 필요한 것은 아니지만 편의상 모두 같은 개수의 임의경로를 발생시켰다.

 <Figure 9>는 실험3의 412개 임의경로가 가지는 배송시간들이 정규분포를 따른다는 것을 FlexSim의 ExpertFit을 사용하여 보여준다. <Figure 10>은 Minitab의 통계분석 그래프요약으로 실험3은 평균 667.76분, 표준편차 58.78분으로 정규분포를 따른다. <Table 2>는 각 실험당 412개씩의 임의경로들을 발생시켜 현실과 같이 매 시간 변화하며 차량이동방향에 따라 다른 속도자료로 배송시간들을 계산한 결과 값과 왕복비대칭해법으로 탐색한 결과값의 비교 분석표이다. 표에는 왕복비대칭해법으로 탐색한 해에 대한 배송시간과 40!개의 가능한 경로들이 나타낼 배송소요시간 분포를 파악하기 위해 각 실험에 대해 412개씩의 임의로 생성한 경로들에 대한 배송시간들의 평균값, 표준편차, 최소값과 최대값, Z 값이 있다. Z 값은 각 case마다 표의 제안해 배송시간 값과 412개의 임의경로 배송시간의 평균값의 차이를 표준편차 값인 Std.Dev.로 나눈 것이다.

<Figure 9> An Example Goodness Of Fit Test For Normal Distribution Using Expertfit

<Figure 10> An Example Screen Capture From Minitab For The Experiment 1 Case Random Route Delivery Time

<Table 2> Comparison Analysis Of The Results From Sug-gested Heuristic And Randomly Generated Routes

 실험 3의 412개 임의경로 배송시간과 왕복비대칭해법의 배송시간을 비교하여 보면 본 연구의 해법에서 도출된 경로의 배송시간은 361.55로 Z =-5.20으로 최상위 값에 속한다. 실험 3 이외의 모든 실험도 412개 임의경로의 배송시간은 정규분포를 따르며 해법에서 도출된 경로의 배송시간은 Z 값이 -4.9에서 -5.58 사이 값으로 40!개의 가능한 모집단 경로들 중에서 매우 짧은 배송 소요시간을 가지는 경로임을 보여주고 있다.

5. 결 론

 본 연구에서는 왕복비대칭의 이동 소요시간과 시간대별로 변화하는 차량의 이동속도를 적용한 VRP를 다루었다. 단일의 창고와 단일의 배송차량으로 제한을 한 모형으로 창고를 출발하여 모든 배송지를 방문한 후 다시 창고로 돌아오는 조건을 가지며 목적함수는 배송완료 시간의 최소화이다. 다루지 않은 복수의 배송차량 문제는 본 연구의 결과물을 활용하여 연구 개발할 계속 과제로 남겨둔다. 제안해법의 유효성을 입증하기 위해 동일 조건에서 배송경로 탐색해법이 없으므로 탐색한 경로가 가능한 경로들의 모집단에서의 수준을 평가해보는 방법을 사용하였다.

 12개의 시간구간과 40개의 배송지를 설정하고 모집단을 대변하기에 충분한 수의 임의의 경로들을 생성 평가하여 제안한 해법으로 탐색한 해와 배송에 소요되는 시간을 비교하였다. 창고의 위치를 각각 다르게 4가지로 설정한 4가지 사례에 대하여 시험한 결과 제안해법의 탐색경로는 평균 342.68분 소요에 비해 임의경로의 평균은 661.63분으로 아주 큰 차이를 보였다. 무엇보다 임의로 생성한 412가지의 경로들의 집단이 정규분포를 따르고 있으며 그 집단의 표준편차를 고려한 값을 계산해본 결과 평균 -5.19로 나타났다. 이는 제안해법으로 탐색한 경로의 소요시간은 40!개의 가능한 모집단의 경로들 중에서 이 보다 작은 값을 가지는 배송경로가 있을 확률이 0에 가까움을 나타내고 있다.

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).