1.서 론

과거에는 물류산업이 제조업을 지원하는 부수산업으 로만 여겨졌으나 이제는 기업의 전체 공급망을 관리하는 중요한 산업으로 여겨지고 있다. 물류산업의 총 매출액 은 2001년 약 46조 원에서 2009년 약 75조 원으로 증가 하였으며 기업의 총 매출액 대비 물류비도 계속해서 증 가하고 있다[9].

국가 물류비 추이를 살펴보면 재고유지비는 감소하고 수송비가 차지하는 비중이 지속적으로 증가하고 있다[8]. 이렇게 물류비나 물류산업의 양적 증가와 함께 물류 중 요성의 증대는 물류경쟁력이 곧 기업경쟁력이 되고 있음 을 보여주고 있다. 물류에서 많은 비중을 차지하는 육상 물류는 도로교통과 밀접한 관계를 가지고 있는데, 인구 의 지속적인 대도시권 유입으로 인해 대도시권의 도로교 통문제는 심해지고 있으며 이것은 도로혼잡비용을 증가 시키고 기업의 생산성 감소와 국가경쟁력을 저하시키고 있다.

본 연구는 기업의 생산성과 물류경쟁력을 높이고 궁 극적으로 국가경쟁력을 높이기 위해서 대도시에서의 교 통혼잡을 고려한 차량 배송경로 문제를 다루고 있다. 교 통혼잡을 고려하기 위해 본 연구에서는 시간과 도로에 따라 다른 차량통행속도를 적용하였는데 같은 도로라 할 지라도 교통혼잡이 있는 경우 시간에 따라 차량의 이동 방향에 따라 다른 차량이동속도를 나타내게 되고 이를 반영하여 차량의 경로를 결정하였다. 또한 2대 이상의 복수차량에 대한 차량경로문제를 해결하기 위한 해법을 제시하고 있으며 이를 위해 Sweep 알고리즘과 공동구역 을 사용하고 이를 통해 각 차량에 적절한 배송지를 할당 하고 있다.

복수차량의 구역할당과 교통혼잡을 고려한 해법연구를 위해 이전의 연구들을 살펴보면 시간에 따라 다른 차량통 행속도를 반영하여 차량경로를 다루는 문제는 1992년의 Malandraki and Daski[11]에 의해 TDVRP(Time Dependent VRP)의 휴리스틱 알고리즘, Ahn and Shin[1]의 savings, insertion, local improvement 알고리즘의 수정을 통한 TDVRP 고찰에 관한 연구, 시간 종속 차량 속도를 기반으로 하는 차량 스케줄링 모델에서 데이터 수집과 데이터 저장을 모 두 향상시키기 위해 시간제약이 없는 TDVRP를 고려한 Hill and Benton[6]의 연구, Malandraki and Dial[12]의 임의 로 발생되는 TSP에 대한 휴리스틱 해법, 시간 종속 모델이 시간 비종속 모델에 비해 많은 개선을 가져온다는 것을 FIFO 방식을 만족하는 상황 하에서 비교한 Ichoua et al.[7] 의 연구, 시간에 따른 주행 속도에 따라 최적화된 차량 할 당 및 차량 경로 문제를 해결하기 위해 non-passing을 제안 한 Kuo et al.[10]의 연구들이 있다.

복수차량에 의한 구역할당 문제는 Cordeau et al.[4]의 유클리드 거리를 이용한 연구, Sweep 알고리즘과 assignment approach 2가지 방법으로 structured solution의 모집단 분포를 발생시켜 얻은 구역 내의 경로들은 유전자 알고리 즘을 통해 개선한 Baker and Ayechew[2]의 연구, 50개 도시 와 5개의 창고에서 용량제약조건을 고려하여 그룹을 생성 한 후 exact 알고리즘을 사용하여 경로를 설정하고 경로개 선을 위해 3-opt local search method를 사용하여 발생하는 비용을 비교하는 Barreto et al.[3]의 연구 등이 있다.

본 연구는 시간과 차량이동방향에 따라 가변적인 차 량이동속도에서 복수대의 차량으로 배송할 경우 효율적 인 배송이 되도록 구역으로 분할하여 각 차량에 알맞은 배송구역을 할당하고 할당된 배송구역에 대해 최적 차량 경로를 결정하는 휴리스틱 해법을 제시한다.

