Weekly home healthcare routing and scheduling with overlapping patient clusters

This paper presents a two-stage approach for efficiently solving a weekly home healthcare scheduling and routing problem. Two new mixed-integer linear programming (MILP) models are proposed, where the first is used for making patient-therapist assignments over the week, and the second for deriving daily routes. In both MILPs, the objective function contains a hierarchically weighted set of goals. The major components of the full problem are continuity of care, downgrading, workload balance, time windows, overtime, and mileage costs. A new preprocessing procedure is developed to limit the service area of each therapist to a single group of overlapping patients. Once the groups are formed, weekly schedules are constructed with the MILPs. The overall objective is to minimize the number of unscheduled visits and total travel and service costs subject to the operational constraints mentioned above. Computational experiments are conducted with real data sets provided by a national home health agency. The results show that optimal solutions can be obtained quickly at both the assignment and routing stages and that they are comparable to the results obtained with a proposed integrated model. In either case, the corresponding schedules were better on all metrics when compared to the schedules used in practice.