A Lagrangian Relaxation-based Algorithm to Solve a Home Health Care Routing Problem


1 Department of Industrial Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

3 Arts et Métiers Paris Tech, LCFC, Metz, France


Nowadays, a rapid growth in the rate of life expectancy can be seen especially in the developed countries. Accordingly, the population of elderlies has been increased. By another point of view, the number of hospitals, retirement homes along with medical staffs has not been grown with a same rate. Hence, Home Health Care (HHC) operations including a set of nurses and patients have been developed recently by both academia and health practitioners to consider elderlies’ preferences willing to receive their cares at their homes instead of hospitals or retirement homes. To alleviate the drawbacks of pervious works and make HHC more practical, this paper introduces not only a new mathematical formulation considering new suppositions in this research area but also a solution approach based on Lagrangian relaxation theory has been employed for the first time. The main strategy of used algorithm aims to fill the gap between the lower bound and upper bound of problem and finds a solution which has both optimality and feasibility properties. By generating a number of numerical examples, results show the performance of the proposed algorithm analyzed by different criteria as well as the efficiency of developed formulation through a set of sensitivity analyses.


1.     Fikar, C. and Hirsch, P., "Home health care routing and scheduling: A review", Computers & Operations Research,  Vol. 77, (2017), 86-95.
2.     Employment, E.C.D.-G.f. and E., E.O.U., "Europe's demographic future: Facts and figures on challenges and opportunities, Office for official publications of the European communities,  (2007).
3.     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,  Vol. 248, No. 2, (2016), 428-443.
4.     Lin, C.-C., Hung, L.-P., Liu, W.-Y. and Tsai, M.-C., "Jointly rostering, routing, and rerostering for home health care services: A harmony search approach with genetic, saturation, inheritance, and immigrant schemes", Computers & Industrial Engineering,  Vol. 115, (2018), 151-166.
5.     Liu, R., Xie, X. and Garaix, T., "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics", Omega,  Vol. 47, (2014), 17-32.
6.     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,  Vol. 72, (2017), 160-176.
7.     Sahebjamnia, N., Fard, A.M.F. and Hajiaghaei-Keshteli, M., "Sustainable tire closed-loop supply chain network design: Hybrid metaheuristic algorithms for large-scale networks", Journal of Cleaner Production,  Vol. 196, (2018), 273-296.
8.     Rasmussen, M.S., Justesen, T., Dohn, A. and Larsen, J., "The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies", European Journal of Operational Research,  Vol. 219, No. 3, (2012), 598-610.
9.     Nickel, S., Schröder, M. and Steeg, J., "Mid-term and short-term planning support for home health care services", European Journal of Operational Research,  Vol. 219, No. 3, (2012), 574-587.
10.   Liu, R., Xie, X., Augusto, V. and Rodriguez, C., "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care", European Journal of Operational Research,  Vol. 230, No. 3, (2013), 475-486.
11.   Mankowska, D.S., Meisel, F. and Bierwirth, C., "The home health care routing and scheduling problem with interdependent services", Health Care Management Science,  Vol. 17, No. 1, (2014), 15-30.
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,  Vol. 23, No. 1, (2015), 89-113.
13.   Fikar, C. and Hirsch, P., "A matheuristic for routing real-world home service transport systems facilitating walking", Journal of Cleaner Production,  Vol. 105, (2015), 300-310.
14.   Cappanera, P., Scutellà, M.G., Nervi, F. and Galli, L., "Demand uncertainty in robust home care optimization", Omega,  Vol. 80, (2018), 95-110.
15.   Dukkanci, O. and Kara, B.Y., "Routing and scheduling decisions in the hierarchical hub location problem", Computers & Operations Research,  Vol. 85, (2017), 45-57.
16.   Mestria, M., "New hybrid heuristic algorithm for the clustered traveling salesman problem", Computers & Industrial Engineering,  Vol. 116, (2018), 1-12.
17.   Golshahi-Roudbaneh, A., Hajiaghaei-Keshteli, M. and Paydar, M.M., "Developing a lower bound and strong heuristics for a truck scheduling problem in a cross-docking center", Knowledge-Based Systems,  Vol. 129, (2017), 17-38.
18.   Astorino, A., Gaudioso, M. and Miglionico, G., "Lagrangian relaxation for the directional sensor coverage problem with continuous orientation", Omega,  Vol. 75, (2018), 77-86.
19.   Miller, C.E., Tucker, A.W. and Zemlin, R.A., "Integer programming formulation of traveling salesman problems", Journal of the ACM (JACM),  Vol. 7, No. 4, (1960), 326-329.
20.   Fard, A.M.F., Gholian-Jouybari, F., Paydar, M.M. and Hajiaghaei-Keshteli, M., "A bi-objective stochastic closed-loop supply chain network design problem considering downside risk", Industrial Engineering & Management Systems,  Vol. 16, No. 3, (2017), 342-362.
21.   Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R., "A bi-objective green home health care routing problem", Journal of Cleaner Production,  Vol. 200, (2018), 423-443.
22.   Taguchi, G., Introduction to quality engineering: Designing quality into products and processes. 1986.
23.   Fard, A.M.F. and Hajiaghaei-Keshteli, M., "A bi-objective partial interdiction problem considering different defensive systems with capacity expansion of facilities under imminent attacks", Applied Soft Computing,  Vol. 68, (2018), 343-359.
24.   Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Tavakkoli-Moghaddam, R., "The social engineering optimizer (SEO)", Engineering Applications of Artificial Intelligence,  Vol. 72, (2018), 267-293.
25.   Fathollahi-Fard, A.M. and Hajiaghaei-Keshteli, M., "A stochastic multi-objective model for a closed-loop supply chain with environmental considerations", Applied Soft Computing,  Vol. 69, (2018), 232-249.
26.   Hajiaghaei-Keshteli, M. and Fard, A.M.F., "Sustainable closed-loop supply chain network design with discount supposition", Neural Computing and Applications,  (2018), 1-35.
27.   Nasiri, E., Afshari, A.J. and Hajiaghaei-Keshteli, M., "Addressing the freight consolidation and containerization problem by recent and hybridized meta-heuristic algorithms", International Journal of Engineering-Transactions C: Aspects,  Vol. 30, No. 3, (2017), 403-410.
28.   Sadeghi-Moghaddam, S., Hajiaghaei-Keshteli, M. and Mahmoodjanloo, M., "New approaches in metaheuristics to solve the fixed charge transportation problem in a fuzzy environment", Neural Computing and Applications,  (2017), 1-21.
29.   Samadi, A., N., M., Fathollahi Fard, A.M. and Hajiaghaei-Keshteli, M., "Heuristic approaches to solve the sustainable closed-loop supply chain", Journal of Industrial and Production Engineering,  Vol. 35, No. 2, (2018), 102-117.