<p>This study addresses the problem of optimally routing and scheduling nurses to meet the dynamic daily demands of patients. It incorporates two key real-world considerations: multiple services requested per patient, with prerequisite relations reflecting the multifaceted nature of diseases, and synchronized visits that allow for allowable delays between nurses’ arrivals. The latter enables better and more flexible planning compared to previous studies, which required nurses to arrive simultaneously. The problem is formulated as a mixed integer linear programming problem, and two techniques are developed to solve it: a Genetic Algorithm with Repair Mechanisms (GA-RM) and a Decomposition Heuristic with a Common Sub-Problem (DH-CSP). The repair mechanisms in GA-RM effectively address infeasible solutions, enhancing the diversity and quality of the generated solutions. Meanwhile, DH-CSP decomposes the problem into separate Sub-Problems (SPs) and solves them in parallel using GA-RM. Subsequently, uncovered patients and unassigned nurses in the SPs are reexamined in a CSP. This method combines a decomposition technique, which breaks down the large-scale problem into smaller SPs, with a metaheuristic method (GA-RM) that finds solutions for these SPs. According to the results of the statistical test, both proposed techniques have equal computation times; however, DH-CSP produces higher-quality solutions than GA-RM. Additionally, the results indicate that for large instances, SPs play a crucial role in covering patients, achieving an average coverage of 40% of the total patient population.</p>