J Appropr Technol > Volume 8(2); 2022 > Article
P-중앙값과 보로노이 다이어그램을 활용한 복합적 주행환경에서의 무인 배송 로봇 협력배송경로 구현을 위한 이동가능지점 선정 방안 연구

Abstract

최근 자율주행 기술이 크게 발달하면서 노동집약적이고 위험한 환경에서의 배송업무의 로봇 적용이 시도되고 있다. 드론과 모바일 배송 로봇 등과 같이 다양한 크기와 목적으로 구현된 무인 배송 로봇이 개발되었지만, 제한된 주행 특성으로 배송지까지의 물류배송을 구현하기 위해서는 여러 배송 로봇의 협력이 필요로 하다. 이 연구에서는 다양한 주행 환경을 극복하기 위한 여러 배송 로봇의 협력주행 시나리오를 구축하였다. 1대의 자율주행 화물 차량과 5대의 모바일 배송 로봇으로 차도와 인도를 주행하는 주행영역을 비교분석을 하여, 이동가능지점 선정에 활용하였다. 화물 차량은 차도와 인도에서 주행 가능한 5대의 모바일 배송 로봇을 이동가능지점에 하차시켜, 모바일 배송 로봇이 차량접근이 불가능한 배송지로 물품을 이송할 수 있도록 한다. 모바일 배송 로봇이 배송지까지 최소이동 거리를 가지는 이동가능지점을 찾기 위해, 본 논문에서는 P-중앙값과 보로노이 다이어그램 꼭짓점을 사용하여 선정하였으며, 각 방법론의 특징과 결과를 비교 분석하여 보로노이 다이어그램 방법론의 위치선정문제 적용 가능성을 확인하였다. P-중앙값을 사용한 이동가능지점은 실제 도로의 거리를 토대로 계산되었으며, 짧은 평균 이동 거리를 가진다. 보로노이 다이어그램 방법론은 위치정보를 토대로 유클리디언 거리를 이용하기에, 이동가능지점을 선정하는데 계산시간이 P-중앙값에 대비하여 짧다. 그 결과 물류배송 중 발생하는 상황에서 보로노이 다이어그램 방법론의 사용 적용성이 있다고 판단되며, 도로정보와 인프라가 부족한 험지와 오지에서도 활용 가능성이 있다고 보인다.

With the recent development of autonomous driving technology, various unmanned vehicles such as serving robots, mobile delivery robots, and drones have been developed. However, each robot has a different driving area, so it is necessary to find cooperative route for optimal unmanned delivery. In this paper, a cooperative scenario of an autonomous courier vehicle and five mobile delivery vehicles perform unmanned delivery tasks. The courier vehicle moves from a warehouse to the second hierarchy point, and drops off the five mobile delivery vehicles in order to transport goods to the doorstep of the destinations. We define the second hierarchy point by using the P-Median method and the Voronoi diagram method, and compare the results of each method using real map data. The points using P-Median are calculated based on the actual road distance and have shorter average moving distance than the Voronoi diagram method. The Voronoi diagram uses the Euclidian distance based on location information, which defines the second hierarchy point faster than the P-Median method. By comparing the results, we consider the Voronoi diagram method have capability in the cooperative multi-vehicle delivery route problem. The result of this paper have potential to be used in rough and remote areas where road information and infrastructure are lacking.

서론

