Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


38199.pdf (2.82 MB)

ETD Abstract Container

Abstract Header

Decomposition Methods for Routing and Planning of Large-Scale Aerospace Systems

Scott, Drew
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1617108065278479

Abstract Details

2021, MS, University of Cincinnati, Engineering and Applied Science: Mechanical Engineering.
The aim of this thesis is to explore decomposition methods for solving problems of routing and planning of aerospace systems, specifically to those of Unmanned Aerial Vehicles (UAVs). Given some parameter of the system to optimize, the routing can be formulated as some optimization problem, which incorporates all the information of the system and any constraints on the routing of the UAVs. As these problems grow in size, with more UAVs, constraints, and targets, the problem becomes increasingly more difficult to solve, and often in an exponential manner. Optimal solutions in these cases are computationally expensive to solve. While sub-optimal and locally-optimal solutions can often be found with much less computation, there still remains a gap from the global optimum. As the system grows larger, the cost of this gap grows too, whether it be in monetary cost, increased equipment degradation, or longer time to complete tasks. Thus, extra computational time spent to find the optimal solution may be justified. However, as the systems increase in size, there will reach a point where finding the global optimum becomes intractable for whatever machine (computer) is being utilized to solve it. One method to do solve faster is to decompose the problem into smaller subproblems. Solving multiple subproblems iteratively can be faster than solving the original, primal problem outright. The decomposition methods here are developed to the end of solving the Persistent Intelligence Surveillance Reconnaissance (PISR) problem. This involves routing a set of UAVs to continuously monitor a set of targets of varying importance. Targets deemed more important must be visited more frequently. This problem and the frequency constraints can be modeled as a Multiple Depot Traveling Salesman Problem (MDTSP) incorporating the revisit periods of each target. Two different decomposition schemes are studied in this thesis. The first is a market based method, where the UAVs are treated as resources and a price is associated with each which determines which targets are assigned to its tour. The second method studied here is Dual Decomposition. This involves a relaxation of the constraints of the problem at hand, or a subset of them, forming the Lagrangian. This can result in an easier optimization problem and if coupling constraints are relaxed, can result in a separable optimization problem. This can solve the primal problem outright in some cases, and in other only provide a lower bound to the minimization problem. The bound is useful to further solve the problems to optimality by being passed into a branch-and-bound algorithm or similar. This work provides analysis on different update rules for the dual variables in terms of time and iterations required to maximize the dual function. The methods studied here are subgradient updates, ellipsoid method, and bundle methods. The subproblem occurring in our dual decomposition is an Elementary Shortest Path Problem with Revisit Constraints. Multiple different methods to solve this subproblem are analyzed here. Each algorithm is compared in terms of optimiality and time to solve.
Manish Kumar, Ph.D. (Committee Chair)
Michael Alexander-Ramos, Ph.D. (Committee Member)
David Casbeer, Ph.D. (Committee Member)
Satyanarayana Gupta Manyam, Ph.D. (Committee Member)
87 p.
Mechanical Engineering
optimization; combinatorial; routing; aerospace systems; UAVs; decomposition

Recommended Citations

Citations

  • Scott, D. (2021). Decomposition Methods for Routing and Planning of Large-Scale Aerospace Systems [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1617108065278479

    APA Style (7th edition)

  • Scott, Drew. Decomposition Methods for Routing and Planning of Large-Scale Aerospace Systems. 2021. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1617108065278479.

    MLA Style (8th edition)

  • Scott, Drew. "Decomposition Methods for Routing and Planning of Large-Scale Aerospace Systems." Master's thesis, University of Cincinnati, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1617108065278479

    Chicago Manual of Style (17th edition)

ucin1617108065278479
36
© 2021, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.