Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements

Home health care or home care (HHC/HC) refers to the delivery of social, medical and paramedical services to clients in their own homes. Each day, care workers start from the HHC/HC centre, visit some clients and return to the centre. During the service delivery process, there is usually a lunch break for each worker. In this paper, we address a real-life home care worker scheduling and routing problem with the consideration of lunch break requirements. A three-index mathematical model is constructed for the problem. The problem is decomposed into a master problem and several pricing sub-problems, and is optimally solved by a branch-and-price (B&P) algorithm. Specifically, a sophisticated label-correcting algorithm is designed to address lunch break constraints in pricing sub-problems; some cutting-edge acceleration strategies are applied during the column generation process. Experimental results show that the proposed B&P algorithm is able to produce satisfied solutions within an acceptable runtime and outperforms the mixed integer programming solver CPLEX.