## 6 Material and Method
### Building the Final Path  
Using the route for each UAV (i.e., the series of DPs) and the nodes weight C from the SSSP instances, the final path can be built by constructing the trajectories connecting the DPs together. To build the trajectory from the SSSP instances, one must start from the final node and find the previous node, using the CSC graph representation, whose weight plus the edge weight is the smallest. The process is repeated until the start node is found. During this process, the direction of the edge leading to the previous node is calculated and the node is added to the path only when there is a change in direction. This allows for the creation of a path with the minimum number of nodes.  
Once the path is built, the speed, power consumption, and position of the UAV as a function of time are calculated precisely. For this, the UAV model discussed in Section 5  
Figure 8: (a) Crossover operator and (b) mutation operator.  
Figure 7: Solution encoding.  
is used. For vertical segment, the acceleration and deceleration are ignored and the UAV speed and power are set to their optimal values. For horizontal segments, the segment can be decomposed into three sections: the acceleration, the steady state, and the deceleration. Starting with the first segment of the path, the initial speed is necessarily zero. Based on the angle with the next segment the speed reduction as a percent of the maximum speed reached on the segment is determined by looking in the lookup table discussed in Section 5. A binary search is then used to find the value of \(v_{max}\), the maximum speed reachable on the segment. The binary search is bound by 0 and \(v_{optimal}\), the optimal speed of the UAV. A speed is reachable when there is enough distance to accelerate to the speed and enough distance to decelerate to the reduced speed. If \(v_{max}\) is equal to \(v_{optimal}\), the segment is necessarily composed of the three sections (i.e., acceleration, steady state, and deceleration). If \(v_{max}\) is smaller than \(v_{optimal}\), there is no section at steady state. When calculating \(v_{max}\), the start and end time for the acceleration, the steady state and the deceleration are also computed. The polynomial interpolation functions for the acceleration and deceleration are used to set the instantaneous speed and power of the UAV. The position of the UAV is calculated based on the previous position and the instantaneous speed. The speed at the end of the segment is used as the initial speed for the next segment and the process is repeated.  
In the event that the initial speed at the beginning of a segment is too high to accommodate for a deceleration to the reduced speed found in the lookup table for a given turning angle, the initial speed that would allow the deceleration is calculated and used as the final speed for the previous segment. The final speed for the previous segment becomes a constraint and the previous segment is reprocessed. This can be repeated multiple times allowing the algorithm to revisit multiple previous segments. This can happen in a situation where there is a long segment followed by a series of short segments followed by a sharp turn. The UAV would achieve a high speed on the long segment, would not reduce its speed before entering the short segments and would not have enough distance to reduce its speed before arriving to the sharp turn. With the proposed approach, the UAV will reduce its speed on the long segment and will arrive at the correct speed at the sharp turn.