자율주행기술의 발달로 공장에서 사람을 대신하여 일하던 로봇은 공장을 벗어나 다양한 곳에서 적용이 시도되고 있다. 운행서비스뿐만 아니라 서빙 로봇, 배송 로봇과 같은 다양한 서비스들이 나타나기 시작하면서(Kim et al ., 2017) 높은 노동강도를 가지고 있는 물류 배송 서비스에서의 적용이 시도되고 있다(Lee, 2021). 또한, 모바일 배송 로봇, 드론과 같은 다양한 자율주행 배송 로봇이 나타나면서(Chong et al ., 2012), 기존에 물류배송이 힘들었던 위험한 험지와 소외되어온 오지에 자율주행 물류배송의 가능성을 보인다(Maeng et al ., 2021; Lee, 2022). 하지만, 이러한 로봇은 각각의 주행환경의 특성에 맞춰 개발되었기에, 제한된 주행영역을 넘어 복합적인 환경에서의 자율주행 배송실현을 위해서는 다양한 기종 간의 협업 배송이 필요로 하다. 기존의 협업 배송은 이기종 간의 배송으로(Chen et al ., 2019; Deng et al ., 2019; Mathew et al ., 2015) 하늘, 지상, 해양, 등 전혀 다른 주행영역을 운행하는 이기종들의 협업을 통해 이루어진다. 이기종은 서로 간에 만날 수 있는 지점이 제한되어 있어, 기존에는 후보 지점 중 가장 가까운 지점을 이동 가능지점을 선정하여 진행되었다(Garone et al ., 2011). 하지만, 다양한 환경을 주행할 수 있는 각각의 배송 로봇이 등장하면서, 주행 영역의 범위가 복잡해지면서, 가장 가까운 지점이 이동가능지점으로 단정하기 어려워졌다(Yang et al ., 2010).
주행영역이 분명하게 나뉘는 이기종 배송 로봇과 달리, 다양한 배송 로봇의 주행영역은 같은 주행영역 안에서도 다양하게 나뉘어진다. 지상 영역의 경우, 차도와 인도, 그리고 도로가 없는 험지와 같이 주행영역이 나누어지며, 하늘과 해양에서도 주행 높이에 따라 기체가 달라진다. 이처럼 세부 주행영역으로 인해 배송 로봇들의 이동가능지점 후보지가 무수히 많아지면서, 적합한 이동가능지점을 선정할 필요성이 생겨났다. 본 연구에서는 차량과 모바일 배송 로봇을 대상으로 서로 다른 주행영역을 분석하고, 협업배송경로 생성을 위한 이동가능지점 선정 방법을 고찰하였다.

이론적 배경

