Drones have been used in new types of transportation services such as drone-based package delivery and air transportation. One of the necessary elements for the drone-based transportation service system is a vertiport, which is a designated area for take-off and landing of drones. In the early phase of planning a network of vertiports, it is important to consider midair congestion of drone traffic in order to avoid the risk of collisions, because the risk increases complexity in scheduling and routing in the subsequent operations phase.
In this study, we propose a novel hub location problem that incorporates congestion occuring by interactions between hub-to-hub arcs. Our original formulation contains nonconvex bilinear terms, which is hard to solve. However, by exploiting the property of an optimal solution, we linearize the original problem using Reformulation-Linearization Technique. Even though we obtain a linearized version of the original problem, the problem still quickly becomes intractable as the size of the problem increases. To overcome the large-size problem, we develop a heuristic algorithm based on a genetic algorithm. Using numerical examples, we demonstrate that considering collision risks has a significant impact on the quality of the location solution derived from the mathematical model and confirm the improved performance of the heuristic algorithm.
드론은 드론 기반의 배송이나 공중 대중교통과 같은 새로운 형태의 교통 서비스의 중요한 부분으로 자리잡아가고 있다. 드론 기반 운송 서비스 시스템에 필요한 요소 중 하나는 드론의 이착륙을 위해 지정된 구역을 의미하는 출도착시설 (vertiport)이다. 출도착시설 네트워크의 형태에 따라 교통 관리 시스템의 운영 단계에서 필요한 비행 스케줄링이나 비행경로의 라우팅 등의 난이도가 증가하기 때문에 충돌의 위험을 감소시키기 위해 설계 시 상공의 혼잡을 고려하는 것이 중요하다.
본 연구에서는 허브와 허브 사이 아크 간의 상호작용에 의해 발생하는 혼잡을 고려하는 새로운 허브 위치 최적화 문제를 제안한다. 처음 제안한 문제는 비볼록 목적함수를 포함하고 있다. 우리는 최적해의 속성을 밝히는 명제를 제시함으로써 Reformulation-Linearization technique이 적용 가능함을 보이고 기존 문제를 선형화하였다. 기존 문제의 선형화에도 불구하고, 문제의 크기가 증가함에 따라 현실적으로 다루기 어려운 문제가 된다. 이러한 문제점을 극복하기 위해 유전 알고리즘에 기초한 휴리스틱 알고리즘을 개발하였다.
마지막으로 정확한 위험 추정함수를 이용하는 것의 중요성을 실험을 통해 확인하고 시설 운영 비용과 위험 우려 정도의 변화가 최적해에 미치는 영향 등을 관찰하였으며 제안한 휴리스틱 알고리즘의 성능을 검증하였다.
