Addressing consistency and demand uncertainty in the Home Care planning problem

Abstract

Optimizing Home Care Services is receiving a great attention in Operations Research. We address arrival time consistency, person-oriented consistency and demand uncertainty in Home Care, while jointly optimizing assignment, scheduling and routing decisions over a multiple-day time horizon. Consistent time schedules are very much appreciated by patients who, in this setting, are very sensitive to changes in their daily routines. Also person-oriented consistency positively impacts on service quality, guaranteeing that almost the same set of caregivers take care of a patient in the planning horizon. Demand uncertainty plays a pivotal role, too, since both the set of patients under treatment and their care plan can change over time. To the best of our knowledge, this is the first paper dealing with all these aspects in Home Care via a robust approach. We present a mathematical model to the problem, and a pattern-based algorithmic framework to solve it. The framework is derived from the model via decomposition, i.e. suitably fixing the scheduling decisions through the concept of pattern. We propose alternative policies to generate patterns, taking into account consistency and demand uncertainty; when embedding them in the general framework, alternative pattern based algorithms originate. The results of a rich computational experience show that introducing consistency and demand uncertainty in pattern generation policies is crucial to efficiently compute very good quality solutions, in terms of robustness and balancing of the caregiver workload. In addition, a comparison with a simpler model, where no kind of consistency is imposed, shows the importance of considering consistency in pursuing a valuable patient-centered perspective, with a positive effect also on the efficiency of the solution approach.

Fig. 1

The layered graph $G_W$ for $|W|=5$, $|K|=2$, $|T|=2$, and a pattern example in dashed line

Fig. 2

Realizations of uncertain visits: 60 patients - consistency-unaware

Fig. 3

Operator utilization factor: 60 patients - consistency-unaware

Fig. 4

Optimality gap: 60 patients - consistency-unaware

Fig. 5

Realizations of uncertain visits: 60 patients - consistency-aware

Fig. 6

Operator utilization factor: 60 patients—consistency-aware

Fig. 7

Optimality gap: 60 patients—consistency-aware

Fig. 8

Consistency vs not consistency in pattern generation for 60 patients: impact on the number of possible realizations

Fig. 9

Realizations of uncertain visits: 100 patients, 20% uncertain visits—consistency-aware

Fig. 10

Operator utilization factor: 100 patients, 20% uncertain visits—consistency-aware

Fig. 11

Optimality gap: 100 patients, 20% uncertain visits - consistency-aware

Fig. 12

Effects of extending time and memory limits on efficiency

Fig. 13

Realizations of uncertain visits: 100 patients, 30% uncertain visits - consistency-aware

Fig. 14

Operator utilization factor: 100 patients, 30% uncertain visits - consistency-aware

Fig. 15

Optimality gap: 100 patients, 30% uncertain visits—consistency-aware

Fig. 16

Realizations of uncertain visits: average results—consistency-aware

Fig. 17

Operator utilization factor: average results—consistency-aware

Fig. 18

Optimality gap: average results—consistency-aware