Healthcare staff routing to provide healthcare service to the patients is one of the real-world scheduling problems similar to multiple travelling salesman problems (MTSP). Healthcare staff members provide daily medical services at patients' homes. The service provider authority has to schedule these staff in an effective and efficient way so that it achieves the minimum total cost. The aim of this study is to propose an Adaptive Local Search based on Genetic Algorithm (GA) to solve Healthcare Staff Routing Problem. Two new types of Adaptive Local Searches have been proposed to explore the optimal solutions. Also, Immigrant Scheme has been applied to improve the performance of the proposed GA. With this feature, we make an effort to motivate the GA to replace population occasionally by calling the best GA chromosome when the GA struggles at the local optimal solution. By the proposed algorithm, an effective routing schedule for staff members is generated. Our empirical study demonstrates that the proposed GA with Adaptive Local Search and Immigrant Scheme outperforms its rival methods in terms of the sum of distances.