드론을 포함한 3종 운송수단의 배송경로 최적화

1. 서 론

드론은 소형화된 고속 운송수단일 뿐만 아니라, 도로망을 이용하지 않고 이동이 가능하다는 장점을 갖는다. 따라서 물류 인프라가 부족하거나 접근이 어려운 지형에 위치해 서비스가 제한된 지역의 수요를 충족시킬 수 있다. 이에 아마존 프라임 에어(Amazon Prime Air), 구글(Google), 디에이치엘(DHL) 등의 물류회사에서 드론의 도입을 시도한 바 있다(Yoo et al., 2018). 특히, 독일 물류회사 디에이치엘(DHL)은 빅토리아 호수의 우케레웨(Ukerewe)섬에서 의약품 배송 실험을 진행한 바 있다(Ghelichi et al., 2021). 그 결과, 해로와 육로를 이용하는 경우 약 240km의 거리를 6시간 정도 이동해야 하는 반면, 드론을 활용할 경우 약 60km의 거리만을 이동하여 평균 40분만에 배송을 완료하였다. 일본, 미국 등은 국가 차원에서 드론 특구 등을 지정하여 실험 및 연구를 진행하고 있으며(Nonami, 2016), 대한민국 우정사업본부에서도 2017년 득량도 소포, 등기 드론 배송 실험 등으로 드론 활용에 박차를 가하고 있다(Kang, 2020).

위와 같이 드론은 속도가 빠르며 동선의 제약이 적다는 장점이 있지만, 반대로 적재 총량이 작으며 동력 공급이 꾸준히 되어야 한다는 단점도 있다(Boysen et al., 2018). 이러한 단점을 보완하기 위해 드론이 포함된 배송 문제를 다루는 많은 연구에서 트럭과 드론을 동시에 운영하는 방법을 제안하였다(Crişan and Nechita, 2019). 이 때 트럭은 운송수단일 뿐만 아니라 드론의 동력 및 배송물품 공급지 역할도 수행하게 되며(Chang and Lee, 2018), 이와 같은 형태의 물류시스템에서 최적 경로에 대한 연구들이 다수 수행된 바 있다(Murray and Chu, 2015; Agatz et al., 2018; Ha et al., 2018). 또한 미국의 기업인 아마존은 2016년 <아이템 배송을 위한 하늘물류센터와 무인기 활용>이라는 특허를 등록한 바 있는데, 이는 드론을 포함한 2종류 이상의 운송수단으로 구성된 확장적 물류시스템에 대한 개괄을 포함하고 있다(Berg et al., 2016). 다만, 이처럼 운송수단이 다른 운송수단을 싣고 다니는 형태의 다중 운송수단으로 구성된 물류시스템에 대한 최적화 측면의 연구는 아직 활발히 진행되지 않았다.

본 연구는 배, 트럭, 드론의 3종 운송수단으로 구성된 물류시스템을 제안하고, 그 배송경로 및 스케줄을 결정하는 최적화 모형을 제시하고자 한다. 일반적으로 운송수단은 규모, 적재용량 및 속도에 따라 분류할 수 있는데, 해당 기준에 따르면 본 논문에서 선정한 3종 운송수단은 서로 상이한 특성을 갖는다. 배의 경우 속도가 느리지만 규모와 적재용량이 크기 때문에 대규모 거점 배송에 적합한 광범위 운송수단이다. 반대로, 드론은 적재용량이 작지만 속도가 빠르고 규모가 작기 때문에 국소 범위의 최종 고객, 즉 라스트마일 배송(Last-mile delivery)에 유리하다(Aurambout et al., 2019). 트럭의 경우 도로망이 설치되어 있는 범위 내에서는 자유도 높은 운송이 가능하나, 배에 비해서 적재용량이 작은 편이다. 배송경로의 특성 또한 다양한데, 배는 해상운송 전용, 트럭은 육상운송 전용, 드론의 경우 수륙양용의 성격을 가진다.

본 연구에서 제안하는 3종 운송수단 물류시스템은 도로망 유무나 지형적 특성 등으로 인해 접근성이 낮았던 지역에 효율적인 배송을 가능케 할 것으로 기대한다. 특히, 제안하는 물류시스템은 대규모 해상 운송수단인 배를 포함하기 때문에 트럭과 드론만으로는 배송이 어렵던 도서지역 배송에 활용할 수 있다. 구성하는 운송수단을 변경할 시, 산간지역의 배송 케이스에도 적용이 가능하다. 예를 들어 대형 트레일러와 트럭, 드론을 이용하면 중앙 물류센터에서 지역 물류창고로, 지역 물류창고에서 산간지역 고객에게로 3종 운송을 수행할 수 있다. 제안된 물류시스템은 특히 국내에서의 활용성이 높을 것으로 기대되는데, 대한민국은 국토의 약 70% 이상이 산지이며 400개 이상의 유인도가 존재하는 반도 지형이라는 지리적 특성을 갖고 있기 때문이다. 현재 물류서비스는 <생활물류서비스산업발전법>이라는 법규로 균형적인 발전을 보장할 만큼 보편적인 국민 권익으로 인식된다. 본 논문에서 제안된 3종 운송수단 물류시스템이 도서산간지역의 기초 물류 인프라로 활용될 수 있다.

본 논문은 앞서 언급한 것처럼 배, 트럭, 드론 총 3종류의 운송수단을 이용한 물류시스템을 제안하고 그 배송경로 및 스케줄을 최적화하는 문제를 정의한다. 정의된 문제를 해결하기 위해 혼합 정수 이차 제약조건 계획(Mixed-Integer Quadratically-Constrained Programming) 모형을 제안하고, 그 계산 결과를 제시한다. 이 때, 무작위 데이터 기반의 계산 실험과 해당 물류시스템이 잘 활용될 수 있는 대표적인 케이스인 도서지역 실제 데이터를 기반으로 계산 실험을 진행하고, 그리디 휴리스틱(Greedy Heuristic)의 해와 비교하여 분석한다. 또한 제안하는 수리모형은 고객들의 개별 배송완료 시간을 최소화하는 목적함수를 채택하였는데, 이를 기반으로 도서지역 재난상황에서 구호물품을 조달하는 상황을 가정할 수 있다. 수리모형과 휴리스틱을 통해 구한 해를 기반으로 긴급재난 시 섬 지역 구호물품 배송 시나리오 분석을 제시한다.

본 연구는 크게 두 가지 의의를 가진다. 첫 번째, 3종 이상의 서로 다른 운송수단을 포함하는 새로운 물류시스템을 제안함에 더해, 단순한 아이디어 제시에 그치지 않고 해당 물류시스템을 효율적으로 운용하기 위한 경로/스케줄링 모형 및 휴리스틱 알고리즘도 제시하여 그 실용성을 제고하였다. 두 번째, 국내 실제 도서지역 데이터를 기반으로 한 시나리오 분석 등 실증적 분석을 수행하여 연구의 현실 활용성을 구체적으로 제시하였다. 특히 본 연구는 실험결과를 통해 제안된 물류시스템 및 수리모형이 상업적 용도뿐만 아니라 재난 구호 등 공익 목적으로 활용될 수 있음을 보여 해당 연구의 범용성을 뒷받침한다.

이후 논문의 구성은 다음과 같다. 제2장에서는 선행연구에 대해 알아본다. 제3장에서는 3종 운송수단 물류시스템의 배송 문제에 대해 자세히 설명하며, 제4장에서는 해당 문제를 해결하는 수리모형을 제시한다. 제5장에서는 모형의 계산 결과 평가를 위해 구성한 간단한 그리디 휴리스틱 알고리즘을 소개한다. 제6장에서는 밀집도, 드론 배송 노드 수 기준으로 임의 생성된 데이터에 수리모형을 적용하여 실험한 결과를 제시한다. 그리고 실제 위치 기반 데이터에 해당 모형을 적용하여 실험한 결과를 제시하고, 휴리스틱 알고리즘의 결과와 비교 및 분석한다. 얻어진 해에 대해 도서지역 재난상황에서 구호물품 배송상황을 가정하여 시나리오 분석을 수행한다. 제 7장에서는 이 연구의 결론 및 추후 연구 방향을 제안한다.

2. 선행연구

