## 6 Material and Method
### Genetic Algorithm  
Once the cost matrix is built, the GA is used to assign the DPs to the UAVs and to find the order in which they will be visited forming complete tours. The GA is a metaheuristic that was first proposed by [PERSON] in 1975 [33]. As of today, it is still one of the most broadly used metaheuristics in engineering. The pseudocode is given at Algorithm 6. It works by creating a population of candidate solutions referred to as the parent solutions. It then starts an iterative process where parent solutions are selected, child solutions are created from good parents using crossover, child solutions are modified using mutation and parent solutions are replaced by the child solutions before the next iteration. Once the termination criterion has been met, the best solution is returned by the algorithm.  
```
1:Initialize the parent solutions
2:whileiteration<maxiterationdo
3: compute fitness of parent solutions
4: select parent solutions through selection
5: create child solutions through crossover
6: modify child solutions through mutation
7: replace parent solutions
8: Return best solution
```  
**Algorithm 6** Genetic Algorithm  
In our implementation, the candidate solutions are encoded as illustrated in Figure 7. The solution is represented using two strings where the first one includes the DPs visited by the UAVs and the second one includes which UAV visits each one of the DPs. When decoding the solution strings, the start point (i.e., point 0) is added at the beginning and at the end of each route resulting in a tour. The GA is configured to use 100 candidate  
\begin{table}
\begin{tabular}{|c c c c c|} \hline \hline
**From** & **To** & **1** & **2** & **3** &... & \(N\) \\ \hline \hline
1 & & C\({}_{1,2}\) & C\({}_{1,3}\) & & C\({}_{1,N}\) \\ \hline
2 & C\({}_{2,1}\) & & C\({}_{2,3}\) & & C\({}_{2,N}\) \\ \hline
3 & C\({}_{3,1}\) & C\({}_{3,2}\) & & & C\({}_{3,N}\) \\ \hline \(\ldots\) & & & & & \\ \hline \(N\) & C\({}_{N,1}\) & C\({}_{N,2}\) & C\({}_{N,3}\) & & \\ \hline \hline \end{tabular}
\end{table}
Table 1: Example of a Cost Matrix.  
solutions with 200 iterations. These settings were tested experimentally and generated good results. The selection is made by tournament where two parents are randomly picked and the best one is retained. The process is repeated to select the second parent. The crossover is done using a single-point crossover as shown in Figure 8a. The crossover point is selected randomly, the elements before the point come from the first parent while the elements after the points come from the second parent. When selecting the elements from the second parent, one must be careful not to select elements that have already been selected from the first parent. Once the end of the second parent has been reached, the selection starts back from the beginning of the second parent. The inverse is done to create child 2. The mutation operation is implemented as illustrated in Figure 8b where two elements from the solution strings are selected and swapped. Not shown in Figure 8, but applied to every child solution is the 2-opt local search heuristic which removes loops from the solution. The readers are referred to [34; 35] for more details on the 2-opt local search. Finally, the replacement is implemented with elitism where the two best parents survive to the next iteration and replace the two worse children. Being a non-deterministic algorithm, the GA may produce different results every time it is run, to maximize the quality of the final path found, the proposed framework runs the GA three times and selects the best solution from the three runs.