동시에 복합적인 판단과 다양한 일을 처리할 수 있는 사람과 달리, 현재 대부분 로봇은 한가지 기능을 구현하도록 설계제작 되어 있다. 하지만, 물류배송문제는 여러 환경을 거쳐 목적지에 도착하기 위해 로봇에게 복합적인 기능을 요구한다. 예를 들어 기존 화물 업무를 보면, 차량을 통해 물품을 배송지 근처로 이송한 뒤, 배송기사가 물품을 하차하여 배송지에 전달하는 복합적인 업무이다. 이러한 업무를 자율주행 배송 로봇으로 진행하기 위해서는, 도로주행이 가능한 자율주행 차량과 도로와 인도를 오갈 수 있는 모바일 배송 로봇의 협업으로 물품이 배송될 수 있을 것이다. 이러한 협업 배송에 대해 기존의 협업 경로에 관한 연구들을 살펴보면 Travel salesman problem (TSP), Genetic algorithm, Ant colony algorithm 등을 활용하여 이기종 경로를 탐색해 온 것을 알 수 있다(Chen et al ., 2019; Yang et al ., 2010). Drexel (2012)은 협업 경로에 있어서 문제에 따라 Mixed integer programming, branch-and-bound, branch-and-price, metaheuristics 등과 같은 방법들을 사용하여 진행하였다. Deng et al . (2019)은 Unmanned ground vehicle (UGV)과 Unmanned aeral vehicle (UAV)의 경로를 선정하기 위해 UAV의 운행 시간을 고려한 GTSP (Generalized Traveling Salesman Problem)을 사용하였으며, 두 수송체가 만날 수 있는 이동 가능지점은 UAV의 주행이 끝나는 지역과 가장 가까운 곳으로 선정하였다. Mathew et al . (2015)은 Genetic algorithm을 활용하여 경로생성을 진행하며, UGV과 UAV 만날 수 있는 지점을 경로생성 전에 지정하였다. Garone et al . (2011)은 선박과 항공기를 활용한 환자이송문제에 대해 두 수송체가 정차하는 포인트를 기준으로 TSP를 활용하여 경로를 구성하였다.
앞선 이기종 간의 협엽 경로에 관한 연구들을 통해서, 서로 다른 배송체의 경로생성을 위해서는 사전에 이동가능지점을 선정하는 것이 필요로 한 것을 알 수 있다. 기존 연구에서 진행된 이기종 배송 로봇와 달리, 본 연구에서 진행하는 화물 차량과 모바일 배송 로봇은 중첩되는 주행 경로를 가지고 있다. 화물 차량은 도로에서 주행하며, 모바일 배송 로봇은 도로와 인도에서 주행 가능함으로서, 두 수송체가 만날 수 있는 이동가능지점은 차도 위의 모든 지점이 된다. 가장 가까운 도로를 이동가능지점을 할 경우, 베터리 용량 제한으로 상대적으로 주행거리가 짧은 모바일 배송 로봇의 주행 거리가 길어져 주행을 제대로 마칠 수 없다. 기존의 연구들을 통해 이기종 간의 협업 경로의 경우, 각각 한 대의 기종을 사용하여 협업 경로를 구성한 것을 알 수 있다. Deng et al . (2019)은 한 대의 UAV와 한 대의 UGV의 협업 주행을 위하여 드론의 주행이 끝나는 지점을 이동가능지점으로 선정하였다. 본 연구에서는 기존 연구와 달리 한 대의 화물 차량과 다수의 모바일 배송 로봇의 경로 설정을 고려하고 있다. 이 경우 모바일 배송 로봇의 이동 거리를 최소화하며 화물 차량의 이동 또한 최소화 할 필요성이 있다.
다수의 모바일 배송 로봇이 최소거리를 이동하여 배송지에 접근 가능한 이동가능지점을 찾기 위해, 본 연구에서는 위치선정방법론을 활용하였다. 위치선정방법론은 수요자가 필요로 한 설비 혹은 장소의 입지를 선정하는 방법론으로, 다양한 방법론들이 개발됐다. 본 연구에서는 여러 방법론 중에서 수요자들로부터 평균 거리가 최소가 되는 P개의 위치를 찾는 P-중앙값 방법론을 활용하였다. 이 방법론은 Hakimi (1964)에 의해 소개되었으며, 학교, 도서관, 응급실과 같이 접근성이 우선적으로 고려되는 공공기관 위치선정에 사용되었다. 이뿐만 아니라, 전력망의 길이를 최소화하는 변전소의 위치, 지역 내 인구모델을 활용한 천연가스버스 충전소, 교통량 데이터를 활용한 전기차충전소와 같이 다양한 곳에서도 활용되었다(Yu et al ., 2008; Park et al ., 2013). P-중앙값 방법론의 기본 모형은 다음과 같다.
(1.1)
minijaidijXij,subject to
(1.2)
jXij=1,iI,
(1.3)
jYj=P,jJ,
(1.4)
XijYj,jJ,iI,
(1.5)
Xij0,1,jJ,iI,
(1.6)
Yj0,1,jJ.
식 (1.1)은 목적함수로 수요지 i 와 입지점 j 의 거리 dij 값이 최소가 되는 위치를 찾는 것을 목적으로 한다. 이때 ai 는 수요지 i 에 대한 수요량을 의미하며, 이는 각 지점의 사용 수요자들에 대한 비중을 같이 고려하는 것이다. 식 (1.2)는 제약조건으로 수요지 i 는 반드시 입지점 j 로부터 서비스를 받아야 함을 나타내는 조건이다. 식 (1.3)의 제약조건을 통해 선택된 입지의 개수가 P 개가 되도록 함을 나타낸다. 식 (1.4)는 수요지 i 가 입지점 j 로부터 서비스를 받는 경우, j 지점이 반드시 운영돼야 함을 보여준다. 식 (1.5)식 (1.6)은 결정변수로 0 혹은 1 의 값을 가져 입지 여부를 결정한다.
P-중앙값 방법론을 통해 화물 차량과 모바일 배송 로봇이 최소거리 이동을 통해 만날 수 있는 지점 선정에 활용 가능할 것으로 보이나, 물류배송문제에 입지선정모델 적용에는 한계가 있다. 입지선정모델과 달리 물류배송문제는 배송 중에 배송지가 추가 혹은 변경되거나, 도로상황이 변경될 수 있는 동적인 문제로, P-중앙값과 같은 위치선정모델은 설정된 요소 변경이 계산 중에는 적용되지 않으며, 계산에 많은 시간이 필요하다. 이러한 계산소요시간으로 인해 도로 네트워크 상태가 계속적으로 변화하는 동적인 모델에서는 적합한 의사결정을 할 수 없는 경우가 생길 수 있다, 특히 험지와 오지의 경우, 도로 인프라의 정보가 부족하여 위치선정이 불가능 할 수 있다. 하여, 본 연구에서는 도로정보가 아닌 지역 위치정보를 이용하는 보로노이 다이어그램을 적용 위치선정을 진행하여, P-중앙값 방법론과 비교 대조해 보았다.
보로노이 다이어그램은 2차원 공간에 있는 점들을 직선을 통해 공간을 나누는 방법으로 2차원뿐만 아니라 3차원 공간에서도 활용된다(Liu and Zhang, 2009). 평면에 있는 점집합 p={p1, p2, ..., Pn} 이 주어진 경우, 인접한 점들을 연결하여 이루어진 선들을 수직이등분선으로 분할 하는 방법으로, 이 수직이등분선을 활용하여 공간분할 가능하다. 공간분할을 통해 생성된 다각형을 보로노이 다이어그램이라 하며 이는 V={V(p1), V(p2), ..., V(Pn)}으로 표현한다. 이렇게 생성된 다이어그램은 공간 내에 장애물 회피하는 경로생성 및 비행체의 경로생성과 같은 다양한 환경에서 활용하고 있다(Marbate and Jaini, 2013; Ghorpade, 2016). Bhattacharya and Gavrilova (2008)은 보로노이 다이어그램을 활용하여 복잡한 환경에서도 자율주행로봇이 장애물에 부딪히지 않는 경로를 생성하였으며, Ayawli et al . (2019)Garrido et al (2006)는 동적인 환경에서도 빠르게 장애물을 회피하는 경로를 만드는 것을 보로노이 다이어그램을 활용하여 보였다. 이처럼 빠른 시간 안에 운행이 가능한 지역을 선정함에 보로노이 다이어그램사용이 적합한 것을 앞선 연구들을 통해 확인할 수 있다. 공간을 빠르게 분할 할 수 있는 장점으로 계산시간이 필요로 하지 않기에 빠른 선택이 가능한 것으로 판단되어 본 연구에서 각 배송지의 지리정보를 활용하여 이동가능지점 선정하는 것에 활용하였다.

