Tabu Search with Variable Neighborhood Search Algorithm for Home Healthcare Routing Problem for Multiple Hospitals with Balanced Workload

Abstract

In this paper, we study home healthcare routing and scheduling problem where multiple hospitals serve patients. In the public hospitals in healthcare system of Türkiye, patients requiring home healthcare are assigned to the hospital that serves their place of residence. This can cause the workload of hospitals to become unbalanced in terms of the time needed for both traveling and operation. The aim of this paper is to generate routes with a balanced workload for hospitals, giving consideration to the time windows of patients and the working hours of health workers. Firstly, we construct a mathematical model which can solve toy and small-scale problems whilst taking into account the importance of a balanced workload. Then, a Tabu Search with a Variable Neighborhood Search (TS-VNS) algorithm is developed to solve large-scale problems. The performance of the TS-VNS algorithm is tested by comparing the results of the mathematical model with the generated test problems at a small scale. Additionally, large-scale test problems from the literature are sourced for the problem and solved by the TS-VNS algorithm. The results demonstrate the efficiency of the TS-VNS algorithm.

Keywords

• Home healthcare
• tabu search
• variable neighborhood search
• workload balance
• OR in healthcare

References

1. [1] P. Eveborn, P. Flisberg, and M. Rönnqvist, “Laps Care—an operational system for staff planning of home care”, European Journal of Operational Research, vol. 171, no. 3, pp. 962–976, Jun. 2006, doi: 10.1016/j.ejor.2005.01.011.
2. [2] “WHO’s work on the UN decade of healthy ageing (2021-2030)”. Accessed on: Feb. 13, 2023. [Online]. Available: https://www.who.int/initiatives/decade-of-healthy-ageing
3. [3] “Home healthcare market size, share & trends analysis report, 2022-2030”. Accessed on: Feb. 13, 2023. [Online]. Available: https://www.researchandmarkets.com/reports/5450245/home-healthcare-market-size-share-and-trends
4. [4] E., Cheng, and, J. L. Rich, “A home healthcare routing and scheduling problem”, 1998. Accessed on: Feb. 13, 2023. [Online]. Available: https://scholarship.rice.edu/handle/1911/101899
5. [5] S. Afifi, D.-C. Dang, and A. Moukrim, “Heuristic solutions for the vehicle routing problem with time windows and synchronized visits”, Optim Lett, vol. 10, no. 3, pp. 511–525, Mar. 2016, doi: 10.1007/s11590-015-0878-3.
6. [6] M. Cissé, S. Yalçındağ, Y. Kergosien, E. Şahin, C. Lenté, and A. Matta, “OR problems related to home health care: A review of relevant routing and scheduling problems”, Operations Research for Health Care, vol. 13–14, pp. 1–22, Jun. 2017, doi: 10.1016/j.orhc.2017.06.001.
7. [7] M. Di Mascolo, C. Martinez, and M.-L. Espinouse, “Routing and scheduling in home health care: A literature survey and bibliometric analysis”, Computers & Industrial Engineering, vol. 158, p. 107255, Aug. 2021, doi: 10.1016/j.cie.2021.107255.
8. [8] C. Fikar and P. Hirsch, “Home health care routing and scheduling: A review”, Computers & Operations Research, vol. 77, pp. 86–95, Jan. 2017, doi: 10.1016/j.cor.2016.07.019.

