1. 서 론1)

우리는 지난 몇 년간 광범위한 응용 분야에서 무인 항공기(UAV)의 인기와 활용을 목격해 오고 있다[1]. 드론은 군사, 촬영, 농업, 재난 및 긴급구조, 배송 등 다양한 분야에서 다양한 목적으로 널리 응용되고 있다. 특히 홍수나 지진 등 자연 재해 또는 분쟁 피해 지역 등에서 식량이나 식수, 긴급 구호품 전달 등 재난 구호 활동에도 이미 중요한 역할을 하고 있다[6]. 드론 배송 시장 또한 폭발적으로 성장하고 있다. Market.us에 따르면, 글로벌 드론 패키지 배송 시장 규모는 2023년에 약 10억 달러에서 2033년에는 약 340억 달러로 연평균 성장률이 약 42.3%에 달할 것으로 예상되고 있다[11].

드론으로 널리 알려진 무인항공기를 이용한 배송은 트럭이나 이륜차와 같은 전통적인 배송 수단의 접근성을 저해하는 교통 상황이나 다양한 장애물을 우회하여 고객이나 특정 위치로 직접 물품을 배송함으로써 배송 시간을 크게 단축시킬 수 있는 혁신적인 서비스이다. 배송 시간 단축을 통한 라스트 마일 물류비용 절감 효과가 크며, 도로 상황이나 지형의 영향을 거의 받지 않아 유연한 배송이 가능하다. 드론은 현대 물류 환경에서 혁신과 효율성을 높일 수 있는 중요한 요소 중 하나이며, 물류 라스트 마일에서 가장 뜨거운 이슈 중 하나임은 의심의 여지가 없다[2]. 드론 기술이 발전함에 따라 라스트 마일 배송에서 드론을 이용하여 기존의 배송 방법을 보완할 수 있게 되었다[4]. 특히 드론은 도서 및 산간 지역과 같이 기존의 도로를 통한 접근이 어렵거나, 재난 지역과 같이 긴급하게 물자를 배달해야하는 상황에서 매우 효과적으로 사용될 수 있다.

드론 배송에는 멀티로터 타입의 VTOL 드론이 널리 활용되고 있다. VTOL 드론은 수직이착륙이 가능하기 때문에 활주로가 불필요하며 좁은 공간에서도 이착륙이 가능한 장점이 있다. 이것은 드론이 배송 지점에 더욱 가까이 접근하는 것을 가능하게 해 준다. 실제 드론 배송 서비스 운영을 위해서는 VTOL 비행경로의 이륙 및 착륙구간과 실제 순항하는 비행구간의 식별이 매우 중요한 요소라 할 수 있다. 그 이유는 출발점이나 배달점과 같은 노드에서는 이륙 또는 착륙 비행을 하는 동안 드론이 해당 노드의 지표면에서부터 상공까지 점유하기 때문이다. 실제 이륙과 착륙 구간은 드론 비행에서 위험한 구간에 속하기 때문에 비행경로에서 해당 구간들을 명확히 식별하는 것은 드론 배송의 안전성 확보를 위해서도 중요하다. 그러나 이러한 드론 배송이나 비행과 관련하여 경로를 다루는 많은 연구들에서 VTOL 비행경로가 실제 비행 궤적을 잘 표현할 수 있는 형태로 다루는 연구는 많지 않다. 따라서 본 연구에서는 드론 배송에 널리 활용되는 VTOL 드론의 수직 이착륙 비행 특성을 고려한 드론 비행경로 모델의 구조적인 표현에 대한 정의를 제공한다. VTOL 비행경로의 특징인 이륙과 착륙구간을 효과적으로 표현하기 위해서 그래프 모델을 기반으로 중첩된(nested) 형태의 그래프 구조를 이용하였다. 또한 해당 드론 비행경로 모델의 구조적 정의를 기반으로 실제 드론 비행에서 중요하게 사용되는 다양한 시간 속성과 계산 방법을 살펴본다. 이처럼 본 논문에서는 드론 배송 서비스 제공을 위한 주요 과정들을 포괄적으로 살펴보면서 VTOL 비행경로모델의 구조와 시간 속성에 대해 자세히 소개한다. 이러한 경로 모델의 구조와 속성 정보를 이용하여 드론 배송 경로의 가시성 확보와 함께 배송서비스 제공을 위한 전반적인 운영 계획의 수립이나 배송 모니터링, 나아가 드론 비행 경로상에서 발생할 수 있는 교차점이나 충돌 여부 식별 및 충돌 방지 전략 수립 등 다양한 활용이 가능할 것으로 예상된다.

다음 제2장에서는 관련 연구들을 간략히 살펴보고, 제3장에서 드론 배송 서비스에 대해 포괄적으로 소개한 다음 제4장에서 VTOL 드론 비행경로 모델의 정의를 기술한다. 제5장에서는 경로 모델이 가지는 다양한 시간 속성들을 살펴보고 제6장에서 결론을 맺는다.

2. 기존연구

드론의 활용은 전 세계적으로, 특히 유럽 국가들에서 빠른 속도로 발전하고 있으며, 드론의 용도는 매우 다양하다[5]. 비가시권에서의 무인 자동비행을 위한 비행미션 정보가 드론에게 전달되면, 드론은 전달받은 비행경로 정보를 따라 자동 비행을 하게 된다. 이처럼 사전에 정의된 비행 경로를 자동으로 비행할 수 있다면 그 응용 범위는 크게 넓어진다[12].

라스트 마일 배송 서비스에서 드론을 활용하기 위한 노력들이 특히 두드러지는 만큼 드론 배송과 관련된 다양한 연구들이 진행되고 있고, 배송 경로 계획 및 경로 최적화에 초점을 맞춘 연구들 또한 활발히 진행되고 있다. 드론 배송경로 계획은 출발지와 목적지 사이의 최적 경로를 찾기 위하여 UAV에서 탐구해야 할 가장 중요한 문제 중 하나이기 때문이다. 이러한 경로 계획 문제는 과거에도 많은 연구들이 진행되어 왔고 주로 선형계획, 수리 최적화 및 메타 휴리스틱 모델 등 다양한 알고리즘들을 활용해 왔다[1]. 그러나 이러한 드론 배송 경로 계획이나 경로 최적화 문제를 다루는 다양한 연구들[3, 7, 8, 13, 14, 16]에서도 VTOL 비행 특성을 고려한 드론 비행경로의 구조적 표현에 대해서는 구체적으로 다루고 있지 않다. 또한 배송 서비스 운영 관점에서 제한된 버티포트(vertiport) 리소스를 두고 경쟁하는 eVTOL UAV들에 대한 도착순서 지정 및 스케줄링에 대한 최적화 문제를 다루는 연구[10]에서도 실제 운영되는 드론의 경로에 대한 구조적인 표현은 제공하지 못하고 있다. 특히 드론의 비행경로에서 VTOL 비행 특성을 고려하여 이륙 및 착륙구간의 구조적인 구분을 잘 표현하거나 모델링된 연구는 찾아보기가 쉽지 않다.

드론 비행 및 운영과 관련된 많은 연구들에서도 그래프 모델을 이용하여 드론 경로나 궤적을 표현하고 있다. 드론 라우팅이나 경로 계획 등 여러 최적화 문제에서도 경로 구조를 그래프의 정점과 간선을 이용하여 표현하며, 이는 보통 지상에서 이동체의 경로 표현에 효과적이다. 그러나 차량과 같이 도로를 기반으로 2차원 평면상에서의 경로는 X-Y 두 좌표를 이용하여 표현하기에 충분하지만, 3차원 공간을 비행하는 드론 경로는 3차원 구조로 표현되어야 할 필요가 있다. 그러나 정점과 간선으로 구성된 그래프 모델의 일반적인 정의만으로는 이를 표현하기에 부족하다. 따라서 본 연구에서는 중첩된 그래프 구조를 이용하여 VTOL 드론 비행 특성을 잘 반영할 수 있는 경로의 표현이 가능한 정의를 제공하고자 한다. 그래프에서 정점은 노드, 포인트, 버텍스 등으로, 간선은 아크, 링크, 애로우 등으로 다양하게 사용되나 본 연구에서는 노드와 링크를 사용하기로 한다.

3. 드론 배송 서비스 개요

