×

New decomposition methods for home care scheduling with predefined visits. (English) Zbl 1458.90298

Summary: The continuous aging of the population and the desire of the elderly to stay in their own homes as long as possible has led to a considerable increase in the demand for home visits. In this context, home care agencies try to serve more patients while maintaining a high level of service. They must regularly decide which patients they can accept and how the patients will be scheduled (care provider, visit days, visit times). In this paper, we aim to maximize the number of new patients accepted while ensuring a single provider-to-patient assignment and a consistency of the visits times for every patient through the week. To solve this problem, we propose an extension to an existing logic-based Benders decomposition. Moreover, we present a new pattern-based logic-based Benders decomposition and a matheuristic using a large neighborhood search. The experiments demonstrate the efficiency of the proposed approaches and show that the matheuristic can solve all the benchmark instances in less than 20 s.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

PARPAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Begur, S. V.; Miller, D. M.; Weaver, J. R., An integrated spatial dss for scheduling and routing home-health-care nurses, Interfaces, 27, 4, 35-48 (1997)
[2] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[3] Bertels, S.; Fahle, T., A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem, Comput Oper Res, 33, 10, 2866-2890 (2006) · Zbl 1086.90533
[4] Borsani, V.; Matta, A.; Beschi, G.; Sommaruga, F., A home care scheduling model for human resources, ICSSSM 2006, 1, 449-454 (2006)
[5] Braekers, K.; Hartl, R. F.; Parragh, S. N.; Tricoire, F., A bi-objective home care scheduling problem: analyzing the trade-off between costs and client inconvenience, Eur J Oper Res, 248, 2, 428-443 (2016) · Zbl 1346.90207
[6] Cheng, E.; Rich, J. L., A home health care routing and scheduling problem, Working paper, NA, NA (1998)
[7] Cissé, M.; Yalçındağ, S.; Kergosien, Y.; Şahin, E.; Lenté, C.; Matta, A., Or problems related to home health care: a review of relevant routing and scheduling problems, Oper Res Health Care, 13, 1-22 (2017)
[8] Decerle, J.; Grunder, O.; El Hassani, A. H.; Barakat, O., A memetic algorithm for a home health care routing and scheduling problem, Oper Res Health Care, 16, 59-71 (2018)
[9] Di Gaspero, L.; Urli, T., A CP/LNS approach for multi-day homecare scheduling problems, International Workshop on Hybrid Metaheuristics, 1, 1-15 (2014)
[10] Fikar, C.; Hirsch, P., Home health care routing and scheduling: a review, Comput. Oper. Res., 77, 86-95 (2017) · Zbl 1391.90261
[11] Frifita, S.; Masmoudi, M.; Euchi, J., General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits, Electron. Notes Discrete Math., 58, 63-70 (2017) · Zbl 1387.90086
[12] Gamst, M.; Jensen, T. S., A branch-and-price algorithm for the long-term home care scheduling problem, Oper. Res. Proc. 2011, 1, 483-488 (2012) · Zbl 1306.90050
[13] Grangier, P.; Gendreau, M.; Lehuédé, F.; Rousseau, L.-M., A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking, Comput. Oper. Res., 84, 116-126 (2017) · Zbl 1391.90061
[14] Grenouilleau, F.; Legrain, A.; Lahrichi, N.; Rousseau, L.-M., A set partitioning heuristic for the home health care routing and scheduling problem, Eur J Oper Res, 275, 1, 295-303 (2019) · Zbl 1430.90264
[15] Heching, A.; Hooker, J. N.; Kimura, R., A logic-based benders approach to home healthcare delivery, Transp. Sci., 53, 2, 510-522 (2019)
[16] Hooker, J. N.; Ottosson, G., Logic-based benders decomposition, Math Program, 96, 1, 33-60 (2003) · Zbl 1023.90082
[17] Lin, C.-C.; Hung, L.-P.; Liu, W.-Y.; Tsai, M.-C., Jointly rostering, routing, and rerostering for home health care services: a harmony search approach with genetic, saturation, inheritance, and immigrant schemes, Comput. Ind. Eng., 115, 151-166 (2018)
[18] Macintyre, C. R.; Ruth, D.; Ansari, Z., Hospital in the home is cost saving for appropriately selected patients: a comparison with in-hospital care, Int. J. Qual. Health Care, 14, 4, 285-293 (2002)
[19] Rest, K.-D.; Hirsch, P., Daily scheduling of home health care services using time-dependent public transport, Flexible Serv. Manuf. J., 28, 3, 495-525 (2016)
[20] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci., 40, 4, 455-472 (2006)
[21] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, J Comput Phys, 159, 2, 139-171 (2000) · Zbl 0997.90105
[22] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, International conference on principles and practice of constraint programming, 417-431 (1998), Springer
[23] Sinha, M.; Bleakney, A., Receiving Care at Home (2014), Statistics Canada
[24] Torres-Ramos, A.; Alfonso-Lizarazo, E.; Reyes-Rubiano, L.; Quintero-Araújo, C., Mathematical model for the home health care routing and scheduling problem with multiple treatments and time windows, Proceedings of the 1st International Conference on Mathematical Methods & Computational Techniques in Science & Engineering, 1, 140-145 (2014)
[25] Trautsamwieser, A.; Hirsch, P., A branch-price-and-cut approach for solving the medium-term home health care planning problem, Networks, 64, 3, 143-159 (2014)
[26] Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A. L.; Velasco, N., A matheuristic for the truck and trailer routing problem, Eur J Oper Res, 230, 2, 231-244 (2013) · Zbl 1317.90057
[27] Yalçındağ, S.; Cappanera, P.; Scutellà, M. G.; Şahin, E.; Matta, A., Pattern-based decompositions for human resource planning in home health care services, Comput. Oper. Res., 73, 12-26 (2016) · Zbl 1349.90897
[28] Zhang, T.; Yang, X.; Chen, Q.; Bai, L.; Chen, W., Modified ACO for home health care scheduling and routing problem in chinese communities, Networking, Sensing and Control (ICNSC), 2018 IEEE 15th International Conference on, 15, 1-6 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.