Multi-depot home health care routing and scheduling problem with multimodal transportation: Mathematical model and solution methods

Document Type : Article


Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran


Providing appropriate home health care is one of the increasing concerns in the health care organizations. Home Health Care provides various services for disabled or elderly individuals at their homes. Also, deal with the current critical situation of the coronavirus disease (COVID-19) due to the limited capacity of hospitals and the feeling of insecurity in crowded places, home health care is more recommended. This paper addresses a Home Health Care Routing and Scheduling Problem (HHCRSP) with two modes of transportations including public and private modes. Also, multi-depot version of the problem is studied to enhance the service delivery in scattered points. In this study, a mathematical model is presented based on a Mixed Integer Linear P‌rogramming (MILP) whose objective function is minimization of the sum of the travel distance and overtime costs. Furthermore, three meta-heuristic algorithms including Invasive Weed Optimization (IWO), Grasshopper Optimization Algorithm (GOA) and Simulated Annealing (SA) are presented for solving the large-sized problems. Since the performance of meta-heuristic algorithms depends on setting the parameters, Taguchi method is used to statistically set parameters of the developed algorithms. The computational results have shown that the proposed IWO has worked better than the other two proposed algorithms statistically.


1.         Decerle, J., Grunder, O., El Hassani, A.H. and Barakat, O.“A matheuristic for a multi-depot home health care problem”, IFAC-PapersOnLine. 51(11), pp. 340-345 (2018).
2.         Fathollahi-Fard, A.M., Govindan, K., Hajiaghaei-Keshteli, M. and Ahmadi, A. “A green home health care supply chain: New modified simulated annealing algorithms”, Journal of Cleaner Production, 240, pp. 118200 (2019).
3.         Rest, K.D., Trautsamwieser, A. and Hirsch, P. “Trends and risks in home health care”. Journal of Humanitarian Logistics and Supply Chain Management, 2(1), pp. 34-53 (2019).
4.         Fernandez, A., Gregory, G., Hindle, A. and Lee, A.C. “A model for community nursing in a rural county”. Journal of the Operational Research Society, 25(2), pp. 231-239 (1974).
5.         Begur, S.V., Miller, D.M. and Weaver, J.R. “An integrated spatial DSS for scheduling and routing home-health-care nurses”. Interfaces, 27(4), pp. 35-48 (1997).
6.         Braekers, K., Hartl, R.F., Parragh, S.N. and Tricoire, F. “A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience”, European Journal of Operational Research, 248(2), pp. 428-443 (2016).
7.         Fikar, C. and Hirsch, P. “Evaluation of trip and car sharing concepts for home health care services”, Flexible Services and Manufacturing Journal, 30(1-2), pp. 78-97 (2018).
8.         Nasir, J.A., and Dang, C. “Solving a more flexible home health care scheduling and routing     problem with joint patient and nursing staff selection”, Sustainability, 10(1), 148 (2018).
9.         Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R. “A bi-objective green home health care routing problem”, Journal of Cleaner Production, 200, pp. 423-443 (2018).
10.       Tohidifard, M., Tavakkoli-Moghaddam, R., Navazi, F. and Partovi M. “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), pp. 358-363 (2018).
11.       Lanzarone, E. and Matta, A. “Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care”, Operations Research for Health Care, 3(2), pp. 48-58 (2014).
12.       Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J. and Raidl, G.R. “Metaheuristics for solving a multimodal home-healthcare scheduling problem”, Central European Journal of Operations Research, 23(1), pp. 89-113 (2015).
13.       Rest, K.D. and Hirsch, P. “Daily scheduling of home health care services using time-dependent public transport”, Flexible Services and Manufacturing Journal. 28(3), pp. 495-525 (2016).
14.       Xiao, Y. and Konak, A. “The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion”. Transportation Research Part E: Logistics and Transportation Review. 88: pp. 146-166 (2016).
15.       Jakob, A., Craig, J.L. and Fisher, G. “Transport cost analysis: a case study of the total costs of private and public transport in Auckland”. Environmental Science & Policy. 9(1): pp. 55-66 (2006).
16.       Masanobu, K.I.I. and Hanaoka, S. “Comparison of sustainability between private and public transport considering urban structure”, IATSS Research, 27(2), pp. 6-15 (2003).
17.       Trautsamwieser, A., Gronalt, M. and Hirsch, P. “Securing home health care in times of natural disasters”, OR spectrum, 33(3), pp. 787-813 (2011).
18.       Liu, R., Yuan, B. and Jiang, Z. “Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements”, International Journal of Production Research, 55(2), pp. 558-575 (2017).
19.       Riazi, S., Wigström, O., Bengtsson, K. and Lennartson, B. “A column generation-based gossip algorithm for home healthcare routing and scheduling problems”, IEEE Transactions on Automation Science and Engineering, 16(1), pp.127-137 (2018).
20.       Euchi, J. “Optimising the routing of home health caregivers: can a hybrid ant colony metaheuristic provide a solution? ”, British Journal of Healthcare Management, 26(7), pp. 192-196 (2020).
21.       Shi, Y., Boudouh, T. and Grunder, O. “A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand”, Expert Systems with Applications, 72, pp. 160-176 (2017).
22.       Decerle, J., Grunder, O., El Hassani, A.H. and Barakat, O. “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 (2017).
23.       Mankowska, D.S., Meisel, F. and Bierwirth, C. “The home health care routing and scheduling problem with interdependent services”. Health care management science. 17(1), pp. 15-30 (2014).
24.        Liu, R., Tao, Y. and Xie, X. “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits”, Computers & Operations Research, 101, pp. 250-262 (2019).
25.       Mehrabian, A.R. and Lucas, C. “A novel numerical optimization algorithm inspired from weed colonization”, Ecological informatics, 1(4), pp. 355-366 (2006).
26.       Saremi, S., Mirjalili, S. and Lewis, A. “Grasshopper optimisation algorithm: theory and application”, Advances in Engineering Software. 105: pp. 30-47 (2017).
27.      Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. “Optimization by simulated annealing” science. 220(4598), pp. 671-680 (1983).
28.        Nasir, J.A., and Kuo, Y.H. “A decision support framework for home health care transportation with simultaneous multi-vehicle routing and staff scheduling synchronization”, Decision Support Systems, 138, 113361 (2020).
29.       Rajkumar, R., Anandakumar, K. and Bharathi, A. “Grasshopper Optimization Algorithm based Feature Selection with Twin Support Vector Machine Classifier for Coronary Artery Heart Disease Prediction”, International Journal of Control and Automation, 12(6), pp. 256-267 (2019).
30.       Renukadevi, T. and Karunakaran, S. “Optimizing deep belief network parameters using grasshopper algorithm for liver disease classification”. International Journal of Imaging Systems and Technology, 30(1), pp. 168-184 (2020).
31.        Esmaeili-Douki, A., Mahzouni-Sani, M., Nikhalat Jahromi, A., and Jolai, F. “A novel fuzzy bi-objective vehicle routing and scheduling problem with time window constraint for a distribution system: A case study”, Scientia Iranica, In press (2020).
32.       Ross, P.J. Taguchi Techniques for Quality Engineering: Loss Function, Orthogonal Experiments, Parameter and Tolerance Design. McGraw-Hill, New York (1988).
33.       Yazdani, M., Zandieh, M., Tavakkoli-Moghaddam, R. and Jolai, F. “Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem”, Scientia Iranica, 22(3), pp. 1242- 1257 ( 2015).