연구 방법

본 연구에서는 도로주행이 가능한 한 대의 화물 차량과 다섯 대의 모바일 배송 로봇이 협업하는 시나리오를 구성하였다. 모바일 배송 로봇은 차도와 인도를 자유롭게 주행 가능하며, 1대의 배송 로봇이 1곳의 배송지에 물품을 배송하는 시나리오를 가진다. 연구의 대상지로 서울대학교 지도를 활용하였으며 지도정보는 OSM (Open Street Map)을 통해 정보를 취득하였다. 화물 차량이 주행 가능한 도로는 차도로 서울대학교 지도에서 152개의 도로 교차점을 가지고 있으며, 모바일 배송 로봇이 주행 가능한 도로는 차도와 인도로 532개의 도로 교차점을 가지고 있다. 화물 차량과 모바일 배송 로봇이 만날 수 있는 후보지는 차도 위의 모든 지점이며, P-중앙값 방법론에서의 거리계산은 도로정보를 토대로 계산하여, 배송지로부터 최소이동 거리를 가지는 이동가능지점을 찾는 데 사용하였다.

1. P-중앙값 모델링을 활용한 위치선정방안

P-중앙값 모델링은 기본 모형을 근거로 다음과 같이 변형하였다.
(2.1)
minijdijXij,subject to
(2.2)
jXij=1,iI,
(2.3)
P=NumberofdestinationsNmberofmobilevehicles,
(2.4)
jYj=P,jJ,
(2.5)
jJXijYj,jJ,   jI,
(2.6)
Yj{0,1},   jJ.
<Index>
I : 배송지
J : 이동가능지점 후보지152개의 도로 노드
dij : ij 사이의 실제 이동거리
xij : 결정변수
Yj : 결정변수
식 (2.1)은 목점함수로 이동가능지점으로부터 배송지까지의 거리를 최소를 가지도록 구성되었다. 본 모델에서는 수요량이 지점마다 같으므로 aij 는 생략된다. di,jij 사이의 실제 도로 거리를 나타내며, I 는 5개의 배송지, J 는 이동가능지점 후보지로 152개의 모든 도로를 나타낸다. 식 (2.2)는 5대의 모바일 배송 로봇은 모두 이동가능지점으로부터 이송되는 것을 나타내며, 식 (2.3)식 (2.4)을 통해 이동가능지점의 개수 P를 선정한다. 본 연구에서는 5개의 배송지에 대해 5대의 배송 로봇이 각각 배송 가능함으로, 하나의 이동가능지점이 필요하여 P 값은 1을 가진다. 선정된 위치는 이동가능지점으로 사용 가능하며 이에 할당하기 위해 식 (2.5) 같이 표현하였다. 식 (2.6)과 식 (2.7)은 결정변수로 이동가능지점이 사용 가능한 경우 1, 불가능한 경우 0, 이동가능지점으로부터 배송지까지 이동 가능한 경우 1, 불가능한 경우 0과 같이 이진 변수로 표현하였다. P-중앙값 방법론은 ILOG CPLEX Optimize studio 12.10을 활용하여 계산하였으며, 보로노이 다이어그램은 Colab python 3.6 환경으로 계산하였다.

