# Structured Urban Airspace Capacity Analysis: Four Drone Delivery Cases
## 3 Flight Planning Algorithm
### Inner Loop: Single sUAS Flight Planning Problem
The constraints of Equations (4)-(7) are for satisfying the minimum separation requirement at each waypoint. In Figure 2, for example, if \(\mathcal{E}(p(\alpha_{i}))\) consists of \(n_{i}-1\) segments for sUAS \(\alpha_{i}\), each segment requires a flight time that satisfies the separation requirement. The left-hand side of each constraint of Equations (4)-(7) is the flight time for the segment of each constraint, which must be greater than and equal to the time that satisfies the separation requirement. For the constraints, flight distances between waypoints and the flight schedule are required. The flight schedule is stored in \(T\) for each waypoint \(v\in\mathcal{V}\), and \(T\) is updated every time a sUAS is allocated and shared with \(\forall\alpha_{i}\in\mathcal{A}^{+}\). Figure 2.9  
\(A\) is the number of elements in \(\mathcal{A}\). Then, the formulated optimisation problem can be solved by any well-known linear programming algorithm. In this study, we utilise the  
\[\mathcal{E}(p(\alpha_{i})):e_{(1,2)}^{i},e_{(2,3)}^{i},\ldots,e_{(n_{i}-1,n_{ i})}^{i}.\]0 Independent airspace graphs for each sUAS. interior-point algorithm. In Equation (8), decision variables, \(s^{i}_{1},s^{j}_{2},\cdots,s^{i}_{n_{i}-1}\), are constant speeds for the flight segment, which are transformed into flight times, and assigned into weights \(\mathcal{W}_{i,t}\) for each flight route candidate of sUAS \(\alpha_{i}\in\mathcal{A}^{+}\). \[\mathcal{E}(p(\alpha_{i})):e_{(1,2)}^{i},e_{(2,3)}^{i},\ldots,e_{(n_{i}-1,n_{ i})}^{i}.\]1  
Therefore, a solution to the airspace graph \(\mathcal{G}_{i}=(\mathcal{E},\mathcal{V},\mathcal{W}_{i,t},T)\) can simultaneously provide a flight route and its speed profile for sUAS \(\alpha_{i},\forall\alpha_{i}\in\mathcal{A}^{+}\) while satisfying minimum separation at all times. We also construct flight distance weights \(\mathcal{W}_{d}\) on \(\mathcal{G}_{i}\) to utilise the flight distance \(d\) as a second criterion. The weights \(\mathcal{W}_{d}\) are the same for all sUASs, which are necessary to prioritise for the multiple SUASs' flight planning problem when two or more SUASs arrive at the same destination at the same time, more details about the priority are discussed in Section 3.3. The single sUAS flight planning problem that motivated this study can be formulated as follows:  
**Problem 1**. : _Given an unique airspace graph \(\mathcal{G}_{i}=(\mathcal{E},\mathcal{V},\mathcal{W}_{i,t},\mathcal{W}_{d},T)\), sUAS \(\alpha_{i}\) in \(\mathcal{G}_{i}\), and its origin \(v^{i}_{1}\in\mathcal{V}\) and destination \(v^{i}_{n_{i}}\in\mathcal{V}\) reachable from the origin, construct a flight route \(p(\alpha_{i})\) and a speed profile \(s(\alpha_{i})\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\) such that_  
* _the separation requirement is satisfied from the planned sUAS_ \(\forall\alpha_{i}\in\mathcal{A}^{-}\)_;_
* _the speed profile of each sUAS must be within its feasible speed range;_
* _and the airspace graphs are updated every time when a sUAS_ \(\alpha_{i}\in\mathcal{A}^{+}\) _is planned._  
In this study, we solve Problem 1 using [PERSON]'s algorithm [PERSON] (1999).