A Branch-Price-and-Cut approach for solving the medium-term home health care planning problem

The planning of home health care services is still done manually in many industrial countries. However, efficient decision support is necessary to improve the working plans and relieve the nurses from this time consuming task. The problem can be summarized as follows: clients need to be visited one or several times during the week by appropriately skilled nurses; their treatments have predefined time windows. Additionally, working time requirements for the nurses such as breaks, maximum working time per day, and daily as well as weekly rest times have to be considered. We propose a Branch‐Price‐and‐Cut solution approach to solve this problem exactly, using the solutions of a variable neighborhood search solution approach as upper bounds. The algorithm is capable of solving to optimality real‐life based test instances with up to nine nurses, 45 clients, and 203 visits during the week.