2. 보로노이 다이어그램을 활용한 위치선정방안

보로노이 다이어그램 적용을 위해 아래와 같이 모델링 하였다. n 개의 배송지를 가지고 있을 때, 각 지점 pi의 위치정보는 다음 식 (3.1)과 같이 표현된다. i 는 개별 배송지 번호이다.
(3.1)
pi=(xlatitudei,xlongitudei).
n 개의 배송지 정보는 아래 식 (3.2)으로 나타낼 수 있다.
(3.2)
Pi={p1,p2,,pn}.
이웃한 점들의 수직이등분선은 B(pi, pj)={y|d(pi, y)=d(pj, y)}로 정의되며, d는 유클리디안 공간에서의 두 점 사이의 직선거리를 뜻한다. 앞서 실제 도로를 따라 이동하는 거리 di,j 와 다른 수치이다. 이 수직이등분선으로 주행 공간은 식 (3.3)과 같이 나누어진다.
(3.3)
V(i)={yd(y,pi)d(y,pj)},   for ij.
Figure 1(a)는 {p1, p2, p3, p4, p5}의 배송지를 갖는 경우에 대한 이웃한 배송지들의 수직이등분선을 나타내고 있다. 그림에서 이 수직이등분선의 교차점은 {v1, v2, v3}와 같이 가진다. 이렇게 배송지점 정보를 토대로 만들어진 수직이등분선들의 교차점들을 중심으로, 이와 연관된 배송지들 pi를 접점으로 하는 외접원을 생성할 수 있다. Figure 1(b)Figure 1(a)의 교차점을 중심으로 외접원을 생성한 예시이다. 생성된 외접원의 반지름의 크기를 비교하여, 가장 작은 반지름을 가지고 있는 교차점을 이동가능지점으로 선정한다. Figure 1(c)v1을 중심으로 하는 원의 반지름이 가장 작음을 나타내고 있다. 이때 반지름의 크기 R을 산출하기 위하여 식 (3.4) ~ (3.6)와 같이 헤론의 공식을 이용 하였으며, 가장 작은 반지름 R을 가지는 vi,를 이동가능지점으로 선정하였다.
헤론의 공식은 주어진 서로 다른 세 점 pi, pj, pk 을 지나는 최소 반지름을 갖는 원의 반지름을 구하는 공식으로, 핵심을 요약하면 다음과 같다. 주어진 점 pi, pj, pk식 (3.4)부터 (3.6)까지 적용하면 최소 반지름 Rpi, pj, pk 을 구할 수 있다.
(3.4)
s=d(pi,pj)+d(pj,pk)+d(pk,pi)2,
(3.5)
S=s(s-d(pi,pj))(s-d(pj,pk))(s-d(pk,pi)),
(3.6)
Rpi,,pj,pk=d(pi,pj)d(pj,pk)d(pk,pi)4S(S-d(pi,pj))(S-d(pj,pk))(S-d(pkpi)),
Figure 1(b)에서 3개 원의 반지름은 각기 Rp1, p2, p3, Rp3, p4, p5, Rp1, p3, p5이다. 이중 가장 짧은 반지름 Rmin은 다음의 (3.7)식으로 구할 수 있다.
(3.7)
Rmin=min (Rp1,p2,p3,Rp3,p4,p5,Rp1,p3,p5).

