Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.42 No.4 pp.16-22
DOI : https://doi.org/10.11627/jkise.2019.42.4.016

Pick Up and Delivery Vehicle Routing Problem Under Time Window Using Single Hub

Jiyong Kim†

Department of Systems Engineering, Korea Air Force Academy

Corresponding Author : 92liberty@gmail.com

Received 16/07/2019 Finally Revised 04/11/2019 Accepted 13/11/2019

Abstract

After Dantzig and Rasmer introduced Vehicle Routing Problem in 1959, this field has been studied with numerous approaches so far. Classical Vehicle Routing Problem can be described as a problem of multiple number of homogeneous vehicles sharing a same starting node and having their own routes to meet the needs of demand nodes. After satisfying all the needs, they go back to the starting node. In order to apply the real world problem, this problem had been developed with additional constraints and pick up & delivery model is one of them. To enhance the effectiveness of pick up & delivery, hub became a popular concept, which often helps reducing the overall cost and improving the quality of service. Lots of studies have suggested heuristic methods to realize this problem because it often becomes a NP-hard problem. However, because of this characteristic, there are not many studies solving this problem optimally. If the problem can be solved in polynomial time, optimal solution is the best option. Therefore, this study proposes a new mathematical model to solve this problem optimally, verified by a real world problem. The main improvements of this study compared to real world case are firstly, make drivers visit every nodes once except hub, secondly, make drivers visit every nodes at the right time, and thirdly, make drivers start and end their journey at their own homes.

Key Words : Hub , Routing , Travelling Salesman Problem , Vehicle

단일 허브를 이용한 시간 제약이 존재하는 수거 및 배달 차량 경로 문제

김 지 용†

공군사관학교 시스템공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

Georgia Institute of Technology

1. 서 론

각자의 개성을 존중하고 다양성을 추구하는 현대 사 회에서는 고객들의 욕구, 필요 역시 과거와는 다르게 다 양해지고 세분화되었으며 빠르게 변화한다. 넓은 범위에 서 빠르게 변화하는 고객의 수요를 만족시키기 위해 물 류의 흐름을 효율적으로 만드는 것은 곧 비용 절감으로 이어지기에 이는 물류 분야의 큰 관심사가 되었다. 최근 드론의 가치가 부상함에 따라 Amazon이 드론을 물류 분 야에 적용한 사례도 있으나, 전통적인 의미에서 물류의 수송은 차량(Vehicle)으로 이루어진다.

1959년, Dantzig and Rasmer[2]가 차량 경로 문제를 제 시한 이후 해당 분야는 많은 연구가 이루어졌다. 전통적 인 차량 경로 문제는 하나의 출발지에 동일한 차량이 여 러 대 존재하며 수요지의 입장에서 한 번씩만 방문될 수 있도록 차량의 경로를 설정하고 각 수요지의 수요를 만 족시킨 후 출발지로 돌아오는 문제이다. 전통적인 차량 경로 문제는 현실 세계의 다양한 상황을 반영하기 위해 추가적인 제약식을 가지며 발전하였고 공급지에서 물건 을 수거하고 수요지에 이를 배달하는 차량 경로 문제도 등장하였다. 공급지에서 하나의 수요지에 대해 한 대의 차량을 할당한다면 이는 가장 빠르게 수요를 만족시킬 수 있는 방법일 것이다. 그러나 이는 필연적으로 많은 비용이 필요하므로 이를 해결하기 위해 허브가 등장하 였다. 허브란 다른 노드들로부터 네트워크의 흐름이 모 이는 곳을 말하며 물류, 교통, 데이터 통신 등 다양한 many-to-many network에서 사용된다. 허브는 각각의 노 드들을 직접 연결하는 것보다 네트워크의 흐름을 특정 장소로 집중하는 것이 경제적이거나 서비스 수준을 향상 시킬 수 있을 때 사용하는데 대량의 네트워크 흐름이 집 중되기에 이를 규모의 경제라고 한다. 허브를 사용하여 규모의 경제를 실현하는 분야로는 항공, 우편/택배 시스 템, 전자 통신 시스템, 긴급 서비스 등을 예시로 들 수 있다[8].