구역으로 분할하여 각 차량에 배송구역을 할당하여 최 적 차량경로를 결정한다는 것은 전체 배송지들과 창고 그 리고 복수대의 차량이 주어졌을 때, 각각의 차량에 배송지 들을 알맞게 할당하고 창고로부터 각 차량에 할당된 배송 지를 순회하고 다시 창고로 돌아오는 경로를 결정한다는 것이다. 그런데 복수대의 차량에 배송지들을 할당하는 경 우 문제가 되는 것은 각각의 차량이 배송지들을 순회하고 배송을 마치는 각각의 배송종료시간 차이이다. 배송종료시 간의 차이가 클수록 배송이 비효율적으로 이루어졌다는 것 을 말하며 각 차량에 배송지들이 적절하게 할당되지 않았 다는 것을 의미한다. 본 연구에서는 Sweep 알고리즘을 사 용하여 구역을 분할하고 각 구역 차량 배송종료시간의 차 이가 적어지도록 공동구역을 설정, 2차 재할당하는 방법을 제시한다. 이를 위해 제 2장에서는 문제를 정의하고 제 3장 에서는 제시하는 휴리스틱 해법을 설명하고 제 4장에서는 본 연구에서 제시하는 해법의 실험결과를 보여준다.

2.문제의 정의

본 연구에서 다루는 복수차량 배송구역 할당 모형은 Park and Moon[15]에서 다룬 것과 동일한 것으로 시간대 와 차량의 이동방향에 따라 달라지는 차량이동 속도환경 에서 각각의 차량이 하나의 창고를 출발하여 각 차량에 할당된 배송지를 방문한 후 다시 원점으로 돌아오는 경 우이다. 이 모형의 목적함수는 각 차량의 배송부하를 균 형있게 할당하고, 각각의 차량들이 배송할 이동경로를 최적으로 탐색함으로써, 각 차량들의 배송종료 시점을 동일하게 하는 것이다.

본 연구에서 다루는 문제는 배송화물 무게 제약이나 배송 종료시간의 제약은 없으며 모형의 구성에 따른 가 정은 Moon and Park[14]에서 정의한 것에 ⑨가 추가되었다. 가정에서 i와 j는 임의의 두 배송지점이다.

본 연구에서 다루는 모형은 현실에서와 같이 이동순 서가 결정되고 이동을 시작한 후 소요시간을 계산하여 어떤 시간에 특정구간을 거쳐 가는지가 결정되면 그 특 정구간의 이동속도를 알 수 있게 된다. 이러한 속도결정 의 특성으로 인해 높은 난이도의 조합형최적화 문제에 해당되고 이 최적화 문제를 해결하기 위해서는 휴리스틱 해법을 사용하여 실험하고 사용한 해법의 수행도를 평가 한다.

3.해법의 설계

차량별 배송지 할당은 Park and Moon[15]에서 제시한 공동구역을 사용하여 균형을 맞추는 방법을 사용한다. 그러나 본 연구에서는 2차 재할당하는 방법이라는 차이 점이 있다. 실험의 개략적인 단계는 다음과 같다. 먼저 차량의 수가 k대이면 k개의 구역과 k-1개의 공동구역으 로 분할한다. 차량별 배송구역과 공동구역으로 분할하는 방법은 Park and Moon[15]의 방법과 같은 방법을 사용한다.

두 번째 단계는 공동구역의 배송지들을 각 구역으로 추가 할당하는 단계이다. 이 단계에서는 Park and Moon[15] 에서와는 달리 Sweep 알고리즘을 사용한 2차 재할당을 한다.

제안해법의 수행도 평가를 위해 공동구역 없이 Sweep 알고리즘을 사용하여 두 개의 구역으로 나눈 것과 본 연 구에서 제시한 공동구역을 사용한 2차 재할당 해법의 결 과를 비교 분석한다.

3.1.구역설정과 배송종료시간의 계산

3.1.1.구역설정

차량별 배송구역과 공동구역으로 분할하는 것은 Park and Moon[15]의 초기구역의 분할과 같은 방법을 사용한다. 구역분할에서의 이전 연구와 차이점은 창고의 위치가 전 체 배송지의 바깥쪽에 위치하는 경우만 다루는데 있다. 따라서 k-1개의 공동구역과 k개의 구역으로 분할되는 것 은 이전 연구와 동일하며 구역과 공동구역으로 분할하는 방법은 다음과 같다.

