# A Memetic Algorithm for an External Depot Production Routing Problem
## 4 Experiments and Results
### Results  
The tests performed on 128 instances have yielded the averages over the four classes of instances represented by the rows in Table 15.  
In this table, %Diff denote the percentage difference between the cost determined with the MA and the cost determined with the TPDH. This rate of change determines the relative evolution of the results of the MA compared to the TPDH. The column Instance with the sub-columns \(n\), \(l\), \(m\) designates the instances used for tests with \(n\) clients, \(l\) periods on the planning horizon and \(m\) vehicles. The columns SWAP1, BI, SWAP2, BI&SWAP2, SWAP1& SWAP2, and ALL contain the sub-columns of the total cost percentage difference and the CPU percentage difference of the corresponding local search algorithms. In Table 15, the combination of local search SWAP1 and SWAP2 (SWAP1&SWAP2) offers the best percentage difference with an overall average decrease of 10.50% in the cost obtained with MA compared to TPDH. The second-best combination of local search algorithms is the use of BI and SWAP2 (BI &SWAP2) with an overall reduction of 10.23% on the total cost of production, storage, and vehicle rounds. In this experiment, it was found that the combination of all local searches is less efficient than the combination of two of them. In terms of calculation time, only the use of BI as a local search method offers a reduction in calculation time of 36.85% (%Diff CPU = \(-\)36.85% in the Table 15). Although it has produced the largest number of better solutions, MA with a combination of SWAP1 and SWAP2 local searches shows an overall relative increase of 1759.09% in computation time compared to TPDH. Out of 192 (32 \(\times\) 6) results obtained on all tests, TPDH obtained better results on only three tests concerning instances (\(n=40\), \(l=3\), \(m=3\)) with the use of the local search methods BI, SWAP2 and the combination of SWAP1 and SWAP2 which gives a very low rate of 1.56% (3/192). The best solution for each of the 32 instances is obtained with the MA. Table 16 shows the distribution of the best solutions according to the local search method or combination of local search methods used, considering both the overall cost and the computation time. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameters Description** & **Candidate Values** & **Best Values** \\ \hline Population size (_Pop_Size_) & [10;20;30] & 20 \\ Maximum number of generations (_Max_gen_) & [30;35;40] & 35 \\ Local search probability (_LS_search_prob_) & [20\%;30\%;40\%] & 20\% \\ \hline \hline \end{tabular}
\end{table} 
Table 14: Parameter tuning results for MA. In Table 16, _Nbr_BS_ refers to the number of best solutions obtained with each local search method in the implementation of MA. According to Tables 15 and 16, the local search methods BI, SWAP1(S1) and SWAP2(S2) individually had the same number of best solutions in the implementation of MA. Thus, each local search taken individually yielded 2 best results out of the 32 average results, i.e., a rate of 6.25% each. The combination of all the local search methods (ALL) also resulted in two best results, which also corresponds to a rate of 6.25% (100 \(\times\) (2/32)). The highest number of best solutions was obtained with the combination of the local search methods SWAP1 and SWAP2. This combination alone represents the 17 best results out of the 32 in Table 16, a rate of 53.125%. The second-best combination is the one using BI and SWAP2. This combination yielded 7 best solutions out of 32 with a rate of 21.875%. In Table 17, each row gives details of the best solution for each instance in Table 15. The columns PROD, INV, and TRANS indicate the average production, storage, and transport costs (vehicle trips) of the best solution obtained with MA, respectively. COST is the average total cost of production, storage, and distribution (transport). RL refers to the local search used to obtain this result. Overall, Table 17 shows that the share of production cost in the overall cost is 72.87% (100 \(\times\) (72,758.91/99,847.04)).