규모의 경제를 실현하고 효율적인 시스템 구성을 위해 서는 허브의 위치가 중요한 고려 요소가 된다. 허브의 위 치를 선정하는 문제는 크게 두 가지로 나눌 수 있다. 첫째 는 p-hub median problem(pHMP)이며 허브와 허브에 할당 되는 비(非)허브 노드들은 전체 시스템의 비용을 최소화 할 수 있도록 결정된다. 둘째는 p-hub allocation problem (pHAP)로서 전체 시스템의 비용을 최소화하는 것은 같지 만 허브 노드를 사전에 알고 있다는 점에서 pHMP와 차 이를 보인다[3]. 허브 위치 문제에서 고려할 비용 구조는 이동 거리에 따른 비용, 허브 운영 비용, 물건의 수집, 교 환, 배달 비용 등이며 각각의 항목은 다른 항목간의 비교 를 위해 비용 계수를 갖는다. 전체 비용은 각각의 항목에 비용 계수를 곱한 것의 합으로 계산한다.

허브와 관련된 기존 연구로는 먼저 Nagy and Salhi[11] 의 many-to-many location routing problem을 들 수 있다. Location 중 일부는 허브의 역할을 하는 터미널이며 그 이외의 location은 차량으로 방문하는 고객의 노드이다. 그들은 한 명의 고객은 최소 한 대의 차량이 방문하도록 하였으며 한 대는 수집, 한 대는 배달 차량으로서 최대 두 번까지 한 명의 고객을 방문할 수 있게 하였다. 그들 은 이 문제를 해결하기 위해 수리 모형과 휴리스틱 방법 을 제시하였다.

Wasner and Zapfel[13]은 노드-허브, 허브-허브, 허브- 노드뿐만 아니라 허브가 아닌 노드끼리의 연결을 포함한 경로를 구하는 방법을 제시하였으며 Nagy and Salhi와는 달리 차량이 동시에 수집과 배달을 할 수 있도록 설정하 였다. 그들은 오스트리아의 우편 배달 시스템에 허브를 적용하였다. Cetiner et al.[1]도 유사하게 터키의 우편배 달 시스템에 허브를 활용하였다. 그들은 문제를 해결하 기 위해 먼저 직선거리를 활용하여 허브의 위치를 결정 한 뒤, 이를 바탕으로 경로 문제를 풀었다. 그 후, 거리를 단계적으로 수정하여 위의 두 단계를 반복하는 방법을 적용하였다. 이 연구는 복수의 허브와 복수의 차량을 이 용, 각 경로의 시작과 끝을 허브 노드로 하는 휴리스틱 알고리즘을 제시하였다.

그러나 실생활에서는 반드시 모든 차량들이 허브에서 출발하여 허브로 복귀하지는 않는다. 각각의 차량들은 서 로 다른 지점에서 경로를 시작하고 끝낼 수 있으며 각 노 드 별로 도착 시간의 제한이 있을 수 있다. 또한 같은 지 점을 여러 번 방문하는 것은 비효율적이다. 이에 본 연구 에서는 시간 제약 하에서 여러 대의 차량이 고유의 출발 지를 갖고 허브를 제외한 노드들은 나뉘어서 한 번씩만 방문하는 각자의 경로를 마친 후, 고유의 출발지로 복귀 하는 차량 경로 문제를 해결하고자 한다. Sohn and Park [12]는 허브가 3개 이상인 차량 경로 문제일 경우 고정된 p-Hub에 노드를 단일 할당하는 문제의 NP-hardness를 증 명하였다. 경로 문제는 NP-Hard이며 NP-Complete 문제이 기에 Kang and Lee[7], Cagri Koc et al.[9], Moon and Park[10] 등 많은 선행 연구들이 다양한 휴리스틱 기법을 적용하여 문제를 해결한 것을 확인할 수 있던 반면 최적 수리 모형은 많이 적용되지 않은 것을 확인할 수 있었다. Sohn and Park[12]는 허브가 3개 이상일 때의 NP-hardness 를 보임과 동시에 허브가 2개 이하일 경우 polynomial time안에 문제를 해결할 수 있음을 보였는데 본 연구는 한 개의 허브만을 다루기에 polynomial time안에 최적해 를 찾을 수 있다. 이에 휴리스틱 기법을 적용한 많은 선행 연구와는 달리 최적화 수리 모형을 제안하고자 한다.

