논문리뷰 - Coordinated logistics with a truck and a drone

여기서 last-mile delivery의 수요가 증가할 것이라는 언급이 있다. 라스트 마일이란 상품이 최종 목적지까지 배송되기 위한 과정으로 상품을 개인 소비자에게 직접 전달하기 위한 배송 마지막 구간을 의미한다. 즉, 무인정찰기를 배송시스템에 도입하여 하늘과 도로를 통해 배송함으로써 차세대 물류 시스템을 수행할 것이라는 전망이다. 무인항공기 기반 배송 시스템은 장단점이 명백하게 있는데 일단 드론은 운송 비용이 낮고 사람의 개입없이 운행할 수 있으며 도로 교통에 영향을 받지 않기 때문에 빠르게 운행할 수 있다. 그러나 운반 용량이 매우 작고 이동 반경이 짧으며 충전을 자주 해야한다.

위의 그림은 트럭으로만 배달한 경우, 드론으로만 배달한 경우, 트럭과 드론으로 배달한 경우의 배송경로를 나타낸다. 드론은 트럭의 속도보다 약 4배 정도 빠르다고 가정하였고 (c)에서 볼 수 있듯이 어느 한 가지로 배송하는 것과는 배송 경로의 차이가 있음을 알 수 있다.

이 논문의 목적은 드론과 트럭을 함께 사용하여 배송하는 것의 효율성을 판단하는 것이다. 이러한 실제 시스템 중 하나가 HorseFly이다. 실제로 어느 정도까지 서비스 품질을 향상시킬 수 있는지 파악되지 않았기 때문에 수학적으로 얼마나 개선을 실현시킬 수 있는지 언급한다.

이는 TSP의 일반적인 경우이므로 최적으로 풀기 매우 어렵다. 그러므로 문제를 작은 파라미터 집합으로 줄이고 이러한 파라미터가 문제의 결과에 어떻게 영향을 미치는지 결정한다. 고객은 유클리드 평면에서 확률 밀도에 따라 분포한다고 가정한다. 이 논문은 특정 문제 사례에 대한 것보다는 인구 밀도에 따라 한 지역에서 많은 고객이 서비스를 받을 때 장기적인 행동에 대해 신경을 쓴다. 본질적으로 VRP 모델의 사례로 생각할 수 있다. 서로 정반대되는 장단점을 가진 두 종류의 차량을 최적으로 조정하는 문제로 생각할 수 있다.

$n$개의 고객이 있다고 가정하며 트럭의 속도는 $\phi_0$, 드론의 속도는 $\phi_1$로 나타낸다. ($\phi_0<\phi_1$) compact planar region을 $\mathcal{R}$, $\mathcal{R}$에서의 loop를 $\mathcal{L}$, 모든 loop $\mathcal{L}$의 집합을 Loop($\mathcal{R}$)이라 하면 $d(x, \mathcal{L})$를 다음과 같이 $x$와 loop $\mathcal{L}$ 사이의 거리로 나타낼 수 있다. $$ d(x, \mathcal{L})=\min _{x^{\prime} \in \mathcal{L}}\left\|x-x^{\prime}\right\| $$ 이는 일반적인 유클리드 거리를 나타내고 {1,...$n$}의 순열 집합을 $S_n (\sigma \in S_n)$이라 하면 항공기에서 집합 $S$의 $\epsilon$-neighborhood는 다음과 같이 $N_{\epsilon}(\mathcal{S})$로 쓰인다. $$ N_{\epsilon}(\mathcal{S})=\left\{x \in \mathbb{R}^{2}: \min _{x^{\prime} \in \mathcal{S}}\left\|x-x^{\prime}\right\| \leq \epsilon\right\} $$ 먼저 앞서 언급한 horsefly routing problem을 공식적으로 정의한다. 트럭 1대와 드론 1대에 대해 $p_1,...,p_n$을 포인트의 집합이라 한다면 다음을 만족하는 최적 솔루션이 $p_1,...,p_n$의 최적 horsefly tour이다.

아래 그림은 $p_1,...p_6$의 지점에 대해 $\phi_1/\phi_0=3/2$ 인 문제와 $\phi_1/\phi_0=3$인 문제의 horsefly 경로 문제의 솔루션이다. $x_1$을 임의의 출발점으로 정의하면, 두 경로 모두 $\sigma = {1,3,5,2,6,4}$이다.