본 장에서는 VTOL 드론 비행경로 구조를 다루기 전에 드론 배송 서비스에 대하여 간략하지만 포괄적으로 살펴본다. 동시에 본 논문에서 초점을 맞추어 설명하는 드론 배송 서비스 범위에 대해서도 드론 배송프로세스와 함께 살펴본다. 드론 배송이라는 용어 자체는 우리에게 친숙하더라도 실제 그 내용과 범위는 비교적 넓은 편이다. 따라서 드론 배송 서비스 제공을 위해 현실적으로 고려되어야 하는 주요 요소들을 간략하게 살펴보고자 한다.

드론 배송 서비스의 가장 기본 형태는 한 대의 드론이 출발점을 출발하여 하나의 배달점을 방문하고 다시 출발점으로 돌아오는 point-to-point 배송이며, 다수의 배달점을 방문하고 출발점으로 돌아오는 TSP(Traveling Salesman Problem) 형태가 일반적인 라스트 마일 배송 유형이라 할 수 있다. 라스트 마일 배송 서비스에서도 운영되는 드론의 수나 한 대의 드론이 방문 가능한 배달점 개수에 따라 다양한 형태로 구분될 수 있다. 본 논문에서는 한 대의 드론이 하나 이상의 배달점을 방문하는 다지점 배송 서비스를 예시로 설명하기로 한다.

3.1 드론 배송 서비스 네트워크 구성

우편이나 택배 또는 유통업체 등 다양한 사업자들이 드론을 이용하여 자사의 물품을 신속하게 배송하기 위한 다양한 시도와 노력을 기울이고 있다. 드론을 이용한 배송 서비스 제공을 위해서는 우선 드론 배송 서비스 네트워크 구성이 필요하다. 이때 서비스 제공자들은 자사의 배송 서비스 제공이 가능한 특정 위치 또는 지역을 검토해야 한다. 드론 배송 서비스 네트워크는 기본적으로 서비스 출발점과 서비스를 제공받는 배달점으로 구성될 수 있다. 이러한 지점들의 위치는 서비스 제공자의 비즈니스 영역이나 다루는 물품 유형에 따라서 기존에 존재하는 자사의 물류 창고나 상점 등을 서비스 출발점으로 하여 서비스 제공이 가능한 대상 배달점들을 선정할 수 있다. 이와 반대로 서비스 제공 수요가 발생되는 지점을 고려하여 적절한 위치에 새로운 서비스 출발점을 구축할 수도 있다.

최근에는 수소에너지 등을 동력원으로 이용하는 드론도 활발히 소개되고 있지만 아직은 배터리가 널리 이용되고 있다. 드론의 비행거리나 운용시간은 배터리 용량에 비례하여 증가할 수 있겠지만 배터리 무게와 트레이드 오프(trade-off)를 고려하면 현실적인 비행시간이나 거리는 제한적일 수 밖에 없으며 아직은 대략 30분에서 1시간 이내 또는 약 10km 내외의 수준으로 알려져 있다. 2022년 미국 캘리포니아 록포드(Rockford)와 텍사스 컬리지 스테이션(College Station)에서 시범적으로 드론 배송 서비스를 시작한 아마존 Prime Air 또한 자사의 풀필먼트 센터를 출발점으로 하여, 약 5km 이내의 범위를 대상으로 약 30분 이내 배송 완료를 목표로 하였다[9]. 이런 점들을 고려하면 아직은 그 운용 범위가 한정된 영역 내에서 구성된다.

출발점과 함께 배달점 결정도 필요하고 이 역시 간단하지 않다. 우편이나 택배 배달과 같이 대부분의 주소지를 대상으로 서비스를 제공하는 것은 아직 시기상조라 할 수 있다. 큰 이유는 우선 드론의 실질적인 이륙과 착륙을 위한 헬리포트(heliport) 또는 버티포트 등과 같은 시설 측면에서의 충분한 공간 확보가 필요하기 때문이다. 또한 배송 서비스 제공을 위해 일정 수준의 수요가 필요하고 발생된 수요를 충분히 소화할 수 있는 배송 자원의 제약 등도 고려되어야 한다. 이런 이유들로 인해 아직은 여러 시범 서비스들이 인구가 밀집한 도심지보다 농어촌이나 도서산간 지역과 같이 배달점 밀도가 낮은 지역들에서 우선적으로 추진되고 있다. 이렇게 드론 터미널과 같이 출발점에 해당하는 하나의 배달거점을 중심으로 비행 가능한 다수의 배달점들을 포함하는 일정한 서비스 가능 영역 내에서 그 운영 범위가 결정될 수 있다.

<Figure 1>에서 (a)는 실제 지도를 기반으로 드론 배송 서비스 제공을 위하여 6개의 노드로 구성된 드론 배송 서비스 네트워크(이하 배송 네트워크)에 대한 하나의 예시이다. 이러한 배송 네트워크는 지형적인 구조와 고정된 장애물 그리고 서비스 수요 등을 고려해 다양한 형태로 구성될 수 있고, (b)와 같이 그래프 모델을 이용하여 배송 네트워크 구조의 간단한 표현이 가능하다. 본 논문에서는 해당 배송 네트워크를 예제로 이용하여 설명을 이어나가기로 한다. (b)의 배송 네트워크 그래프 G에서 노드들은 출발점 또는 배달점과 같이 드론의 수직이착륙이 가능한 지점들을 표현한다. 그리고 두 개의 노드를 연결하는 링크는 두 노드 사이의 비행 구간을 의미한다. 예시와 같이 배송 네트워크 그래프 G에서 6개의 노드들은 집합 V = {BP-01, DP-01, DP-02, DP-03, DP-04, DP-05}와 같이 구성된다. 여기서 노드 “BP-01”은 특별히 배달거점(base point)을, 나머지 노드들은 배달점(delivery point)을 의미하는 라벨이다. 이처럼 G는 하나의 고정된 배달거점과 5개의 배달점으로 구성된 배송 네트워크를 표현하게 된다.

실제 환경에서는 하나 이상의 배달거점이 존재할 수 있고 트럭과 드론을 함께 운용하는 형태와 같이 배달거점이 가변적으로 운영될 수도 있지만 본 논문에서는 일반적인 배송 형태에 초점을 맞추어 설명한다. 그리고 배달거점과 배달점에 존재하는 이착륙 포인트 개수도 고려하지 않는다. 이는 운영 단계에서 동시에 운영 가능한 자원의 제약에 해당하며 이착륙 포인트가 많을수록 운용의 복잡성은 높아지지만 운용 능력은 증가할 수 있을 것이다. 이처럼 배송 네트워크 환경은 복잡하고 다양하게 구성될 수 있고 대부분은 드론 배송 서비스 제공자에 의해 구체적인 실현이 필요하다.

3.2 드론 비행경로의 설정

배송 네트워크 G의 두 지점을 연결하는 하나의 경로는 사전에 충분한 시험 비행을 통해 안전성이 검증된 경로로 설정될 필요가 있다. 지상에서는 도로를 따라 이동 경로가 결정되지만, 드론의 경우 비행금지구역 또는 다양한 장애물 등을 회피하면서 효율적인 비행을 위해 보통 최단거리인 직선 형태의 경로로 설정된다. 비행경로와 도로의 가장 큰 차이는 고도 정보이고, 3차원 공간을 비행하기 때문에 고도를 조정하는 것으로 일부 정적인 장애 요소를 회피할 수도 있다. 일반적으로 이륙 후 배달점까지의 비행경로는 순항을 위해 동일 고도나 일정한 비행 속도를 유지하는 것이 배터리 소모 측면에서 효율적이다. 그러나 배달점이 높은 산에 위치하거나 출발점과 배달점의 고도 차이로 인해 상승(climb) 또는 하강(descent) 비행 구간이 포함되기도 한다. 따라서 드론 비행이 가능한 고도 등 관련 법규의 준수와, 비가시권 및 자동비행 중 발생할 수 있는 다양한 위험으로부터의 안전 문제도 고려해야하기 때문에 사전에 충분한 시험 비행을 통해 안전하고 효율적인 경로를 설정하게 된다.

