The Problem of Locating and Routing Unmanned Aerial Vehicles

Introduction

An unmanned system can be described as an electro-mechanical system without operator aboard (Vargas 2012). Currently, these systems include ground vehicles, aerial vehicles, underwater vehicles, surface vehicles, unattended munitions and sensors. Among all of those, UAV is the most famous type. This is also clear from the fact that U.S., the leader country in unmanned system technology, has allocated 95% of the resources used for unmanned systems for UAVs (US DoD UAV Roadmap 2011). The beginning of the use of UAV technology for human benefit goes to early 20th century. The concerns about safety, cost and ease in usage makes it more attractive to use UAVs instead of classical manned aircrafts, whenever it is possible. UAVs can be employed easily in cases where human life is in danger, such as military operations executed in bad weather, threatening environmental conditions or contaminated regions. Scientific research activities such as data collection, commercial and security duties like border watching, monitoring vehicle traffic, controlling protected areas like energy transmission lines are other cases where UAVs are employed frequently. Organizations have already spent billions of dollars for this technology, and apparently this expenditure will continue to rise with the increasing need in both governmental and civilan organizations. With development of flight capabilities like range, observation, endurance and altitude, UAVs seem to be indispensable factor for increasing military power (Glade 2000). In armed forces, UAVs can be used in executing a number of missions such as transportation, search and rescue, electronic warfare and signals intelligence, battle damage assessment, surveillance and reconnaissance and attacking an enemy target. In addition to all these capabilities of UAVs, especially vertical takeoff and landing is one of the most important capabilities for a navy. With this capability, small UAVs can be deployed to small platforms. Therefore, even small patrol ships can be utilized as stations to operate surveillance or similar operations. Utilizing these privileged systems efficiently is as important as having them as a force multiplier. One of the most important aspects related to the efficiency of their use is stationing and routing them in an optimal manner. In this book chapter, a decision problem is discussed to seek an answer to the combined question of how to locate and route a fleet of UAVs optimally which can station on ships. Note that, this problem can be adapted easily to land-based operations. In this problem, a set of demand points, fleets of UAVs and ships, and candidate stations are assumed. Not all demand points are required to be visited, however, each visited demand point has a certain benefit, while the objective is to maximize the total operation benefit collected by visiting these points. The selection of allowed stations, assignment of ships to these selected stations and assignment of UAVs to the ships are executed simultaneously. It is assumed that the number of ships is not a constraint and any number of ships can be assigned to any selected station. Moreover, the authors also deal with the extension of this basic problem which allows a demand point to have a time window for being visited by a UAV and also allows a UAV to take off and land on ships assigned at different stations. Note that location, routing and prize (benefit) collection are main aspects of the problems described above. Location and routing are well studied subjects, while there is relatively less attention in prize collection. Separately, location problem and routing problem are combinatorial optimization problems which have attracted attention of many researchers because they have several application fields such as logistics, telecommunications, military operations etc. These two problems are closely related to each other. Location problems focus on the decisions which provide an infrastructure for routing problems. Combination of these two problems creates another well-known problem type known as location and routing problem (LRP). A specific variant of this problem, the UAV location and routing problem can be defined as prize maximization LRP with additional constraints reflecting operational limitations.