결과 및 고찰

실험을 통한 결과를 배송지 간의 거리 간격에 따라 선정된 위치와의 거리 관계를 비교 분석하였다. Figure 2은 실험결과 중 대표적인 내용을 보여준다. Figure 2(a)는 배송지 간의 간격이 일정 이상 떨어져 있는 경우, (b)는 일부 배송지 간의 간격이 가까운 경우, (c)는 모든 배송지 간의 거리가 인접한 경우를 보여준다. 각 배송지는 파란색 동그라미로 나타냈으며, 빨간 사각형 지점은 P-중앙값을 활용하여 선택된 지점이며, 보로노이 다이어그램을 활용한 지점은 녹색 사각형으로 표시하였다. Figure 2의 경우, 이동가능지점으로부터 5개의 배송지 간의 거리는 다음 Table 1과 같다. 거리 계산에는 다익스트라 알고리즘(Dijkstra et al ., 1959)을 활용하여 실제 도로를 기준으로 거리를 측정하였다.
Figure 2Table 1에 보이듯, 전체 거리와 평균 거리에 대해 P-중앙값의 방법론이 더 짧은 거리를 이동하는 것을 보여주었다. 하지만 Case (c)와 같이 배송지 간의 거리가 인접한 경우, 두 방법론을 통한 이동가능지점의 위치에 큰 차이가 나지 않는다. 지도상의 위치를 보더라도 근접한 위치를 선정하는 것을 알 수 있다. 보로노이 다이어그램을 통해 선정된 위치는 P-중앙값에 비해, 전체 거리와 평균 거리에 대해 큰 값을 보여주지만, 지도 위에서 선정된 위치를 확인해 보면, 각각의 배송지들을 연결한 선 안에 위치하는 것을 알 수 있다. 배송지의 개수가 5개가 아니라 임의의 개수 n을 가지더라도, 선택된 이동가능지점은 각 배송지들을 연결한 범위 안에 위치한다.

결론

이 연구는 서로 다른 로봇들의 협업을 위한 물류배송경로 생성을 위해 P-중앙값과 보로노이 다이어그램을 사용하여 이동가능지점 선정해 보았다. 실제 도로정보를 활용하여 최소평균거리를 가지는 지점을 찾는 P-중앙값은 보로노이 다이어그램에 비해 평균적으로 짧은 거리를 가지는 지점을 찾아주었다. 그러나, 이 방법은 위치선정을 위해 모든 도로 노드를 계산해야 하며, 이로 인해 계산에 시간이 소요된다. 반면에 보로노이 다이어그램은 도로정보가 아닌 지역의 위치정보로만 계산된다. 도로정보가 사용되지 않기에, 선정된 이동가능지점과 배송지 간의 거리는 P-중앙값에 비해 더 멀지만, 계산에 시간이 P-중앙값에 비해 짧다. 이로 인해 빠른 계산이 필요한 주행 중 상황, 혹은 도로정보가 확보되지 않은 험지와 오지에서 사용하기 적합할 것으로 보인다.
본 연구에서는 서울대학교 차도와 인도 정보를 기준으로 진행되었으나, 다양한 환경에서의 적합성을 위해 도로정보가 구축되지 않은 험지와 도로에서 구현할 필요성이 있다. 또한, 배송 중에 배송지가 바뀌거나, 추가적인 배송지가 도로주행 중에 발생하는 경우와 같이 다양한 환경에서 실험하며 검증할 필요성이 있다고 본다. 본 연구에서는 차도와 인도의 주행영역의 범위가 같다. 하지만 도로 인프라가 확충되지 않은 험지 혹은 인프라 정보가 부족한 오지의 경우, 세부 주행영역의 범위가 서로 다르다. 이러한 주행영역에 대한 특성을 분석하고 이에 맞는 위치선정방법에 대한 연구가 필요할 것으로 보인다.