또한 두 지점 사이의 비행경로는 비행 방향으로 구분하여 단선 및 복선으로의 구성 여부도 서비스 제공자가 결정할 수 있다. 만약 복선으로 구성한다면, 두 노드 v_i와 v_j를 연결하는 링크를 e_ij라 할 때, e_ij ≠ e_ji이며, 이는 일반적인 열차의 복선 선로와 유사하게 이해할 수 있다. 이러한 요소들은 앞에서 언급한 배달거점 및 배달점에서의 이착륙 포인트 개수 결정과 연계하여 고려될 수 있는 문제이다. 이처럼 사전에 잘 설정된 비행경로는 배송이 발생할 때마다 배송경로 생성에 반복적으로 사용되고, 비행미션으로 드론에 전달되어 자동비행에 활용된다. 여기서 두 지점 사이의 최단 경로 탐색 문제 등은 그 동안 활발하게 다루어져 왔고 지금도 활발하게 연구가 진행되는 분야이며 본 연구에서 주요하게 다루는 대상은 아니다.

이렇게 출발점 및 배달점 노드, 그리고 각 노드 사이의 비행경로인 링크를 통해 배송 네트워크의 물리적 구조가 구성된다. 이는 정의 단계로 배송경로는 주문이 발생한 이후 결정되어 생성된다. 다음절에서는 이러한 배송미션 생성에 대해 소개한다.

3.3 드론 배송미션의 생성

구조적으로 구성이 완료된 드론 배송 서비스 네트워크 G에서 사전에 설정된 각 구간별 비행경로들은 배송서비스 제공을 위한 인프라에 해당한다. 실제 배송을 위한 주문이 발생되어야 해당 배송을 위한 비행경로가 생성된다. 여기서 서비스 제공자에 의해 단일 지점(single-point) 배송 또는 다지점(multi-point) 배송과 같은 서비스 운영 형태도 결정될 수 있다. 서비스 형태에 따라 배송 미션도 달라진다. 긴급한 배송의 경우 신속성을 최우선으로 고려하여 한 대의 드론이 하나의 주문을 처리하는 것이 서비스의 주목적일 수 있다. 이때 출발점과 하나의 배달점 사이의 경로를 비행하기 위한 미션이 생성된다. 그럼에도 불구하고 효율성 측면에서 한 대의 드론으로 2~3개 정도의 주문을 함께 처리하기 위한 다지점 배송 서비스도 고려될 수 있다. 이는 차량을 이용한 일반적인 배송 형태와 같으며, 배송 물품의 중량과 배터리 용량에 따른 비행시간 및 비행거리 에 따라 결정될 수 있는 문제이다. 따라서 비교적 가벼운 물품을 대상으로 배송 서비스를 제공하는 업체들의 경우 주문이 발생하는 상황에 따라 다지점 배송 서비스 운영도 비용-효율성 측면에서 고려할 수 있을 것이다.

배송미션의 생성은 일반적인 배송 환경에서 한 대의 차량으로 처리해야 하는 물품이 주어졌을 때 운행 거리나 시간, 또는 비용 최소화 등을 위한 TSP, 또는 운행 가능한 차량 수 등의 자원 제약이 존재할 때 VRP(Vehicle Routing Problem) 등 다양한 목적함수를 가지는 최적화 문제와 유사하며 널리 다루어지고 있는 분야이다. 그러나 본 논문에서는 일반적인 TSP나 VRP처럼 당일 배송 주문이 사전에 주어지는 것이 아니라 랜덤하게 발생하는 서비스 유형으로 설명 범위를 한정하고자 한다. 그 이유는 드론 배송 서비스의 주요 장점 중 하나인 신속성에 초점을 맞추기 위함이다. 실제 드론 배송 서비스를 제공하는 아마존이나 스타벅스, 도미노 피자 등과 같은 업체들은 당일 배송 목록이 사전이 주어지는 형태가 아니다. 따라서 먼저 발생된 주문을 먼저 처리하기 위한 FCFS 형태의 배송에 초점을 맞추어 소개한다. 업체별로 주문이 발생되는 특정 분포를 가정하지는 않았지만 일정 수준에서 현실적으로 처리가 가능함을 전제로 설명한다.

실제 드론 배송은 배터리 용량에 따른 비행시간과 적재 물품의 중량 등과 같은 제약들을 고려하면, 한 번에 방문 가능한 배달점은 2~3곳 이내가 현실적이다. 하나의 주문 발생 후 적당히 짧은 시간 이내에 새로운 주문이 발생한다면 한 대의 드론으로 배송할 수 있지만, 하나의 주문 발생 이후 계속해서 다음 주문을 기다릴 수는 없다. 이는 주문이 발생될 때의 상황과 주문을 처리하는 담당자의 경험적 판단에 의해 적절하게 결정될 수 있다. 이때 배달점이 2곳 이상이면 어떤 배달점을 먼저 방문할 지에 대한 순서만 결정되면 된다. 하나의 배송에서 방문 지점 수가 3개 이하이며, 생성 가능한 경로의 수가 매우 적기 때문에 간단히 해결되는 문제이다. 예를 들어 배달거점을 출발하여 두 곳의 배달점 v₁과 v₂를 방문하고 다시 출발점으로 돌아오는 배송의 경우 생성 가능한 경로는 단 두 가지만 존재한다. 이때 두 가지 경로는 보통의 경우 거리가 같기 때문에 비행속도나 기타 비용에 영향을 주는 다른 변수값의 차이가 없다면 두 해(solution)의 목적 함수 값은 같을 것이고 어떤 솔루션을 선택해도 무방할 것이다.

그러나 배송 네트워크에서 하나 또는 그 이상의 배송이 완료되지 않은 상황에서는 새로운 배송이 발생했을 때 그 경로는 달라질 수 있다. 그 이유는 배달거점이나 배달점 노드 또는 비행경로 링크를 공유하게 되면서 충돌이 발생할 수 있기 때문이다. 이런 상황을 고려하기 위한 하나의 수단으로 본 논문에서 소개하는 VTOL 비행 특성을 표현한 비행경로 모델의 정의와 시간 속성은 매우 유용하게 활용될 수 있다. 따라서 VTOL 드론 비행경로 모델에 대한 구조적 정의를 다음 4장에서 소개하고, 해당 경로가 가지는 다양한 시간 속성을 5장에서 자세히 설명하기로 하고, 드론 배송 프로세스의 흐름을 간략히 소개하는 것으로 본 3장을 마무리한다.

3.4 드론 배송 프로세스 흐름

앞서 설명한 내용들을 기반으로 하나의 다지점 배송 서비스 처리를 위한 프로세스는 <Figure 2>의 예시와 같은 업무들의 흐름으로 모델링될 수 있다. 먼저 출발점에서의 배달준비, 이륙 후 배달점으로 비행, 배달점 도착 후 물품 전달, 다시 출발점으로 회귀, 출발점 도착 후 배달완료와 같은 이해하기 쉬운 업무들로 구성될 수 있다. 물품 수취인에게는 물품이 전달되면 배송이 완료되지만, 서비스 제공자의 드론 배송 프로세스는 드론이 출발점으로 무사히 회귀하는 것으로 완료된다. 이러한 프로세스 모델은 드론의 비행경로와 일치하며 배송 서비스 운영 단계에서 활용 및 관리될 수 있다.

이처럼 사전에 잘 정해진 비행경로를 이용하여 드론의 자동비행으로 배송 서비스 제공을 위한 일반적인 과정과 주요 특징 및 고려사항들을 간략하게 살펴보았다. 이를 통해서 드론 배송 서비스 제공을 위한 환경이 매우 복잡하고 다양함을 이해할 수 있다.

4. VTOL 드론 비행경로 모델

본 장에서는 3장에서 소개한 VTOL 드론의 비행 특성을 고려한 비행경로 모델을 소개한다. 다양한 분야에서 여러 형태로 드론비행 경로가 활용되고 있지만, 앞서 언급한 것처럼 1~3개 정도의 다지점 배송 서비스 유형을 구체적인 예시로 활용한다.

4.1 VTOL 드론비행경로모델

한 대의 드론이 주어진 다지점 배송을 수행하기 위한 배송미션(delivery mission) d = {1, 2, ...}가 생성된다. 드론 배송 d의 수행을 위하여 드론은 배달거점에서 이륙하고, 첫 번째 배달점 상공에 도착하여 착륙을 진행한다. 착륙이 완료되면 물품 전달 및 적재함 정리 등 업무 처리 시간이 소요된다. 해당 배송이 완료되고 아직 배송이 남은 경우 다시 이륙하여 다음 배달점으로 비행하게 된다. 이런 과정의 반복을 통해 모든 배송 업무 처리가 완료되면 출발지인 배송거점으로 회귀하게 된다.

