Home nursing and domiciliary care are rapidly expanding within healthcare systems and impose precise requirements on transportation and operational planning. This paper formulates an integrated mixed‑integer programming model for the single‑depot nurse scheduling and vehicle routing problem with time windows, service penalties and workforce constraints. Each patient request is characterized by service duration, a (soft) time window and a priority level, while nurses have limited shift capacities and skill compatibilities and vehicles have finite operating time. The model jointly determines visit sequences, service start times and nurse–patient assignments to balance service quality, staff workload and travel effort; the objective combines total travel time, penalties for service delay/earliness and preference‑based rewards. To evaluate the model, exact solutions are obtained for small instances and numerical experiments on representative scenarios analyze the effects of demand patterns, time‑window tightness and shift structures on routing efficiency and total travel distance. For large‑scale instances, a variable neighborhood search (VNS) metaheuristic is developed and implemented, exploiting multiple neighborhood structures and local improvement operators to produce high‑quality solutions within practical runtimes. Comparative results show that coordinated scheduling and routing substantially reduce travel distances and improve operational efficiency without compromising service coverage, and that the VNS provides a scalable, effective solution method for real‑world problem sizes. The study offers actionable insights for transportation planners and healthcare managers and motivates further research on dynamic requests and multi‑skill workforce allocation.