본 논문의 구성은 다음과 같다. 먼저 제 2장에서는 본 연구에서 다루는 문제를 정의하고 이를 해결하기 위한 최적화된 수리 모형을 제시한다. 제 3장에서는 제시한 수리 모형의 타당성을 검증하기 위한 수치 실험과 그 결 과를 제시한다. 끝으로 제 4장은 요약과 결론으로 구성 된다.

2. 문제 정의 및 최적화 수리 모형

2.1 문제 정의

본 연구가 해결하고자 하는 문제는 단일 허브를 이용 한 시간 제약이 존재하는 수거 및 배달 경로 최적화 문제 이며 미국 동부의 식자재 배달 회사의 실제 데이터를 사 용하였다. 문제 상황은 다음과 같다. 어떤 임의의 지역에 는 다수의 농장과 식당이 있다. 농장은 대부분 도심 외곽 에 위치하며 식당은 대부분 시내 중심가에 위치한다. 임의 의 두 농장이 취급하는 물품은 같을 수 있으며 각 농장은 여러 식당에 물품을 납품할 수 있고, 식당 역시 여러 농 장에서 물품을 주문할 수 있다. 그런데 이로 인해 한 장 소를 여러 번 방문하게 되는 현상이 발생하게 되었다. 이는 여러 개의 식당에 납품하는 농장과 여러 개의 농장에서 주문하는 식당이 있으며 복수의 운전자가 배달하기 때문 이다. 이 현상은 농장보다는 식당에 큰 문제가 되는데 필 요한 물품들이 한 번에 도착하지 않아 식재료를 준비하 는 시간이 지연되기 때문이다. 또한 이런 비효율성으로 인해 운전자들은 종종 배달 시간을 준수하지 못하게 된 다. 약 한 달간의 데이터를 분석한 결과 두 번 이상 방문 된 식당은 18%, 시간 내에 배달을 받지 못한 식당은 31% 에 달하였다. 이에 본 연구는 두 번 이상 동일한 장소를 방문하는 비효율성을 해결하고 시간 제약을 준수하기 위 해 허브의 개념을 제시한다. 허브의 위치 선정 문제는 먼 저 허브의 위치를 결정하는 pHAP 방식을 채택하였다. 다 음으로 경로 설정의 경우 허브는 모든 운전자가 한 번씩 방문하되 그 외의 노드는 모든 운전자 중 한 명의 운전자 에 의해 한 번만 방문된다. 다음으로 Cetiner et al. [1]과 달리 각 운전자들은 경로의 시작과 끝을 허브가 아닌 각 자의 집으로 한다.

경로 설정 문제에 유용한 네트워크 최적화 모형으로는 TSP(Travelling Salesman Problem)가 있다. 그러나 일반적 인 TSP 모델은 한 명의 Salesman이 출발지를 제외한 모 든 노드들을 한 번씩만 방문한 후 출발지로 돌아가므로 본 연구가 추구하는 바와 일치하지 않는다. 또한 일반적 으로 TSP는 발생하는 전체 비용을 최소화하는 것을 목적 으로 하는 반면, 본 연구는 운전자들이 한 개의 노드를 방문할 때마다 비용을 지불하는 구조를 취하고 있다. 따 라서 해당 일자에 방문해야 하는 노드가 정해져있으므로 전체 비용은 정해져있고 이에 전체 비용을 최소화하는 것이 아닌 전체 이동 거리를 최소화하는 것을 목적으로 한다. 본 연구의 모델은 여러 명의 Salesman, 즉 운전자 들이 허브 노드는 모두 방문하되 허브를 제외한 나머지 노드들은 나뉘어서 한 번씩만 방문하는 것이며 운전자가 방문하였을 경우 1, 그렇지 않을 경우 0의 값을 갖는 이 진변수를 활용하여 최적화된 수리 모형을 제시한다. 수 리 모형에 반영되는 기본 가정 사항은 다음과 같다.