$\mathcal{L}$의 $\epsilon$-neighborhood는 Route의 내부(inner) 부분인 $R_{\text{in}}$와 외부(outer) 부분인 $R_{\text{out}}$을 가진다. 아래 그림의 (a)는 $R_{\text{in}}$과 $R_{\text{out}}$을 나타낸다. 색칠된 부분과 빗금친 부분이 모두 $R_{\text{out}}$이므로 면적 Area($R_{\text{out}}$) = $\pi \epsilon^{2}+\epsilon \ell$, 둘레 perimeter($R_{\text{out}}$) = $\ell + 2\pi\epsilon$이다. (b)는 내부 loop $\mathcal{L}_\epsilon^{\prime}$ 과 모든 $\epsilon^{\prime}$에 대해 $R_{\mathrm{out}}^{\prime} \subseteq R_{\mathrm{in}}$ 임을 보여준다.

아래 그림의 (a)와 (b)는 loop $\mathcal{L}$을 가지는 지역 $\mathcal{R}$을 통과하는 지그재그(zig-zagging) 모양과 나선형(spiralling)모양의 투어를 나타낸다. 수요 밀도가 불균등(non-uniform)일 때, (c)와 (d)에서 같이 최적 loop는 밀도가 더 높은 지역에 집중되어야 한다.

아래 그림에는 $N$=16인 사각형 패치 $\mathcal{P}_i$가 있다. (a)와 (b)는 하나의 loop를 패치의 모양에만 의존하는 방식으로 항상 다수의 loop로 분해할 수 있음을 보여준다. (c)와 (d) 또한, 패치의 모양에만 의존하는 방식으로 하나의 loop로 loop들의 집합을 항상 결합할 수 있음을 보여준다.

[참고] Claim9. 위의 식 (1)의 lower bound가 문제의 최적 목적 값이다.

아래 그림은 Claim9의 스케치이다. (a)와 같이 문제(1)의 솔루션에서 시작하고 (b)와 같이 $x_i^{\prime}$이 구성된다. 그리고 나서 (c)처럼 $x_i^{\prime}$들을 통해 투어를 얻는다.

이 논문에서는 2가지 계산 실험을 하는데 첫 번째 실험은 계수 $\alpha$(논문의 (12)와 (???)에서 사용됨)를 추정하기 위해 사용하는 균일하게 분포된 수요를 가지는 unit square에서 이루어진다. 두 번째 실험에서는 $\alpha$의 추정치를 사용하여 균일하지 않은 분포에 따른 수요와 도로망에서의 실시간 주행 정보가 사용될 때의 효율성 향상에 대해 예측을 한다. 아래 그림은 두 개의 다른 horsefly 투어를 나타낸다. (a)는 $k$=1, $\phi_1$=1.5이고 (b)는 $k$=3, $\phi_1$=3이다. (여기서 $k$는 무인항공기의 개수이다.) $p_i$의 다른 색깔 (검정, 회색, 흰색)은 3개의 무인항공기 중 어느 것이 해당 지역을 방문하는지를 나타낸다.

아래 그림에서 (a)는 캘리포니아(California) 주 패서디나(Pasadena)의 지도를 보여주고 (b)는 패서디나에 위치한 모든 1734 인구조사(census) 블록의 중심으로 구성된 초기 데이터 집합을 보여준다. (c)는 그 중심에서 샘플링한 $n$=25인 지점의 도로망에 대한 TSP 투어를 나타내고 (d)는 2단계 휴리스틱(논문 4.1참고)을 사용하여 계산한 horsefly tour를 보여준다.

아래 12개 차트는 각각 특정한 수의 고객 $n$과 무인항공기 속도 $\phi_1$에 대해 수행한 실험이다. 검은색 막대는 트럭 한 대가 $n$개의 고객을 방문하는 데 걸리는 시간(시간)을 나타낸다. 회색 막대는 트럭과 무인항공기가 horsefly 투어를 할 것으로 예상되는 시간을 나타낸다. 흰색 바는 트럭과 무인정찰기가 horsefly 투어를 수행하는 데 소요되는 실제 시간을 나타낸다.

아래 차트는 무인항공기 개수 $k$와 속도 $\phi_1$에 대해 수행한 실험이다.

실험 결과 트럭만 사용하는 것보다 트럭과 무인항공기를 동시에 사용했을 때 시간이 더 적게 걸리는 것을 확인할 수 있다.

논문 결과는 다음과 같이 정리할 수 있다.

• 무인항공기와 트럭 배달의 효율성은 각각의 속도 비율의 제곱근에 비례한다.
• True globally 최적 솔루션이 아니라 트럭과 무인항공기 사이의 조정된 경로를 계산하기 위해 휴리스틱한 방법을 사용함.(분석의 weak point 중 하나)
• 이 논문에서 제시된 문제에 대한 솔루션을 찾는 테크닉을 현재까지 알지 못하지만, 물류에 대한 무인항공기의 관심이 증가함에 따라 향후 몇 년 내에 그러한 기술들이 가능할 것으로 예상함.

Cite