Acknowledgments

이 논문은 국토교통부의 스마트시티 혁신인재육성사업과 서울대학교의 그린 캠퍼스 실천을 위한 수경재배 스마트 파밍기술개발연구, 교육부 및 한국연구재단의 4단계 두뇌한국21 사업(4단계 BK21 사업), 그리고 서울대학교 공학연구원의 지원을 받아 수행된 연구입니다.

Figure 1
The way to find the second hierarchy points using the voronoi diagram vertices. (a) Finding vertices based on five destination locations, (b) The circumscribed circles base on the vertices, (c) Selecting the smallest circumscribed circle base on radius size.
jat-2022-00129f1.jpg
Figure 2
The selected second hierarchy points by p-median and voronoi diagram and five random destinations in SNU (a) all five destinations are located away, (b) some of random destination are located closely, (c) all five destinations are located closely.
jat-2022-00129f2.jpg
Table 1.
Distances from the second hierarchy points where selected by p-median and voronoi diagram method to five destinations [Unit: m]
Total Average Min. Max.
Case (a) P-중앙값 1,023 5,117 625 1,700
보로노이 다이어그램 1,073 536 802 1,600
Case (b) P-중앙값 5,420 1,080 710 1,155
보로노이 다이어그램 6,230 1,246 830 1,900
Case (c) P-중앙값 180 902 77 328
보로노이 다이어그램 159 795 36 313

References

