## 4 Algorithms
### Path Relinking Procedure
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Best-Known**} & \multicolumn{3}{c}{**Our Best**} & \multirow{2}{*}{\%Gap**} & \multirow{2}{*}{\%Gap**} & \multirow{2}{*}{\%Gap**} \\ \cline{2-2} \cline{4-7}
**Problem** & \multicolumn{1}{c}{\ \begin{tabular}{c} **Number of** \\ **Vehicles** \\ \end{tabular}  } & \multicolumn{1}{c}{**Total Distance**} & \multicolumn{1}{c}{**Reference**} & \multicolumn{1}{c}{ \begin{tabular}{c} **Number of** \\ **Vehicles** \\ \end{tabular}  } & \multicolumn{1}{c}{**Total Distance**} & \multicolumn{1}{c}{**Time (s)**} \\ \hline C101 & 10 & 827.30 & [47] & 10 & 827.30 & 0.0000 & 533.12 \\ C102 &



## 6 Conclusions

In this paper, we formulated mathematical modeling and a heuristic for solving a home healthcare routing and scheduling problem in which caretakers must visit specific patients within a specific time frame. This problem can be formulated into a vehicle routing problem with time windows (VRPTW) and compatibility constraints. Due to the NP-hard nature of the problem, we presented a new heuristic combining particle swarm optimization, inserting procedure, local search, path relinking, and ruin-and-rec create (R&R) procedures. In particular, the inserting procedure is used to generate initial solutions and restore the feasibility of the solution. The constructed local search procedure representing the particle's movement to the local space is used to improve the solutions. Path relinking represents the global search movement of particles; at each iteration, the procedure is used to improve the current solution by integrating the current solution with the current best solution. R&R is deployed in cases where leaping out of the local optimum is necessary. To test the performance of the heuristic, we applied it to [PERSON]'s instances with 25, 50 and 100 customers and compared objective values obtained with our heuristic and the optimum values collected from published literature. Computational results show that our proposed heuristic performs better on smaller instances and in all clustered problems (C1 and C2 instances). Further investigation with compatibility constraints included in the model shows that our proposed heuristic also performed very well on 25 customer instances yielding solutions with less than 10% optimality gap. However, only 5 optimal solutions are found in the model with compatibility constraints compared with 52 optimal solutions found in the model without the constraints. This also suggests that the problem is much more difficult compared with regular VRPTW. The parameters in this study are experimentally selected to balance the computation time and solution quality. This does not guarantee the best performance of the algorithm. Moreover, as searching for the parameters is very time-consuming, one could consider the parameterized metaheuristic as presented in [52]. Conceptualization, P.S. and C.L. ; Data curation, P.S. ; Formal analysis, C.L. ; Investigation, P.S. ; Methodology, P.S. and C.L. ; Software, P.S. ; Supervision, C.L. ; Validation, P.S. and C.L. ; Visualization, C.L. ; Writing--original draft, P.S. ; Writing--review and editing, C.L. All authors have read and agreed to the published version of the manuscript. This research is supported by the Royal Golden Jubilee Ph.D. Program [Grant No. PHD/0041/2560]; and the Research Group in Mathematics and Applied Mathematics, Department of Mathematics, Faculty of Science, Chiang Mai University. Not applicable. The authors thanks the Royal Golden Jubilee Ph.D. Program, and the Research Group in Mathe-matics and Applied Mathematics, Department of Mathematics, Faculty of Science, Chiang Mai University for the support. The authors appreciate [PERSON] for her proofreading help. The authors declare no conflict of interest. ## References

* [1] United Nations. _World Population Prospects 2019, Volume II: Demographic Profiles_; Department of Economic and Social Affairs: New York, NY, USA, 2019.