Journal of Transportation Research

Journal of Transportation Research

Single‑Depot Nurse Scheduling and Vehicle Routing with Time Windows and Service Penalties in Home Healthcare: Modeling and Variable Neighborhood Search

Document Type : Original Article

Authors
Mahdieh Sheikhi 1
Javad Behnamian 2
1 Ph.D., Student, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.
2 Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.
10.22034/tri.2026.566440.3418
Abstract
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.
Keywords
Home Nursing
Vehicle Routing
Staff Scheduling
Operational Resource Allocation
Variable Neighborhood Search
Subjects
-Arabzadeh, E., Fatemi Ghomi, S. and Karimi, B. (2023). Multi-period home health care routing and scheduling problem with the medical grouping of patients. Scientia Iranica, 30(5), 1781-1795.
-Atta, S., Basto‑Fernandes, V., & Emmerich, M. (2025). A concise review of the home health care routing and scheduling problem. Operations Research Perspectives, 15, 100347.
-Belhor, M., El‑Amraoui, A., Jemai, A., & Delmotte, F. (2023). Multi-objective evolutionary approach based on K-means clustering for home health care routing and scheduling problem. Expert Systems with Applications, 213, 119035.
-Biswas, D., Alfandari, L., & Archetti, C. (2024). A triple bottom line optimization model for assignment and routing of on-demand home services. Computers & Operations Research, 167, 106644.
-Du, G., & Zhang, J. (2022). Cross-regional manpower scheduling and routing problem with stochastic service times in home health care. Computers & Industrial Engineering, 173, 108668.
-Erdem, M., Koç, Ç., & Yücel, E. (2022). The electric home health care routing and scheduling problem with time windows and fast chargers. Computers & Industrial Engineering, 172(A), 108580.
-Fathollahi‑Fard, A. M., Ahmadi, A., Goodarzian, F., & Cheikhrouhou, N. (2020). A bi-objective home healthcare routing and scheduling problem considering patients’ satisfaction in a fuzzy environment. Applied Soft Computing, 93, 106385.
-Goodarzian, F., Shokri Garjan, H., & Ghasemi, P. (2023). A state-of-the-art review of operation research models and applications in home healthcare. Healthcare Analytics, 4, 100228.
-Guo, J., & Bard, J. F. (2023). A three-step optimization-based algorithm for home healthcare delivery. Socio‑Economic Planning Sciences, 87(A), 101517.
-HadjTaieb, S., Cheikh, M., Hani, Y., El Mhamedi, A., & Moalla Loukil, T. (2025). Towards sustainable home (health)-care: Bi-objective formulation for electric vehicle routing. Computers & Industrial Engineering, 205, 111165.
-Hosseini, S.-S., Adulyasak, Y., & Rousseau, L.-M. (2026). Consistent home health care routing and scheduling problem under time uncertainty. Transportation Research Part E: Logistics and Transportation Review, 205, 104509.
-Liu, W., Dridi, M., Fei, H., & Hajjam El Hassani, A. (2021). Hybrid metaheuristics for solving a home health care routing and scheduling problem with time windows, synchronized visits and lunch breaks. Expert Systems with Applications, 183, 115307.
-Masmoudi, M., Borchani, R., & Jarboui, B. (2025). Generalized variable neighborhood search algorithm for vehicle routing problem with time windows and synchronization. Computers & Operations Research, 183, 107193.
-Muriyatmoko, D., Djunaidy, A., & Muklason, A. (2025). An integrated optimization approach to cross-domain scheduling and routing. Decision Analytics Journal, 17, 100654.
-Nasir, J. A., & Kuo, Y.-H. (2020). A decision support framework for home health care transportation with simultaneous multi-vehicle routing and staff scheduling synchronization. Decision Support Systems, 138, 113361.
-Oladzad‑Abbasabady, N., Tavakkoli‑Moghaddam, R., Mohammadi, M., & Vahedi‑Nouri, B. (2023). A bi-objective home care routing and scheduling problem considering patient preference and soft temporal dependency constraints. Engineering Applications of Artificial Intelligence, 119, 105829.
-Pena de Aguiar, A. R., Pereira Ramos, T. R., & Gomes, M. I. (2023). Home care routing and scheduling problem with teams’ synchronization. Socio‑Economic Planning Sciences, 86, 101503.
-Parreño‑Torres, C., Reula, M., Alvarez‑Valdes, R., & Parreño, F. (2024). Solving the palliative home health care routing and scheduling problem with an integer linear programming model. Expert Systems with Applications, 249, 123728.
-Rekabi, S., Moradi, B., Salamian, F., Fadavi, N., Zokaee, M., & Aghsami, A. (2024). A home healthcare routing‑scheduling optimization model considering time‑balancing and outsourcing. Supply Chain Analytics, 7, 100077.
-Reula, M., Parreño‑Torres, C., Lamas‑Fernandez, C., & Martinez‑Sykora, A. (2025). A flexible mathematical model for home health care problems. European Journal of Operational Research, 327(3), 791–807.
-Ting Zhang, Liu, Y., Yang, X., Chen, J., & Huang, J. (2023). Home health care routing and scheduling in densely populated communities considering complex human behaviours. Computers & Industrial Engineering, 182, 109332.
-Yazır, O.A., Koç, Ç. & Yücel, E. (2023). The multi-period home healthcare routing and scheduling problem with electric vehicles. OR Spectrum 45, 853–901.