이처럼 주어진 m개의 배달점을 정해진 순서대로 방문하고 다시 배달거점으로 되돌아오는 비행을 고려해 보자. 배송미션 d에 대한 드론 비행경로는 다음과 같이 정의될 수 있다.

Definition 1. Drone flight route

한 대의 드론이 m(≥1)개의 배달점을 방문하는 배송미션 d를 수행하기 위한 드론 비행경로 모델은 유방향 그래프 G_d = (V_d, E_d)로 정의한다. 배달점(delivery points) 집합 V_d = {v_p | p = 0, 1, ..., m+1}는 G_d를 구성하는 노드들의 집합이다. 여기서 드론 회귀점을 표현하기 위한 더미 노드 v_m+1을 추가한다. ∀v_p, 만약 p = 0이면, 노드 v₀은 배달거점 (base point)을 의미한다. 회귀점은 출발점과 동일하기 때문에, v₀은 출발점에 해당하는 배달거점을, v_m+1은 회귀점인 배달거점을 표현하는 것으로 구분되지만 두 노드의 지리적인 위치에 같다[15].

다음은 배달점 구간(delivery point segments)으로 명명된 링크 집합 E d = { e p q : ( v p , v q ) | v p , v q ∈ V d , p ≠ q } 는 두 개의 배달점 v_p와 v_q를 연결하는 드론 비행 구간들의 집합을 의미한다.

배송을 위한 하나의 드론비행경로 G_d는 배송 네트워크 그래프 G의 하나의 서브셋으로 실제 배송 미션이 생성될 때마다 발생되는 인스턴스로 이해할 수 있다. <Figure 1>의 G와 같이 드론 비행경로를 구성하는 주요 노드들은 X-Y 좌표를 이용하여 2차원 지도상에 해당 위치가 표현될 수 있고, 이동 순서에 따른 링크들의 연결로 전체 경로를 표현할 수 있다. 그러나 이러한 표현으로는 VTOL 비행을 위해 이륙과 착륙 구간이 명확히 구분되는 3차원 비행 궤적을 표현하기에 다소 부족하다. 그 이유는 경로를 구성하는 모든 지점들의 좌표에는 고도 정보가 필요하고, 이륙과 착륙 구간에서는 하나의 노드가 아닌 서로 다른 고도값을 가진 노드로 구분되어 표현되어야 하기 때문이다. 드론의 자동비행을 위해서는 비행 궤적에 대한 비행경로를 전달받아 비행을 시작하게 된다. 이때 비행 궤적은 순서화된 waypoint들의 집합으로 구성된다. 드론의 자동 비행은 하나의 waypoint에서 다음 waypoint로의 연속적인 이동으로 이루어지고 여기서 비행 궤적은 X-Y 좌표에 고도(altitude) 정보가 포함된 3차원 좌표들의 순서화된 집합으로 표현 가능하다. 따라서 정의 1과 같은 일반적인 그래프 모델만으로는 실제 비행경로 표현에 부족함이 존재하다.

4.2 단위비행구간

따라서 본 논문에서는 중첩된 그래프 구조를 이용하여 사전에 정의된 이륙부터 착륙까지의 실제 비행 궤적의 표현이 가능한 비행경로 모델에 대한 정의를 제공한다. 보다 구체적으로 하나의 드론이 배달거점을 출발하여 한 곳의 배달점을 방문(착륙)하고 다시 배달거점으로 회귀하는 상황을 고려해 보자. 이때 한 번의 비행에 해당하는 구간은 배달거점에서부터 첫 번째 배달점까지다. 그리고 다시 배달거점으로 회귀해야하기 때문에 방향이 반대인 비행구간 하나가 더 필요하다. 이 경우 비행미션은 두 개의 단위비행구간으로 구성되며 앞서 소개한 드론 배송프로세스를 통해 쉽게 이해할 수 있다.

정의 1에 의해 하나의 드론비행경로 G_d에서 두 지점 p와 q사이의 비행구간을 표현하는 링크 e_pq는 p지점에서 이륙하여 q지점에 착륙하는 것을 의미하는 것으로 단위비행구간이 될 수 있다. 이는 항공이나 군사 분야 등에서 사용하는 “sortie” 또는 “single-leg flight”로 이해할 수 있다. 이는 비행체가 이륙하여 비행을 마친 후 다시 이륙지점으로 회귀하여 착륙까지의 과정을 의미하지만, 드론의 경우 보통은 배달지점에 착륙하기 때문에 출발점에서부터 배달점 착륙까지를 하나의 소티로 간주할 수 있다. 배달점에서 임무를 마친 드론이 다시 출발점인 배달거점으로 회귀하기 위해서는 2개의 소티가 연결된 하나의 비행경로가 필요하다. 물론 드론이 배달점 상공에서 착륙하지 않고 투하배달을 하는 경우 하나의 소티로 하나의 비행경로를 구성하는 것이 가능하지만, 이것 또한 서비스 제공자의 운영 방식에 포함되어 결정되는 요소이다.

따라서 <Figure 3>과 같이 VTOL 비행 특성인 이륙 및 착륙구간을 고려하여 3차원 공간에서의 비행 궤적을 표현하기 위해 드론비행경로 G_d에서 두 배달점의 연결 링크로 표현된 단위비행구간 e_pq를 delivery point segment라 하고 중첩된 그래프 개념을 이용하여 구체화된 구조적 정의를 소개한다.

Definition 2. Delivery point segment

정의 1에서 두 개의 배달점 v_p와 v_q를 연결하는 하나의 단위비행구간 링크 e_pq∈E_d = (W_pq, L_pq)는 다시 순서화된 waypoint 집합인 W_pq = {w_i | i∈ℕ}와 두 개의 waypoint w_i와 w_j를 연결하는 링크에 해당하는 waypoint segment의 집합 L_pq = {l_ij : (w_i, w_j) | w_i, w_j∈W_pq, i≠j}로 정의한다.

이 정의는 한 단계 상위 레벨에서 드론비행경로 G_d가 노드 v_p와 링크 e_pq의 구성으로 정의되는 것과 유사하다. 하나의 링크 e_pq에 waypoint 집합과 두 waypoint를 연결하는 waypoint segment 집합으로 구성된 그래프가 다시 중첩되어 정의되는 것이다.

두 배달점 사이의 비행구간에 해당하는 delivery point segment e_pq를 구성하는 waypoint들은 해당 지점에서의 드론 위치나 속도 등을 포함하여 다양한 속성 정보를 가질 수 있다. 기본적으로 3차원 공간상에서 드론의 위치 좌표값(x, y, z)을 포함하며 비행속력이나 배송미션 처리 등과 관련된 다양한 속성들을 가질 수 있다. 드론의 자동비행을 위하여 이륙구간과 착륙구간의 식별은 특히 중요한 요소이지만 정의 2에서도 아직은 VTOL 비행을 위한 이착륙 구간을 명확히 표현하지 못하고 있다. 수직이착륙 구간을 식별하기 위하여 <Figure 3>과 같이 이륙점(p)부터 착륙점(q)까지의 비행궤적에서 이륙(take-off), 비행(flight), 착륙(landing) 구간으로 보다 세분화된 구분이 필요하다. 따라서 본 논문에서는 식 (1)~식 (3)과 같이 waypoint의 좌표값 들을 이용하여, <Figure 3>과 같이 하나의 단위비행구간 e_pq에 대해 이륙구간 e p q T , 비행구간 e p q F , 착륙구간 e p q L 로 명확하게 구분하였다.

where W p q T = {w_i | lon(w_i) = lon(v_p) and lat(w_i) = lat(v_p), w_i∈W_pq}

where W p q L = {w_i | lon(w_i) = lon(v_q) and lat(w_i) = lat(v_q), w_i∈W_pq}

where W p q F = {w_i | (max(i):w_i∈W p q T ) ≤ i ≤ (min(i):w_i∈ W p q L )}

이와 같이 하나의 링크로 표현되던 단위비행구간은 다시 waypoint 기반의 중첩된 그래프를 이용하여 구체적인 비행경로 구조로 표현될 수 있다. 소개된 드론 비행경로 모델을 이용하면 개념적인 경로의 표현을 넘어 3차원 비행궤적에 대한 표현과 VTOL 드론의 특성을 고려한 전체 비행구간에서 이륙, 비행(순항), 착륙 구간에 대한 명확한 구분과 활용이 가능하게 된다.

