Developing a mathematical model for staff routing and scheduling in home health care industries: Genetic algorithm-based solution scheme

Document Type : Article

Authors

Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

Abstract

Efficient management of providing home health care services requires many considerations. In this paper, a mathematical model for the daily staff routing and service scheduling is developed for home health care companies. In this model, both economic factors and qualitative service-oriented performance measures are simultaneously optimized. To make the model more realistic, many real situations such as considering different qualifications and diverse vehicles for staff members, different requirements and predetermined preferences for patients, possible temporal interdependencies between services, and continuity of care (CoC) are taken into account. We also added some important constraints related to blood sampling requirements, which make our proposed model more complex. The proposed model is a mixed integer linear programming model (MILP) that belongs to an NP-hard class of optimization problems. To solve such a complex mathematical model, a genetic algorithm (GA) is proposed to find near-optimal solutions. We use some randomly generated test instances with different sizes to evaluate the performance of the GA. Finally, it is demonstrated how the proposed solution scheme can end up with proper scheduling and routing policies compared to those obtained through exact methods.

Keywords

References

References:
1. Tarricone, R. and Tsouros, A.D., Home Care in Europe: the Solid Facts, WHO Regional Office Europe (2008).
2. Bouajaja, S. and Dridi, N. "A survey on human resource allocation problem and its applications", Operational Research, 17(2), pp. 339-369 (2017).
3. Pouraliakbarimamaghani, M., Mohammadi, M., and Mirzazadeh, A. "A queuing location-allocation model for a capacitated health care system", Scientia Iranica, E., 24, pp. 751-764 (2017).
4. Bredstrom, D. and Ronnqvist, M. "Combined vehicle routing and scheduling with temporal precedence and synchronization onstraints", European Journal of Operational Research, 191(1), pp. 19-31 (2008).
5. Kergosien, Y., Lente, C., and Billaut, J.-C. "Home health care problem: An extended multiple traveling salesman problem", Proc., 4th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA'09), Dublin (Irlande), pp. 10-12 (2009).
6. 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, 219(3), pp. 598-610 (2012).
7. 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).
8. 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).
9. Elbenani, B., Ferland, J.A., and Gascon, V. "Scatter search approach for solving a home care nurses routing and scheduling problem", In University of Montreal, Canada (2011).
10. Wirnitzer, J., Heckmann, I., Meyer, A., and Nickel, S. "Patient-based nurse rostering in home care", Operations Research for Health Care, 8, pp. 91-102 (2016).
11. Laporte, G. "The vehicle routing problem: An overview of exact and approximate algorithms", European Journal of Operational Research, 59(3), pp. 345- 358 (1992).
12. Toth, P. and Vigo, D., Vehicle Routing: Problems, Methods, and Applications, Siam (2014).
13. Eksioglu, B., Vural, A.V., and Reisman, A. "The vehicle routing problem: A taxonomic review", Computers & Industrial Engineering, 57(4), pp. 1472-1483 (2009).
14. Gutierrez, E.V. and Vidal, C.J. "Home health care logistics management: Framework and research perspectives", International Journal of Industrial Engineering and Management, 4(3), pp. 173-182 (2013).
15. Fikar, C. and Hirsch, P. "Home health care routing and scheduling: A review", Computers & Operations Research, 77, pp. 86-95 (2017).
16. 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).
17. Cheng, E. and Rich, J.L. "A home health care routing and scheduling problem", URL http://citeseerx. ist. psu. edu/viewdoc/summary (1998).
18. Bertels, S. and Fahle, T. "A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem", Computers & Operations Research, 33(10), pp. 2866-2890 (2006).
19. Eveborn, P., Flisberg, P., and Ronnqvist, M. "Laps care an operational system for staff planning of home care", European Journal of Operational Research, 171(3), pp. 962-976 (2006).
20. Braysy, O., Dullaert, W., and Nakari, P., Municipal Routing Problems: A Challenge for Researchers and Policy Makers? In: Witlox FJA, Ruijrok CJ (eds) Bijdragen Vervoerslogistieke Werkdagen, Nautilus Academic Books, Zelzate, pp 330-347 (2007).
21. Akjiratikarl, C., Yenradee, P., and Drake, P.R. "PSObased algorithm for home care worker scheduling in the UK", Computers & Industrial Engineering, 53(4), pp. 559-583 (2007).
22. Trautsamwieser, A. and Hirsch, P. "Optimization of daily scheduling for home health care services", Journal of Applied Operational Research, 3(3), pp. 124-136 (2011).
23. 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).
24. Duque, P.M., Castro, M., Sorensen, K., and Goos, P. "Home care service planning. The case of landelijke thuiszorg", European Journal of Operational Research, 243(1), pp. 292-301 (2015).
25. Redjem, R. and Marcon, E. "Operations management in the home care services: a heuristic for the caregivers, routing problem", Flexible Services and Manufacturing Journal, 28(1-2), pp. 280-303 (2016).
26. Frifita, S., Masmoudi, M., and Euchi, J. "General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits", Electronic Notes in Discrete Mathematics, 58, pp. 63-70 (2017).
27. Decerle, J., Grunder, O., El Hassani, A.H., and Barakat, O. "A memetic algorithm for a home health care routing and scheduling problem", Operations Research for Health Care, 16, pp. 59-71 (2018).
28. Liu, R., Yuan, B., and Jiang, Z. "A branch-andprice algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times", Flexible Services and Manufacturing Journal, 31(4), pp. 989-1011 (2019).
29. Demirbilek, M., Branke, J., and Strauss, A. "Dynamically accepting and scheduling patients for home healthcare", Health Care Management Science, 22(1), pp. 140-155 (2019).
30. Regis-Hernandez, F., Carello, G., and Lanzarone, E. "An optimization tool to dimension innovative home health care services with devices and disposable materials", Flexible Services and Manufacturing Journal, 32(3), pp. 1-38 (2020).
31. Baker, B.M. and Ayechew, M. "A genetic algorithm for the vehicle routing problem", Computers & Operations Research, 30(5), pp. 787-800 (2003).
32. Liu, S., Huang, W., and Ma, H. "An effective genetic algorithm for the  fleet size and mix vehicle routing problems", Transportation Research Part E: Logistics and Transportation Review, 45(3), pp. 434-445 (2009).
33. Ghoseiri, K. and Ghannadpour, S.F. "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm", Applied Soft Computing, 10(4), pp. 1096-1107 (2010).
34. Tasan, A.S. and Gen, M. "A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries", Computers & Industrial Engineering, 62(3), pp. 755-761 (2012).
35. Wang, H.-F. and Chen, Y.-Y. "A genetic algorithm for the simultaneous delivery and pickup problems with time window", Computers & Industrial Engineering, 62(1), pp. 84-95 (2012).
36. 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, 230(3), pp. 475-486 (2013).
37. Pankratz, G. "A grouping genetic algorithm for the pickup and delivery problem with time windows", Or Spectrum, 27(1), pp. 21-41 (2005).
38. Holland, J.H., Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, U Michigan Press (1975).
39. Gen, M., Cheng, R., and Lin, L., Network Models and Optimization: Multiobjective Genetic Algorithm Approach, Springer Science & Business Media (2008).
40. Fraley, S., Oom, M., Terrien, B., and Date, J. "Design of experiments via Taguchi methods: orthogonal arrays", The Michigan Chemical Process Dynamic and Controls Open Text Book, USA, 2(3), p. 4 (2006).
Scientia Iranica
Volume 28, Issue 6 - Serial Number 6
Transactions on Industrial Engineering (E)
November and December 2021
Pages 3692-3718

Files

History

  • Receive Date: 27 July 2019
  • Revise Date: 13 November 2019
  • Accept Date: 03 March 2020

Share

How to cite

Statistics