Unmanned Aerial Vehicles (UAVs)-based commercial services, exemplified by drone delivery, have captured widespread interest from technology companies, startups, and policymakers. Drone delivery has the potential to address the last-mile problem and reduce ground traffic congestion. However, to scale up drone delivery in urban environments, proper traffic management systems must be put in place. Such traffic management has been theorized by a range of concepts of operations. Among these, tube-based operations have been implemented to support commercial delivery services in cities. Therefore, to enable tube-based operations, it is necessary to generate tubes that drones can follow to complete their tasks safely and efficiently while ensuring that these tubes meet safety requirements and can be utilized for commercial purposes.

There is currently limited literature on designing route networks for drone deliveries and evaluating the safety of such networks. Although various related studies focus on vehicle routing problems, robotic path planning, air traffic management, network flow, road design, and circuit design, they cannot be directly applied to designing drone delivery route networks due to differences in problem settings and complexity. None of these studies can readily balance system-level (network) optimality, individual route performance, and computational time adequately in real-world scenarios. Hence, it is crucial to develop network planning methods specifically for drone delivery networks in cities and to evaluate the safety of different route network designs, especially regarding third-party risk. To fill the research gap, this thesis includes four studies on designing route networks.

The first study in Chapter 3 addresses the challenge of ensuring system-level optimality while solving the network planning problem rapidly for real-world scenarios. The primary objective of system-level optimality is to minimize airspace occupancy to reduce impacts on the ground. This study proposes a priority-based route network planning method that utilizes a priority structure to break down the NP-hard network planning problem into a set of single-path planning problems for faster planning. The method generates a network by planning a set of paths sequentially. Additionally, the study introduces a novel space cost function to enable the design of dense and aligned routes. The proposed method is tested on various scenarios and compared with other state-of-the-art methods, and the results demonstrate that our method can generate near-optimal route networks with significant computational time savings.

The second study in Chapter 4 seeks to balance maximizing the performance of individual routes and the system in a reasonable computational time. Optimizing individual routes may result in air traffic congestion, causing the entire system to perform poorly or even fail. To address this issue, the study proposes a competition-based route planning method. It enables each origin-destination (OD) pair to compete against other OD pairs for an optimized route, such as the shortest distance, coordinated by a system-level evaluation, leading to an efficient network design. The core concept is congestion costing, a soft constraint that coordinates the allocation of airspace. The proposed method is tested and compared across various scenarios, showing a good balance between individual and system-level optimality. In some complex scenarios, the method can find a feasible solution fast, while others fail.

In contrast to the first two studies that employ graph-search-based planning, the third study in Chapter 5 utilizes mathematical programming to address the network planning problem. It can ascertain the complexity of the problem and find an optimal solution. It also provides further insights into whether the search-based planning methods are fast and optimal enough. The study formulates the planning problem as a multi-commodity network flow (MCNF) model and utilizes generic integer programming (IP) optimization solvers to solve the MCNF model. The MCNF method is tested and compared with a graph-search-based planning method across several different scenarios. The results show that the MCNF model can generate shorter routes, but it requires significant computational time. On the other hand, the graph-search-based planning method can quickly and efficiently find near-optimal solutions, but it may fail to find all paths in some complicated scenarios.

The fourth study in Chapter 6 evaluates the safety risks of risk-aware path planning in route network designs, which fills the gap that existing literature only studies the risk of a single route and gives insights into the commercial usage of route network designs. Drone operations can pose safety risks to persons and property on the ground, referred to as third-party risks. Most existing so-called "risk-aware" planning methods have considered risk minimization per flight, including the proposed planning methods. However, it is not clear if such risk minimization per flight works well for network designs where there exist a large number of annual flights. This study conducts a series of simulations to assess the third-party risks of different risk-aware path planning in route network designs, like with and without risk minimization per flight. The results show that considering risk minimization per flight in network design can reduce the total number of fatalities in an area, but at the cost of a critical increase in safety risks for persons living in areas that are favored by risk minimization per flight.

To sum up, this thesis introduces two graph-search-based planning methods: a priority-based approach that optimizes system-level requirements and rapidly generates route networks, and a competition-based approach that balances the maximization of individual-level and system-level performance. Additionally, a mathematical programming-based planning method is presented: an MCNF model that generates optimal solutions, albeit with potentially significant computational time. Finally, the risk simulations show the capability of proposed network designs in reducing fatalities; however, for large demands, the risk remains high and other approaches are necessary to further mitigate risk.