4.3 드론비행경로의 표현

본 연구에서 소개한 드론비행경로모델의 정의는 VTOL 비행을 위한 드론의 실제 비행경로에 대한 구조적인 이해를 돕는다. 이러한 개념과 정의를 이용하여 배송 주문이 주어졌을 때 드론비행경로 예시를 소개하는 것으로 4장을 마무리한다.

하나의 배달거점과 5개의 배달점으로 구성된 배송 네트워크 G에서 두 배달점 “DP-02”, “DP-05”를 순서대로 방문하고 돌아오기 위한 배송미션 d=1이 주어졌다고 가정하자. 이때 드론 배송경로는 아래 <Figure 4>와 같이 하나의 배달거점과 2개의 배달점, 그리고 3개의 단위비행구간의 구성으로 표현될 수 있다. 드론이 배달거점 v₀을 출발하여 첫 번째 배달점 v₁을 방문한 다음, 두 번째 배달점인 v₂를 방문하고 다시 배달거점 v₃으로 회귀하는 드론비행경로 G₁ = (V₁, E₁)은 정의 2에 의해서 V₁ = {v₀, v₁, v₂, v₃}과 E₁ = {e₀₁, e₁₂, e₂₃}으로 구성된다. 여기서 v₀과 v3은 배달거점을 의미하고, v3은 정의 1에서 회귀점을 의미한다. 그리고 e₂₃은 두 번째 배달점 v₂에서 v₃으로 회귀하는 단위비행구간을 나타낸다.

그리고 정의 2에 따라 두 배달점 사이의 비행구간 e_pq는 waypoint w_i와 waypoint segment l_ij들을 이용하여 구체화된 비행 궤적을 표현한다. 3개의 단위비행구간으로 구성된 G₁에서 배달거점 v₀과 첫 번째 배달점 v₁ 사이의 단위비행구간 e₀₁ = (W₀₁, L₀₁)이 만약 5개의 waypoint로 구성되었다면 W₀₁과 L₀₁은 다음과 같다.

그리고 e₀₁의 이륙, 비행, 착륙구간 e p q T , e p q F , e p q L 는 식 (1)~식 (3)에 의해 아래 예시와 같은 구조로 구성될 수 있다. 예시를 살펴보면, 이륙구간과 비행구간에서는 중간에 waypoint가 존재하지 않기 때문에 한 번의 비행으로 이동한다. 그러나 착륙구간에는 3개의 waypoint가 존재하기 때문에 착륙비행 도중 정밀 착륙을 위한 호버링(hovering) 등 여러 다양한 이유로 waypoint가 존재하는 것을 알 수 있다. 나머지 두 비행구간 e₁₂와 e₂₃도 마찬가지로 같은 방법으로 명확히 표현될 수 있다.

이와 같이 본 연구에서는 그래프 모델의 노드와 링크를 이용한 드론 비행경로 모델의 일반적인 표현에서 나아가 각각 링크에 대해 다시 waypoint와 waypoint segment로 구성된 중첩된 그래프 구조를 이용하여 하나의 소티에 해당 하는 단위비행구간, 그리고 해당 단위비행구간에 대하여 이륙구간과 착륙구간, 그리고 비행구간의 명확한 구분을 위한 구조적 정의를 소개하였다. 해당 정의를 기반으로 각 지점 및 구간별 다양한 시간 속성이 포함할 때 드론 비행 및 배송 계획의 수립, 운영 시뮬레이션 및 검토 등 다양한 용도에 효과적으로 활용할 수 있다. 이어지는 5장에 드론 비행경로가 가지는 다양한 시간 속성들의 소개와 간략한 예제를 이용한 계산방법을 설명한다.

5. 드론 비행경로의 시간속성

본 장에서는 드론 비행경로를 구성하는 노드와 링크가 가지는 주요 시간속성들을 살펴보고 계산 방법 및 절차를 소개한다. 앞서 3.3절에서 기술한 것과 같이 비행경로는 서비스 제공자가 운영하는 배송 서비스 유형에 의해 다양할 수 있기 때문에 본 논문에서는 FCFS 형태의 배송 서비스를 구체적 예시로 활용하여 설명하기로 한다. 그렇다하더라도 적용 범위를 한정시킬 필요는 없으며, 수직이착륙 자동비행을 위한 경로의 생성 및 운영과 관련된 다양한 분야에서 활용 가능하다.

드론은 GCS(Ground Control Station)로부터 배송을 위한 비행미션 데이터를 전송받아 자동 비행을 시작할 수 있다. 비행미션은 해당 배송을 위한 비행경로의 구조적 정보뿐 아니라 비행경로의 고도 및 속도 정보 등도 함께 포함하고 있다. 따라서 비행경로의 구조와 시간 속성을 이용 하여 전체 비행궤적 정보에 대한 가시화와, 이를 이용하여 서로 다른 드론이 노드 또는 링크에서의 경합을 회피하기 위한 전략 수립 및 드론 운영의 안전성 확보도 가능하다. 특히 배송 효율성 향상을 위해 다수의 드론을 운영하고자 할 때 신속한 자동비행 계획 수립을 통한 자동화된 운영이 필요하다. 따라서 안전한 드론 배송 서비스 운영을 위한 다양한 시간 속성들에 대해 살펴본다.

5.1 Processing Time and Flight Time

드론비행경로 G_d에는 다양한 시간속성이 있으며 해당 속성을 가지는 주요 객체는 노드와 링크를 들 수 있다. 노드에 해당하는 배달거점과 배달점에서는 해당 지점에서 배송 관련 업무 등의 처리에 소요되는 시간속성이 존재한다. 그리고 두 노드를 연결하는 링크에서는 드론의 이동에 소요되는 시간속성들이 존재한다. 노드에서 발생하는 시간들은 processing time으로, 링크에서 발생하는 시간들은 flight time으로 통칭하기로 한다.

먼저 노드 객체 v_p에서는 기체상태점검이나 통신상태점검과 같은 비행준비업무, 배송물품적재와 같은 배송준비 업무, 그리고 배달점에서는 물품전달, 적재함체결과 같은 배송처리업무에 소요되는 시간속성들이 존재한다. 각 업무의 소요시간은 일반적으로 적절히 표준화된 시간으로 주어진다. 예를 들어 출발점에서 “물품적재 == 2min”과 같이 서비스 프로세스 운영자 또는 업체에 의해 정해지는 값이다. 다음으로 링크 객체 e_pq에서는 두 v_p와 v_q 사이의 이동에 소요되는 비행시간이 주요한 시간속성이다. 두 지점 사이의 거리는 정해진 값이므로 운영자가 설정하는 속도를 이용하여 e_pq의 비행시간은 쉽게 계산될 수 있다. 여기서 하나의 e_pq에 포함된 w_i의 경우 해당 지점에서 필요에 따라 정지비행을 위한 호버링 타임 등이 발생할 수 있다.

정의2와 같이 링크 e_pq는 또다시 노드인 waypoint와 링크인 waypoint segment로 표현된다. 따라서 e_pq를 구성하는 waypoint 또한 필요에 따라 processing time을 가질 수 있다. 예를 들어 드론이 이륙 후 이륙점 상공에서 다음 지점으로의 비행을 시작하기 전에 비행의 안전이나 임무와 관련하여 몇 초간 호버링하거나, 착륙점에서 착륙비행 도중 착륙 정밀도 향상을 위한 마커 인식 등을 위하여 약간의 호버링을 수행하는 등 다양한 비행 환경을 고려하여 설정할 수 있다. 그리고 하나의 비행구간 e_pq가 직선 형태가 아닌 경우 방향 전환을 위하여 두 개 이상의 l_ij로 구성되어 있다면 두 링크 l_ij의 연결점에 해당하는 waypoint에서도 필요에 따라 드론 기체와 물품의 안전을 고려하여 약간의 정지 타임을 설정할 수 있다. 그렇다 하더라도 비행시간과 배터리 소모량 관점에서 불필요한 호버링은 최소화하는 것이 좋다.

