In this study, the exact algorithm of generalized vehicle routing problem for persistent UAV system is developed and investigated. Using the characteristics of UAVs a mixed linear integer programming is formulated. The MILP contains multiple depots, multiple trips, an initial condition, capacity, and distance constraints. The exact algorithm so solve MILP is developed based column generation. The master problem is a set partitioning problem which is identical with decomposition of VRPTW, while subproblem has more constraints which the UAV characteristics have to be reflected. The subproblem is a generalized version of elementary shortest path problem as it allows multiple reuse and initial condition. Solving subproblem spend most of the time in column generation. Therefore, we used a dynamic algorithm called label correcting algorithm. The branch-and-price showed a better performance than solving MILP directly, which was 50 times faster of execution time in best case. Branch-and-price showed better result in mixed type customer instance when problem size get bigger.
본 연구에서는 지속적인 무인항공기 시스템을 위한 일반 차량 경로 문제의 최적해 알고리즘을 개발하고 연구하였다. 기존의 차량 경로 문제와 차별화되는 무인 항공기 시스템의 특징이 정의되었고, 이 특성을 이용하여 혼합 선형 정수 계획법이 모델링된다. 혼합 선형 정수 계획법에는 다중 거점, 다중 경로, 초기 조건, 거리 및 용량 제약이 포함된다. 최적해를 찾는 알고리즘은 열 생성 기법을 기반으로 개발되었다. 마스터 문제는 시간제약이 있는 차량 경로 문제에서 일반적으로 정의되는 집합 파티셔닝 문제이며 하위 문제에는 무인 항공기 특성을 반영해야 하는 제약이 더 많다. 하위 문제는 다중 경로와 초기 조건을 허용하므로 기본 최단 경로 문제의 일반화 된 형태이다. 열 생성 기법의 대부부의 시간은 하위 문제에 소비되므로, 레이블 수정 알고리즘이라는 동적 알고리즘으로 하위 문제를 풀었다. 분지평가법은 혼합 선형 정수 모형을 직접 푸는 것보다 우수한 성능을 보였으며 최상의 경우 실행 시간이 50배 이상 빨랐다. 문제 규모가 커지면 분지평가법은 더 나은 결과를 보였다.
