Meta-Heuristic Algorithms for Multi-Objective Home Health Care Routing and Scheduling Problem Considering Time Windows and Workload Balance of Nurses

Document Type : Original Article


1 Ph.D Candidate, Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

2 Assistant Professor, Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.


Home Healthcare provides a wide range of home care services from prevention to rehabilitation and primary care to professional nursing services. This research presents a two-objective mathematical model based on the mixed integer linear programming approach for the home healthcare routing and scheduling problem (HHCRSP) with the objectives of minimization the nurses’ travel costs and the maximal working time difference among nurses. Considering the multimodal transportation, several initial health centers and one final health center and patient and nurse time windows are important features of the studied mathematical model. Small-sized problems have solved by using the Ɛ-constraint method on GAMS software. Also, due to the NP-hardness of the problem, MOPSO and NSGA-II algorithms have used to solve the medium and large-sized problems. The statistical results showed that the NSGA-II performed better than the MOPSO for medium and large sizes of problems in both MID and NOS performance metrics. Overall, Results of the performance metrics on different sizes of problems indicate the efficient and effective performance of NSGA-II in solving the understudied problem.


Main Subjects

  1. Adelli, M., & Zandieh, M. (2013). Multiobjective Simulation-Optimization Approach for Integrated Sourcing and Inventory Decisions. Journal of Industrial management perspective, 3(3), 89-110. (In Persian)
  2. Akjiratikarl, C., Yenradee, P., & Drake, P. R. (2007). PSO-based algorithm for home care worker scheduling in the UK. Computers & Industrial Engineering, 53(4), 559-583.
  3. Akbari, M., Dorri Nokarani, B., & Zandieh, M. (2012). Scheduling Working Shifts for Multi-skilled Workforces with Genetic algorithm Approach. Journal of Industrial Management Perspectives, 2(3), 87-102 (In Persian).
  4. Algethami, H., Landa-Silva, D., & Martínez-Gavara, A. (2017). Selecting Genetic Operators to Maximise Preference Satisfaction in a Workforce Scheduling and Routing Problem. In ICORES, 416-423.
  5. Asghari, M., & Mirzapour Al-e-hashem, S. M. J. (2019). A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources. Transportation Research Part E: Logistics and Transportation Review, 134,
  6. Becker, C. A., Lorig, F., & Timm, I. J. (2018). Multiagent Systems to Support Planning and Scheduling in Home Health Care Management: A Literature Review. In International Workshop on Artificial Intelligence in Health, Springer, Cham, 13-28.
  7. Begur, S. V., Miller, D. M., & Weaver, J. R. (1997). An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces, 27(4), 35-48.
  8. Braekers, K., Hartl, R. F., Parragh, S. N., & Tricoire, F. (2016). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European Journal of Operational Research, 248(2), 428-443.
  9. Cappanera, P., & Scutellà, M. G. (2015). Joint assignment, scheduling, and routing models to home care optimization: A pattern-based approach. Transportation Science, 49(4), 830-852.
  10. Coello, C. A. C., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on evolutionary computation, 8(3), 256-279.
  11. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
  12. Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O. (2017). Impact analysis of workload balancing on the home health care routing and scheduling problem. In 2017 4th International Conference on Control, Decision and Information Technologies (CoDIT), IEEE, 0096 -0101.
  13. Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O. (2019). A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchronization and working time balancing. Swarm and Evolutionary Computation, 46, 171-183.
  14. Erdem, M., & Koç, Ç. (2019). Analysis of electric vehicles in home health care routing problem. Journal of Cleaner Production , 234, 1471-1483.
  15. Euchi, J., Zidi, S., & Laouamer, L. (2020). A hybrid approach to solve the vehicle routing problem with time windows and synchronized visits in-home health care. Arabian Journal for Science and Engineering, 45(12), 10637-10652.
  16. 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,
  17. Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. (2018). A bi-objective green home health care routing problem. Journal of Cleaner Production, 200, 423-443.
  18. Fernandez, A., Gregory, G., Hindle, A., & Lee, A. C. (1974). A model for community nursing in a rural county. Journal of the Operational Research Society, 25(2), 231-239.
  19. Grenouilleau, F., Legrain, A., Lahrichi, N., & Rousseau, L. M. (2019). A set partitioning heuristic for the home health care routing and scheduling problem. European Journal of Operational Research, 275(1), 295-303.
  20. Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., & Raidl, G. R. (2015). Metaheuristics for solving a multimodal home-healthcare scheduling problem. Central European Journal of Operations Research, 23(1), 89-113.
  21. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks, IEEE, 4, 1942-1948.
  22. Khishtandar, S., Zandieh M., Dorri Nokarani, B., & Ranaei Siadat,  S. O. (2016). Evolutionary Algorithms for Location Allocation Biomethane Supply Chain Problem. The Journal of Industrial Management Perspectives, 6(3), 29-54 (In Persian).
  23. Li, Y., Xiang, T. & Szeto, W. Y. (2021). Home health care routing and scheduling problem with the consideration of outpatient services. Transportation Research Part E: Logistics and Transportation Review, 152,
  24. Liu, W., Dridi, M., Fei, H., & El Hassani, A. H. (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, 115307.
  25. Leff, B., Burton, L., Mader, S., Naughton, B., Burl, J., Clark, R., Greenough, W.B., Guido, S., Steinwachs, D., & Burton, J. R. (2006). Satisfaction with hospital at home care. Journal of the American Geriatrics Society; 54(9), 1355-1363
  26. Rest, K. D., & Hirsch, P. (2016). Daily scheduling of home health care services using time-dependent public Flexible Services and Manufacturing Journal, 28(3), 495-525.
  27. Rest, K. D., Trautsamwieser, A. and Hirsch, P. (2012). Trends and risks in home health care. Journal of Humanitarian Logistics and Supply Chain Management, 2(1), 34-53.
  28. Reyes-Sierra, M., & Coello, C. C. (2006). Multi-objective particle swarm optimizers: A survey of the state-of-the-art. International journal of computational intelligence research, 2(3), 287-308.
  29. Salehi, M., & Rezaei, H. (2019). A fuzzy multi-objective model for allocating orders to suppliers under shortfall and price-quantity discounts: An mpso and nsga-ii with tuned parameters. International Journal of Industrial Engineering & Production Research, 30(2), 225-239.
  30. Schott, J. R. (1995). Fault tolerant design using single and multicriteria genetic algorithms optimization. Master’s thesis Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge.
  31. Tohidifard, M., Tavakkoli-Moghaddam, R., Navazi, F., & Partovi M. (2018). A Multi-Depot Home Care Routing Problem with Time Windows and Fuzzy Demands Solving by Particle Swarm Optimization and Genetic Algorithm. IFAC-PapersOnLine, 51(11), 358-363.
  32. Trautsamwieser, A., & Hirsch, P. (2011). Optimization of daily scheduling for home health care services. Journal of Applied Operational Research3(3), 124-136.
  33. Verma, A., & Kaushal, S. (2017). A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Computing, 62, 1-19.
  34. Wirnitzer, J., Heckmann, I., Meyer, A. & Nickel, S. (2016). Patient-based nurse rostering in home care. Operations Research for Health Care, 8, 91-102.
  35. Yazdani, M., M. Zandieh & Tavakkoli-Moghaddam, (R. 2019). Evolutionary algorithms for multi-objective dual-resource constrained flexible job-shop scheduling problem. OPSEARCH, 56(3), 983-1006.
  36. Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: Methods and applications, Swiss Federal Institute of Technology (ETH), Zuerich, Switzerland, Dissertation ETH No. 1339.