A multi-objective home healthcare delivery model and its solution using a branch-and-price algorithm and a two-stage meta-heuristic algorithm

The application of optimization techniques to home care service planning has received increasing attention, as more patients are in need of dedicated care. Currently, the problem of scheduling home care services is not performed in an optimal way taking into account the complexities of the problem in an integrated way and thus there is substantial room for improvement as the scale of the industry increases. We address the home care planning problem by formulating a mixed integer programming model that simultaneously considers the assignment of nurses to patients, the scheduling of nurses’ workdays and the routing of nurses between patients. The problem is formulated as a multi-objective problem that aims to minimize healthcare-associated service and routing costs while maximizing compatibility of nurses and patients. Two approaches are developed to solve the problem, namely a branch-and-price algorithm as well as a two-stage meta-heuristic. We evaluate the performance of each solution approach, and also assess the value of integrating the assignment, scheduling and routing decisions versus solving these problems sequentially. Computational studies demonstrate that our multi-objective model can bring about savings in healthcare costs and improve the compatibility between nurses and patients. These studies also demonstrate that solutions with increased compatibility do not necessarily come at a price of increased healthcare costs. Furthermore, we show that the two approaches we develop are superior to solving the mixed integer programming model using a conventional solver.