단계 1 : Sweep 알고리즘을 사용하여 전체 배송지에서 구역 1의 배송지를 결정한다. 전체 배송지의 수가 n개이고 차량의 수가 k개일 때 구역 1의 배송지의 수는 n×0.75/k이다.

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

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

단계 4 : 공동구역의 수 k-1, 구역의 수 k개가 만족되 지 않았으면 단계 2와 단계 3을 반복하여 실 행한다. 이 때 구역의 번호와 공동구역의 번 호는 연속으로 증가한다. 공동구역의 수 k-1,

구역의 수 k개가 만족 되었으면 3.1.2의 구역 의 초기경로 결정을 실행한다.

3.1.2.초기경로 결정과 배송종료시간 계산

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

3.2.공동구역의 2차 재할당

공동구역 배송지 할당은 Sweep 알고리즘을 사용하며 2단계의 할당을 한다. Park and Moon[15]에서의 공동구역 배송지 할당은 한 단계만을 사용하는데 본 연구에서는 두 단계의 할당 방법을 사용하여 각 구역의 편차를 보다 줄여준다. <Figure1>은 할당의 두 단계를 설명하고 있다.

단계 1 : 각 구역에 할당해야 할 배송지 수를 결정한다.

제 3.1절에서 분할된 구역과 그 구역에서 결정된 초기 경로의 초기 배송종료시간이 주어지면 공동구역으로부터 구역 1, 2, …, k에 할당해야 할 배송지의 수를 결정한다. 배송종료시간이 짧은 구역에 다음의 식을 이용해 할당해 야 할 배송지의 수 N_i를 결정한다.

T = ∑ i = 1 k T i ∑ i = 1 k X i N i = T max − T i T

위 수식에서 사용한 기호의 내용은 다음과 같다.

T : 하나의 배송지에 배송하는 평균 시간

N_i : 공동구역에서 각 구역 i로 할당해야 할 배송지 수

T_max : 구역 중 가장 긴 배송종료시간

T_i : 구역 i의 배송종료시간

x_i : 구역 i의 배송지 수

i : 구역 번호, 1, 2, 3, …, k

k : 분할된 구역의 갯수

단계 2 : 단계 1에서 계산된 N_i 만큼의 배송지를 Sweep 알고리즘을 사용하여 구역 i에 할당한다.

단계 3 : 단계 2에서 구역 i에 할당한 배송지들로 다 시 최적경로를 결정하고 결정된 경로에 의해 각 구역의 배송종료시간을 계산한다.

Park and Moon[15]의 거리알고리즘을 사용하는 경우 는 구역 i에 공동구역 배송지가 추가되면서 경로가 결정 되고 Sweep 알고리즘을 사용하는 경우는 할당될 공동구역 배송지가 결정된 후에 구역 i의 배송지들에 대해 Moon and Park[14]의 최적경로결정 알고리즘을 사용하여 구역 i 의 경로를 다시 탐색해야 한다.

사용한 알고리즘에 의해 최적경로가 결정되었으면 제 3.1.2절의 방법으로 구역 i에 대한 배송종료시간을 계산한다.

단계 4 : 재 계산된 배송종료시간에 따라 각 구역에 재 할당해야 할 배송지의 수 N^*_i를 결정한다.

N ′ i = 1 − T ′ i ∑ i = 1 k T i × y j − ∑ i = 1 k N i

N^′_i : 공동구역에서 각 구역 i로 할당해야 할 배송지 수

N_i : 첫 번째 단계에서 각 구역 i로 할당된 배송지 수

T^'_i : 구역 i의 배송종료시간

y_j : 공동구역 j의 배송지 수

i : 구역 번호, 1, 2, 3, …, k

j : 구역 번호, 1, 2, 3, …, k－1

k : 분할된 구역의 갯수

단계 5 : 단계 4에서 계산된 할당할 공동구역 배송지 수만큼 각 구역에 할당하되 Sweep 알고리즘을 사용한다. 경로결정방법과 배송종료시간 계 산방법은 단계 3과 같다.