Ayawli, B.B.K., Mei, X., Shen, M., Appiah, A.Y., and Kyeremeh, F. (2019). Mobile robot path planning in dynamic environment using voronoi diagram and computation geometry technique. Ieee Access, 7, pp. 86026-86040.
crossref
Bhattacharya, P., and Gavrilova, M.L. (2008). Roadmap-based path planning-using the voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine, 15(2), pp. 58-66. DOI:10.1109/MRA.2008.921540.
crossref
Chen, M., Chen, Y., Chen, Z., and Yang, Y. (2019). Path planning of uav-ugv heterogeneous robot system in road network, In International conference on intelligent robotics and applications, pp 497-507.
crossref
Chong, Z.J., Qin, B., Bandyopadhyay, T., Wongpiromsarn, T., Rebsamen, B., Dai, P., Kim, S., Ang, M.H., Hsu, D., Rus, D., and Frazzoli, E. (2013). Autonomy for mobility on demand, Intelligent Autonomous Systems, 12, pp. 671-682. Springer, Berlin, Heidelberg.
crossref
Deng, D., Jing, W., Fu, Y., Huang, Z., Liu, J., and Shimada, K. -2019. Constrained heterogeneous vehicle path planning for large-area coverage, In 2019 ieee/rsj international conference on intelligent robots and systems (iros), pp 4113-4120.
crossref
Dijkstra, E.W., and et al (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), pp. 269-271.
crossref pdf
Drexl, M. (2012). Synchronization in vehicle routing-a survey of vrps with multiple synchronization constraints. Transportation Science, 46(3), pp. 297-316. https://doi.org/10.1287/trsc.1110.0400.
crossref
Garone, E., Naldi, R., and Casavola, A. (2011). Traveling salesman problem for a class of carrier-vehicle systems. Journal of Guidance, Control, and Dynamics, 34(4), pp. 1272-1276.
crossref
Garrido, S., Moreno, L., Abderrahim, M., and Martin, F. (2006). Path planning for mobile robot navigation using voronoi diagram and fast marching, In 2006 ieee/rsj international conference on intelligent robots and systems, pp 2376-2381.
crossref
Ghorpade, S. (2016). Airspace configuration model using swarm intelligence based graph partitioning, In 2016 ieee canadian conference on electrical and computer engineering (ccece), pp 1-5.
crossref
Hakimi, S.L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), pp. 450-459. https://doi.org/10.1287/opre.12.3.450.
crossref
Kim, S.-W., Gwon, G.-P., Hur, W.-S., Hyeon, D., Kim, D.-Y., Kim, S.-H., Kye, D.-K., Lee, S.-H., Lee, S., Shin, M.-O., and Seo, S.-W. (2017). Autonomous campus mobility services using driverless taxi. IEEE Transactions on Intelligent Transportation Systems, 18(12), pp. 3513-3526. DOI:10.1109/TITS.2017.2739127.
crossref
Lee, J.-S. (2021). Autonomous Freight Vehicles and Freight Transportation Market [자율주행 화물자동차와 화물운송시장], Monthly KOTI Magazine on Transport, pp. 6-11. https://www.dbpia.co.kr/Journal/articleDetail?nodeId=NODE11058319.
Lee, T.-H. -2022. Research Direction and Tasks of Logistic Research Headquarters for 2022: Smartization, Digitalization, and Establishment of Growth Strategy for Non-face-to-face Logistics Service Industry [2022년 물류연구본부 연구방향 과 과제 : 스마트화·디지털화, 비대면 물류서비스 산업 성장 전략 구], Monthly KOTI Magazine on Transport, pp. 36-41. https://www.dbpia.co.kr/Journal/articleDetail?nodeId=NODE10520740.
Liu, L., and Zhang, S. (2009). Voronoi diagram and gis-based 3d path planning, In 2009 17th international conference on geoinformatics, pp 1-5.
Maeng, M.S., Ahn, S.H., Moon, J.H., and Dockko, S. (2021). Strategies for a Phase 2 Road Map of Global Problem Solving Center 2030. Journal of Appropriate Technology, 7(1), pp. 115-124.
crossref pdf
Marbate, P., and Jaini, P. (2013). Role of voronoi diagram approach in path planning. International Journal of Engineering Science and Technology, 5(3), pp. 527.https://doi.org/10.37675/jat.2021.7.1.115.
crossref
Mathew, N., Smith, S.L., and Waslander, S.L. (2015). Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions on Automation Science and Engineering, 12(4), pp. 1298-1308. DOI:10.1109/TASE.2015.2461213.
crossref
Park, B., Lee, K.J., and Choi, K. (2013). Optimum location choice for bike parking lots using heuristic p-median algorithm. Journal of the Korean Society of Civil Engineers, 33(5), pp. 1989-1998.
crossref
Yang, J., Qu, Z., Wang, J., and Conrad, K. (2010). Comparison of optimal solutions to real-time path planning for a mobile vehicle. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 40(4), pp. 721-731. DOI:10.1109/TSMCA.2010.2044038.
crossref
Yu, J.-W., Lee, M.-Y., and Oh, S.-C. (2008). A model of location decisions of natural gas filling station considering spatial coverage and travel cost. Journal of Korean Society of Transportation, 26(3), pp. 145-153.
TOOLS
METRICS Graph View
  • 0 Crossref
  •  0 Scopus
  • 174 View
  • 9 Download
Related articles


ABOUT
BROWSE ARTICLES
EDITORIAL POLICY
FOR CONTRIBUTORS
Editorial Office
1F, 9-ho, 79, Seoun-ro, Seocho-gu, Seoul 06630, Republic of Korea
Tel: +82-2-887-0226    E-mail: editor.ejat@gmail.com                

Copyright © 2022 by Academic Society for Appropriate Technology.

Developed in M2PI

Close layer
prev next