모선-자선 협력 경로 최적화 = Mothership-Drones Collaborative Path Optimization

다국어 초록 (Multilingual Abstract)

The mothership-drone collaborative system is an operational framework in which a mobile platform (the mothership) supports the launch and retrieval of multiple drones, and the drones visit customers under limited payload capacity and endurance constraints. For efficient mission execution in such a system, collaborative route optimization that jointly considers the routes of the mothership and drones, as well as the launch-retrieval locations, is essential. Many previous studies assume a fixed mothership speed or allow the mothership to stop, and thus do not explicitly account for the minimum and maximum speed bounds that inherently exist for fixed-wing aircraft platforms. This study addresses the Mothership-Drones Collaborative Path Optimization problem that incorporates the minimum and maximum speed bounds of the mothership.
Because the problem requires simultaneously determining launch-retrieval locations and the routes of the mothership and drones in a continuous space, directly optimizing it is computationally challenging. To tackle this difficulty, we discretize the continuous space by sampling a set of candidate launch-retrieval vertices, construct routes by selecting vertices, and finally refine the launch-retrieval locations in the continuous space via nonlinear optimization. For the discretized problem, we formulate a mixed-integer linear programming (MILP) model, which serves as a benchmark that provides exact solutions to the discretized problem. We propose two frameworks with different solution-generation strategies in the discretized space. The metaheuristic-based ISGN uses a genetic algorithm as the core search engine on the sampled vertex set to generate the mothership and drone routes, and then improves the launch-retrieval vertex locations in the continuous space via nonlinear programming. The scheduling-heuristic-based ISHN derives the mothership route by solving a traveling-salesman-problem variant (M1-PDTSP) with the sampled vertex set as input, and subsequently improves the overall routes through continuous space nonlinear programming and local search.
To validate the performance of the proposed frameworks, Monte-Carlo simulations were conducted. As the number of customers increased, both frameworks exhibited increasing objective values and computation times; however, across all scenarios, ISHN achieved a lower mean objective value and a smaller standard deviation than ISGN, confirming its superiority in terms of solution quality and stability. ISHN showed smaller mean and standard deviation in computation time, demonstrating that it consistently produces high-quality solutions within shorter runtimes.

국문 초록 (Abstract)

모선-자선 협력 시스템은 이동식 플랫폼인 모선이 다수의 자선의 발진·회수를 지원하고, 자선이 제한된 탑재 용량과 체공시간 하에서 고객을 방문하는 운용구조이다. 이러한 시스템의 효율적 임무 수행을 위해서는 모선과 자선의 경로 및 발진·회수 위치를 함께 고려하는 협력 경로 최적화가 필수적이다. 기존 연구들은 모선의 속력을 고정하거나 정지 가능하다고 가정하는 경우가 많아, 고정익 항공기 플랫폼에서 존재하는 모선의 최소·최대 속력 범위를 명시적으로 고려하지 않았다. 본 연구는 모선의 최소·최대 속력 범위를 포함하는 모선-자선 협력 경로 최적화(Mothership-Drones Path Optimization) 문제를 다룬다.
본 문제는 연속 공간에서 발진·회수 위치와 모선과 자선의 경로를 동시에 결정해야 하므로, 이를 직접 최적화하는 것은 계산적으로 어렵다. 이에 연속 공간에 발진·회수 후보 정점 집합을 샘플링하여 이산화하고, 정점을 선택하여 경로를 구성한 뒤, 최종적으로 연속 공간에서 비선형 최적화를 통해 발진·회수 위치를 개선하는 접근을 취한다. 이때 이산화된 문제에 대해서는 혼합정수선형계획법(MILP) 모델을 제시하며, 이는 이산화된 문제의 정확해를 제공하는 기준 모델로 활용된다. 본 연구는 이산 공간에서의 해 생성 전략이 서로 다른 두 프레임워크를 제안한다. 메타-휴리스틱 기반의 ISGN은 샘플링된 정점 집합 위에서 유전 알고리즘을 핵심 탐색 엔진으로 사용하여 모선 및 자선 경로를 생성한 후, 연속 공간에서 비선형 계획법을 통해 발진·회수 정점 위치를 개선한다. 스케줄링 휴리스틱 기반의 ISHN은 샘플링된 정점 집합을 입력으로 외판원 문제 변형(M1-PDTSP)을 해결하여 모선 경로를 도출하고, 이후 연속 공간 비선형 계획법과 지역 탐색을 통해 전체 경로를 개선한다.
제안한 프레임워크의 성능을 검증하기 위해 몬테-카를로 시뮬레이션을 수행하였다. 고객 수 증가에 따라 두 프레임워크 모두 목적함수 값과 실행시간이 증가하는 경향을 보였으나, 모든 시나리오에서 ISHN이 ISGN보다 더 낮은 목적함수 평균과 더 작은 표준편차를 기록하여 해 품질과 안정성 측면에서 우수함을 확인하였다. 실행시간 또한 ISHN이 평균과 표준편차가 모두 더 작아, 더 짧은 시간 내에 일관되게 우수한 해를 도출함을 보였다.

목차 (Table of Contents)

• I. 서론 1
• 1.1 연구배경 1
• 1.2 관련 연구 동향 4
• 1.3 관련 연구 분석 9
• 1.4 기여 10
• II. 문제 정식화 12
• 2.1 가정 12
• 2.2 이산화 14
• 2.3 수학적 정식화 15
• III. 메타-휴리스틱 기반 ISGN 프레임워크 23
• 3.1 ISGN 프레임워크 개요 23
• 3.2 샘플링 24
• 3.3 유전 알고리즘 24
• 3.4 염색체 25
• 3.5 초기해 27
• 3.6 적합도 평가 28
• 3.7 교차 연산 32
• 3.8 돌연변이 연산 34
• 3.9 유전 알고리즘 결과 37
• 3.10 비선형 계획법 43
• IV. 휴리스틱 기반 ISHN 프레임워크 47
• 4.1 ISHN 프레임워크 개요 47
• 4.2 k-평균 군집화 48
• 4.3 샘플링 49
• 4.4 M1-PDTSP 50
• 4.5 2차 원뿔 계획법과 비선형 계획법 52
• 4.6 환승 탐색 55
• V. 결과 및 분석 57
• 5.1 ISGN의 결과 57
• 5.2 ISHN의 결과 62
• 5.3 몬테-카를로 시뮬레이션 64
• VI. 결론 75
• Abstract 78