본 연구에서 사용할 Sweep 알고리즘은 Gillett and Miller [5]에 있다. 공동구역에서 구역 i로 할당할 배송지 수가 결 정되면, 제 3.1절에서 결정된 구역 i의 가장자리의 배송지 와 공동구역의 배송지가 각도로 계산하였을 때 가장 작은 각을 이루는 공동구역의 배송지부터 Sweep 알고리즘을 이 용하여 구역 i에 차례대로 할당한다. 할당이 끝나면 경로탐 색알고리즘을 사용하여 경로를 결정하고 결정된 경로에 대 한 배송종료시간을 계산해야 한다.

Park and Moon[15]의 거리알고리즘이 본 연구에서 사 용한 Sweep 알고리즘과 다른 점은 ‘할당해야 할 배송지 수만큼 각 구역에 배송지를 할당’하고 ‘배송종료시간 계 산’을 하는 단계인데 이 단계에서 거리알고리즘은 추가해 야 할 배송지들을 초기에 분할된 구역 i의 배송지들과의 거리계산에 의해 가장 짧은 거리의 배송지 순으로 추가해 나가면서 경로를 결정한다. 이 때문에 제 3.2.1절의 Sweep 알고리즘이 가지는 경로를 재탐색하는 단계는 생략된다.

3.3.해법의 비교

본 절에서는 공동구역 없이 Sweep 알고리즘으로 구역을 분할한 경우와 공동구역이 있고 공동구역의 배송지들을 Sweep 알고리즘을 이용하여 각 구역으로 할당하여 구역 으로 분할하는 경우 중 어떤 해법이 더 좋은 해를 가지 는지 비교한다.

먼저 주어진 전체 배송지를 공동구역 없이 Sweep 알 고리즘을 사용하여 k개의 구역으로 분할한다. 그리고 제 3.1.2절의 설명에 따라 각 구역의 최적경로를 결정하고 결정된 경로에 대해 배송종료시간을 계산한다. 그 후에 각 구역간의 배송종료시간의 차이를 계산하고 이를 통해 구역간의 불균형을 파악한다.

그 다음은 제 3.1절과 제 3.2절의 내용에 따라 공동구역 배송지들을 Sweep 알고리즘을 이용한 2차 재할당 휴리스틱 해법에 따라 지정된 구역에 모두 할당하고 각 구역의 최적 경로를 탐색하여 그 경로에 대한 배송종료시간을 계산한다. 이에 따라 각 구역간 배송종료시간의 불균형을 파악한다.

마지막으로 앞서 설명한 두 가지 방법, 즉 공동구역 없는 구역분할의 결과에 의한 구역간 배송종료시간 차이 와 공동구역 있는 2차 재할당 휴리스틱 해법에 따른 구 역간 배송종료시간의 차이가 얼마나 다른지 비교 분석한다. 이 값의 비교 분석을 통해 어떤 해법이 구역간 배송종료 시간의 불균형을 완화하는데 더 나은지 확인한다.

4.제안해법의 평가

제안해법의 수행도 평가를 위한 실험은 전체 배송지의 수 80개, 창고의 수는 1개이며 창고위치는 배송지들 가운 데가 아닌 바깥쪽에 위치하며 속도는 한 시간 단위로 도 로와 차량이동방향에 따라 다른 경우에 2대의 차량으로 배송하는 경우에 대해 실험한다. 실험의 목적은 2대의 차 량에 합리적으로 배송지를 할당하고 각 차량의 최적경로 를 결정하는 것이다. 이를 위해 제 3장에서 설명한 휴리 스틱 해법을 사용하고 휴리스틱의 성능평가를 위해 공동 구역이 없이 Sweep 알고리즘을 사용하여 2대의 차량에 배송지를 할당한 경우와 배송종료시간을 비교한다.

4.1.구역설정

본 연구에서는 2대의 차량으로 실험함으로 k는 2이고, 구역의 수는 2개, 공동구역은 1개로 분할한다. 분할 방법은 창고를 중심으로 Sweep 알고리즘을 사용하여 분할한다.

구역과 공동구역에 포함될 배송지의 수는 전체 배송 지의 수가 80개이므로 c = 0.75일 때에 각 구역의 배송지 수는 각각 30개이고 공동구역의 배송지 수는 20개로 분 할된다. <Figure2>에서 분할된 구역 중 오른쪽 구역은 구역1이고 왼쪽구역은 구역 2이다. 분할된 두 개의 구역 에 대해서 각각 최초 경로를 결정하고 결정된 경로에 대 해 배송종료시간을 계산한다.

