## 4 Algorithms
### Path Relinking Procedure
\begin{tabular}{l l} \hline \hline \multicolumn{2}{l}{**R&R Procedure**} \\ \hline
1. & **Input**: Routing solution \\
2. & Randomly select a caretaker, set to _Removal_, and remove all patients belonging to that caretaker from the routing solution. \\
3. & **For**\(patient\in\) _Removal_**do** \\
4. & Insert _patient_ by applying the _Inserting procedure_ to each caretaker; if there is no place to insert, \\  & deploy a new caretaker and apply the procedure again \\
5. & **End For** \\ \hline \hline \end{tabular} 

## 5 Computational Results on Solomon's Instances

To test our constructed heuristic, we apply it to solve the well-known benchmark instances called Solomon's instances with 25, 50, and 100 customers. As mentioned earlier, there are 3 groups of instances, C (clustered), R (random) and RC (randomly clustered). The parameters used in all simulation results are: number of particles, set at 15 (\(n=15\)); number of R&R runs, which is 5 (\(r=5\)); and maximum iterations, set at 500 (\(Iter\_max=500\)). These parameters greatly affect the performance of the heuristic. For example, if the number of particles is high, the objective function value tends to be better. However, we will have to sacrifice the time needed to execute each iteration. Since a higher number of particles doesnot guarantee a better solution, we limit the number of particles to 15 where the running time is comparatively low. The number of R&R is set to 5 in an attempt to diversify particles when they have similar solutions or similar route. This normally occurs when the heuristic reaches a local optimum, since the path relinking process tends to move all particles that are similar to each other. As for the maximum number of iterations, in all problems tested this has never reached 500, hence the number is set to 500. To illustrate the proposed heuristic's performance, the heuristic is written in [PERSON]'s language [45; 46] and run on AMD Ryzen 9 12-Core processors with 3.8 GHz CPU and 64 GB of RAM. The results shown in Tables 3-5 compare the optimum objective function values and that obtained with our heuristic for the Solomon's instances with 25, 50, and 100 customers, respectively. For those instances where the optimal solutions have not been found in the existing literature, we compare our results with the best solutions from the literature. The number of vehicles presented is equivalent to the number of caretakers. The customers presented can be seen as the patients. The \"%Gap\" is the percentage difference between the values obtained with our heuristic and the optimal values. With 52, 21, and 18 out of 56 cases that our heuristic can find the optimal solutions in 25, 50, and 100 customer instances, we can say that our heuristic performs better in smaller-size instances. In general, our heuristic performs better in C1 and C2 instances since the %Gap is smaller compared to the R1, R2, RC1, and RC2 instances. Moreover, in most cases the optimal solutions have yet to be found, and the %Gap is less than 5%. Note that for all computations, the distance between each pair of nodes is truncated to 1 digit. It is also worth mentioning that the running time for each iteration on 25-customer instances is recorded at approximately 1 s for RC2 instances (at 20 total number of iterations), 2 s for all C1, R1, R2, and RC1 instances (at 10, 10, 12, and 20 iterations), and 3 s for C2 instances (at 15 iterations). The running times for each iteration on 50 customer instances are 4 s for C1 (at 25 iterations), 5 s for R2 and RC2 (at 25 and 30 iterations), and 6, 7, and 10 s for R1, RC1, and C2 instances (at 20, 25, and 30 iterations), respectively. For those instances with 100 customers, the running time for each iteration is recorded at approximately 30 s for all C1 instances, and 1 min for C2, R1, R2, RC1, and RC2 instances. Note that the running time depends on the number of particles and maximum iterations set.