정리하면 배달거점 및 배달점 노드에서는 드론 배송프로세스에 따라 업무처리와 관련된 processing time이 설정될 수 있고, 링크에 포함되는 waypoint에서도 다양한 목적으로 호버링 타임 등이 설정될 수 있다. 노드에서 소요되는 모든 시간값은 적절한 값으로 사전에 설정되기 때문에 별도의 계산이 필요한 것은 아니다. 이러한 시간속성들은 계획단계에서는 ‘예상(estimated) 시각’으로 표현되고, 운영단계에서는 ‘실제(actual) 시각’으로 기록되고 관리될 수 있다. Estimated 값들은 실제 비행 과정에서 Actual 값으로 지속적으로 업데이트된다. 일반 차량용 내비게이션에서 특정 목적지에 대해 출발 전 예상도착시각과 출발 이후 변화하는 실제도착시각으로 이해할 수 있다. 아래와 같은 주요 시간속성들을 이번 장에서 자세히 설명한다.

5.2 비행구간의 거리 및 시간 계산

비행경로의 노드에서 설정되는 processing time과 달리 모든 링크들은 길이 정보가 사전에 정해지기 때문에 링크에서의 비행시간은 비행구간에 설정된 속도 정보를 이용하여 계산될 수 있다. 2차원 평면에서 두 지점 사이의 직선거리인 유클리디안 거리(Euclidean distance)는 좌표값으로 쉽게 계산되지만, 실질적인 이동거리는 보통 맨해튼 거리 (Manhattan distance)를 사용한다. 배송 네트워크에서도 하나의 비행구간 e_pq의 길이와 실제 비행거리는 이륙과 착륙 구간으로 인해 서로 달라진다. e_pq에서 두 지점 v_p와 v_q의 좌표 (x_p, y_p)와 (x_q, y_q)로는 이륙구간과 착륙구간을 표현하지 못하기 때문에 <Figure 3>과 같이 두 지점 사이의 실제 비행거리는 이륙구간의 거리 dist(e p q T )와 착륙구간의 거리 dist(e p q L )가 포함되어야 한다. 드론비행경로를 결정할 때 이륙지점 및 착륙지점의 고도인 alt(v_p)와 alt(v_q) HASL(height above sea level)은 각 노드의 지면고도(ground level)를 고려하여 아래 식 (4)~식 (6)의 예시와 같이 사전에 정해질 수 있는 값으로 쉽게 얻을 수 있다.

따라서 이륙지점 ground level이 20m HASL이고, 이륙고도는 80m HASL로 설정하면, 실제 드론은 60m AGL(above ground level)까지 이륙하게 되므로 이륙구간의 비행거리는 60m가 된다. 그리고 두 지점의 고도를 고려하여 e_pq의 비행구간 e p q F 의 실제 비행거리는 3차원 공간에서의 유클리디안 거리인 dist ( e p q F ) = ( Δ x ) 2 + ( Δ y ) 2 + ( Δ z ) 2 가 된다. 그러나 비행구간이 직선이 아닌 경우 e_pq를 구성하는 l_ij들의 거리의 합인 ∑ dist ( l i j ) , ∀ l i j ∈ e p q F 로 계산될 수 있다. 이와 같이 e_pq를 구성하는 모든 구간의 거리가 정해지면, 지정된 속도정보를 이용하여 링크에서의 비행시간 ETF를 얻을 수 있다.

e_pq에서 이륙, 비행, 착륙속도는 서로 다르게 운영될 수 있다. 이는 드론 성능과 물품 무게, 그리고 비행 안전 등 다양한 요소들과 시험비행 결과들을 종합적으로 고려하여 결정될 수 있다. 보통은 경우 이륙 및 착륙구간에서는 비행구간에 비해 약간 낮은 값으로 설정된다. <Figure 5>는 실제 드론 테스트 비행을 통해 기록된 로그데이터로부터 얻은 속력-시간 그래프와 해당 비행경로 화면을 함께 표현한 예시이다. 해당 그래프에서 보는 것과 같이 e_pq는 크게 이륙, 비행, 착륙의 3개 구간으로 구분된다. 이륙구간에서 드론은 천천히 이륙한 다음 상공에서 약간 호버링 후 배달점으로 비행을 시작한다. 지정된 비행속력에 도달할 때까지 가속 후 순항하면서 배달점 상공에 도착한다. 또 다시 약간의 호버링 후 천천히 안전하게 착륙을 진행한다.

각 구간에 지정된 속력에 도달하기 위한 가속도 기울기를 살펴보면 가속도가 크기 때문에, 비행시간 계산을 위해 S-curve가 아닌 Trapezoidal motion profile을 활용한다. 하나의 e_pq의 속력-시간 그래프는 <Figure 6>과 같이 근사하여 이해할 수 있다. e_pq의 각 비행구간(이륙/비행/착륙)의 거리가 주어지고, 속력 프로파일을 기반으로 각 구간과 전체 비행경로의 비행시간을 계산할 수 있다. e_pq에서 각 구 간의 속력은 아래 예시와 같이 설정하여 운영할 수 있다.

배터리를 동력으로 하는 드론의 특성상 실제 비행구간에서 가속과 감속 구간은 비교적 짧게 나타난다. 가속도는 드론 제원이나 성능에 따라 차이가 있으나, 본 논문에서는 a = 2.0m/s²을 이용하였다. 그리고 <Figure 6>과 같이 하나의 e_pq에서 이륙구간 e p q T , 비행구간 e p q F , 착륙구간 e p q L 은 다시 가속구간(accelerating section, t₀~t₁), 순항구간(cruising section, t₁~t₂), 감속구간(decelerating section, t₂~t₃)으로 구분된다. 세분화된 각 구간의 속력함수 v(t)는 1차함수와 상 수로 간단하게 표현될 수 있다. 위 예시에서 이륙구간에 설정된 속력 speed^T가 4.0m/s이면, 가속구간과 순항구간, 그리고 감속구간에서의 속력은 아래 식 (7)~식 (9)를 이용하여 계산될 수 있다.

이처럼 가속, 순항, 감속구간에서의 속력 함수를 이용하여 식 (10)과 같이 이륙구간 거리 dist(e p q T )를 계산할 수 있다. 이 값은 식 (5)와 같이 사전에 설정된 고도값 60m AGL과 같기 때문에 이륙구간의 비행시간 ETF(e p q T ) = (t₁–t₀) + (t₂–t₁) + (t₃–t₂)와 같이 3개 구간(가속, 순항, 감속)에서 소요된 시간의 합과 같다.

먼저 가속시간 (t₁–t₀)은 식 (7)에서 이륙구간에 설정된 속력 4.0m/s에 도달하는데 걸린 시간으로, t₀ = 0이고 2t = 4이므로 t₁ = 2초이며, 가속거리는 4m이다. 마찬가지로 감속구간에서도 식 (9)와 같이 t₃의 속력 υ p q T D ( t 3 ) = 0 이고 -2t = -4이므로 감속시간 (t₃–t₂)도 2초가 소요되며, 감속거리도 4m이다. 나머지 이륙구간도 4.0m/s로 순항한 거리에 해당하는 순항시작시각 t₁부터 순항종료시각 t₂까지의 거리 Δdist(t₁, t₂)는 식 (11)에서 52m이며, t₁ = 2이고 t₂ = 15가 되기 때문에 순항한 시간 (t₂–t₁) = 13초임을 알 수 있다. 그러므로 이륙구간 전체의 거리인 dist(e p q T ) = 60m에 대해, t₀ ~ t₃ 시점까지의 timestamp와 위치들은 쉽게 계산되며, <Table 1>과 같이 이륙구간의 비행시간 ETF(e p q T )는 총 17초가 소요됨을 알 수 있다.

이상으로 드론이 출발점에서 이륙을 시작하여 이륙구간의 고도 60m AGL에 도착하는데 걸린 시간은 식 (11)과 (12)를 이용해 계산되었다. 여기서 중요하게 고려되어야 하는 시간속성이 존재한다. 각 링크에 포함된 waypoint에서 발생되는 processing time은 해당 구간의 비행시간에 포함되어야 한다는 것이다. 드론이 한 지점에서 이륙하여 다른 지점에 도착할 때까지 비행에 소요된 시간은 <Figure 6>과 같이 이륙 후 이륙점 상공 및 착륙점 상공, 또는 각 구간 내에 특정 지점에서의 호버링 시간과 같이 e_pq에 포함된 모든 waypoint에 머무른 시간 ETP(w_i)가 존재한다면, 해당 시간들은 전체 비행시간에 포함되어야 한다. 그러므로 ETF(e p q T )는 식 (13)과 같이 표현될 수 있다.