<Figure2>에서 각 구역의 배송지 수는 30개씩이므로 구역 1의 경로는 48 61 73 45 77 18 4 27 71 36 75 55 16 37 32 79 31 53 26 64 60 39 20 54 9 14 42 80 44 12 이고 배송종료시간은 164.52분이다. 구역 2의 경로는 1 70 43 57 11 7 69 51 13 41 25 58 2 33 29 76 67 8 6 15 17 30 62 38 63 46 65 3 47 78이고 배송종료시간은 236.36분이다.

4.2.공동구역과 2차 재할당

공동구역의 배송지를 구역 1과 구역 2로 할당하는 것 은 2차 재할당으로 이루어진다. 첫 번째 단계는 제 4.1절 에서 계산된 구역간 배송종료시간 차이의 비율에 의해 하나의 구역에 추가될 배송지의 수가 결정되고, 추가될 배송지 수만큼 정해진 구역에 추가하고 난 뒤 다시 최적 경로에 의해 각 구역의 배송종료시간이 계산된다. 두 번 째 단계로 첫 단계에서 계산된 각 구역간 배송종료시간 의 차이와 비율에 의해 다시 각 구역에 추가될 배송지의 수를 결정한다. 이 두 단계에서 공동구역의 배송지를 각 구역에 할당하는 방법은 제 3.2절에서 설명한 Sweep 알 고리즘을 사용한다.

구역과 공동구역 분할 후 각 구역의 최적경로를 탐색 하여 배송종료시간을 계산하면 구역 1은 164.52분, 구역 2는 236.36분으로 구역간 배송종료시간의 차이가 71.84 분으로 두 구역이 모두 배송을 종료하는 시간인 236.36 분을 기준으로 했을 때 비율은 약 0.3이다. 이 실험 값들을 제 3.2절의 첫 번째 식에 대입하면 공동구역에서 구역 1로 1차 할당해야 할 배송지의 수는 10.8로 11개가 된다. 공동 구역 배송지 중 구역 1에 할당할 11개의 배송지는 Sweep 알고리즘에 의해 결정되며 24, 10, 40, 72, 22, 68, 34, 23, 52, 50, 5이다. 이 배송지들을 구역 1에 할당하고 난 뒤 다시 Moon and Park[14]의 경로결정알고리즘에 의해 최 적경로를 탐색하면 <Figure3>의 구역 1의 경로로 표시된다.

1차 할당의 결과로 구역 1의 41개 배송지의 결정된 경 로는 <Figure3>에 표시되어 있는 것과 같이 48 24 10 40 61 73 45 77 18 4 27 72 22 68 71 36 75 55 16 37 34 23 52 50 5 32 79 31 53 26 64 60 39 20 54 9 14 42 80 44 12이고 배송종료시간은 249.09분이다. Sweep 알고리 즘을 사용한 1차 할당에서의 두 구역이 모두 배송을 종 료하는 시간은 249.09가 되고 두 구역의 배송종료시간의 차이는 12.73분이고 비율차이는 0.05이다.

이 값들을 제 3.2절의 두 번째 식에 대입하여 두 번째 단계에서 각 구역으로 할당해야 할 배송지의 수를 계산 하면 구역 1은 4개, 구역 2는 5개이다. 각 구역에 할당해야 할 배송지의 수에 알맞게 Sweep 알고리즘으로 할당하여 경로탐색 알고리즘에 의해 경로를 탐색하면 <Figure4>에 표시한 것과 같이 구역 1은 48 24 10 49 40 61 73 45 77 18 4 27 72 22 68 71 36 75 55 16 37 34 23 56 74 59 52 50 5 32 79 31 53 26 64 60 39 20 54 9 14 42 80 44 12이고 구역 2는 1 70 43 57 11 7 69 51 13 41 28 35 66 19 21 25 58 2 33 29 76 67 8 6 15 17 30 62 38 63 46 65 3 47 78의 경로로 결정된다. 이 때 구역 1의 배송종료 시간은 271.13분이고 구역 2의 배송종료시간은 265.07분 이며 두 구역간 배송종료시간의 차이는 6.06분이고 차이 의 비율은 0.02이다.

4.3.해법의 비교

본 절에서는 공동구역 없이 Sweep 알고리즘으로 구역을 분할한 경우와 공동구역이 있고 공동구역의 배송지들을 Sweep 알고리즘을 이용하여 2차 재할당하여 각 구역을 결정하는 것 중 어떤 해법이 보다 나은 성능을 보이는지를 비교 분석한다.

