Multi-objective dynamic prioritized routing and scheduling for home healthcare services with cooperating service providers

Abstract

In home healthcare service systems, each healthcare service provider (HSP) is assigned a list of patients to be visited at their homes. We focus on generating a daily patient visit plan that selects the patients to be visited according to their priorities and locations, and determines the route of each HSP. Additionally, we address unexpected urgent patients by solving an optimization problem involving all HSPs cooperating when an urgent patient visit request arises. This problem is formulated with multiple objectives in a lexicographic optimization framework. Two approaches have been implemented: a mixed integer programming model solved within a time limit (TL-MIP) and a Greedy Randomized Adaptive Search Procedure followed by Variable Neighborhood Search (GRASP+VNS). These approaches are compared in a case study that considers serving patients, with several performance metrics analyzed through extensive simulation experiments. The results indicate that the heuristic approach (GRASP+VNS) significantly reduces run times (by approximately 85% on the average overall instances) compared to the TL-MIP approach, while providing solutions that are not far from the TL-MIP approach in terms of the total priority of visited patients, the heuristic deviates at most 2% over different types of instances. Centralized planning with cooperation among two or three service providers reduced the total travel time by 30% and 45%, respectively, and decreased the number of postponed visits by 50% compared to the non-cooperation model.