A three-step optimization-based algorithm for home healthcare delivery

This paper examines the problem of providing healthcare services to patients who reside at various aging, rehabilitation and treatment facilities or who are home bound, and who may require multiple visits per week. To meet this goal, a 3-step algorithm is developed that efficiently constructs weekly schedules for individual providers working through an agency. The objective is to balance a set of metrics that include travel distance, productivity points, daily workload, equity, overtime and the need to accommodate breaks. Additional factors include patient time windows, continuity of care, and nurse skill qualifications, all of which are treated as soft constraints. In Step 1 of the algorithm, we divide locations of requested visits into distinct clusters and assign each visit to a provider. Both k-means clustering and a mixed-integer linear programming model are applied iteratively until no local improvement is possible. In Step 2, a modified traveling salesman problem is formulated and solved for each nurse each day to find optimal schedules and routes. In Step 3, a local search heuristic based on swapping and gap adjustments is developed to improve the solution obtained in Step 2 and to add a lunch break to each schedule. The procedure is tested on instances with up to 20 nurses and 440 requested visits per week with data provided by a national home healthcare agency, and comparisons are drawn with the actual schedules used over several months. Statistical tests verify that the proposed approach offers significantly better schedules for both nurses and patients. We conclude with a sensitivity analysis of the demand–supply ratio to determine its effect on solution quality.