Long-term home care scheduling

In several countries, home care is provided for certain citizens living at home. The long-term home care scheduling problem is to generate work plans spanning several days such that a high quality of service is maintained and the overall cost is kept as low as possible. A solution to the problem provides detailed information on visits and visit times for each employee on each of the covered days. We propose a branch-and-price algorithm for the long-term home care scheduling problem. The pricing problem generates one-day plans for an employee, and the master problem merges the plans with respect to regularity constraints. The method solves instances with up to 99 visits during one week. This truly illustrates the complexity of the problem.