Multi-Objective Dynamic Prioritized Routing and Scheduling for Home Healthcare Services With Cooperating Service Providers
General Description of Research:
Home health services have become a critical component of health care delivery, helping reduce pressure on hospitals. Effective delivery relies on generating optimal schedules and routes for daily patient visits and making the best use of providers’ time. This is a complex, computationally challenging problem that must be solved quickly to be practical.
We developed a dynamic home healthcare routing model that incorporates cooperating service providers, urgent requests and time-dependent travel times. We also designed new algorithms to handle multiple prioritized objectives. Our case study and experiments show that provider cooperation reduces postponed visits and travel time, while our algorithms deliver high-quality solutions within reasonable run times.
Research Abstract:
In home healthcare systems, each healthcare service provider (HSP) is assigned a list of patients to visit in their homes. This research focuses on generating a daily patient-visit plan that selects patients based on priority and location, and determines each HSP’s route. It also addresses unexpected urgent requests by solving an optimization problem in which all HSPs cooperate when an urgent patient visit arises. The problem is modeled with multiple objectives using a lexicographic optimization framework.
Two approaches were developed: a mixed-integer programming model solved within a time limit (TL-MIP) and a Greedy Randomized Adaptive Search Procedure with Variable Neighborhood Search (GRASP+VNS). The approaches were compared in a case study using several performance metrics analyzed through extensive simulation experiments. Results show the heuristic approach (GRASP+VNS) reduced run times by about 85% on average compared with TL-MIP, while producing solutions within 2% of TL-MIP in total priority of visited patients across instance types. Centralized planning with cooperation among two or three service providers reduced total travel time by 30% and 45%, respectively, and cut the number of postponed visits by half compared with the non-cooperation model.