Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements. Issue 2 (17th January 2017)

• Record Type: Journal Article
• Authors: Liu, Ran; Yuan, Biao; Jiang, Zhibin
• Is Part Of: International journal of production research. Volume 55:Issue 2(2017)
• Page Start: 558
• Page End: 575
• Publication Date: 2017-01-17
• Subjects: healthcare logistics -- scheduling -- transportation -- lunch break -- branch-and-price; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2016.1213917
• Languages: English
• ISSNs: 0020-7543

Abstract

Abstract : 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.