# Structured Urban Airspace Capacity Analysis: Four Drone Delivery Cases
## 3 Flight Planning Algorithm
### Outer Loop: Multiple sUASs Flight Planning  
The main idea of this study is that the single sUAS flight planning problem can be formulated by assigning the separation-satisfied flight time weights in the airspace graph as described in Section 3.2. By doing so, the problem is able to not only manage separation between every pair of sUASs, but also consider operational factors such as the feasible speed ranges, available routes, the separation requirements. However, the separation of each sUAS only satisfies the separation requirement from a set of allocated sUASs. In this section, we address the multiple sUASs flight planning problem by solving each single sUAS flight planning problem in an iterative way. At each iteration, each sUAS finds the optimal flight route including its speed profile by solving Problem 1 (inner loop), and one of the sUASs is allocated using a criterion-based algorithm (outer loop). In this study, we utilise the FCFS and LCFS algorithms for the outer loop algorithm. Once inputs of the multiple sUASs flight planning problem are given, Algorithm 1 starts the flight planning process until \(\mathcal{A}^{+}\) is empty (Line 3). The algorithm first generates airspace graphs \(\mathcal{G}^{k}_{i}=(\mathcal{E},\mathcal{V},\mathcal{W}_{d},T^{k}),\forall \alpha_{i}\in\mathcal{A}^{+}\) (Line 2). Assigning separation-satisfied flight time weights to all possible flight paths in the airspace graph is a time-consuming task. In order to reduce the complexity of the problem caused by the high degree of the airspace graphs, we select the \(h\)-shortest routes for \(\mathcal{G}^{k}_{i}=(\mathcal{E},\mathcal{V},\mathcal{W}_{d},T^{k}),\forall \alpha_{i}\in\mathcal{A}^{+}\) by using [PERSON]'s algorithm, and generate \(\mathcal{G}^{k}_{i}\) only considering the \(h\)-shortest routes (Line 4-5) [48]. Then, each sUAS has its unique airspace graph that contains flight time weights \(\mathcal{W}^{k}_{i,t}\) determining the optimal flight route with its speed profile. The optimal flight route \(p^{*}(\alpha_{i})\) and its speed profile \(s(\alpha_{i})\) are obtained by using [PERSON]'s algorithm, \(\forall\alpha_{i}\in\mathcal{A}^{+}\) (Line 6) [49]. sUAS \(\alpha^{*}_{i}\) that arrives first to its destination is obtained by using the FCFS algorithm (Line 7), and allocated (Line 15). The flight plan of sUAS \(\alpha^{*}_{i}\) is transferred from \(\mathcal{A}^{+}\) to \(\mathcal{A}^{-}\) (Line 12). Note that, in this study, \(\alpha_{i}\) refers to a flight as well as a sUAS. In the case that more than two sUASs arrive at the same destination at the same time (Line 8), the flight distance weights \(\mathcal{W}_{d}\) are utilised to allocate sUAS \(\alpha^{*}_{i}\) amongst them (Line 9-13). In either case, a sUAS is allocated and its flight schedule is shared with sUAS \(\alpha_{i}\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\). Based on the flight schedule each airspace graph \(\mathcal{G}^{k}_{i}\) is updated, \(\forall\alpha_{i}\in\mathcal{A}^{+}\) (Line 20). Note that, to change the outer loop algorithm to other criterion-based algorithms, such as the LCFS algorithm, users are only required to change the outer loop algorithm Line 7 and Line 10 to what the users want.