where, i > min(i) : w_i ∈W p q T

이처럼 e_pq의 나머지 비행구간 및 착륙구간의 비행시간 ETF(e p q F )와 ETF(e p q L )도 이륙구간과 같은 방법으로 계산할 수 있다. 이때 w_min(i) 및 w_max(i)는 v_p 및 v_q와 같고 ETP(v_p)와 ETP(v_q)에 해당하기 때문에 이륙전 및 착륙후 처리시간이 된다. 이를 통해 v_p 출발 후 배달점 도착시간 ETA(v_q)의 계산이 가능하고 e_pq의 시간 정보가 포함된 궤적 표현이 가능하다.

이상으로 단위비행경로 e_pq에 대한 시간 속성 중 ETP와 ETF에 대해 자세히 살펴보았다. 이 값들은 뒤에서 기술할 드론 운영에서 비행경로 시각화를 위하여 각 지점들에 대한 ETA와 ETD의 계산에 중요한 시간변수들로 활용된다.

5.3 ETP(w_i) and ETF(l_ij) in e_pq

드론비행경로모델에서 2가지 중요한 시간속성에 대해 살펴보았고, 본 절에서는 G_d에 할당하고 계산하는 과정을 소개한다. 먼저 w_i와 l_ij의 시간 속성을 할당하는 방법을 살펴본다.

정의1과 2에 의해 드론비행경로의 구조는 w_i와 l_ij만으로도 v_p를 포함하여 표현이 가능하기 때문에 먼저 e_pq를 구성하는 노드 w_i와 링크 l_ij에 시간값 할당에 대해서 설명한다. 각 w_i에서의 소요시간과 l_ij에서의 비행시간은 사전에 정해진 값과 계산된 값들을 이용하여, 식 (14)와 같이 두 개의 매트릭스를 이용하여 제공하기로 한다. 비행 미션에 따라 G_d와 두 가지 시간속성 데이터 P_d와 F_d가 아래와 같이 주어지면, 이를 이용하여 시간속성 변수에 할당 및 계산하는 과정을 통해 배송미션 및 드론배송서비스 운영 계획에 활용 가능하다.

각 e_pq는 충분한 시험 비행을 통해 안전한 항로로 확인되고, 항로의 수정이나 설정 속력의 변경이 없다면, P_d와 F_d는 동일한 값으로 계속해서 활용될 수 있다. (P_d와 F_d는 매트릭스로 구조로 표현되었으나 연산 목적보다 데이터 구조 관점에서 속성값을 저장하는 다수의 List들에 대한 Array 구조로 이해할 수 있다.)

P_d의 각 행은 G_d를 구성하는 각 비행구간 e_pq에 해당하고, 하나의 행에는 그 e_pq에 속한 모든 w_i의 processing time 정보가 나열되어 있다. 각 행의 길이는 대응되는 각 e_pq에 포함된 waypoint 개수와 같다. 이때 e_pq에 속한 waypoint 개수는 서로 다를 수 있기 때문에 각 행의 길이도 다를 수 있다. P_d의 값을 이용하여 G_d의 모든 w_i의 processing time ETP(w_i)는 식 (15)와 같이 할당된다. 그리고 k번째 비행구간의 마지막 waypoint는 k+1번째 비행구간의 첫 번째 waypoint에 해당하기 때문에 식 (16)과 같이 두 waypoint는 서로 같다.

유사하게 F_d의 각 행 또한 G_d를 구성하는 e_pq에 해당하며, 하나의 행에는 해당 e_pq에 포함된 모든 waypoint segment l_ij의 flight time을 제공한다. 따라서 계산된 F_d의 값을 이용하여 G_d의 모든 l_ij의 flying time ETF(l_ij)는 식 (17)과 같이 할당된다.

주어진 P_d와 F_d를 이용하여 할당된 각 ETP(w_i)와 각 ETF(l_ij)를 이용하여, G_d의 각 지점의 ETP(v_p)와 각 구간의 ETF(e_pq)의 계산에 활용한다.

5.4 ETP(v_p) and ETF(e_pq) of G_d

드론비행경로 G_d의 단위비행구간 e_pq∈E_d의 세부 구성요소인 waypoint w_i와 waypoint segment l_ij의 시간속성들에 대한 할당 및 계산과정을 살펴보았다. 다음은 G_d를 구성하는 v_p와 e_pq의 시간속성에 대한 계산 과정을 살펴본다. ETP(v_p)와 ETF(e_pq)는 앞서 소개한 ETP(w_i)와 ETF(l_ij)를 이용하여 계산될 수 있다. 먼저 ETP(v_p)는 ETP(w_i)를 이용하여 식 (18)과 같이 설정된다. 이 때 배달거점과 배달점에 대해 구분이 필요하다. 여기서 각 v_p에서 머무르는 시간인 ETP(v_p)는 v_p로 진입하는 비행구간인 e_p-1,p의 waypoint 집합인 W_p-1,p에서 마지막 w_i의 processing time과 같다. 단, v_p가 배달거점이면, v₀에서 진출하는 e₀₁의 waypoint 집합 W₀₁의 첫 번째 waypoint의 ETP(w_i∈W₀₁)에 해당한다. 이후 순차적으로 방문하는 모든 배달점과 마지막에 도착한 배달거점에서 머무르는 시간도 동일하게 할당된다.

다음으로 G_d를 구성하는 각 비행구간 e_pq의 비행시간 ETF(e_pq)는 식 (19)와 같이 계산된다. 식 (13) 및 (19)와 같이 ETF(e_pq)는 e_pq의 모든 waypoint segment의 ETF(l_ij) 합과 W_pq의 첫 번째 waypoint 및 마지막 waypoint를 제외한 나머지 ETP(w_i)의 합을 다 더한 것과 같다. 첫 번째와 마지막 waypoint에서 ETP는 식 (18)에서 ETP(v_p)와 ETP(v_q)에 할당되기 때문에 비행시간에서 제외된다. 따라서 e_pq 구간에 포함된 각각의 waypoint에서 머무르는 시간이 모두 0이면, 그냥 ETF(l_ij)의 합과 같게 된다.

5.5 ETD and ETA at a Node

드론비행경로 G_d를 구성하는 두 객체 v_p와 e_pq에 대해 업무수행 및 비행에 소요되는 시간의 할당과 계산하는 방법 및 과정에 대해 살펴보았다. 다음은 G_d의 비행계획을 가시화하기 위하여 각 지점에서 드론의 도착예정시각과 출발예정시각을 계산하는 과정을 살펴본다. 먼저 G_d의 각 v_p에서는 해당 지점에서 머무르는 시간인 processing time 을 가지기 때문에 해당 지점의 도착시각 ETA(v_p)가 정해지면 출발시각 ETD(v_p)는 자동으로 계산된다. ETA(v_p)와 ETD(v_p) 계산은 ETP와 ETF 계산과 마찬가지로 w_i와 l_ij를 활용한다. 따라서 ETA(w_i)와 ETD(w_i)를 계산하는 과정을 먼저 소개한다.