초기 드론은 군사적 목적인 방공, 감시 활동에 주로 사용되었지만(Pahsa, 2011; Ma'Sum et al., 2013), 그 활용 분야가 넓어지면서 물류 산업 외에도 농업(Costa et al., 2012), 방송 산업(Tilak, 2020) 등 여러 분야에서 이용되고 있다(Lee and Choi, 2016). 특히 드론의 장점인 높은 접근성과 속도에 초점을 맞춘 연구들이 진행되고 있다. 드론이 재난상황을 예측, 발견하여 인간이 빠르게 해당 재난에 대처할 수 있게 하는 재난관리 관련 연구가 수행된 바 있다(Restas, 2015; Tanzi et al., 2016). 또한, 드론은 높은 이동성을 기반으로 응급 의료 서비스에도 활용이 가능하며(Nenni et al., 2020), 인도적 물류(Humanitarian Logistics)로 다양한 응급 의약품 배송에 활용될 수도 있다(Scott and Scott, 2020). 물류 인프라의 부족으로 모든 지역에 트럭으로 배송을 하기 어려운 상황에서 의약품 배송(Mateen et al., 2020), 재난으로 인해 잔해로 도로가 뒤덮인 상황에서의 응급품 배송(Rabta et al., 2018)과 같은 연구도 수행된 바 있다.

드론을 물류시스템에서 효율적으로 이용하기 위해서는 경로 최적화 문제를 해결해야 하는데, 이는 전통적인 차량 경로 문제(Vehicle routing problem)로부터 파생된 문제라 할 수 있다. 차량 경로 문제는 거점에서 차량이 출발하여 배달과 같이 고객이 필요로 하는 서비스를 제공 하기 위해 일정한 순서대로 여러 지점의 고객을 방문하고 돌아오는 최적 경로를 결정하는 문제이다. 문제를 해결하기 위해 사용된 여러 방법론과 차량의 수, 고객의 요구 수요, 시간, 지역적 특성 등 문제를 구성하는 요소들의 변화에 따른 연구가 진행되어 왔다(Eksioglu et al., 2009).

드론의 경로에 대한 연구는 다음과 같이 제시된 바 있다. 드론의 수(Javadi et al., 2020), 거점의 수(Li et al., 2020), 방문 조건(Bouman et al., 2018) 등 경로와 관련된 주요 특징의 변화에 따른 연구들이 진행되어 왔다(Macrina et al., 2020). 드론만으로 배송할 시 연료 재충전이 가능한 중간 거점들을 거쳐 모든 고객에게 배송할 때 사용되는 연료량이 최소화되는 경로를 찾기 위한 수리모형과 휴리스틱 또한 제안된 바 있다(Sundar and Rathinam, 2013). 드론을 활용한 경로 문제는 물류시스템뿐 아니라 다른 분야에서도 활용되는데, 그 중 하나는 운동 경기의 공중 촬영에서 드론의 촬영 경로를 최소화하며 시청자들의 만족도를 높이는 방법에 대한 연구이다(Natalizio et al., 2013). 드론의 총 이동 거리를 최소화함과 동시에 고객의 만족도를 최대화하고, 사용된 드론의 수를 최소화하는 다목적 함수 문제의 수리모형을 통해 스포츠 경기 촬영에 대한 시나리오를 제시한 연구도 발표된 바 있다(Guerriero et al., 2014)

트럭과 드론을 함께 사용하는 배송에 대한 연구 또한 다음과 같이 제안되었다. 먼저 트럭을 드론의 이/착륙 지점으로 가정하여 트럭과 드론의 결합에 따라 시나리오를 제시한 연구가 발표되었다(Murray and Chu, 2015). 해당 연구에서는 물류 거점에서 고객까지 거리가 멀어 직접적으로 드론을 사용할 수 없기 때문에 드론과 차량을 동시에 사용하는 외판원 문제(Traveling Salesman Problem with Drone, TSP-D) 시나리오와 물류 거점이 고객과 가까운 곳에 위치하여 트럭과 드론이 개별적으로 배송을 할 수 있는 시나리오를 다루었다. 드론과 트럭을 동시에 사용하는 외판원 문제에 대한 수리모형과 지역 탐색(Local Search), 동적계획법(Dynamic programming) 기반의 휴리스틱 알고리즘을 제시한 연구도 발표되었다(Agatz et al., 2018). 트럭과 드론이 서로 기다리는 시간과 비용을 최소화하는 수리모형을 제시하며 실험을 통해 비교하여 분석한 연구 또한 제시되었다(Ha et al., 2018). 또한 해당 연구는 해결하고자 하는 문제가 해밀토니언 회로 문제(Hamiltonian Circuit Problem)의 일반화된 버전으로 비결정난해(NP-hard)문제임을 명시한 바 있다.

드론을 사용하는 배송에서 드론의 비행 제약에 대해 다루는 연구들도 진행되었다(Hong et al., 2018). 드론과 화물의 무게로 인해 변화하는 드론 배터리 소모 조건을 만족하며 배송 비용과 배송 시간의 최소화를 목적으로 하는 경로 문제에 대한 연구가 수행된 바 있다(Dorling et al., 2016). 드론과 화물의 무게, 드론 배터리 소모 관계에 더해 법규나 기상조건 등으로 인해 일시적으로 설정되는 비행 금지 지역 조건을 고려하여 2단계 탐색 휴리스틱 알고리즘을 제시한 연구도 존재한다(Jeong et al., 2019).

<Table 1>과 <Table 2>에 선행 연구를 분류하여 정리하였다. <Table 1>은 경로 최적화 문제에 드론을 활용할 때 각 연구에서 차별적으로 다룬 부분을 기준으로 나누었다. <Table 2>는 드론이 활용된 산업 분야로 분류하였다. 물류, 농업, 재난 관리 등 여러 분야에서 활용되고 특히, 물류에서 경로 최적화 문제로 트럭과 함께 사용되는 연구들이 활발하게 진행되었지만, 트럭과 드론을 제외한 추가적인 운송수단에 대한 연구는 미국의 기업인 아마존이 2016년 등록한 <아이템 배송을 위한 하늘물류센터와 무인기 활용>이라는 특허 외에 미비한 실정이다. 따라서 본 논문은 드론을 섬 지역의 배송에 활용하여 운송수단의 수 증가라는 차이를 가진 연구를 진행하였다.

Table 1.

Summary of Related Literature – characteristics

Table 2.

Summary of Related Literature - area

3. 문제 설명

3.1 도서 지역의 기존 배송시스템

이 논문에서 다루는 문제는 3종류의 운송수단을 이용한 도서지역의 배송문제이다. 도서지역의 배송은 바다라는 지리적 특성 때문에 배가 필요하다. 도서지역에 대한 기존 배송시스템의 경우 내륙 항구에서 출발한 배가 노선을 따라 각 섬에 방문하는 것으로 시작된다. 배송지역 내에 존재하는 섬들 중 규모가 큰 섬의 경우, 내륙 항구에서 출발하는 배가 직접 방문하는 노선이 존재한다. 따라서 각 섬의 항구에서 배송물품을 적재한 트럭이 출발하여 각 고객에게 직접 배송한다. 반면, 배의 직항 노선이 없는 섬에 배송을 해야 하는 경우, 직항 노선이 있는 가까운 섬에서 다시 작은 배에 물품을 적재하여 배송한다. 이 경우 배송시간이 오래 걸리며 배송 비용도 증가한다.

국내 도서지역을 보면 배송 지역 내 여러 섬들간 직선 거리는 평균 5~10km 정도이지만, 바다라는 지리적 특성 때문에 트럭으로 배송을 진행할 수 없다. 따라서 이런 환경에서 속도가 빠르고 접근성이 높은 드론을 활용할 경우, 전체 배송시스템의 효율성을 높일 수 있을 것으로 판단된다. <Figure 1>은 섬 지역의 배송에서 드론의 활용여부에 따른 배송시스템을 보여준다. 내륙 항구에서 직항 노선이 있는 섬은 항구가 있는 섬, 직항 노선이 없는 섬은 항구가 없는 섬으로 표현하였다.

Figure 1.

Island Delivery System Using Three Transportation Modes

3.3 모형화 아이디어

앞서 정의된 3종류 운송수단 배송경로 문제를 수리모형으로 표현하기 위해 네트워크 형태로 문제를 표현하며, 각 배송지는 노드로, 각 운송수단의 움직임은 아크 상의 흐름(Flow)으로 표현한다. 특히 각 배송 노드를 <Figure 2>와 같이 운송수단의 배송/방문 형태에 따라 7개의 케이스 T, TD, TDA, TDB, TDC, D, SD로 분류하였다. 즉, 본 연구에서 제시하는 수리모형은 먼저 각 배송 노드를 위 7개 케이스 중 하나에 할당한다. 할당 결과에 따라 각 노드가 그에 따른 흐름을 형성할 수 있도록 제약조건을 구성하고, 전체 배송경로 및 스케줄이 결정되는 구조를 갖는다.

Figure 2.

Customer Node Classification Case

먼저 각 고객 노드는 배송하는 운송수단에 따라 트럭으로 배송하는 케이스와 드론으로 배송하는 케이스로 나눌 수 있다(<Figure 2>). 먼저 드론으로 배송하는 케이스는 D와 SD이다. 케이스 D는 지상 드론 배송 노드이며 케이스 SD는 해상 드론 배송 노드이다. 트럭 또는 드론으로 한 번만 배송한다는 가정에 의해 케이스가 D, SD인 노드는 물품을 배송하는 드론만 방문할 수 있다.

트럭으로 배송하는 케이스는 T, TD, TDA, TDB, TDC로 여기에 속하는 노드는 드론의 위치와 관련 없이 모두 트럭으로 배송한다. 그 안에서도 드론을 적재한 트럭이 고객 노드에 배송을 하는 케이스는 TD와 TDA이다. 드론이 있는 트럭이 고객 노드에 물품을 배송한 후 그대로 고객 노드를 떠나는 케이스가 TD, 해당 고객 노드에서 드론이 이륙하여 드론이 없는 트럭이 고객 노드를 떠나는 케이스가 TDA이다. 배송경로의 흐름에서 보면 들어오고 나가는 운송수단이 트럭과 드론, 2종류이지만 함께 떠나는 케이스와 각각 다른 노드로 떠나는 케이스로 나뉜다.

나머지 T, TDB, TDC라는 3개 케이스는 드론이 배송을 위해 이륙하여 드론을 적재하지 않은 트럭이 배송하는 케이스이다. 먼저 케이스 T는 드론이 없는 트럭이 고객 노드에 물품을 배송하며 드론이 없는 트럭이 노드를 떠난다. 이 경우 배송경로의 흐름에서 들어오고 나가는 흐름은 트럭 1종류이다. 케이스 TDB는 드론이 없는 트럭이 배송하며 드론이 착륙하여 드론이 있는 트럭이 떠나는 경우이며, 배송경로의 흐름에서 볼 때 각각 다른 노드에서 트럭과 드론이 들어오지만, 같은 다음 고객 노드로 나가는 흐름을 보여준다. 케이스 TDC는 드론이 없는 트럭이 배송하며 드론이 착륙 후 배송을 위해 해당 고객 노드에서 다시 이륙하는 경우이다. 배송경로의 흐름에서 트럭과 드론이 다른 고객 노드에서 들어오며, 나갈 때도 각각 다른 고객 노드로 나가는 흐름을 보여준다.

4. 수리모형

4.3 목적함수와 제약조건

$\[ minimize \sum _{a\in A}^{}\sum _{i\in N_a^C}^{}{\tau }_i^s \]$

(0)

$\[ \begin{array}{c}{u}_i^{TD}+u_i^{TDA}+u_i^{TDB}+u_i^{TDC}+u_i^T+u_i^D+u_i^{SD}=1\hfill \\ \forall i\in N_a^C,\forall a\in A\hfill \end{array} \]$

(1)

$\[ \begin{array}{cc}\sum _{i\in N_a^D}^{}{u}_i^{SD}+u_i^D=1\hfill & \forall a\in A\hfill \end{array} \]$

(2)

$\[ \begin{array}{cc}\sum _{i\in N_a^C}^{}{u}_i^{SD}\le 1\hfill & \forall a\in A\hfill \end{array} \]$

(3)

$\[ \begin{array}{cc}\sum _{i\in N_a^C}^{}{x}_{P_a,i}^m=1\hfill & \forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(4)

$\[ \begin{array}{cc}\sum _{i\in N_a^C}^{}{x}_{i,P_a^{\text{'}}}^m=1\hfill & \forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(5)

$\[ \begin{array}{c}\sum _{i\in \left\{P_a\right\}\cup N_a^C}^{}{x}_{ij}^m=\sum _{k\in N_a^C\cup \left\{P_a^{\text{'}}\right\}}^{}{x}_{jk}^m\hfill \\ \forall j\in N_a^C,i\ne j\ne k,\forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(6)

$\[ \begin{array}{c}1-u_j^{SD}\le \sum _{i\in \left\{P_a\right\}\cup N_a^C}^{}{x}_{ij}^T+x_{ij}^D\le 2\left(1-u_j^{SD}\right)\hfill \\ \forall j\in N_a^C,i\ne j,\forall a\in A\hfill \end{array} \]$

(7)

$\[ \begin{array}{c}2\left(u_j^{TD}+u_j^{TDA}+u_j^{TDB}+u_j^{TDC}\right)\le \sum _{i\in \left\{P_a\right\}\cup N_a^C}^{}{x}_{ij}^T+x_{ij}^D\hfill \\ \forall j\in N_a^C,i\ne j,\forall a\in A\hfill \end{array} \]$

(8)

$\[ \begin{array}{c}{u}_j^g\le \sum _{\left(\rho ,\sigma \right)\in E_j^f}^{}{x}_{\rho ,\sigma }^T{x}_{\rho ,\sigma }^D\hfill \\ \forall j\in N_a^C,\forall a\in A,\forall \left(f,g\right)\hfill \\ \in \left\{\left(I,TD\right),\left(I,TDA\right),\left(O,TD\right),\left(O,TDB\right)\right\}\hfill \end{array} \]$

(9)

$\[ \begin{array}{c}\sum _{\left(\rho ,\sigma \right)\in E_j^f}^{}{x}_{\rho ,\sigma }^T{x}_{\rho ,\sigma }^D\le 1-u_j^g\hfill \\ \forall j\in N_a^C,\forall a\in A,\forall \left(f,g\right)\hfill \\ \in \left\{\left(I,TDB\right),\left(I,TDC\right),\left(O,TDA\right),\left(O,TDC\right)\right\}\hfill \end{array} \]$

(10)

$\[ \begin{array}{c}{u}_j^T+u_j^D\le \sum _{i\in \left\{P_a\right\}\cup N_a^C}^{}{x}_{ij}^T+x_{ij}^D\le 2-\left(u_j^T+u_j^D\right)\hfill \\ \forall j\in N_a^C,i\ne j,\forall a\in A\hfill \end{array} \]$

(11)

$\[ \begin{array}{c}{u}_j^m\le \sum _{\left(\rho ,\sigma \right)\in E_j^f}^{}{x}_{\rho ,\sigma }^m\hfill \\ \forall j\in N_a^C,\forall a\in A,\forall \left(f,m\right)\in \left\{\left(I,T\right),\left(I,D\right),\left(O,T\right),\left(O,D\right)\right\}\hfill \end{array} \]$

(12)

$\[ \begin{array}{cc}{u}_{ij}^D\le 1-u_i^D{u}_j^D\hfill & \forall i,j\in {N_a}^C,i\ne j,\forall a\in A\hfill \end{array} \]$

(13)

$\[ \begin{array}{c}{u}_{ij}^D-u_i^D\le 1-u_i^g\hfill \\ \forall i,j\in N_a^C,i\ne j,\forall a\in A,\forall g\in \left\{TDA,TDC\right\}\hfill \end{array} \]$

(14)

$\[ \begin{array}{cc}{y}_{P_a}^m=1\hfill & \forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(15)

$\[ \begin{array}{cc}{y}_{P_a^{\text{'}}}^m=\left|N_a\right|& \forall a\in A,\forall m\in \left\{T,D\right\}\end{array} \]$

(16)

$\[ \begin{array}{c}{y}_i^m-y_j^m+L_a{x}_{ij}^m\le L_a-1\hfill \\ \forall i,j\in N_a,i\ne j,\forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(17)

$\[ \begin{array}{c}{\tau }_j^s\ge {\tau }_j^l+t_{ij}^T+L_a\left(u_j^g{x}_{ij}^T-1\right)\hfill \\ \forall i\in \left\{P_a\right\}\cup N_a^C,\forall j\in N_a^C,i\ne j,\forall a\in A,\hfill \\ \forall g\in \left\{T,TD,TDA,TDB,TDC\right\}\hfill \end{array} \]$

(18)

$\[ \begin{array}{c}{\tau }_j^s\ge {\tau }_i^l+t_{ij}^D+L_a\left(u_j^D{x}_{ij}^T-1\right)\hfill \\ \forall i\in \left\{P_a\right\}\cup N_a^C,\forall j\in N_a^C,i\ne j,\forall a\in A\hfill \end{array} \]$

(19)

$\[ \begin{array}{cc}{\tau }_j^s\ge {\tau }_{P_a}^l+t_{P_a,j}^D+L_a\left(u_j^{SD}-1\right)\hfill & \forall j\in N_a^C,\forall a\in A\hfill \end{array} \]$

(20)

$\[ \begin{array}{cccc}{\text{τ}}_i^s\le {\text{τ}}_i^l\hfill & \hfill & \hfill & \forall i\in N_a^C,\forall a\in A\hfill \end{array} \]$

(21)

$\[ \begin{array}{c}{\tau }_j^l\ge {\tau }_i^l+t_{ij}^m+L_a\left(\left(u_j^{TDB}+u_j^{TDC}\right)x_{ij}^m-1\right)\hfill \\ \forall i\in \left\{P_a\right\}\cup N_a^C,\forall j\in N_a^C,i\ne j,\hfill \\ \forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(22)

$\[ \begin{array}{cc}1-x_{P_a,j}^D\ge u_j^{TDC}\hfill & \forall j\in N_a^C,\forall a\in A\hfill \end{array} \]$

(23)

$\[ \begin{array}{c}\sum _{\left(\rho ,\sigma \right)\in E^f}^{}{x}_{\rho ,\sigma }^V=1\hfill \\ \forall f\in \left\{I,O\right\},E^O=\left\{\left(P,i\right)|\forall i\in A\right\},\hfill \\ E^I=\left\{\left(i,P^{\text{'}}\right)|\forall i\in A\right\}\hfill \end{array} \]$

(24)

$\[ \begin{array}{cc}\sum _{i\in A\cup P}^{}{x}_{ij}^V=\sum _{k\in A\cup P^{\text{'}}}^{}{x}_{jk}^V\hfill & \forall j\in A,i\ne j\ne k\hfill \end{array} \]$

(25)

$\[ \begin{array}{cc}\sum _{i\in A\cup P}^{}{x}_{ij}^V=1\hfill & \forall j\in A,i\ne j\hfill \end{array} \]$

(26)

$\[ \begin{array}{c}{y}_i^V-y_j^V+L_v{x}_{ij}^V\le L_v-1\hfill \\ \forall i\in A\cup P^{\text{'}},\forall j\in A\cup \left\{P,P^{\text{'}}\right\},i\ne j\hfill \end{array} \]$

(27)

$\[ \begin{array}{c}{\tau }_j^V\ge {\tau }_i^V+t_{ij}^V+L_v\left(x_{ij}^V-1\right)\hfill \\ \forall i\in A\cup P,\forall j\in A\cup P^{\text{'}},i\ne j\hfill \end{array} \]$

(28)

$\[ {\text{τ}}_P^V=0 \]$

(29)

$\[ \begin{array}{cc}{\tau }_a^V\le {\tau }_{P_a}^l\hfill & \forall a\in A\hfill \end{array} \]$

(30)

$\[ \begin{array}{cc}{x}_{ij}^m\in \left\{\mathrm{0,1}\right\}\hfill & \forall i,j\in N_a,\forall a\in A,\forall m\in \left\{T,D\right\}\hfill \end{array} \]$

(31)

$\[ \begin{array}{cc}{x}_{ij}^V\in \left\{\mathrm{0,1}\right\}\hfill & \forall i,j\in A\cup \left\{P,P^{\text{'}}\right\}\hfill \end{array} \]$

(32)

$\[ \begin{array}{cc}{u}_i^g\in \left\{\mathrm{0,1}\right\}\hfill & \forall i\in N_a^C,\forall g\in G\hfill \end{array} \]$

(33)

$\[ \begin{array}{cc}{\tau }_i^s\ge 0\hfill & \forall i\in N_a,\forall a\in A\hfill \end{array} \]$

(34)

$\[ \begin{array}{cc}{\text{τ}}_i^l\ge 0\hfill & \forall i\in N_a,\forall a\in A\hfill \end{array} \]$

(35)

위의 (0)-(35)는 본 논문의 문제를 수리모형화한 수식이다. 목적함수 (0)은 모든 고객 노드에 배송하는 서비스 시간의 합을 최소화한다. 제약식 (1)-(3)은 지역 내 고객 노드에 배송하는 운송수단 결정에 대한 내용이다. $$ u_i^{TD},u_i^{TDA},u_i^{TDB},u_i^{TDC},u_i^T$$와 같이 트럭으로 배송하는 노드 변수와 $$ u_i^D,u_i^{SD}$$처럼 드론으로 배송하는 노드 변수로 구성된 제약식 (1)을 통해 각 고객 노드에 배송하는 형태가 결정 변수 u의 값에 따라 <Figure 3>의 7가지 케이스 중 하나로 설정된다. 제약식 (2)에서 드론 노드 i에 해상 드론이 배송할 때 $$ u_i^{SD}=1$$, 지상 드론이 배송할 때 $$ u_i^D=1$$이 되는데, 고객 노드에 배송은 한 번만 이루어지며 재방문은 불가능하다는 가정으로 인해 지상 드론 또는 해상 드론을 이용하여 1번의 배송만 가능한 것을 표현한다. 해상 드론이 지역 내 최대 1개의 고객 노드에 배송할 수 있다는 조건은 제약식 (3)을 통해 나타난다.

Figure 3.

Customer Node Classification Case and Decision Variable U

제약식 (4)-(7)은 각 지역 내 트럭, 드론 배송경로의 흐름 보존 제약식이다. 제약식 (4)는 배에서 내린 트럭과 드론이 지역의 항구 P_a에서 출발하여 배송하는 것을 보여준다. 제약식 (5)는 지역 내 모든 고객 노드에 배송을 완료한 트럭과 드론이 다시 항구 $$ P_a^{\text{'}}$$로 돌아오는 것을 보여준다. 각 고객 노드에 들어오는 운송수단이 있으면 반드시 나가는 운송수단이 있어야 한다는 제약식 (6)을 통해 배송경로의 흐름이 보존된다. 제약식 (7)은 지역 내 임의의 고객 노드 j에 해상 드론의 배송에 대한 변수 $$ u_j^{SD}$$와 트럭의 경로 변수 $$ x_{ij}^T$$, 드론의 경로 변수 $$ x_{ij}^D$$의 관계를 보여준다.

제약식 (8)-(10)은 트럭에 드론이 있거나 드론이 트럭에 이/착륙하여 트럭과 드론이 고객 노드에 같이 있을 때 필요한 제약식이다. 제약식 (8)은 노드 변수 $$ u_j^{TD},u_j^{TDA},u_j^{TDB},u_j^{TDC}$$와 같이 노드 j에서 트럭과 드론이 함께 있을 때 트럭과 드론의 경로 흐름에 대한 제약식이다. 아크가 노드에 들어오고 나가는 흐름 상태 집합 F = {I,O}에 따라 트럭과 드론이 같이 오거나 따로 올 수 있으며 나가는 경우도 같이 나가거나 따로 나갈 수 있다.

제약식 (9)는 트럭과 드론이 같이 들어오는 때, 같이 나가는 때에 해당하는 제약식이며 제약식 (10)은 트럭과 드론이 따로 들어오는 때, 따로 나가는 때에 해당하는 제약식이다. 본 문제는 트럭의 경로 흐름과 드론의 경로 흐름을 모두 고려하며, 노드 분류 케이스가 존재한다. 따라서 제약식 (9)와 (10)에서 $$ x_{\rho ,\sigma }^T,x_{\rho ,\sigma }^D$$는 해당 고객 노드에서 트럭과 드론의 직전 방문 노드, 직후 방문 노드가 같은지 여부를 판단하는 제약식이다. 제약식 (9)와 (10)에서 아크상의 흐름과 노드 분류 케이스는 쌍으로 고려해야 한다. 예를 들어 제약식 (9)에서 아크상의 흐름을 나타내는 f와 노드 분류 케이스인 g를 쌍으로 고려한 (f, g)에서 (I, TDA)는 가능하지만 (O, TDA)는 불가능하다. 제약식 (9)와 (10)에서 $$ E_j^f$$는 $$ E_j^I=\left\{\left(i,j\right)|i\in \left\{P_a\right\}\cup N_a^C,i\ne j,\forall a\in A\right\}$$와 $$ E_j^O=\left\{\left(j,k\right)|k\in N_a^C\cup \left\{P_a^{\text{'}}\right\},j\ne k,\forall a\in A\right\}$$의 합집합이다. 제약식 (23)은 케이스 TDC의 오류 경로 방지 제약식이다.

제약식 (11)-(12)는 드론이 없는 트럭과 배송을 나간 드론처럼 트럭과 드론이 분리되어 배송할 때 만족해야 하는 조건들이다. 제약식 (11)은 드론이 없는 트럭이 배송하는 노드 변수 $$ u_j^T$$, 드론이 배송하는 노드 변수 $$ u_j^D$$와 트럭 배송경로 변수 $$ x_{ij}^T$$, 드론 배송경로 변수 $$ x_{ij}^D$$의 관계를 표현한다. 제약식 (12)는 분리된 트럭 또는 드론이 해당 고객 노드에 배송하기 위해 들어가고 나올 때 만족해야 하는 조건이다. 트럭과 드론이라는 2종의 운송수단이 분리되어 각각 배송하는 상황에 대한 제약식이기에 노드 분류 케이스 대신 운송수단 집합 m∈M을 이용하여 아크상의 흐름을 나타내는 f와 m을 (f, m)의 형태로 쌍으로 고려한다.

제약식 (13)과 (14)는 드론의 배송에 관한 제약식이다. 제약식 (13)은 다른 운송수단에서 이륙해서 하나의 고객 노드에 배송을 한 드론이 트럭에 착륙하는 과정 없이 추가적으로 배송을 하는 것을 방지한다. 예를 들어 노드 i에서 노드 j로 드론이 이동하여 $$ x_{ij}^D$$가 1이라면 노드 변수 $$ u_i^D$$와 $$ u_j^D$$는 동시에 1일 수 없고, 노드 변수 $$ u_i^D$$와 $$ u_j^D$$가 1이라면 $$ x_{ij}^D$$는 0이 되어 드론이 노드 i에서 노드 j로 이동할 수 없다는 것이다. 여기에서 $$ u_i^D{u}_j^D$$는 노드 i에 대한 변수 $$ u_i^D$$와 노드 j에 대한 변수 $$ u_j^D$$가 같은 값을 갖는지 여부를 판단하기 위한 제약식이다. 판단이 필요한 이유는 노드 i에서 노드 j로 드론이 이동한다면 두 노드 중 하나는 이/착륙 노드이며, 다른 노드는 배송 노드이기 때문이다.

제약식 (14)는 해당 고객 노드의 케이스가 TDA나 TDC처럼 드론이 이륙하는 노드와 그 경로에 대한 제약식이다. 노드 i에서 노드 j로 드론이 이동할 때 노드 j가 드론으로 배송하는 노드면 $$ u_j^D$$는 1이 되고 노드 i는 케이스 TDA, TDC 중 하나에 포함된다. 노드 j가 드론으로 배송하는 노드가 아니라면 노드 i는 TDA, TDC를 제외한 나머지 가능 케이스에 포함된다. 제약식 (15)-(17)은 지역 내 출발 거점의 역할을 하는 항구 노드 P_a에서 출발하여 모든 고객 노드에 배송한 후 돌아오는 항구 노드$$ P_a^{\text{'}}$$까지 지역 내 배송의 순환경로를 방지하는 제약식이다.

제약식 (18)-(22)는 시간에 관한 제약식이다. 드론은 이/착륙 과정에서 트럭과의 결합이 필요하며 이 때 운송수단간 대기시간이 발생할 수 있다. 따라서 본 모형에서는 시간 변수를 각 노드마다 서비스 제공 시간 τ^s와 서비스 완료 시간 τ^l로 분리하였다. 제약식 (18)은 트럭으로 배송하는 고객 노드의 시간 제약식이다. 제약식 (18)에서 $$ u_j^g{x}_{ij}^T$$는 노드 j가 트럭으로 배송하는 케이스 g∈{T,TD,TDA,TDB,TDC}에 속하고 노드 i에서 노드 j로 트럭이 이동할 때 노드 i의 서비스 완료 시간인 $$ {\tau }_i^l$$과 노드 i에서 노드 j까지 걸리는 트럭의 이동 시간을 고려하여 노드 j의 서비스 제공 시간인 $$ {\tau }_j^s$$를 결정한다는 의미에서 사용되었다.

제약식 (19)는 지상 드론으로 배송하는 고객 노드, 제약식 (20)은 해상 드론으로 배송하는 고객 노드의 시간 제약식이다. 제약식 (19)에서 $$ u_j^D{x}_{ij}^D$$는 노드 j가 드론으로 배송하는 노드이며 노드 i에서 노드 j로 드론이 이동할 때 노드 i의 서비스 완료 시간인 $$ {\tau }_i^l$$과 노드 i에서 노드 j까지 걸리는 드론의 이동 시간을 고려하여 노드 j의 서비스 제공 시간인 $$ {\tau }_j^s$$를 결정한다는 의미에서 사용되었다. 제약식 (21)은 지역 내 모든 고객 노드에서 서비스 제공 시간 τ^s가 서비스 완료 시간 τ^l보다 앞선다는 것을 보여준다.

제약식 (22)는 드론이 착륙하는 노드 케이스인 TDB와 TDC에 대한 제약식이다. 드론이 착륙하는 노드에서 서비스 완료 시간 τ^l은 트럭의 도착과 드론의 도착을 모두 고려하여야 한다. 제약식 (22) 중 의사결정 변수간 곱 형태인 $$ \left(u_j^{TDB}+u_j^{TDC}\right)x_{ij}^m$$에서 ∀m∈{T,D}이므로 m이 트럭 T일 경우 노드 j가 드론 착륙 노드라면 $$ \left(u_j^{TDB}+u_j^{TDC}\right)$$의 값은 1이 되며, 그 때 노드 i에서 노드 j로 트럭이 이동한다면 $$ x_{ij}^m$$의 값은 1이 되며 그렇지 않은 경우 0이 된다. m이 드론 D일 경우 $$ \left(u_j^{TDB}+u_j^{TDC}\right)$$의 값은 0이 되며, 그 때 노드 i에서 노드 j로 드론이 이동한다면 $$ x_{ij}^m$$의 값은 1이 되며 그렇지 않은 경우 0이 된다. 고객 노드에 트럭이 배송하며 다른 고객 노드에 배송을 마친 드론이 착륙할 경우, 서비스 완료 시간 τ^l은 해당 고객 노드를 떠나 다음 고객 노드로 출발하는 시간을 뜻하므로 트럭과 드론이 모두 해당 고객 노드에 도착한 최종 시간이 서비스 완료 시간 τ^l임을 설명한다.

제약식 (24)-(28)은 배의 경로에 대한 제약식이다. 제약식 (24)로 인해 배는 내륙 항구 P에서 출발하며, 운송을 마치면 다시 내륙 항구 P^'으로 돌아와야 한다. 제약식 (25)와 (26)은 각 지역의 항구에 한 번씩만 방문한다는 조건과 배의 수송경로 흐름을 보존한다는 것을 표현한다. 제약식 (27)은 배의 순환경로를 방지하는 제약식이다. 제약식 (28)은 배의 수송 완료 시간 τ^V에 대한 제약식이다. 제약식 (29)를 통해 배, 트럭, 드론의 전체 배송이 시작되는 시간 $$ {\tau }_P^V$$을 설정하며 각 지역의 배송 시작 시간 $$ {\tau }_{P_a}^l$$은 배가 해당 지역의 항구에 도착한 시간인 $$ {\tau }_a^V$$이후가 된다는 것을 제약식 (30)을 통해 설정한다. 제약식(31)-(35)는 변수에 대한 제약식이다.

5. 휴리스틱 알고리즘

제시한 수리모형을 활용한 실험의 품질을 평가하기 위해 단순한 구조의 그리디 휴리스틱 알고리즘을 구현하여 비교 대상으로 활용한다. 해당 휴리스틱 알고리즘을 구성할 때에 가장 중점적으로 고려한 사항은 그리디 휴리스틱을 경로 결정 과정에 최대한 활용하는 것이다. 특히, 모형에서는 각 배송 노드를 7개의 케이스로 나누어 동시에 고려하나, 아래 휴리스틱 알고리즘은 거리에 따른 그리디 휴리스틱으로 트럭의 배송경로를 먼저 생성한 후 남은 노드들을 드론 배송 노드들로 할당하는 형태를 갖는다. 아래의 단계는 그리디 휴리스틱의 단계 설명이며 <Figure 4>는 그리디 휴리스틱의 흐름도를 보여준다.

Figure 4.

Greedy Heuristic Flow Chart

• 단계 1. 각 섬에 대하여 아래 과정 수행
•  1.1. 거점에서 가장 짧은 아크를 찾는 형태로 M개 노드를 포함한 트럭 경로 생성
•  1.2. 트럭 경로에 포함되지 않은 N-M개 노드들은 드론 배송 노드로 지정
•  1.3. 트럭 경로에 포함된 노드들의 무게중심 C를 계산
•  1.4. 드론 배송 노드들을 C로부터 먼 순서대로 정렬
•  1.5. 가장 C로부터 먼 배송 노드는 해상 드론 배송 노드로 할당
•  1.6. 나머지 드론 배송 노드에 대해 아래 과정 수행
   1.6.1. 트럭 경로 상의 아크 중 꼬리 노드, 머리 노드부터 이동시간 합이 가장 짧은 아크 선정
   1.6.2. 해당 아크의 꼬리 노드를 이륙지점, 머리 노드를 착륙지점 할당
•  1.7. 결정된 아크를 기반으로 거점 출발시간을 0으로 가정한 서비스 시간 계산
• 단계 2. 배의 경로를 모두 나열하여 서비스 시간 합이 가장 작은 조합 선정

<Figure 5>는 휴리스틱 알고리즘 단계 1의 진행을 보여준다. 단계 1은 각 섬 지역 별 트럭과 드론의 배송경로를 구하는 단계로 <Figure 5>에서 N은 13개이며 트럭으로 배송하는 노드 수 M은 7개이다. 따라서 나머지 6개 노드는 드론으로 배송한다. 트럭보다 드론이 빠르게 배송할 수 있기 때문에 전체 서비스 시간의 합을 줄이기 위해서는 드론으로 멀리 있는 노드에 배송하는 것이 좋은데, 멀리 있는 노드를 선정하기 위해 지역 내 모든 노드들의 무게중심을 활용하였다.

Figure 5.

Heuristic Step 1

<Figure 5(a)>에서 선정하는 무게중심 C는 각 노드의 2차원 좌표를 이용하여 계산하였다. 또한 트럭이 노드 OD에서 출발하여 노드 TN1을 방문하여 물품을 배송하고, 노드 TN11을 드론이 배송한다면 노드 TN11에서 이동시간 합이 가장 짧은 노드인 OD와 TN1이 각각 드론의 이륙 노드와 착륙 노드로 할당된다. 드론이 착륙하여 트럭에 적재되기까지 필요한 대기시간 때문에 목적함수 값이 증가할 가능성이 있으나, 그리디 휴리스틱의 로직을 반영하기 위해 위와 같은 과정으로 경로를 결정한다.

6. 실험 결과 및 시나리오 분석

6.2 실험 결과

(1) 지역 1개 내 고객 노드 밀집도, 드론 노드 수에 따른 임의 생성 데이터 배송 케이스 실험

<Table 3>은 4개의 밀집도, 5개의 드론 노드 수에 따른 20개의 실험을 각각 3600초 계산하여 얻은 트럭과 드론의 배송경로이다. 드론으로만 배송해야 하는 드론 노드 수가 1개에서 5개로 늘어나는 동안 목적함수의 값의 변화는 일정하지 않다. 하지만 같은 데이터를 사용한 같은 밀집도 내에서 비교하여 보면 목적함수 값이 큰 실험의 경우 트럭이 거점으로부터 멀리 떨어진 고객 노드에 배송을 하는 빈도가 높고, 드론의 이동 시간이 긴 것을 확인하였다. 또 트럭의 경로 진행 방향이 일정하지 않고 꼬인 경우 상대적으로 목적함수 값이 높게 나와 다른 해보다 좋지 않았다.

Table 3.

Random Generation Data Experiment

반경 5km 내에 고객 노드가 0개, 5개인 케이스는 대한민국 섬 지역과 비슷한 형태이다. 해안가를 따라 구성된 마을처럼 고객 노드의 밀집도가 가장 낮은 경우, 모든 고객의 서비스 완료 시간 합의 절대값은 크지만 각 케이스 별 얻은 목적함수의 값들의 차이는 반경 5km 내에 고객 노드가 5개인 경우보다 작았다. 노드가 지역 외곽에 위치하여 전체 배송 완료시간에 비해 드론 노드 변경에 따른 시간 차이가 작은 것이 그 이유이다. 하지만 반경 5km 내에 5개, 10개 노드가 존재하는 경우, 지역 외곽에 위치한 고객 노드에 배송하는 운송수단과 경로 순서에 따라 목적함수 값 차이가 다른 케이스보다 크다. 고객 노드가 가장 밀집되어 있는 케이스의 경우 목적함수 값들의 차이가 가장 작은 것을 알 수 있는데, 이는 드론의 이/착륙 노드의 역할을 하는 고객 노드와 드론 배송 노드 간 거리가 다른 케이스보다 작으며 트럭이 밀집된 고객 노드에 배송하기 때문이다.

결론적으로, 위 실험을 통해 트럭은 거점에 근접한 노드에 배송을 하고, 드론은 상대적으로 거점으로부터 먼 노드에 배송을 하는 것이 더 좋은 목적함수 값을 제공한다. 또한, 본 문제는 배송경로에서 트럭과 드론이 결합 및 분리되어 배송하는 형태의 특징이 존재한다. 실험 결과의 추세에 따르면, 각 고객 노드의 배송 서비스 제공 시간의 합을 최소화하는데 운송수단 간 대기시간과 드론의 이동시간 감소의 영향이 크다. 이 실험에서 트럭과 드론의 전체적인 배송 진행방향이 일정한 경우, 대체적으로 트럭의 대기시간과 드론의 이동시간이 감소되어 더 나은 해가 도출된다.

(2) 지역 1개(A1) 배송 케이스 실험

<Figure 6>은 한 지역의 배송경로 탐색에서 수리모형과 그리디 휴리스틱을 통해 얻은 목적함수 값을 비교하는 그래프이다. 앞서 언급한 것처럼 A1 지역에서 거점을 포함한 15개 노드에 대해 실험을 진행하였다. 휴리스틱을 통해 0.1초만에 539.25분이라는 전체 서비스 시간의 합을 목적함수 값으로 얻을 수 있다. 수리모형은 실험 시작 82초 후에 얻어지는 목적함수 값이 휴리스틱의 목적함수 값보다 낮은 값을 가지게 되며 1000초 이후의 목적함수 값은 3600초까지 큰 변화 없이 일정한 값에 수렴하였다.

Figure 6.

Comparison of Objective Function Values for One Area Delivery Experiment

지역 1개의 수리모형과 그리디 휴리스틱 배송경로는 각각 <Figure 7>에 제시된다. <Figure 7(a)>에서 수리모형의 경로를 보면, 트럭이 TN8에서 TN9로, TN9에서 TN7로 배송하는데 전체적인 경로의 방향에서 정반대로 움직이는 특징이 있다. 본 문제가 각 노드의 서비스 시간의 합을 최소화하기에 경로 전체의 방향과 정반대로 갈 경우 배송시간과 비용이 대체적으로 증가하는 다른 차량 경로 문제들과 차이점이 존재한다.

Figure 7.

The Delivery Route in A1

<Figure 7(b)>에서 TN11과 TN12에 물품을 드론이 배송하기 때문에 트럭의 대기시간이 발생하지만 제 5장의 휴리스틱 1.6단계에서 보았듯, 가장 가까운 아크의 꼬리 노드와 머리 노드가 선택되어야 하기 때문에 결정된 경로이다. 해상 드론 배송 노드는 수리모형과 그리디 휴리스틱 실험 모두 DN1으로 같다. 3600초 동안 수리모형으로 계산한 고객의 서비스 시간 합은 517.85분이며 그리디 휴리스틱을 통해 얻은 고객의 서비스 시간 합은 앞서 언급한 것처럼 539.25분으로 수리모형을 사용할 경우 목적함수 값이 21.4분 줄어들게 되며 3.9% 개선된 해를 얻을 수 있다.

<Figure 8>은 1지역 배송에서 각 고객 노드에 배송하는 시간 그래프를 보여준다. 수리모형 계산을 통해 얻은 해에 비해 그리디 휴리스틱의 해에서는 드론의 이/착륙으로 인해 운송수단이 대기하는 시간이 길게 발생한다. <Table 4>는 1지역 배송에서 배송 순서별 고객 노드의 배송 서비스 제공 시간이다. 그리디 휴리스틱을 통해 값을 얻는다면 2번째 순서로 배송하는 노드를 제외하고 모든 배송 순서에서 수리모형을 통해 계산한 것 보다 고객 노드에 배송하는 시간이 늦어지게 된다. 그리디 휴리스틱의 계산에서 대기시간은 드론 배송마다 존재하기에 배송이 진행될수록 누적 대기시간은 증가하게 된다.

Figure 8.

Timeline for Each Customer Node in the Delivery of A1

Table 4.

Service Time for Each Customer Node in the Delivery of A1

결론적으로, 지역 1개 배송 케이스 실험을 보면 멀리 떨어져 있는 고객 노드가 1개일 경우 배에서 띄운 해상 드론으로 배송을 진행하는 것이 효과적이다. 수리모형과 휴리스틱의 경로를 비교해보면, 수리모형 경로는 드론의 이동시간을 줄이는 경로로 형성된다. 따라서 트럭의 경로 방향성이 일부 달라지더라도 이는 트럭 대기시간, 드론 이동시간 감소에 부합하기에, 휴리스틱과 같이 상대적으로 트럭 대기시간과 드론 이동시간이 긴 경우보다 나은 해를 얻는다.

(3) 지역 2개(A1, A2) 배송 케이스 실험

<Figure 9>은 지역이 A1과 A2, 2개일 때 배송 실험의 목적함수 값을 비교한 그래프이다. A1의 노드는 드론 노드 1개와 거점을 포함하여 10개, A2의 노드는 드론 노드 4개와 거점을 포함하여 13개로 진행하였다. 수리모형의 목적함수 값이 그리디 휴리스틱의 목적함수 값보다 좋아지는 시간은 82초이며 이는 <Figure 6>에서 지역 1개의 수리모형과 그리디 휴리스틱의 목적함수 값이 역전되는 시간과 같은 값이다. 지역과 노드의 수가 늘었기에 지역 1개 배송 실험과 달리 지역 2개 배송 실험은 진행된 실험 시간 동안 목적함수 값이 작지만 꾸준히 변화하였다.

Figure 9.

Comparison of Objective Function Values for Two Areas Delivery Experiment

<Figure 10>은 지역 2개의 배송경로 실험의 해를 표시한 것으로, (a)는 A1의 수리모형, (b)는 A2의 수리모형, (c)는 A1의 그리디 휴리스틱, 마지막 (d)는 A2의 그리디 휴리스틱 경로이다. <Figure 10>을 보면 지역 A1의 수리모형과 그리디 휴리스틱의 해에서 드론 노드가 DN1으로 동일하였고 전체적인 경로의 방향도 일정하였다. 하지만 수리모형을 통해 얻은 A2의 배송경로를 <Figure 10(b)>에서 살펴보면 TN2에서 TN4로 배송한 트럭이 TN3로 이동하는 것을 볼 수 있다. 이는 지역 1개 실험인 <Figure 7(a)>에서 TN8에서 TN9로 배송한 후 TN7로 배송하는 것과 같은 이유인데 전체 배송 서비스 시간 합을 줄이기 위해 발생한다.

Figure 10.

The Delivery Route in A1, A2

A1 지역은 수리모형을 통해 얻은 해가 그리디 휴리스틱을 통해 얻은 해와 비교하였을 때 배송 서비스 시간 합이 총 17.3분 감소하였고, 평균적으로 각 고객 노드에 2.16분 빠르게 배송이 가능하다. A2 지역은 수리모형을 통해 얻은 해의 배송 서비스 시간 합이 그리디 휴리스틱의 해에 비해 총 59.55분 감소하였고, 평균적으로 각 고객 노드에 5.41분 빠르게 배송이 가능하다. 수리모형 실험을 1시간 동안 진행하여 얻은 목적함수 값은 1247.75분으로, 그리디 휴리스틱으로 0.1초만에 계산하여 얻은 값인 1324.6분보다 5.8%가 개선되었다.

<Figure 11>은 2지역 배송에서 각 고객 노드에 배송하는 시간 그래프를 보여준다. 수리모형 계산을 통해 얻은 해에 비해, 그리디 휴리스틱의 해에서 각 노드에 배송하는 시간이 지역 1개의 배송에 비해 더 늦어진다. <Table 5>와 <Table 6>는 각각 2지역 배송에서 A1과 A2 지역의 배송 순서별 고객 노드의 배송 서비스 제공 시간이다. <Table 5>에서 수리모형과 그리디 휴리스틱으로 계산되는 배송 순서별 고객 노드 서비스 시간 차이를 보면 갈수록 수리모형의 경로가 고객에게 더 빠르게 배송하는 것을 알 수 있다. 또 <Table 6>에서 고객 노드의 수와 드론 노드의 수 모두 A2 지역이 많기에 A1 지역보다 배송 서비스 제공 시간 차이 값이 큰 것을 알 수 있다.

Figure 11.

Timeline for Each Customer Node in the Delivery of A1, A2

Table 5.

Service Time for Each Customer Node in the Delivery of A1

Table 6.

Service Time for Each Customer Node in the Delivery of A2

결론적으로, 지역 2개의 배송 케이스 실험에서 운송수단간 대기시간이 감소하며 꼬인 경로가 없을 경우 대체적으로 좋은 해를 제공한다. 다만, 본 문제의 특성상 트럭과 드론이 배송경로에서 결합하고 분리되는 과정이 포함되기 때문에 대기시간을 줄이기 위해 A2 지역의 경로 중 TN4에서 TN3로 트럭의 이동이 발생할 수 있다. A2 지역의 수리모형과 휴리스틱의 경로 모두 해상 드론 배송 노드가 우측 작은 섬들에 존재하는 DN1, DN2에서 선정되었는데 이는 6.2.1에서 언급한 이/착륙 노드와 연결된다. 드론 배송 노드 근처에 이/착륙 노드가 있는 것이 대체적으로 좋은 해를 얻게 되어, 이번 실험처럼 2개의 드론 노드가 근접한 경우 하나는 지상 드론으로 배송하며 다른 하나의 노드는 해상 드론으로 배송하는 것이 효과적이다.

(4) 지역 3개(A1, A2, A3) 배송 케이스 실험

A1, A2, A3로 구성된 지역 3개 배송 실험에서 수리모형과 그리디 휴리스틱을 통해 계산되는 목적함수 값 비교는 <Figure 12>에 제시되어 있다. 지역과 노드 수가 늘어났기에 수리모형의 해가 그리디 휴리스틱의 해보다 좋아지는 시간은 335초로 이전 2개의 실험보다 늦게 나타난다. 지역 1개에 대한 그래프인 <Figure 6>, 지역 2개에 대한 그래프인 <Figure 9>과 비교해보면 <Figure 12>는 수리모형을 통해 계산되는 목적함수 값의 변화가 크며 이전에 비해 긴 시간 동안 변화하는 것을 알 수 있다.

Figure 12.

Comparison of Objective Function Values for Three Areas Delivery Experiment

<Figure 13>은 A1, A2, A3 지역의 수리모형과 그리디 휴리스틱을 통해 얻은 배송경로를 보여준다. <Figure 13(c)>에서 이번 실험에 추가된 지역인 A3의 수리모형의 배송경로를 보면 해상 드론 배송 노드가 DN1인 것을 알 수 있다. 모형의 목적함수 값이 전체 고객 노드의 배송 서비스 시간의 합이여서 드론이 거점으로 복귀하는 시간을 고려하지 않아도 되는 특징과 배의 이동시간이 트럭, 드론의 지역 배송시간에 비해 상대적으로 길다는 특징을 통해 DN1이 해상 드론 배송 노드가 되고 DN3가 지상 드론 배송 노드가 된다.

Figure 13.

The Delivery Route in A1, A2, A3

A1 지역은 수리모형의 경로가 그리디 휴리스틱의 경로보다 16.15분 빠르게 모든 고객 노드에 배송할 수 있으며 평균적으로 각 고객 노드에 2.01분 빠른 배송을 한다. A2 지역의 차이는 수리모형을 통해 얻은 고객 노드 배송 서비스 시간 합이 64.8분 빠르며 평균적으로 각 고객 노드에 5.89분 빠른 배송을 한다. A3 지역은 수리모형에서 도출된 경로가 그리디 휴리스틱의 경로보다 23.8분 빠르며 평균적으로 각 고객 노드에 2.38분 빠른 배송을 한다. 지역 3개의 배송에 대한 수리모형 실험을 3600초 진행하였을 때 얻는 해는 1911.74분으로, 그리디 휴리스틱으로 0.06초 계산하여 얻는 2016.5분보다 5.19% 개선되었다.

<Figure 14>은 지역 3개의 배송에서 각 고객 노드에 배송하는 시간 그래프를 보여준다. 지역 1개 배송 실험과 지역 2개 배송 실험보다 수리모형과 그리디 휴리스틱을 통해 얻은 각 배송 순서별 서비스 시간 차이는 증가하는데, 지역의 증가, 드론 노드를 포함한 고객 노드의 증가 때문이다. 실험 결과에 따르면, 지역 내 항구가 존재하는 섬과 4개의 드론 노드가 있는 섬의 거리가 가장 먼 A2 지역의 누적 대기시간이 가장 길다. <Table 7>, <Table 8>, <Table 9>은 각각 A1, A2, A3 지역의 배송 순서별 고객 노드의 배송 서비스 제공 시간이다. 드론 노드의 숫자가 많고, 드론 노드의 위치가 트럭의 경로에서 멀리 떨어져 있는 A2 지역에서 수리모형과 그리디 휴리스틱을 통해 얻는 고객 노드별 서비스 시간 차이가 가장 크며, A1 지역의 차이가 가장 작다.

Figure 14.

Timeline for Each Customer Node in the Delivery of A1, A2, A3

Table 7.

Service Time for Each Customer Node in the Delivery of A1

Table 8.

Service Time for Each Customer Node in the Delivery of A2

Table 9.

Service Time for Each Customer Node in the Delivery of A3

결론적으로, 지역 3개 배송 케이스 실험은 앞선 실험들의 결과 분석을 통해 설명한 내용을 포함한다. 트럭과 드론은 결합과 분리가 일어나기 때문에 트럭이 배송해야 하는 고객 노드가 밀집되어 있고, 거점과 직전에 방문한 고객 노드에서 가까운 고객 노드들에 트럭이 배송하며 상대적으로 멀리 떨어진 노드에 드론이 배송하는 것이 좋은 해를 제공한다. 운송수단의 경로에서 전체적인 방향성이 일정하게 유지되며 비슷한 방향일수록 좋은 해를 얻을 수 있다고 보이지만, 트럭과 드론의 결합 및 분리 과정에서 필연적으로 발생하는 대기시간의 감소를 위해 경로의 방향성이 변화할 수 있다. 드론으로만 배송해야 하는 드론 노드가 1개만 존재하는 경우 해상 드론으로 배송하는 것이 보다 효과적이며, 2개 이상인 경우 근처에 충분한 이/착륙 노드가 존재하지 않는 노드에 해상 드론이 배송하는 것이 좋은 해를 제공할 수 있다.

6.3 재난상황에서 3지역 배송 시나리오 분석

섬 지역에 재난상황이 발생하여 물자 보급, 지원 등이 필요한 상황을 가정하여 시나리오 분석을 진행하였다. 섬 지역에 발생할 수 있는 재난상황은 지진, 해일 등이 존재하며 이런 재난상황이 발생할 경우 인적 피해와 도로 파손, 주거지 파손과 같은 물적 피해가 발생할 수 있다. 이번 시나리오 분석에서는 섬 지역에 재난상황이 발생하였을 때 물품들의 배송에 대해 진행한다. 이번 시나리오에서 보급물품 준비에 필요한 시간은 3600초라고 가정하였는데, 이는 섬 지역에 재난상황이 발생하였을 때 의약품, 생필품, 식수, 비상식량 등 다양한 종류의 보급품과 인력 준비에 필요한 최소 시간이다.

A1, A2, A3, 3개의 지역에 재난상황이 발생하여 구호물품을 보급해야 하는 상황에서 본 논문의 수리모형을 3600초 동안 계산하였을 때 얻는 해와 제 5장에서 제시한 그리디 휴리스틱 단계를 따라 얻는 해의 노드별 서비스 시간은 <Figure 14>에 제시되어 있다. <Figure 14>을 보면 휴리스틱 1.6단계로 인해 각 고객 노드의 서비스 시간과 다음 노드로 떠나는 시간이 서로 달라지며, 트럭이 드론을 기다리는 대기 시간이 존재한다.

총 서비스 시간 합을 최소화하는 지역별 배송경로는 제 4장에서 제시한 수리모형을 통해 얻은 해, 제 5장에서 제안한 그리디 휴리스틱을 계산하여 얻은 해, 마지막으로 그리디 휴리스틱 해에 간단한 방법을 적용하여 개선된 해, 총 3가지 중 가장 좋은 해를 사용한다. 휴리스틱의 해를 기반으로 개선된 해를 얻는 방법은 제 5장의 그리디 휴리스틱 1.6단계에서 머리 노드와 꼬리 노드에 드론 경로를 추가하는 규칙으로 인해 제한되었던 경로를 변경하는 방식이다.

드론의 이/착륙으로 인해 발생하는 대기시간이 줄어든다면 기존 그리디 휴리스틱의 해보다 개선된 해를 구할 수 있어 간선 교환 방법(K-opt)의 개념을 이용하였다. 트럭 배송 노드와 드론 배송 노드는 기존의 휴리스틱과 동일하게 유지하며, 트럭의 경로도 유지하였다. 반면, 드론 착륙 노드의 경우 대기 시간을 최소화하도록 그리디 휴리스틱의 노드에서 다른 노드로 교환하고, 드론의 이륙 노드 및 드론 배송의 순서를 교환하였다. 드론 배송 순서의 교환이란 예를 들어 <Figure 14>을 보면 A3 지역 휴리스틱 경로에서 지상 드론으로 배송하는 순서는 TN7, DN2, DN3, TN2이다. 이 순서를 바꿔 가능한 모든 드론 배송 순서 별 목적함수 값을 비교하였다.

<Figure 15>에서 위의 과정을 통해 그리디 휴리스틱 해를 기반으로 각 지역의 개선된 배송경로를 제시한다. 착륙 노드 교환 과정을 통해 변경되는 부분은 <Figure 15(b)>를 보면 OD를 떠나 TN7에 배송한 드론이 그리디 휴리스틱의 해처럼 TN1에 오는 것이 아니라, 대기시간 최소화를 위해 TN3로 돌아온다. 이륙 노드를 바꿔 생기는 개선점은 <Figure 15(e)>와 <Figure 15(f)>에서 찾아볼 수 있는데, 그리디 휴리스틱의 경로는 A2 지역 노드 OD에서 드론으로 배송하는 노드가 TN7이었으나 <Figure 15(e)>에서도 DN3로 배송할 때 해의 값이 더 좋아지기 때문에 드론이 배송하는 순서를 변경하였다. <Figure 15(f)> 또한, 드론이 DN3에 배송하는 것보다 TN2에 먼저 배송하는 것이 해의 값이 더 좋아지기에 드론 배송의 순서를 변경하고, 드론의 이륙 노드도 바뀌었다.

Figure 15.

The Delivery Route in A1, A2, A3

A1, A2, A3 3지역의 모든 고객 노드에 배송하는 시간의 합을 구할 때 수리모형을 3600초 진행하여 얻은 값은 1911.74분이었고, 제시한 그리디 휴리스틱을 0.06초 계산하여 얻은 값은 2016.5분이었다. 그리디 휴리스틱의 해를 이번 장에서 서술한 교환 과정을 거쳐 개선하여 얻은 값은 1939.05분으로 제시한 그리디 휴리스틱을 이용하여 얻은 해보다 좋지만 수리모형을 3600초 진행하여 얻은 해보다는 좋지 않은 해를 얻었다. 수리모형과 휴리스틱, 간선 교환 방법의 개념을 적용하여 개선된 해라는 총 3가지 방법에 대한 목적함수 값 비교 그래프는 <Figure 16>이다.

Figure 16.

Comparison of Math Model, Heuristic, and Heuristic Solution Based Improved Delivery Route in A1, A2, A3

<Figure 16>에 제시된 것처럼 550초에 수리모형의 해가 간선 교환 방법의 개념을 적용하여 개선된 해보다 좋아지는데, 이는 구호물품 준비시간과 동시에 고려해야 한다. 따라서, <Figure 16>에서 교차가 일어나는 지점인 550초보다 구호물품 준비시간이 짧다면 개선된 해의 경로로 3지역에 배송을 하는 것이 보다 빠르게 모든 노드에 배송할 수 있는 방법이다.

<Table 10>은 3개의 섬 지역의 재난상황에 대한 시나리오를 보여준다. 지역의 수, 지역별 노드 수, 노드 간 이동시간 등 실험 설정은 지역 3개의 배송에 대한 실험과 동일하다. 재난 발생을 인지한 시간은 오전 9시이며 물품 보급 준비 및 출발에는 1시간이 걸린다고 가정한다. 수리모형의 경로, 그리디 휴리스틱의 경로, 간선 교환 방법을 적용하여 개선된 경로 모두 첫 번째 섬 지역 도착 예상 시간이 오전 10시 14분, 두 번째 섬 지역 도착 예상 시간이 오전 10시 56분, 세 번째 섬 지역 도착 예상 시간이 오전 11시 36분으로 같다. 이는 3가지 방법 모두 A3 지역, A1 지역, A2 지역순으로 배송할 때 모든 노드 배송 서비스 시간 합이 최소가 되기 때문이다.

Table 10.

Scenario Timetable for Disaster Situations in Three Island Areas

배의 도착 예상 시간과는 달리 배송 완료 예상 시간을 비교해보면 차이가 존재한다. 수리모형의 경로로 첫 번째 섬 지역을 배송할 경우 오전 11시 33분에 완료되어 배송에 1시간 19분이 소요될 것으로 예상된다. 개선된 경로 또한 수리모형의 경로와 마찬가지로 오전 11시 33분에 완료된다. 하지만 그리디 휴리스틱 경로를 통해 계산할 경우 배송 종료 시간이 오전 11시 57분으로 24분이 늦어 배송에 1시간 43분이 소요될 것이라 예측된다.

두 번째 섬 지역을 배송하는 경우도 수리모형 경로와 개선된 경로 둘 다 배송이 오전 11시 40분에 완료되어 배송에 44분이 필요하지만, 휴리스틱은 16분 늦은 오전 11시 56분에 배송이 완료되어 배송에 1시간이 소요된다. 세 번째 섬 지역은 이전과 달리 수리모형의 경로로 배송할 경우가 가장 빠르게 배송하며, 배송 완료 시간은 오후 1시 52분으로 배송에 2시간 16분이 필요하다. 그 다음으로 빠른 방법은 개선된 경로를 이용하여 배송하는 것으로, 배송이 오후 2시 19분에 완료되어 2시간 43분 동안 배송한다. 마지막으로 휴리스틱의 경로로 배송할 경우 오후 2시 57분에 배송이 완료되어 배송에 3시간 21분이 소요된다.

수리모형의 경로에서 모든 노드에 배송이 완료되는 예정 시간은 오후 1시 52분으로 재난 발생 시간인 오전 9시부터 4시간 52분만에 완료된다. 첫 번째 섬 지역 배송에 1시간 19분, 두 번째 섬 지역 배송에 44분, 세 번째 섬 지역 배송에 2시간 16분이 필요할 것으로 예상되며 평균적으로 하나의 섬 지역 배송 완료에 1시간 26분이 걸린다.

그리디 휴리스틱의 경로에서 모든 노드에 배송이 완료되는 예정 시간은 오후 2시 57분으로 재난 발생 시간인 오전 9시부터 5시간 57분만에 완료된다. 첫 번째 섬 지역 배송에 1시간 43분, 두 번째 섬 지역 배송에 1시간, 세 번째 섬 지역 배송에 2시간 21분이 필요할 것으로 예상되며 평균적으로 하나의 섬 지역 배송 완료에 2시간 1분이 걸린다.

개선된 경로에서 모든 노드에 배송이 완료되는 예정 시간은 오후 2시 19분으로 재난 발생 시간인 오전 9시부터 5시간 19분만에 완료된다. 첫 번째 섬 지역 배송에 1시간 19분, 두 번째 섬 지역 배송에 44분, 세 번째 섬 지역 배송에 2시간 43분이 필요할 것으로 예상되며 평균적으로 하나의 섬 지역 배송 완료에 1시간 35분이 걸린다.

본 논문의 수리모형의 목적함수는 개별 고객 노드의 배송 서비스 완료시간 총합을 최소화하는 것으로, 이는 모든 고객 노드에 물품을 빠르게 배송해야 하는 상황에 적용이 가능하다. 특히, 재난 및 응급상황과 같이 배송 일정이 빠를수록 좋은 상황에 적합하다. 종합하여 보면 <Table 10>과 같이 재난상황이 오전 9시에 발생하였고 인력소집 및 물품준비에 1시간이 필요한 경우, 가장 좋은 해를 제공하는 수리모형의 경로를 따라 배송하는 것이 개선된 해의 경로를 따라 배송하는 것보다 27분 정도 빠르게 배송을 완료한다. 이는 어떤 경로 탐색 방법을 활용하더라도 결과 도출 시간에 무관하게 1시간의 대기시간이 필연적으로 발생하기 때문이다.

7. 결 론

이 연구는 드론을 포함한 3종 운송수단의 배송경로 최적화 문제를 정의하고, 수리모형을 제안하며 간단한 그리디 휴리스틱 알고리즘을 제시하였다. 그리고 그리디 휴리스틱의 해를 기반으로 간선 교환 개념을 적용한 개선된 해를 구하여, 재난상황에서 3지역 배송경로 선택 시나리오 또한 제시하였다. 대부분의 드론을 활용한 배송 연구가 트럭과 드론이라는 운송수단 2개의 배송경로 최적화에 집중되었으나, 본 연구는 3면이 해양인 대한민국의 독특한 상황을 기반으로 운송수단을 추가하는 연구를 진행하였다. 지리적 특성을 가정한 임의 생성 데이터 실험을 진행하였고, 실질 기반의 데이터를 활용하여, 섬 지역의 수를 1~3개로 나누어 실험을 진행하여 수리모형과 휴리스틱 알고리즘을 비교하고 해를 분석하였고, 최적화 모형의 효용성을 제시하였다.

이 연구는 기존의 운송수단을 이용한 배송이 어렵거나 불가능한 섬 지역에 3종 운송수단을 포함하는 새로운 물류시스템을 제안하고 효율적으로 운용하기 위한 수리모형과 휴리스틱 알고리즘을 제시하여 실용성을 제고하였다. 그리고 기존의 운송수단을 이용한 배송이 어려운 지역의 응급상황, 재난상황 등 적용 가능한 범위가 넓기에 국내 실제 도서지역의 데이터를 기반으로 시나리오 분석을 수행하여 연구의 현실 활용성을 제시하였다.

추후 연구로는 운송수단의 수, 드론의 1회 비행에 배송 가능한 고객 노드 수와 같은 본 문제의 가정을 완화하여 다수의 드론을 활용한 배송, 드론이 이륙 후 여러 고객 노드에 배송하는 방법에 대한 연구 등이 가능하다. 고객 노드의 증가, 지역의 증가로 인해 데이터의 크기가 커졌을 때 제안한 휴리스틱 알고리즘의 추가적인 개선 또한 추후 연구로 가능하다. 운송수단의 종류를 배, 트럭, 드론이 아닌 다른 운송수단으로 변경하거나 확장한 연구 또한 추후 연구로 가능하다.

References

• Agatz, N., Bouman, P., and Schmidt, M. (2018), Optimization Approaches for the Traveling Salesman Problem with Drone, Transportation Science, 52(4), 965-981. [https://doi.org/10.1287/trsc.2017.0791]
• Aurambout, J. P., Gkoumas, K., and Ciuffo, B. (2019), Last mile Delivery by Drones: An Estimation of Viable Market Potential and Access to Citizens Across European Cities, European Transport Research Review, 11(1), 1-21. [https://doi.org/10.1186/s12544-019-0368-2]
• Berg, P. W., Isaacs, S., and Blodgett, K. L. (2016), U.S. Patent No. 9,305,280. Washington, DC: U.S. Patent and Trademark Office.
• Bouman, P., Agatz, N., and Schmidt, M. (2018), Dynamic Programming Approaches for the Traveling Salesman Problem with Drone, Networks, 72(4), 528-542. [https://doi.org/10.1002/net.21864]
• Boysen, N., Briskorn, D., Fedtke, S., and Schwerdfeger, S. (2018), Drone Delivery from Trucks: Drone Scheduling for Given Truck Routes, Networks, 72(4), 506-527. [https://doi.org/10.1002/net.21847]
• Chang, Y. S. and Lee, H. J. (2018), Optimal Delivery Routing with Wider Drone-delivery Areas Along a Shorter Truck-route, Expert Systems with Applications, 104, 307-317. [https://doi.org/10.1016/j.eswa.2018.03.032]
• Costa, F. G., Ueyama, J., Braun, T., Pessin, G., Osório, F. S., and Vargas, P. A. (2012, July), The use of unmanned aerial vehicles and wireless sensor network in agricultural applications, In 2012 IEEE International Geoscience and Remote Sensing Symposium, 5045-5048. [https://doi.org/10.1109/IGARSS.2012.6352477]
• Crişan, G. C. and Nechita, E. (2019), On a Cooperative Truck-and-drone Delivery System, Procedia Computer Science, 159, 38-47. [https://doi.org/10.1016/j.procs.2019.09.158]
• Dorling, K., Heinrichs, J., Messier, G. G., and Magierowski, S. (2016), Vehicle Routing Problems for Drone Delivery, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85. [https://doi.org/10.1109/TSMC.2016.2582745]
• Eksioglu, B., Vural, A. V., and Reisman, A. (2009), The Vehicle Routing Problem: A Taxonomic Review, Computers & Industrial Engineering, 57(4), 1472-1483. [https://doi.org/10.1016/j.cie.2009.05.009]
• Ghelichi, Z., Gentili, M., and Mirchandani, P. B. (2021), Logistics for a Fleet of Drones for Medical Item Delivery: A Case Study for Louisville, KY. Computers & Operations Research, 135, 105443. [https://doi.org/10.1016/j.cor.2021.105443]
• Guerriero, F., Surace, R., Loscri, V., and Natalizio, E. (2014), A Multi-obJective Approach for Unmanned Aerial Vehicle Routing Problem with Soft Time Windows Constraints, Applied Mathematical Modelling, 38(3), 839-852. [https://doi.org/10.1016/j.apm.2013.07.002]
• Ha, Q. M., Deville, Y., Pham, Q. D., and Hà, M. H. (2018), On the min-cost Traveling Salesman Problem with Drone, Transportation Research Part C: Emerging Technologies, 86, 597-621. [https://doi.org/10.1016/j.trc.2017.11.015]
• Hong, I., Kuby, M., and Murray, A. T. (2018), A Range-restricted Recharging Station Coverage Model for Drone Delivery Service Planning, Transportation Research Part C: Emerging Technologies, 90, 198-212. [https://doi.org/10.1016/j.trc.2018.02.017]
• Jeong, H. Y., Song, B. D., and Lee, S. (2019), Truck-drone Hybrid Delivery Routing: Payload-energy Dependency and No-Fly Zones, International Journal of Production Economics, 214, 220-233. [https://doi.org/10.1016/j.ijpe.2019.01.010]
• Kang, H. J. (2020), Drone Delivery Service Commercialization Plan Study, The Korean Journal of Air & Space Law and Policy, 35(2), 281-312. [https://doi.org/10.31691/KASL35.2.10.]
• Lee, S. and Choi, Y. (2016), Reviews of Unmanned Aerial Vehicle (drone) Technology Trends and its Applications in the Mining Industry, Geosystem Engineering, 19(4), 197-204. [https://doi.org/10.1080/12269328.2016.1162115]
• Li, Y., Zhang, G., Pang, Z., and Li, L. (2020), Continuum Approximation Models for Joint Delivery Systems Using Trucks and Drones, Enterprise Information Systems, 14(4), 406-435. [https://doi.org/10.1080/17517575.2018.1536928]
• Macrina, G., Pugliese, L. D. P., Guerriero, F., and Laporte, G. (2020), Drone-aided Routing: A Literature Review, Transportation Research Part C: Emerging Technologies, 120, 102762. [https://doi.org/10.1016/j.trc.2020.102762]
• Ma'Sum, M. A., Arrofi, M. K., Jati, G., Arifin, F., Kurniawan, M. N., Mursanto, P., and Jatmiko, W. (2013, September), Simulation of Intelligent Unmanned Aerial Vehicle (uav) for Military Surveillance, In 2013 international conference on advanced computer science and information systems (ICACSIS), 161-166. [https://doi.org/10.1109/ICACSIS.2013.6761569]
• Mateen, F. J., Leung, K. B., Vogel, A. C., Cissé, A. F., and Chan, T. C. (2020), A Drone Delivery Network for Antiepileptic Drugs: A Framework and Modelling Case Study in a Low-income Country, Transactions of The Royal Society of Tropical Medicine and Hygiene, 114(4), 308-314. [https://doi.org/10.1093/trstmh/trz131]
• Moshref-Javadi, M., Lee, S., and Winkenbach, M. (2020), Design and Evaluation of a Multi-trip Delivery Model with Truck and Drones, Transportation Research Part E: Logistics and Transportation Review, 136, 101887. [https://doi.org/10.1016/j.tre.2020.101887]
• Murray, C. C. and Chu, A. G. (2015), The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-assisted Parcel Delivery, Transportation Research Part C: Emerging Technologies, 54, 86-109. [https://doi.org/10.1016/j.trc.2015.03.005]
• Natalizio, E., Surace, R., Loscrì, V., Guerriero, F., and Melodia, T. (2013), Two Families of Algorithms to Film Sport Events with Flying Robots, In 2013 IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems, 319-323. [https://doi.org/10.1109/MASS.2013.40]
• Nenni, M. E., Di Pasquale, V., Miranda, S., and Riemma, S. (2020), Development of a Drone-supported Emergency Medical Service, International Journal of Technology (IJTech), 11(4). [https://doi.org/10.14716/ijtech.v11i4.3951]
• Nonami, K. (2016), Drone Technology, Cutting-edge Drone Business, and Future Prospects, Journal of Robotics and Mechatronics, 28(3), 262-272. [https://doi.org/10.20965/jrm.2016.p0262]
• Pahsa, A., Kaya, P., Alat, G., and Baykal, B. (2011, May), Integrating Navigation & Surveillance of Unmanned Air Vehicles Into the Civilian National Airspaces by using ADS-B Applications, In 2011 Integrated Communications, Navigation, and Surveillance Conference Proceedings, J7-1. [https://doi.org/10.1109/ICNSURV.2011.5935334]
• Rabta, B., Wankmüller, C., and Reiner, G. (2018), A Drone Fleet Model for Last-mile Distribution in Disaster Relief Operations, International Journal of Disaster Risk Reduction, 28, 107-112. [https://doi.org/10.1016/j.ijdrr.2018.02.020]
• Restas, A. (2015), Drone Applications for Supporting Disaster Management, World Journal of Engineering and Technology, 3(03), 316. [https://doi.org/10.4236/wjet.2015.33C047]
• Scott, J. E. and Scott, C. H. (2020), Drone Delivery Models for Medical Emergencies, Delivering Superior Health and Wellness Management with IoT and Analytics, 69-85. [https://doi.org/10.1007/978-3-030-17347-0_3]
• Sundar, K. and Rathinam, S. (2013), Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots, IEEE Transactions on Automation Science and Engineering, 11(1), 287-294. [https://doi.org/10.1109/TASE.2013.2279544]
• Tanzi, T. J., Chandra, M., Isnard, J., Camara, D., Sébastien, O., and Harivelo, F. (2016, July), Towards “drone-borne” Disaster Management: Future Application Scenarios, In XXIII ISPRS Congress, Commission VIII (Volume III-8), 3, 181-189, Copernicus GmbH. [https://doi.org/10.5194/isprsannals-III-8-181-2016]
• Tilak, G. (2020), Drones and Media Industry, RUDN Journal of Studies in Literature and Journalism, 25(2), 360-366. [https://doi.org/10.22363/2312-9220-2020-25-2-360-366]
• Yoo, W., Yu, E., and Jung, J. (2018), Drone Delivery: Factors Affecting the Public’s Attitude and Intention to Adopt, Telematics and Informatics, 35(6), 1687-1700. [https://doi.org/10.1016/j.tele.2018.04.014]