The duration of missions that can be accomplished by unmanned aerial vehicles (UAVs) is limited by the battery or fuel capacity of its constituent UAVs. However, a system of UAVs that is supported by auto-mated refueling bases may support long term or even indefinite duration missions in a near autonomous mode. The UAVs can return to a base, replenish their resources and resume their duties. We develop a mixed integer linear program model to formalize the problem of scheduling such a system that includes multiple bases in disparate geographic locations that are shared between the UAVs. The system consists of a heterogeneous fleet of UAVs (each with different travel speed and distance capabilities), refuel stations and mission trajectories that must be followed by at least one UAV. A UAV may hand off the mission to another in order to return to base for a fuel recharge. For our persistent UAV observing service, we introduce new VRP that is distance constrained heterogeneous VRP with time window, multi-depot route and multiple trips. For the small size example problems, a state of-the-art MILP solver such as CPLEX is sufficient to create a schedule for the model. However, for the large size example problems or dynamic environment, CPLEX turned out that it is not sufficient to create a schedule due to the complexity of this problem. Therefore, to overcome the computation limit of CPLEX, RHTAm was developed and the results are compared with that of CPLEX. This is the first time that a generic scheduling model has been developed that allows mobile agents to return to service after refueling across multiple bases. In practice, the approach allows for a long-term mission to receive uninterrupted UAV service by successively handing off the task to replacement UAVs served by geographically distributed shared bases.
A fleet of unmanned aerial vehicles (UAVs) supported by logistics infrastructure, such as automated service stations, may be capable of long-term persistent operations. Typically, two key stages in the deploy-ment of such a system are resource selection and scheduling. Here, we endeavor to conduct both of these phases in concert for persistent UAV operations. We develop a mixed integer linear program (MILP) to for-mally describe this joint design and scheduling problem. The MILP allows UAVs to replenish their energy resources, and then return to service, using any of a number of candidate service station locations distributed throughout the field. The UAVs provide service to known deterministic customer space-time trajectories. There may be many of these customer missions occurring simultaneously in the time horizon. A customer mission may be served by several UAVs, each of which prosecutes a different segment of the customer mis-sion. Multiple tasks may be conducted by each UAV between visits to the service stations. The MILP jointly determines the number and locations of resources (design) and their schedules to provide service to the cus-tomers. We address the computational complexity of the MILP formulation via two methods. We develop a branch and bound algorithm that guarantees an optimal solution and is faster than solving the MILP directly via CPLEX. This method exploits numerous properties of the problem to reduce the search space. We also develop a modified receding horizon task assignment heuristic that includes the design problem (RHTAd). This method may not find an optimal solution, but can find feasible solutions to problems for which the other methods fail. Numerical experiments are conducted to assess the performance of the RHTAd and branch and bound methods relative to the MILP solved via CPLEX. For the experiments conducted, the branch and bound algorithm and RHTAd are about 550 and 20,000 times faster than the MILP solved via CPLEX, respectively. While the branch and bound algorithm obtains the same optimal value as CPLEX, RHTAd sacrifices about 4.3% optimality on average.
연료의 제한이 있는 무인항공기는 임무 시간의 제약이 존재한다. 복수의 무인항공기와 연료를 재충전 해주는 충전기지를 효율적으로 운용하면 장 시간의 임무들을 주어진 계획 시간 동안 처리 할 수 있다. 제 2 장에서는 이러한 무인 항공기와 충전기지의 효율적인 운영을 위한 방법을 개발하였다. 이를 위하여 새로운 차량 경로 문제를 도입하였으며 혼합 정수 계획법 모델을 개발하였다. 이 모델에서는 복수의 충전기지가 존재하며 여러 종류의 무인항공기들은 스테이션들을 공유한다. 계획 시간 동안 모든 목표물은 각각 무인항공기에 의해서 관측되며 오랜 서비스 시간을 요구하는 목표물은 여러 대의 UAV 의 협력으로 관측 작업을 진행 할 수 있다. 작은 크기의 문제를 해결하기 위해서 혼합 정수 계획법 모델을 CPLEX를 이용하여서 스케줄을 도출하였으며 큰 사이즈의 문제나 역동적 작전환경에서 무인항공기를 운용하기 위해서는 혼합 정수 계획법 모델의 복잡성을 극복한 RHTAm을 개발하였다.
무인항공기 시스템을 사용하기 위해서는 시스템 디자인 단계와 스케줄링 단계가 필요하다. 제 3 장에서는 이러한 두 단계를 동시에 최적화 하는 방법론을 제안하였다. 이를 위하여 혼합 정수 계획법 모델을 개발하였다. 이 모델에서는 여러 무인항공기와 충전기지 후보들을 가지고 무인항공기의 효율적인 관측 작업을 위하여 무인항공기의 대수 와 종류, 충전기지의 대수 와 위치 그리고 무인항공기의 스케줄을 동시에 최적화 하여 도출한다. 혼합 정수 계획법 모델의 복잡성을 극복하기 위하여 분기 한정법과 RHTAd를 개발하였다. 수치 실험 결과 분기 한정법은 혼합 정수 계획법 모델과 같은 최적해를 제공하지만 550배 빠른 계산 능력을 가진다. RHTAd는 혼합 정수 계획법보다 20,000배 빠른 계산 능력을 가지지만 4.3%의 목표값 손실이 발생한다.