모든 노드는 해당 지점의 도착시각 ETA, 머무르는데 소요된 시간 ETP, 그리고 출발시각 ETD를 가지기 때문에 waypoint에서의 출발시각 ETD(w_i)는 식 (20)과 같이 해당 waypoint에 도착시각 ETA(w_i)와 해당 지점에서 머무르는데 소요된 시간 ETP(w_i)의 합으로 구할 수 있다. 여기서 ETP(w_i)는 식 (15)에 의해 P_d로부터 이미 할당된 값이기 때문에, 해당 ETA(w_i)가 결정되면 ETD(w_i)는 간단히 계산된다. 따라서 ETA(w_i)는 식 (21)과 같이 w_i를 직전에 선행하는 w_j에서의 출발시각 ETD(w_j)와 w_j에서 해당 w_i까지의 비행시간 ETF(l_ji)의 합으로 구할 수 있다. 그리고 e_pq의 첫 번째 waypoint w₁의 도착시각인 ETA(w₁∈W_pq)는 인접한 직전 비행구간 e_p-1,p의 마지막 waypoint에 도착한 시각인 ETA(w_max(i)∈W_p-1,q)와 같다. 그러나 만약 p=0이고 i=1이면, 첫 번째 비행구간 e₀₁의 첫 번째 w₁은 전체 경로에서 가장 첫 번째 waypoint이기 때문에 in_degree(e₀₁=w₁) = 0이므로, 진입링크가 존재하지 않는다. 이것은 배달거점의 이륙 위치에 드론배송서비스 제공을 위해 드론을 준비시킬 수 있는 시간을 의미한다. 구체적으로는 배치 “가능한” 시간(availableTimeSlot)을 의미하며, 드론이 해당 지점을 점유할 수 있는 시간의 범위로 제공될 수 있다. 따라서 각 availableTimeSlot 구간 범위는 시작시각 st와 종료시각 et의 쌍으로 표현될 수 있고, 다른 드론에 의해 해당 지점 점유 계획이 이미 존재하는 경우, 해당 시간대인 st ~ et를 피할 수 있는 여러 개의 구간으로 제공하는 것이 가능하다. 따라서 멀티드론 운영 환경에서 가장 중요한 요소 중 하나는 다른 드론들과의 충돌이나 간섭이 제거된 안전한 비행을 제공하는 것이며, 이를 위해 새로운 주문에 대한 비행미션을 수행하기 위해 배달거점의 출발점에 드론을 위치시킬 수 있는 가장 빠른 시각 availableTimeSlot.st₁을 결정하고 제공하는 것이 필요하다.

이와 같이 waypoint의 도착시각 ETA(w_i)와 출발시각 ETD(w_i)를 계산하는 방법과 과정을 살펴보았다. 이를 통하여 G_d를 구성하는 각 v_p에서의 출발예정시각 ETD(v_p)와 도착예정시각 ETA(v_p)를 계산할 수 있다. 각 배달점도 waypoint와 마찬가지로 해당 지점의 도착시각(ETA)과 해당 지점에서 머무르는 시간(ETP), 그리고 해당 지점에서 의 출발시각(ETD) 정보를 가진다. 각 ETD(v_p)는 식 (20)과 유사하게 식 (22)와 같이 해당 지점의 도착시각과 머무르는데 소요된 시간의 합으로 구할 수 있다.

여기서 ETP(v_p)는 ETP(w_i)를 이용하여 그대로 정해지는 값이기 때문에, 해당 지점의 ETA(v_p)만 결정되면 ETD(v_p) 또한 간단하게 계산된다. 따라서 ETA(v_p)는 식 (23)과 같이 직전 배달점에서의 출발시각 ETD와 직전 배달점에서 해당 배달점까지의 비행시간 ETF의 합으로 간단히 계산할 수 있다.

이때 p = 0이면, v_p는 전체 경로에서 첫 번째 노드인 배달거점이기 때문에 ETA(v₀)는 앞서 설명한 첫 번째 비행구간 e₀₁의 첫 번째 waypoint 도착시각인 ETA(w₁)과 같다. 따라서 ETA(v₀) = ETA(w₁∈W₀₁)이며, 식 (24)와 같이 할당될 수 있다.

본 논문 3장과 4장에서 소개한 VTOL 드론 비행경로의 구조적 표현에 대한 정의를 기반으로 다양한 시간속성들에 대해 자세히 살펴보았다. 이처럼 경로 모델이 시간속성과 함께 제공될 때 라스트 마일 물류 환경에서 스마트한 배송 서비스의 구현 및 운영에 다양하게 활용할 수 있게 된다. 본 논문에서 소개한 드론 비행경로와 시간속성 정보를 기반으로 멀티드론을 이용한 다지점 배송 서비스 운영에 대한 구체적인 응용 사례까지는 다루지 않았지만, 논문의 말미에 드론 배송 서비스 운영을 위한 드론 비행경로 구조의 시각화와 다이어그램을 이용하여 시간속성 표현에 대한 간단한 예시를 제공하며 결론을 맺는다.

6. 결 론

스마트 물류의 실현을 위해 라스트 마일 배송 환경에서 드론은 기존 운송수단과 상호보완적으로 작용하며 물류 효율성과 신속성을 크게 향상시킬 수 있다. 또한 스마트 물류시스템은 드론의 다양한 운영을 최적화할 수 있기에, 드론은 스마트 물류를 실현하기 위한 중요한 도구로 작용되고 있다. 본 논문에서는 이런 스마트 물류 환경 구현과 혁신에 주요한 역할이 기대되는 드론 배송 서비스에서 기본이 되는 비행경로 모델의 구조적 표현을 위한 정의를 제공하고자 하였다. 드론 경로를 다루는 기존의 많은 연구들에서 경로를 표현하는 방법과는 다르게 중첩된 그래프 구조를 이용하여 링크마다 수직이착륙 드론의 실제 비행궤적에 대한 가시적 표현을 용이하게 하였다. 그리고 해당 경로 모델을 기반으로 다양한 시간속성들을 통해 배송경로상의 노드에서 처리되는 시간과 링크를 통해 비행하는 시간들에 대한 정확도 높은 계산이 가능하다. 이는 다수의 드론을 이용하는 다지점 배송 서비스 운영 계획 수립과 배송모니터링, 나아가 충돌 방지 전략 등 다양한 활용이 가능할 것으로 예상된다.

그럼에도 본 연구에서는 드론 운영 환경의 다양성과 복잡성으로 인해 제한적인 범위와 상황을 한정지어 설명하였다. 고정된 단일 배달거점, 이륙점과 착륙점 수의 제한과 그에 의존하여 설정되는 선형 경로로 구성된 네트워크, 특히 본 연구에서 다루는 비행경로는 드론과 물품의 안전을 고려하여 직선 형태의 경로 표현에 대하여 제한적으로 다루었다. 이는 서비스 제공자가 운영하고자 하는 비행 형태에 의해 결정될 수 있다. 부드러운 궤적의 곡선 비행을 위한 경로(curved flight path)를 운영하기 위해 스플라인(spline)이나 베지에 곡선(Bézier Curve) 등 곡선 형태의 경로 표현을 다루는 연구로의 확장도 필요하다. 또 다양한 서비스 형태가 있으나, FCFS 형태의 서비스에 초점을 맞추어 제한된 범위에서 설명하였다. 만약 다루고자 하는 서비스 환경에서 적당히 짧은 시간 내에 배송이 빈번하게 발생하는 경우에는 가용한 드론 수와 한 대의 드론이 어떤 주문을 어떤 순서로 처리할 지를 결정하기 위한 다양한 최적화 문제로 다루는 연구도 필요하다. 이때 배송 네트워크상에서 이미 운용 중인 드론이 존재하면, 노드의 점유를 회피하거나 각각의 단위 경로상에서 충돌점을 회피하면서 주어진 배송처리시간 최소화와 같은 다양한 목적 함수를 가지는 문제로 모델링될 수 있다. 또 본 연구에서 다양한 시간속성을 이용하여 드론의 출발가능시각 계산에 활용하였다. 향후 다양한 빈도로 배송이 발생하는 상황에서 점유 구간 및 점유시간 식별 방법에 대해 구체적으로 다루는 연구 또한 필요하다.

마지막으로 드론 다이어그램을 이용하여 본 연구에서 소개한 VTOL 드론 비행경로 모델과 시간속성 정보들의 가시화 예시를 소개한다. 하나의 드론 배송 G₁을 위한 P₁ = [[4, 1, 1, 1, 3], [3, 0, 1, 1, 3], [3, 0, 0, 4]]과 F₁ = [[2, 8, 1, 1], [2, 4, 1, 1], [2, 6, 2]]이 주어지고 ETA(v₀)=10:00으로 정해 졌을 때, G₁의 구조와 노드 및 링크에서의 주요 시간속성들은 <Figure 7>과 같고, <Figure 8>과 같이 드론 다이어그램으로 표현하면 전체 비행에 대해 높은 가시성을 확보할 수 있다. 출발역과 도착역, 중간 정차역에 해당하는 노드와 각 역들을 연결하는 선로 표현과 시간 정보를 통한 열차운영계획 및 스케줄링에 널리 활용되는 열차 다이어그램과 유사하기에, 드론에서도 사전에 정의된 드론 배송 경로를 기반으로 최적의 운영을 위해 유용하게 활용될 수 있다.