1) 배달 회사는 각 농장들이 공급 가능한 물품을 모두 알고 있다.
2) 배달 회사는 각 식당들이 필요한 물품을 모두 알고 있다.
3) 배달 회사는 물품 배달을 할 운전자들의 목록을 가지고 있고 운전자는 회사가 원할 경우 항상 일할 수 있다.
4) 배달이 시작되기 전에 각 운전자들은 자신의 일정을 알고 있다.
5) 각 운전자들은 개인 차량을 이용하여 배달한다.
6) 각 운전자들은 7:00 a.m에 개인 집에서 출발하여 배달 을 마친 후 개인 집으로 복귀한다.
7) 각 운전자들의 개인 차량은 하루에 요구되는 배달량 을 모두 적재할 수 있다.
8) 각 식당으로의 배달은 3:30 p.m까지 마쳐야 한다.

2.2 허브 위치 선정

물류 허브는 일반적으로 각각의 노드들을 1대 1로 연 결하는 대신 특정 노드로 물류의 흐름을 집중시켜 효율 성을 높이고 비용을 절감하는 역할을 한다. 본 연구에서 의 허브는 각 운전자들이 농장에서 가져온 물품들 중 자 신의 배달 스케쥴에 해당하지 않는 물품들을 다른 운전 자에게 인계하고, 다른 운전자가 자신의 배달 스케쥴에 해당하는 물품들을 가져왔을 경우 그를 인수하는 교환의 장소로 운영한다. 모든 농장과 식당을 허브의 후보지로 고려하였고 제 2.1절에서 제시한 것과 같이 대부분의 식 당은 시내 중심가에 위치하여 식당 간 거리가 멀지 않기 에 허브를 두 개 이상 운영하는 것은 비효율적이라고 판 단하였다. 따라서 허브는 모든 농장과 식당 중 한 곳만을 선정하였다.

모든 농장과 식당을 대상으로 허브의 위치를 결정한 첫 번째 조건은 일정 기간 동안 많이 방문된, 즉 농장의 경우 물품을 많이 판매한, 식당의 경우 물품을 많이 구매 한 곳을 고려하였다. 이는 그 동안 많은 운전자들이 해당 장소를 중복하여 방문했을 가능성이 높을 것이라 판단하 였기 때문이다. 그 결과 다른 장소들에 비해 20~30배 가 량 많은 방문 수를 기록한 식당을 두 곳 찾을 수 있었다.

두 번째 조건은 접근성이었다. 일반적으로 접근성이란 임의의 장소에 접근하기 용이한 것을 의미한다. 그러나 허브의 위치가 도심에 너무 가까우면 교통이 복잡하여 여러 차량이 통행하기 어려울 것이라 판단하였고, 허브 의 위치가 도심에서 너무 멀면 이동 거리가 증가하여 Time Window를 만족하기 어려울 것이라 판단하였다. 이 에 따라 먼저 허브의 위치를 원형으로 도심으로부터 10 ~20km 떨어진 곳으로 설정하였으며 교통이 편리할 수 있도록 고속도로로부터 1.5km 안쪽의 농장과 식당을 선 정하였다. 그 결과 총 48개의 농장, 148개의 식당의 허브 후보군을 6개의 농장, 13개의 식당으로 줄일 수 있었으 며 13개의 식당에는 첫 번째 조건을 동시에 만족하는 식 당이 한 개 포함되어 있었다.

위의 두 가지 조건과 허브로서 역할을 수행하기 위 해 충분한 공간을 제공할 수 있는 장소를 파악하여 첫 번째 조건에 해당하는 식당 두 곳, 두 번째 조건에 해당 하는 식당 두 곳을 허브의 후보지로 결정하였다.

2.3 최적화 수리 모형

최적화 수리 모형은 식 (1)부터 식 (16)까지의 Mixed Integer Programming으로 제시한다. 제약식 중 일부는 Hwang and Kim[5], Jin and Kim[6]을 참고하였으며 표기와 결정 변수는 다음과 같다.

<표 기>

