Homecare staff scheduling problem using a GA based approach with local search techniques

Home health care service (HHC) provides daily medical services in patients’ homes. The service aims to satisfy the patients’ requirements, which must be done by one or more qualified staff visiting them within the right time and minimising operational cost. The homecare staff-scheduling problem (HSSP) is an extension of the HHC problem involving planning routes for caregivers visiting n patients. This paper proposes the route scheduling system based on a genetic algorithm approach for solving the HSSP. The focus is to introduce the novel techniques consisting of adaptive-opt (OPT), external k-nearest neighbour swapping (EKN), and internal nearest neighbour search (INN) to incorporate with the GA while also increasing the performance for solving the HSSP. In addition, the trade-off ratio between the percentage of improvement and the execution time is also concerned. The ratio provides the most suitable structure of the proposed GA that can continue to consider other issues for HHC service such as the dynamic scheduling that requires execution speed for recalculating the service plan when some service activities are cancelled immediately. Our empirical study reveals that the proposed techniques can produce improved solutions on two simulated datasets and an adapted case study instance compared to the original GA.