A Heuristic Approach for the Home Health Care Scheduling and Routing Problem

Abstract

Abstract

Home Health Care (HHC) is a health care service delivered by sending caregivers such as nurses or personal support workers (PSW) to visit patients in their homes. The assignment of patients to nurses as well as the sequencing of patients for each nurse is called the Home Health Care Scheduling and Routing Problem (HHCSRP). This thesis proposes a heuristic approach to solve HHCSRP to which it is hard and even impossible to obtain an optimal solution for relative larger instances in a reasonable amount of computational time by using an exact algorithm as HHCSRP is NP hard. In the approach, this thesis developed and contributed a heuristic partition method to partition patients into a number of single nurse groups. The computational test result shows that the proposed approach can achieve good solutions which remain within 5% of the commercial solver CPLEX’s best solution using an acceptable solution time on all test instances.