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

Document Type : Article


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


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.


1. Tarricone, R. and Tsouros, A.D., Home Care in
Europe: the Solid Facts, WHO Regional Oce Europe
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 constraints", 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
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).
Z. Entezari and M. Mahootchi/Scientia Iranica, Transactions E: Industrial Engineering 28 (2021) 3692{3718 3717
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
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 sta  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
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. Fri ta, 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 e ective genetic
algorithm for the 
eet 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 Arti cial
Systems: an Introductory Analysis with Applications
to Biology, Control, and Arti cial 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).
3718 Z. Entezari and M. Mahootchi/Scientia Iranica, Transactions E: Industrial Engineering 28 (2021) 3692{3718
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).