A metaheuristic approach to the assignment, scheduling and routing of care workers in the home and community-based scenario

Abstract

The HIV/AIDS pandemic has reached an unprecedented scale in South Africa. The burden this has placed on the country's already restricted health care resources has lead to a greater emphasis on the value of home-based care. Home-based care is a service model appropriate to a number of contexts from palliative and elderly care to support of orphaned and vulnerable children. Home-based care not only relieves the burden on hospitals and community clinics, but is an affordable alternative to institutional care. In order to recognise home-based care as an equal, rather than an inferior alternative to institutional care, good service delivery is imperative. The numerous restrictions encapsulated by the home-based care problem, such as adhering to time windows and effcient skill and need matching contributes to the complexity of the problem. The wide geographical dispersion of households in South Africa exacerbates this problem. As far as possible the assignment of beneficiaries to care workers should be done in such a way that the travelling time of the care workers will be minimised. Through an extensive literature study, the home-based care problem has been identified as a combination of the Nurse Rostering Problem and the Vehicle Routing Problem with Time Windows. Both of these are optimisation problems that determines the optimal assignment of beneficiaries to care workers and minimise the time spent travelling, while adhering to constraints. A hybrid approach is proposed to address this problem. A conceptual solution algorithm that combines the Variable Neighbourhood Search and Tabu Search metaheuristics is considered in this document. The algorithm will be enhanced by adding a heuristic ordering algorithm which will construct an initial solution. The complete hybrid algorithm was evaluated by applying it to test data from home care visits to orphaned and vulnerable children in Hearbeat's Nellmapius Community Project. The solution algorithm provided sufficient results with care worker schedules not exceeding four hours a day and an equal workload between care workers. The results indicate that the algorithm does have the ability to improve service delivery of home-based care by improved assignment, routing and scheduling of care workers. However, to ensure feasibility of this algorithm, careful implementation and monitoring is imperative.