Efficient Algorithms for Caregiver Routing and Scheduling in Home Health Care Services

Caregiver routing and scheduling is one of the challenge problems in home health care services. Efficient approaches can not only reduce the operating cost but also increase the service efficiency of caregivers. The budget of patients is a critical factor for the patients to make feasible choices among different services, especially for patients with the limited budget. However, few existing works pay attention to the budget of patients. To fill this gap, we initially formulate a novel problem for caregiver routing and scheduling in home health care services by introducing a constraint based on the budget of patients. The objective of the problem is to minimize the total cost of home health care organizations. We provide the proof for its NP-hardness, followed by an approximation algorithm (APA) for the formulated problem. The strategy of the proposed algorithm directly aims to reduce the total cost of home health care organizations, by assigning the caregiver with the minimum total cost to the patient with early time for starting service. Then, we propose two heuristic algorithms, a genetic algorithm (GA) and a tabu search algorithm (TS). Simulation results show that, the proposed algorithms outperform the existing work for various cases, on the same datasets and configuration of the state-of-art work. The total cost of home health care organizations can be reduced by 45.75%, 53.01% and 57.74% on average, by APA, GA and TS, respectively.