# Structured Urban Airspace Capacity Analysis: Four Drone Delivery Cases
## 3 Flight Planning Algorithm
### Outer Loop: Multiple sUASs Flight Planning
```
Input:\(v_{i}^{i},v_{n_{i}}^{i}\in\mathcal{V}\), \(\forall\alpha_{i}\in\mathcal{A}\), airspace information Output:\(p^{*}(\alpha_{i}),s^{*}(\alpha_{i})\), \(\forall\alpha_{i}\in\mathcal{A}\)
1\(k=1\) generate \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{d},T^{k})\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\)
2 while\(\mathcal{A}^{+}\
eq\emptyset\)do
3 find \(h\)-shortest routes for \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{d},T^{k})\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\) (using [PERSON]'s algorithm);
4 generate \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{i,T}^{k},\mathcal{W }_{d},T^{k})\) that only considers the best \(h\) routes, \(\forall\alpha_{i}\in\mathcal{A}^{+}\);
5 find \(p^{*}(\alpha_{i})\) of \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{i,T}^{k})\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\) (using [PERSON]'s algorithm);
6\(\alpha_{i}^{*}\leftarrow\operatorname*{argmin}_{\forall\alpha_{i}\in \mathcal{A}^{+}}p^{*}(\alpha_{i})\) (using FCFS algorithm);
7 ifThere are more than two \(\alpha_{i}^{*}\) existthen
8 find \(p^{*}(\alpha_{i})\) of \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{d},T^{k})\) amongst them (using [PERSON]'s algorithm);
9\(\alpha_{i}^{\dagger}\leftarrow\operatorname*{argmin}_{\forall\alpha_{i}^{*}} p^{*}(\alpha_{i})\) (using FCFS or LCFS algorithm);
10 allocate \(\alpha_{i}^{\dagger}\);
11 transfer \(\alpha_{i}^{\dagger}\) from \(\mathcal{A}^{+}\) to \(\mathcal{A}^{-}\);
12 share \(\mathcal{A}^{-}\) with \(\forall\alpha_{i}\in\mathcal{A}^{+}\);
13
14 else
15 allocate \(\alpha_{i}^{*}\);
16 transfer \(\alpha_{i}^{*}\) from \(\mathcal{A}^{+}\) to \(\mathcal{A}^{-}\);
17 share \(\mathcal{A}^{-}\) with \(\forall\alpha_{i}\in\mathcal{A}^{+}\);
18
19 end if
20\(k=k+1\);
21 update \(\mathcal{G}_{i}^{k}=(\mathcal{E},\mathcal{V},\mathcal{W}_{i,t}^{k},\mathcal{W }_{d},T^{k})\), \(\forall\alpha_{i}\in\mathcal{A}^{+}\) ;
22
23 end if
24
25 end for
```  
**Algorithm 1**The multiple SUASs flight planning algorithm  
We illustrate an example in Figure 6 for a better understanding of Algorithm 1 with an case that \(A\) SUASs fly in the urban airspace. In the first iteration, each sUAS generates its airspace graph \(\mathcal{G}_{i}^{1}\), \(\forall\alpha_{i}\in\mathcal{A}^{+}=\{\alpha_{1},\alpha_{2},\ldots\alpha_{A}\}\). Through the inner loop algorithm, each sUAS's \(p^{*}(\alpha_{i})\) is determined, \(\forall\alpha_{i}\in\mathcal{A}^{+}\), and the most flight-time-efficient sUAS, which is \(\alpha_{2}\), is allocated using the FCFS algorithm. In the second iteration, sUAS \(\alpha_{A}\) is allocated through the same process. In the \((A-1)\)th iteration, sUAS \(\alpha_{3}\) is allocated, and sUAS \(\alpha_{1}\) is allocated last. Flight Planning Example for 1-to-\(\mathcal{M}\) Case (Last-Mile Delivery with a Single Retail Point)  
We used a simulation case in Section 4 to explain the flight planning algorithm and did not include extraneous examples to avoid confusion. We appreciate the readers' understanding in this matter. This example is a sample of the Monte Carlo simulations for the 1-to-\(\mathcal{M}\) case, and its simulation settings are described at the beginning of Section 4. Put briefly, thirty sUASs traverse from the retail point (E68) to each predetermined sUAS' service points (E1\(\sim\)E67) in Figure 8. We apply both the FCFS and LCFS algorithms to this example, and thirty flight plans for each case are shown in Tables 1 and 2, respectively. The results show each sUAS' separation requirement-satisfied flight route and speed profiles for each outer loop algorithm. Due to a 5 s departure separation, 5 s horizontal separation as well as the single retail point of this case, all sUASs find their flight routes with the maximum speed without any conflicts for both cases. For the same reasons, most of the flight routes are the same as the shortest path of each sUAS. Table 3 shows a comparison of the results between the FCFS and LCFS algorithms for this example.