# Structured Urban Airspace Capacity Analysis: Four Drone Delivery Cases
## 3 Flight Planning Algorithm
### Inner Loop: Single sUAS Flight Planning Problem
Although the optimal flight route \(p^{*}(\alpha_{i})\) can be obtained according to Definition 4, if the airspace users want to manage the separation between each sUAS in sequential approaches, the optimality of the obtained flight route might be disturbed in the following separation management stages. One possible option is to solve the multiple sUASs flight planning problem using numerical trajectory optimisation approaches, which is not scalable although the approaches provide high-fidelity flight plans to each sUAS. Such approaches can also require additional processes for managing separation, which might cause optimality or scalability issues. Our objective of formulating the flight planning problem is to find a flight route and speed profile that minimises the flight time of each sUAS while satisfying the separation requirement. The main idea for achieving the objective is to assign a weight to each segment (edge) of the airspace graph where the weight is expressed as a flight time. Then, each sUAS' speed profile also can be obtained by finding its flight route in the airspace graph as defined in Definition 4. We set a flight time of each sUAS as weight \(w\in\mathcal{W}\) to each segment \(e\in\mathcal{E}\) of the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W})\). Note that, a flight time and speed of each sUAS are mutually interchangeable using geographic data included in the airspace graph. Where each speed profile of sUAS is determined within a feasible speed range of each sUAS. Another issue we have pursued is to satisfy the separation requirement between every pair of sUASs. To assign a flight time that satisfies the separation requirement to each edge of \(\mathcal{G}\), we need the flight schedule of the set of planned sUASs including the arrival times of each sUAS at each waypoint as discussed in Section 3.1. The flight schedule \(T\) will be included in the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W},T)\), and used to calculate the weights of the airspace graph. By finding a solution of the airspace graph \(\mathcal{G}\), then, we can obtain a flight route and speed profile of the sUASs while satisfying the separation requirement simultaneously. Each sUAS has different weights \(\mathcal{W}_{i}\) because of different specifications such as the feasible speed range or the separation requirement depending on nearby sUASs. Therefore, sUAS \(\alpha_{i}\in\mathcal{A}^{+}\) has its own airspace graph \(\mathcal{G}_{i}\), as shown in Figure 5.  
Flight Time Weights \(\mathcal{W}_{i,t}\) on \(\mathcal{G}_{i}\)  
We propose a weighting scheme to be applied to the airspace graphs \(\mathcal{G}_{i}\) to fulfil separation-compliant speed profiles. First of all, we introduce a set of constant speeds for each sUAS as follows:  
\[s(\alpha_{i}):s_{1}^{i},s_{2}^{i},\ldots,s_{n_{i}-1}^{i}\]  
where each element of the set \(s(\alpha_{i})\) must be within a feasible speed range [\(s_{\min}^{i}\ s_{\max}^{i}\)], \(\forall\alpha_{i}\in\mathcal{A}\). Furthermore, we define a set of flight distances using geographical data allowing to compute the set \(s(\alpha_{i}),\forall\alpha_{i}\in\mathcal{A}^{+}\)  
\[d(\alpha_{i}):d_{1}^{i},d_{2}^{i},\ldots,d_{n_{i}-1}^{i}.\]  
Let \(u_{j}^{i}=1/s_{j^{\prime}}^{i}\,\forall j\in\{1,2,\ldots,n_{i}-1\},\forall \alpha_{i}\in\mathcal{A}^{+},u_{\max}^{i}=1/s_{\min}^{i}\), and \(u_{\min}^{i}=1/s_{\max}^{i}\), we formulate a linear programming problem and solve the problem to obtain the flight time weight \(\mathcal{W}_{i,t}\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\) as follows:  
min Figure 2.0 s.t. Figure 2.1 (4) Figure 2.2 Figure 2.3 Figure 2.4 (5) Figure 2.5 Figure 2.6 (6) Figure 2.7 (7) Figure 2.8 (8)  
where \(t_{SP}^{(i^{\prime},i)}\) is the minimum time-based separation requirement between preceding sUAS \(\alpha_{i^{\prime}}\) and following sUAS \(\alpha_{i}\) at waypoints as shown in Figures 3 and 4. The objective function of Equation (3) is to minimise the sum of flight time of each segment.