9. [9] L. Grieco, M. Utley, and S. Crowe, “Operational research applied to decisions in home health care: A systematic literature review”, Journal of the Operational Research Society, vol. 72, no. 9: pp. 1960-1991, 2021. https://doi.org/10.1080/01605682.2020.1750311
10. [10] D. Bredström and M. Rönnqvist, “Combined vehicle routing and scheduling with temporal precedence and synchronization constraints”, European Journal of Operational Research, vol. 191, no. 1, pp. 19–31, Nov. 2008, doi: 10.1016/j.ejor.2007.07.033.
11. [11] E. Lanzarone and A. Matta, “Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care”, Operations Research for Health Care, vol. 3, no. 2, pp. 48-58, June 2014, doi: https://doi.org/10.1016/j.orhc.2014.01.003 .
12. [12] G. Carello, E. Lanzarone, and S. Mattia, “Trade-off between stakeholders’ goals in the home care nurse-topatient assignment problem”, Operations Research for Health Care vol. 16, pp. 29–40, March 2018, doi: https://doi.org/10.1016/j.orhc.2017.12.002
13. [13] B. Yuan, R. Liu, and Z. Jiang, “A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements”, International Journal of Production Research, vol. 53, no. 24, pp. 7450–7464, Dec. 2015, doi: 10.1080/00207543.2015.1082041.
14. [14] K.-D. Rest and P. Hirsch, “Daily scheduling of home health care services using time-dependent public transport”, Flex Serv Manuf J, vol. 28, no. 3, pp. 495–525, Sep. 2016, doi: 10.1007/s10696-015-9227-1.
15. [15] Y. Shi, T. Boudouh, and O. Grunder, “A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand”, Expert Systems with Applications, vol. 72, pp. 160–176, Apr. 2017, doi: 10.1016/j.eswa.2016.12.013.
16. [16] M. Masmoudi and N. Cheikhrouhou, “Heterogeneous vehicle routing problems with synchronization: Application to homecare scheduling routing problem”. 9th Conference on Engineering and Management of Healthcare Systems GISEH, Geneva, 2018.
17. [17] R. Liu, B. Yuan, and Z. Jiang, “A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times”, Flex Serv Manuf J, vol. 31, no. 4, pp. 989–1011, Dec. 2019, doi: 10.1007/s10696-018-9328-8.
18. [18] S. Bahadori-Chinibelagh, A. M. Fathollahi-Fard, and M. Hajiaghaei-Keshteli, “Two constructive algorithms to address a multi-depot home healthcare routing problem”, IETE Journal of Research, vol. 68, no. 2, pp. 1108–1114, Mar. 2022, doi: 10.1080/03772063.2019.1642802.
19. [19] N. Tanoumand and T. Ünlüyurt, “An exact algorithm for the resource constrained home health care vehicle routing problem”, Ann Oper Res, vol. 304, no. 1, pp. 397–425, Sep. 2021, doi: 10.1007/s10479-021-04061-9.
20. [20] Y. Li, T. Xiang, and W. Y. Szeto, “Home health care routing and scheduling problem with the consideration of outpatient services”, Transportation Research Part E: Logistics and Transportation Review, vol. 152, p. 102420, Aug. 2021, doi: 10.1016/j.tre.2021.102420.
21. [21] H. Allaoua, S. Borne, L. Létocart, and R. Wolfler Calvo, “A matheuristic approach for solving a home health care problem”, Electronic Notes in Discrete Mathematics, vol. 41, pp. 471–478, Jun. 2013, doi: 10.1016/j.endm.2013.05.127.
22. [22] P. Cappanera, M. G. Scutellà, F. Nervi, and L. Galli, “Demand uncertainty in robust Home Care optimization”. Omega, vol. 80, pp. 95–110, October 2018, doi: https://doi.org/10.1016/j.omega.2017.08.012
23. [23] S. Frifita, M. Masmoudi, and J. Euchi, “General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits”, Electronic Notes in Discrete Mathematics, vol. 58, pp. 63–70, Apr. 2017, doi: 10.1016/j.endm.2017.03.009.
24. [24] S. Lan, W. Fan, S. Yang, P. M. Pardalos and, N. Mladenovic, “A survey on the applications of variable neighborhood search algorithm in healthcare management”, Annals of Mathematics and Artificial Intelligence, vol. 89, no. 8, pp. 741-775, 2021, doi: 10.1007/s10472-021-09727-5.
25. [25] E. Rahimian, K. Akartunalı, J. Levine, “A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems”, Eur J Oper Res, vol. 258, no. 2, pp. 411–423, April 2017, doi: https://doi.org/10.1016/j.ejor.2016.09.030
26. [26] S. Riazi, O. Wigström, K. Bengtsson, and B. Lennartson, “Decomposition and distributed algorithms for home healthcare routing and scheduling problem”, in 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), Sep. 2017, pp. 1–7. doi: 10.1109/ETFA.2017.8247622.
27. [27] S. Riazi, O. Wigström, K. Bengtsson, and B. Lennartson, “A column generation-based gossip algorithm for home healthcare routing and scheduling problems”, IEEE Transactions on Automation Science and Engineering, vol. 16, no. 1, pp. 127–137, Jan. 2019, doi: 10.1109/TASE.2018.2874392.
28. [28] S. E. Moussavi, M. Mahdjoub, and O. Grunder, “A matheuristic approach to the integration of worker assignment and vehicle routing problems: Application to home healthcare scheduling”, Expert Systems with Applications, vol. 125, pp. 317–332, Jul. 2019, doi: 10.1016/j.eswa.2019.02.009.
29. [29] F. Grenouilleau, A. Legrain, N. Lahrichi, and L.-M. Rousseau, “A set partitioning heuristic for the home health care routing and scheduling problem”, European Journal of Operational Research, vol. 275, no. 1, pp. 295–303, May 2019, doi: 10.1016/j.ejor.2018.11.025.
30. [30] F. Grenouilleau, N. Lahrichi, and L.-M. Rousseau, “New decomposition methods for home care scheduling with predefined visits”, Computers & Operations Research, vol. 115, p. 104855, Mar. 2020, doi: 10.1016/j.cor.2019.104855.
31. [31] S. Shahnejat-Bushehri, R. Tavakkoli-Moghaddam, M. Boronoos, and A. Ghasemkhani, “A robust home health care routing-scheduling problem with temporal dependencies under uncertainty”, Expert Syst Appl, vol. 182, no. 115209, November 2021, doi: https://doi.org/10.1016/j.eswa.2021.115209
32. [32] L. Dekhici, R. Redjem, K. Belkadi, and A. Mhamedi, “Discretization of the firefly algorithm for home care”, Can J Electr Comput Eng, vol. 42, no. 1, pp. 20–26, 2016.
33. [33] M. R. Hassani, and J. Behnamian, “A scenario-based robust optimization with a pessimistic approach for nurse rostering problem”, J Comb Optim, vol. 41, no. 1, pp. 143–169, November 2021, doi: https://doi.org/10.1007/s10878-020-00667-0
34. [34] M. S. Rasmussen, T. Justesen, A. Dohn, and J. Larsen, “The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies”, European Journal of Operational Research, vol. 219, no. 3, pp. 598–610, Jun. 2012, doi: 10.1016/j.ejor.2011.10.048.
35. [35] S. Nickel, M. Schröder, and J. Steeg, “Mid-term and short-term planning support for home health care services”, European Journal of Operational Research, vol. 219, pp. 574-587, Jun. 2012, doi: https://doi.org/10.1016/j.ejor.2011.10.042 .
36. [36] D. S. Mankowska, F. Meisel, and C. Bierwirth, “The home health care routing and scheduling problem with interdependent services”, Health Care Management Science, vol. 17, pp. 15-30, 2014, doi: https://doi.org/10.1007/s10729-013-9243-1 .
37. [37] K. Braekers, R. F. Hartl, S. N. Parragh, and, F. Tricoire, “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, pp. 428-443, 2016, doi: 10.1016/j.ejor.2015.07.028
38. [38] A. Hertz and N. Lahrichi, “A patient assignment algorithm for home care services”, Journal of the Operational Research Society, vol. 60, no. 4, pp. 481-495, 2009, doi: https://doi.org/10.1057/palgrave.jors.2602574
39. [39] S. Yalçındağ, A. Matta, E. Şahin, and J. G. Shanthikumar, “The patient assignment problem in home health care: using a data-driven method to estimate the travel times of care givers”, Flexible Services and Manufacturing Journal, vol. 28, pp. 304-335, June 2016, doi: https://doi.org/10.1007/s10696-015-9222-6 .
40. [40] S. Yalçındağ, P. Cappanera, M. Scutella, E. Şahin, and A. Matta, “Pattern-based decompositions for human resource planning in home health care services”, Comput Oper Res, vol. 73, pp. 12–26, September 2016, doi: https://doi.org/10.1016/j.cor.2016.02.011
41. [41] J. Decerle, O. Grunder, A. Hajjam El Hassani, and O. Barakat, “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, vol. 46, pp. 171–183, May 2019, doi: 10.1016/j.swevo.2019.02.009.
42. [42] M. I. Gomes, and T.R.P. Ramos, “Modelling and (re-)planning periodic home social care services with loyalty and non-loyalty features”, Eur J Oper Res, vol. 277, no. 1 pp. 284–299, August 2019, doi: https://doi.org/10.1016/j.ejor.2019.01.061
43. [43] A. Kandakoglu, A. Sauré, W. Michalowski, M. Aquino, J. Graham, and B. McCormick, “A decision support system for home dialysis visit scheduling and nurse routing”, Decis Support Syst, vol. 130, no. 113224, March 2020, doi: https://doi.org/10.1016/j.dss.2019.113224
44. [44] M. Yang, Y. Ni, and L. Yang, “A multi-objective consistent home healthcare routing and scheduling problem in an uncertain environment”, Computers & Industrial Engineering, vol. 160, no. 107560, Oct. 2021, doi: 10.1016/j.cie.2021.107560.
45. [45] H. Bae and I. Moon, “Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles”, Applied Mathematical Modelling, vol. 40, no. 13, pp. 6536–6549, Jul. 2016, doi: 10.1016/j.apm.2016.01.059.
46. [46] E. Jabir, V. V. Panicker, and R. Sridharan, “Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem”, Transportation Research Part D: Transport and Environment, vol. 57, pp. 422–457, Dec. 2017, doi: 10.1016/j.trd.2017.09.003.
47. [47] F. Glover, “Tabu search: Part I”, ORSA Journal on Computing, vol. 1, no. 3, pp. 190–206, Aug. 1989. doi: https://doi.org/10.1287/ijoc.1.3.190
48. [48] N. Mladenović and P. Hansen, “Variable neighborhood search”, Computers & Operations Research, vol. 24, no. 11, pp. 1097–1100, Nov. 1997, doi: 10.1016/S0305-0548(97)00031-2.
49. [49] J.-F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows”, J Oper Res Soc, vol. 52, no. 8, pp. 928–936, Aug. 2001, doi: 10.1057/palgrave.jors.2601163.
50. [50] J. Bergstra, D. Yamins, and D. Cox. “Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures”, International Conference on Machine Learning, pp. 115-123, Feb. 2013, doi: https://doi.org/10.48550/arXiv.1209.5111
51. [51] J. Bergstra, R. Bardenet, Y. Bengio, and B. K´egl. “Algorithms for hyper-parameter optimization”, Advances in Neural Information Processing Systems 24, pp. 2546-2554, 2011.