{"id":{"repo_id":"buffalo","oai_identifier":"oai:ubir.buffalo.edu:10477/86857"},"canonical_url":"https://search.dev.ndltd.org/etd/buffalo/oai:ubir.buffalo.edu:10477/86857","repository":{"repo_id":"buffalo","name":"Buffalo","base_url":"https://ubir.buffalo.edu/oai/request"},"display":{"title":"On Routing Unmanned Aerial Vehicles for Surveillance and Reconnaissance Activities","abstract":"Ph.D.","abstract_html":"Ph.D.","abstract_has_math":false,"creators":["Gao, Cai"],"institution":"State University of New York at Buffalo","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Walteros, Jose","Industrial and Systems Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-02-25T23:23:31Z","date_published":"2025-02-25T23:23:31Z","updated_at":"2026-07-27T19:05:37Z","subjects":["operations research"],"languages":["eng"],"rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10477/86857","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Walteros, Jose","Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Gao, Cai"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-02-25T23:23:31Z","2020","2020-08-11 08:57:22"]},{"key":"dc:publisher","label":"Institution","values":["State University of New York at Buffalo"]},{"key":"dc:type","label":"Dc Type","values":["Text","Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["operations research"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/10477/86857"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ph.D.","As unmanned aerial vehicles (UAVs) have become more prevalent in context of surveillance and reconnaissance, there has been an increasing interest for developing efficient algorithms to optimally route UAVs. However, most common developments on traditional models and algorithms for UAV routing problems are often insufficient to accommodate the needs of UAV routing tasks without introducing fundamental modifications, especially in present moment that new technologies emerge posing new routing challenges. For example, in many pickup and delivery problems, the vehicles often travel in a waypoint-to-waypoint fashion visiting precise locations, which is inadequate for UAV routing because their on-board sensors can collect intelligence data from afar. To better deal with those new routing challenges for UAVs, this dissertation will examine two important UAV routing problems: risk and reward asset routing problem (R\\textsuperscript{2}ARP) and close enough traveling salesman problem (CETSP). R\\textsuperscript{2}ARP studies how to route a UAV to collect rewards (or information) from a collection of targets by routing within their neighborhoods located in hostile environment. To describe the risk and reward distribution, we consider two general risk-reward frameworks: a continuous model (i.e., functions under some basic assumptions) and a discrete model (i.e., a graph-based model). For the continuous risk-reward model, we consider routing a UAV with two user-defined modes -- linear trajectory and rotatory trajectory -- which accommodate the needs of many real-world applications. To solve the R\\textsuperscript{2}ARP, we formulate a mixed-integer programming model based on a discretization scheme. As solving the model directly using current commercial solvers is out of reach for many practical instances, we recast it as a two-stage problem amenable to implement the well-known Benders decomposition method. Various enhancement strategies are provided: fast generation of Benders cuts, strong Benders cuts, a stabilization method and subtour separation procedures. Next, under the framework of the discrete risk-reward model, the trajectory design problem given any entry and exit for a neighborhood is also called reward collection shortest path problem (NP-hard). We propose both an integer programming formulation and an efficient recursive search algorithm, \\emph{mPulse} for the problem. To solve large-scale R\\textsuperscript{2}ARP instances, we also propose an efficient Lin-Kernighan heuristic with a new definition of flip operation. Compared with lower bound and upper bound we derive, the solutions obtained by this heuristic method is of high-quality and always outperform the classic 2-$opt$ algorithm on the most tested instances. In addition to our developments for the R\\textsuperscript{2}ARP, we also examine the a variation of traveling salesman problem, called CETSP, in which the vehicle must get within a specified neighborhood of each target to visit it. We will study the geometric properties given any compact neighborhoods and propose multiple criteria to characterize the optimal CETSP solutions. We will also propose a tool called projection-closed separators to cut off portions of nonoptimal regions from neighborhoods. From computation perspective, we will propose a mixed-integer nonlinear programming (MINLP) model to formulate the CETSP with trimmed (due to separators) convex neighborhoods. In order to enhance the solvability of MINLP, a generalized Benders decomposition method is applied to solve the MINLP efficiently. Computational results demonstrate the effectiveness of the proposed method.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On Routing Unmanned Aerial Vehicles for Surveillance and Reconnaissance Activities"]}]}],"canonical_facts":{"dc:contributor":["Walteros, Jose","Industrial and Systems Engineering"],"dc:creator":["Gao, Cai"],"dc:date":["2025-02-25T23:23:31Z","2020","2020-08-11 08:57:22"],"dc:description":["Ph.D.","As unmanned aerial vehicles (UAVs) have become more prevalent in context of surveillance and reconnaissance, there has been an increasing interest for developing efficient algorithms to optimally route UAVs. However, most common developments on traditional models and algorithms for UAV routing problems are often insufficient to accommodate the needs of UAV routing tasks without introducing fundamental modifications, especially in present moment that new technologies emerge posing new routing challenges. For example, in many pickup and delivery problems, the vehicles often travel in a waypoint-to-waypoint fashion visiting precise locations, which is inadequate for UAV routing because their on-board sensors can collect intelligence data from afar. To better deal with those new routing challenges for UAVs, this dissertation will examine two important UAV routing problems: risk and reward asset routing problem (R\\textsuperscript{2}ARP) and close enough traveling salesman problem (CETSP). R\\textsuperscript{2}ARP studies how to route a UAV to collect rewards (or information) from a collection of targets by routing within their neighborhoods located in hostile environment. To describe the risk and reward distribution, we consider two general risk-reward frameworks: a continuous model (i.e., functions under some basic assumptions) and a discrete model (i.e., a graph-based model). For the continuous risk-reward model, we consider routing a UAV with two user-defined modes -- linear trajectory and rotatory trajectory -- which accommodate the needs of many real-world applications. To solve the R\\textsuperscript{2}ARP, we formulate a mixed-integer programming model based on a discretization scheme. As solving the model directly using current commercial solvers is out of reach for many practical instances, we recast it as a two-stage problem amenable to implement the well-known Benders decomposition method. Various enhancement strategies are provided: fast generation of Benders cuts, strong Benders cuts, a stabilization method and subtour separation procedures. Next, under the framework of the discrete risk-reward model, the trajectory design problem given any entry and exit for a neighborhood is also called reward collection shortest path problem (NP-hard). We propose both an integer programming formulation and an efficient recursive search algorithm, \\emph{mPulse} for the problem. To solve large-scale R\\textsuperscript{2}ARP instances, we also propose an efficient Lin-Kernighan heuristic with a new definition of flip operation. Compared with lower bound and upper bound we derive, the solutions obtained by this heuristic method is of high-quality and always outperform the classic 2-$opt$ algorithm on the most tested instances. In addition to our developments for the R\\textsuperscript{2}ARP, we also examine the a variation of traveling salesman problem, called CETSP, in which the vehicle must get within a specified neighborhood of each target to visit it. We will study the geometric properties given any compact neighborhoods and propose multiple criteria to characterize the optimal CETSP solutions. We will also propose a tool called projection-closed separators to cut off portions of nonoptimal regions from neighborhoods. From computation perspective, we will propose a mixed-integer nonlinear programming (MINLP) model to formulate the CETSP with trimmed (due to separators) convex neighborhoods. In order to enhance the solvability of MINLP, a generalized Benders decomposition method is applied to solve the MINLP efficiently. Computational results demonstrate the effectiveness of the proposed method.","**To request an accessible version of the file(s) associated with this item, contact library@buffalo.edu. Please include the item's persistent URL [http://hdl.handle.net/. . .] in your request.**"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/10477/86857"],"dc:language":["eng"],"dc:publisher":["State University of New York at Buffalo"],"dc:rights":["Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.","Copyright retained by author."],"dc:subject":["operations research"],"dc:title":["On Routing Unmanned Aerial Vehicles for Surveillance and Reconnaissance Activities"],"dc:type":["Text","Dissertation"]},"updated_at":"2026-07-27T19:05:37Z"}