N : 전체 노드의 집합
F : 전체 농장의 집합
FH : 전체 농장과 운전자들의 집의 집합
Hub : 허브의 집합
R : 전체 레스토랑의 집합
D : 운전자들의 집합
S^k : 운전자 k의 Subtour의 집합

<결정 변수>

$x_{i j k} = {\begin{array}{l} 1 & 운전자 k 가노드 i 에서 j 로이동하는경우 \\ 0 & o t h e r w i s e \end{array}$
t_jk : 운전자 k가 노드 j에 도착하는 시간

min \sum_{k \in D} \sum_{i \in N} \sum_{j \in N} d_{i j} \cdot x_{i j k}

(1)

s . t . \sum_{k \in D} \sum_{i \in N} x_{i j k} \geq 1, \forall j \in N

(2)

\sum_{k \in D} \sum_{j \in N} x_{i j k} \geq 1, \forall i \in N

(3)

\sum_{i \in N} x_{i p k} - \sum_{j \in N} x_{p j k} = 0, \forall p \in N, \forall k \in D

(4)

\sum_{k \in D} \sum_{i \in F H} x_{i j k} = 1, \forall j \in F

(5)

\sum_{k \in D} \sum_{i \in N} x_{i j k} = 1, \forall i \in F

(6)

\sum_{i \in F} x_{i j k} = 1, \forall k \in D, \forall j \in H u b

(7)

\sum_{j \in N} x_{i j k} = 1, \forall k \in D, \forall j \in H u b

(8)

\sum_{k \in D} \sum_{j \in N} x_{i j k} = 1, \forall i \in R

(9)

\sum_{k \in D} \sum_{i \in N} x_{i j k} = 1, \forall j \in R

(10)

\sum_{j \in F} x_{hom e [k] j k} = 1, \forall k \in D

(11)

\sum_{i \in S^{k}} \sum_{j \in S^{k}} x_{i j k} \leq | S^{k} | - 1, \forall k \in D

(12)

\sum_{i \in N} a_{j} \cdot x_{i j k} \leq t_{j k}, \forall k \in D, \forall j \in N

(13)

\sum_{i \in N} b_{j} \cdot x_{i j k} \geq t_{j k}, \forall k \in D, \forall j \in N

(14)

| t_{j k} - t_{j p} | \leq 0.5 \forall k, p \in D, \forall j \in H u b

(15)

\begin{array}{l} t_{i k} + (\frac{d_{i j}}{υ_{k}} + i d l e_{k}) \cdot x_{i j k} - M (1 - x_{i j k}) \leq t_{j k} \\ \forall k \in D, \forall i, j \in N \end{array}

(16)

수리 모형의 목적함수 식 (1)은 전체 거리를 최소화하 는 것이며 거리 정보는 Google Map[4]을 활용하였다. 식 (2)는 모든 노드들이 1회 이상씩 방문될 수 있음을 뜻하 고 식 (3)은 모든 노드에서 다른 노드로 출발할 수 있는 횟수가 1회 이상임을 의미한다. 일반적인 TSP 모델에서 는 위의 식이 등호로 성립하나 본 연구의 경우 허브는 모든 운전자들이 방문하여야 함으로 부등호로 성립한다. 식 (4)는 경로의 연속성을 위한 제약식으로 임의의 노드 i에서 노드 p로 이동하였을 경우, 노드 p에서 임의의 노 드 j로 이동한다는 것을 의미한다. 식 (5)는 모든 농장들 이 한 번만 방문 가능하다는 것을 나타내고 식 (6)은 모 든 농장에서 다른 장소로 갈 수 있는 것이 한 번으로 제 한되는 것을 의미한다. 식 (7)은 모든 운전자들이 자신 이 방문해야 할 농장들을 모두 방문한 뒤 허브로 이동 하는 것을 나타내고, 식 (8)은 모든 운전자들이 허브에 서 다른 장소로 이동하는 것을 나타낸다. 식 (9)는 모든 식당에서 다른 장소로 이동하는 것은 한 번으로 제한되 며 식 (10)은 모든 식당들이 한 번만 방문 가능하다는 것을 의미한다. 식 (11)은 모든 운전자들이 자신의 집에 서 출발하는 것을 의미한다. 식 (12)는 모든 운전자들이 자신이 방문해야 할 노드들에 대한 Subtour-Elimination 제약식이다. 식 (13), (14)는 모든 운전자들이 각각의 노 드에 방문 가능한 시간대가 있다는 것을 의미한다. 식 (15)는 모든 운전자들이 허브에 도착하는 시간의 최대 편차가 30분으로 제한되는 것을 의미한다. 이는 임의의 운전자가 너무 오랜 시간동안 다른 운전자들을 기다리 는 것을 방지하기 위함이다. 식 (16)은 현재 노드에서 다음 노드로 이동 시 다음 노드의 도착 시간은 현재 노 드에 도착한 시간으로부터 다음 노드로의 이동 시간과 물품을 인수, 인계하는 시간을 더한 시간 이후에 도착이 가능하다는 것을 의미한다. idle_k는 물품을 인수, 인계하 는 시간을 의미하며 M은 Big M method를 적용하기 위 한 임의의 큰 수이다.

3. 수치 실험 및 분석

3.1 경로 분석

본 장에서는 제 2장에 제시한 최적화 수리 모형을 검 증하고 모형의 타당성을 검증하기 위해 수행한 수치 실 험 결과를 제시한다. 실험 예제는 배달 종료 시간이 3:30 p.m보다 늦었던 날을 선택하였으며 실험 예제의 최적해 는 Python-Gurobi를 활용하였다.

<Table 1>은 각 식당 별로 필요한 물품을 거래하는 농 장을 연결한 것이다. 각 식당은 여러 개의 농장으로부터 필요한 물품을 거래할 수 있다. 예를 들어 식당 a는 농장 A, B, I로부터 필요한 물품을 거래하며 이때 한 개, 또는 두 개의 농장으로부터 필요한 물품을 모두 공급받을 수 는 없다. 즉, 식당 a는 필요한 물품을 공급받기 위해서는 세 개의 농장 모두가 필요하다. 또한 한 개의 농장은 여 러 개의 식당에 물품을 공급할 수 있다. 예를 들어 농장 I는 식당 a, m, n, o에 물품을 제공한다.

<Table 2>는 제 2.3절의 수리 모형을 적용한 결과이며 <Table 3>은 수리 모형을 적용하기 전의 결과이다. Travel Distance는 각 운전자의 집에서 출발하여 수거와 배달을 마친 후 집으로 도착할 때까지 소요 거리를 의미하며 End Time of Delivery는 경로를 마치고 집에 도착한 시간이 아 닌, 식당에 배달을 마친 시간을 의미한다. 반면 Required Time은 집으로 복귀하는 시간까지 포함한다. H1~H5는 각 운전자들의 집을 나타낸다. 허브 노드는 가장 방문이 많았 던 f지점으로 선택하였는데 이는 도로에 대한 접근성이 좋 은 타 허브 후보지와 비교를 하기 위함이다. 실험 결과 허 브를 제외한 모든 노드들은 운전자들이 나뉘어서 한 번씩 방문하였으며 허브 노드인 f는 모든 운전자들이 방문하였 다. 모든 운전자들은 자신에게 할당된 농장들을 모두 방문 한 뒤 허브로 이동하였으며 허브에서 물품을 교환한 후 자신에게 할당된 식당들을 방문하였다. Arrival Time at Hub는 11:30 a.m부터 12:00 p.m으로 최대 편차는 30분이며 가장 늦은 식당 방문 시간은 3:13 p.m으로 이는 수리 모형 에 반영된 기본 가정 사항의 Time Window를 모두 만족하 고 있다는 것을 확인할 수 있다. Raw Data와 비교한 결과 Total Travel Distance는 약 1200 km, Total Required Time은 약 8시간이 줄었다는 것을 확인할 수 있다. 이때 Optimal Solution의 경우, 다른 운전자들이 허브에 도착하는 시간과 맞추기 위해 실제로는 7:00 a.m 이후에 출발하였더라도 모 두 7:00 a.m에 출발한 것으로 가정하였고 허브에서 다른 운전자의 도착을 기다리는 시간을 포함하기에 실제 Total Required Time은 39시간보다 적다. 약 한 달간의 Raw 데이 터와 비교한 결과 최적화 모형은 소요 시간 측면에서 13%, 이동 거리 측면에서 14% 우수하였으며 문제의 모든 제약 조건을 만족하는 것을 확인할 수 있었다. 또한 가장 많은 노드를 방문하는 날은 약 45~50개 수준이었는데 60개의 노드로 실험한 결과 우수하게 해를 찾을 수 있었다.

다음으로 <Table 2>에서 확인할 수 있는 부분은 각 운 전자 별 방문 농장과 식당의 관계이다. 운전자 1의 경우 E 농장만 방문한다. 그런데 E 농장이 납품하는 식당은 j, o 식당이며 j 식당은 K 농장에서도 납품받아야 할 물건이 있다. 반면 운전자 4의 경우 C, D, K, L, M의 다섯 개의 농장을 방문한다. 운전자 1은 운전자 4와 허브에서 만나 필요한 물건을 받아 j 식당에 무사히 배달을 갈 수 있게 된다. 이와 같은 과정을 통해 일부 농장과 식당들이 중복 방문되던 문제를 해결할 수 있다.

<Figure 1(A)>, <Figure 1(B)>는 최적해 결과와 Raw Data에 해당하는 운전자들의 경로를 도식화한 것이다. 운 전자 1부터 5까지 차례대로 검은색, 빨간색, 초록색, 파란 색, 회색으로 각각의 경로를 표현하였다. 그림의 x축은 경도(Longitude), y축은 위도(Latitude)를 나타낸다. 각 노 드들의 좌표는 실제 좌표에서 임의의 수만큼 평행 이동하 여 나타내었다. 허브 노드의 좌표는 (1.99, 1.18)이며 모든 운전자들이 해당 노드를 방문하고 있다는 것을 그림으로 도 확인할 수 있다.

3.2 허브 위치 분석

허브는 가장 많은 방문 횟수를 기록한 식당을 기준으로 하여 결과를 분석하였다. 비록 해당 장소는 허브의 두 번 째 선정 조건에는 벗어나지만 충분한 주차 공간과 냉장 시설을 제공할 수 있다는 점에서 다른 장소들보다 비교 우위를 가졌다. 제 2.2절에서 선정한 총 4개의 허브 후보군 에 대하여 제 2.3절의 최적화 수리 모형을 한 달 간의 데이 터를 입력한 결과 허브의 조건 1, 2를 동시에 만족하는 식 당은 기준 허브에 비하여 이동 거리를 3% 줄일 수 있었다. 반면 조건 2만을 만족하는 식당 두 곳은 기준 허브에 비하 여 이동 거리가 각각 2%, 3% 증가하였다. 이는 다른 두 식당은 매일 방문하지는 않았던 장소이기에 도로 접근성 이 기준 허브에 비해 좋음에도 매일 방문하는 허브로 쓸 경우 이동거리를 증가시킨 것으로 분석된다. 반면 기준 허 브는 매일 방문하던 장소이기에 앞선 두 장소보다 이동거 리를 줄일 수 있던 것으로 분석된다. 허브의 조건 1, 2를 모두 충족한 식당은 가장 적은 이동 거리를 보였지만 이는 기준 허브의 비교 우위를 넘지 못한다고 판단하여 기준 허브를 가장 적합한 장소로 선정하였다.

4. 결 론

본 연구는 전통적인 차량 경로 문제를 실제 제약 사항 을 반영하여 보다 합리적이고 효율적인 수거/배달 최적 화 모형으로 발전시켰다. 주요 발전 사항으로는 첫째, 각 운전자들이 허브에서 모여 수거한 물품을 재분류하는 것 으로 허브를 제외한 노드들이 중복으로 방문되지 않게 하였다. 둘째, 시간 제약을 최적화 모형에 반영하여 각 노드를 방문할 수 있는 가장 늦은 시간을 설정하였다. 첫 번째와 두 번째 발전 사항을 통해 모든 식당은 안정적으 로 필요한 물품을 원하는 시간에 공급받을 수 있게 되었 다. 셋째, 전통적인 모델은 한 곳에서 출발하여 한 곳으 로 복귀하였다면 본 연구의 모형은 각 운전자들이 자신 의 고유한 출발지와 복귀지를 가질 수 있게 되었다. 이는 제 3장에서의 수치 실험을 통해 검증하였다.

향후 연구로는 첫째, 본 연구의 경우 Hub의 위치를 이 미 알고 있는 pHAP를 적용하였으나 경우에 따라 미리 선정한 Hub가 기대보다 덜 효율적일 수 있을 것이다. 따 라서 pHMP를 적용하여 이를 pHAP 모델과 비교해 볼 수 있을 것이다. 둘째, 제시한 최적 모형은 거리만을 고 려하여 목적함수를 구성하였으나 비용 지불 구조가 변경 될 경우 거리 이외의 다른 고려 사항을 추가하여 복수의 목적함수를 갖는 모형으로 만들 수 있을 것이다. 끝으로 필요한 운전자 수를 모델이 직접 결정하도록 발전시키는 방법도 있을 것이다. 본 연구의 모형이 물류 환경의 발전 에 기여할 수 있기를 기대한다.

Acknowledgement

This study was financially supported by Georgia Institute of Technology. Real-world data was provided by Dr. Montreuil, Benoit and his team.

Figure

<Figure 1(A)>.

Routes of Optimal Solution

<Figure 1(B)>.

Routes of Raw Data

Table

<Table 1>.

Matching Restaurants and Farms

<Table 2>.

Optimal Solution of Experimental Data

<Table 3>.

Raw Data of Experimental Data

Reference

Cetiner, S., Sepil, C., and Sural, H., Hubbing and routing in postal delivery systems, Annals of Operations Research, 2010, Vol. 181, No. 1, pp. 109-124.
Dantzig, G.B. and Rasmer, J.H., The Truck Dispatching Problem, Management Science, 1959, Vol. 6, No. 1, pp. 80-91.
Ebery, J., Solving large single allocation p-hub problems with two or three hubs, European Journal of Operational Research, 2001, Vol. 128, No. 2, pp. 447-458.
Google map, http://maps.google.com.
Hwang, I.T. and Kim, H.S., New Mathematical Model for Travel Route Recommendation Service, Journal of Society of Korea Industrial and Systems Engineering, 2017, Vol. 40, No. 3, pp. 99-106.
Jin, J.M. and Kim, H.S., Designing the Operational Concepts for a Futuristic Unmanned Aerial Vehicle Delivery System, Journal of Korean Production & Operations Management Society, 2017, Vol. 28, No. 4, pp. 417-431.
Kang, C.S. and Lee, J.S., A Heuristic for Fleet Size and Mix Vehicle Routing Problem with Time Deadline, Journal of Society of Korea Industrial and Systems Engineering, 2005, Vol. 28, No. 2, pp. 8-17.
Kartal, Z., Hasgul, S., and Ernst, A.T., Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery, Transportation Research Part E, 2017, Vol. 108, pp. 141-159.
Koc, C., Bektas, T., Jabali, O., and Laporte, G., Thirty years of heterogeneous vehicle routing, European Journal of Operational Research, 2016, Vol. 249, No. 1, pp. 1-21.
Moon, G.J. and Park, S.M., A Possible Heuristic for Variable Speed Vehicle Routing Problem with 4 Time Zone, Journal of Society of Korea Industrial and Systems Engineering, 2012, Vol. 35, No. 4, pp. 171-178.
Nagy, G. and Salhi, S., The Many-to-Many Location- Routing Problem, TOP, 1998, Vol. 6, No. 2, pp. 261-275.
Sohn, J.H. and Park, S.S., A linear program for the twohub location problem, European Journal of Operational Research, 1997, Vol. 100, No. 3, pp. 617-622.
Wasner, M. and Zapfel, G., An integrated multi- depot hub-location vehicle routing model for network planning of parcel service, International Journal of Production Economics, 2004, Vol. 90, No. 3, pp. 403-419.