# Structured Urban Airspace Capacity Analysis: Four Drone Delivery Cases
## 3 Flight Planning Algorithm
### Inner Loop: Single sUAS Flight Planning Problem  
In this section, our focus is on flight planning a finite set of sUASs in a given route network-based urban airspace. **Definition 2**. : _Let \(\mathcal{A}=\{\alpha_{1},\alpha_{2},\ldots,\alpha_{i}\}\) be a finite set of sUASs. The set is partitioned into two sets: a set of sUASs to be planned \(\mathcal{A}^{+}\), and a set of planned sUASs \(\mathcal{A}^{-}\) such that \(\mathcal{A}^{+}\cup\mathcal{A}^{-}=\mathcal{A}\), \(\mathcal{A}^{+}\cap\mathcal{A}^{-}=\emptyset\)._  
In the urban airspace, each sUAS flies from its origin to its destination. A feasible flight route for each sUAS in the urban airspace is defined as follows:  
**Definition 3**. : _Is given in the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V})\), sUAS \(\alpha_{i}\in\mathcal{A}^{+}\) to be routed in \(\mathcal{G}\), the initial waypoint \(v_{1}^{i}\in\mathcal{V}\) and the final waypoint \(v_{n_{i}}^{i}\in\mathcal{V}\) to construct a flight route denoted by \(p(\alpha_{i})\) in \(\mathcal{G}=(\mathcal{E},\mathcal{V})\) defined by a sequence of waypoints._  
Thus, in the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V})\), there can be an abundance of flight route candidates denoted by \(\mathcal{C}\) that satisfy the conditions as described in Definition 3. Through Definition 3, each flight route candidate \(p(\alpha_{i})\in\mathcal{C}\) can be given a corresponding flight route (a set of waypoints) as follows:  
\[p(\alpha_{i}):v_{1}^{i},v_{2}^{i},\ldots,v_{n_{i}}^{i}\]  
where \(n_{i}\) is the number of waypoints sUAS \(\alpha_{i}\) traverses as shown in Figure 2. For each sUAS' flight route as given in above equation, there is a set of segments connecting the waypoints, which is as follows:  
\[\mathcal{E}(p(\alpha_{i})):e_{(1,2)}^{i},e_{(2,3)}^{i},\ldots,e_{(n_{i}-1,n_{ i})}^{i}.\]  
Figure 4: Time-based separation concept for crossing points. \(\alpha_{i}\) and \(\alpha_{i^{\prime}}\) are represented by superscript \(i\) and \(i^{\prime}\) in figure, fly from their origin point \(v_{\text{A}}\) and \(v_{\text{B}}\) to their final point \(v_{\text{A}^{\prime}}\) and \(v_{\text{B}^{\prime}}\) through the crossing point \(v_{\text{X}}\) at speeds \(\{s_{1}^{i},s_{2}^{i}\}\) and \(\{s_{1}^{i^{\prime}},s_{2}^{i^{\prime}}\}\), respectively. The superscript and subscript of \(s\) are the SUAS index and segment index, respectively. For each flight route candidate, it is assumed that a performance index for a set of segments \(\mathcal{E}(p(\alpha_{i}))\) can be quantified as a set of positive numeric weighting values, as follows:  
\[\mathcal{W}(p(\alpha_{i})):w_{1}^{i},w_{2}^{i},\ldots,w_{n_{i}-1}^{i}.\]  
Then, the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V})\) is transformed into a weighted directed graph \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W})\) by assigning a weight to each segment for all flight routes. In the airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W})\), each flight route can be estimated by summing all weights of \(\mathcal{W}(p(\alpha_{i}))\), as follows:  
\[\mathcal{T}(p(\alpha_{i}))=\sum_{j=1}^{n_{i}-1}w_{j}^{i}. \tag{1}\]  
Based on the airspace graph, \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W})\), the routing problem that optimises the performance index can be defined as follows:  
**Definition 4**. : _Given an airspace graph \(\mathcal{G}=(\mathcal{E},\mathcal{V},\mathcal{W})\) and corresponding flight route candidates \(\mathcal{C}\), the routing problem is defined as finding a flight route (or a sequence of waypoints) such that_  
\[p^{*}(\alpha_{i})=\operatorname*{argmin}_{p(\alpha_{i})\in\mathcal{C}} \mathcal{T}(p(\alpha_{i})). \tag{2}\]  
The optimal flight route \(p^{*}(\alpha_{i})\) can be found by using the well-known shortest path algorithms such as [PERSON]'s algorithm, A\({}^{*}\) algorithm or exhaustive search algorithm [47].