<Figure5>는 공동구역 없이 Sweep 알고리즘을 사용 하여 두 개의 구역으로 분할하고 경로를 결정한 결과를 보 여준다. 실험의 전체 배송지 수는 80개이므로 두 개의 구 역으로 나누면 각각의 구역에 40개의 배송지를 할당한다. 각 구역의 배송지에 대해 제 3.2절의 경로결정과 배송종 료시간계산을 하면 구역 1은 48 24 10 40 61 73 45 77 18 4 27 72 22 68 71 36 75 55 16 37 34 23 52 5 32 79 31 53 26 64 60 39 20 54 9 14 42 80 44 12의 경로를 갖 게 되고 배송종료시간은 246.86분이다. 그리고 구역 2의 경로는 1 70 43 5749 11 7 69 51 13 56 28 41 74 59 50 66 19 21 35 25 58 2 33 29 76 67 8 6 15 17 30 62 38 63 46 65 3 47 78이고 배송종료시간은 295.1분이다. 두 구역이 모두 배송을 종료하는 시간은 295.1분이고 이 두 구역간 배송종료시간의 차이는 48.24분이고 차이의 비율 은 0.16이다.

이것은 공동구역을 사용하여 분할한 결과에서의 두 구역이 모두 배송을 종료하는 시간 271.13분보다 약 24 분이 길고, 두 구역간 배송시간의 차이도 공동구역을 사 용한 것보다 약 42분 길다. 따라서 공동구역 없이 Sweep 알고리즘을 사용하여 2대의 차량에 배송지들을 할당하 는 것보다 본 연구에서 제시한 2차 재할당해법이 보다 우수하다는 것을 알 수 있다.

<Table1>은 각각 다른 배송지, 창고위치로 11번의 실 험이 제 4.1절에서 제 4.3절의 순서로 행해진 결과가 나와 있다. 실험에서 각각의 구역 1과 구역 2의 배송종료시간 중 더 긴 값이 ‘Max’에 입력되어 있고 그 단위는 분이며 생략되었다. 그리고 ‘Differences’는 두 구역의 배송종료 시간의 차이를 분단위로 표시하였다. <Table1>에서 ‘40:40’은 공동구역을 사용하지 않고 Sweep 알고리즘을 사용하여 두 구역으로 나누어 구역분할 한 실험결과이며 ‘x : y(20)’은 공동구역 배송지의 수를 20개로 하여 구역 할당을 한 것이다. ‘Average’는 각 항목의 평균값이다.

<Table1>에서 ‘40 : 40’과 ‘x : y(20)’의 ‘Max’값의 평균 을 보면 275.75분, 267.52분으로 공동구역이 20개인 경우 가 공동구역이 없는 것보다 두 구역의 배송종료시간이 짧 아서 좋다. 그리고 구역간 배송종료시간의 차이도 공동구 역을 사용한 것이 공동구역이 없는 ‘40 : 40’의 40.33분의 반으로 줄었으므로 본 연구에서 제시한 Sweep 알고리즘 을 사용한 공동구역 2차 재할당 해법이 Sweep 알고리즘으 로 구역분할을 하는 방법보다 우수하다는 것을 알 수 있다.

5.결 론

출퇴근시간대와 같이 왕복 비대칭으로 특정 구간, 특정 시간대에는 차량의 이동속도가 변하는 복수차량 배송 문제 는 전형적인 조합형최적화 문제의 하나이다. 여러 대의 차 량에 배송해야 할 물품들을 동일한 시간에 배송이 끝나도 록 배정하는 것이 주된 목적함수가 되지만 이동속도의 불 확실성이 큰 배송환경에서는 균형잡힌 부하의 할당을 찾는 것이 간단하지 않다. 이러한 문제를 해결하기 위해 본 연구 에서는 공동구역을 설정한 후 일차적인 배송경로를 탐색하 고 차이가 발생한 만큼 한쪽 차량에 배정하고 배송종료시 간을 다시 계산 후 나머지 부분을 각 차량에 분할 재배정하 는 2단계 할당방식을 적용하였다. 그 결과 해법의 비교 분 석에서 기술한 것과 같이 차량별 불균형이 보다 완화된 배송방안을 도출 할 수 있었다