Daily scheduling of caregivers with stochastic times. Issue 9 (3rd May 2018)

• Record Type: Journal Article
• Authors: Yuan, Biao; Liu, Ran; Jiang, Zhibin
• Is Part Of: International journal of production research. Volume 56:Issue 9(2018)
• Page Start: 3245
• Page End: 3261
• Publication Date: 2018-05-03
• Subjects: health care logistics -- routing -- scheduling -- stochastic times -- branch-and-price; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2018.1445879
• Languages: English
• ISSNs: 0020-7543

Abstract

Abstract : This paper addresses a daily caregiver scheduling and routing problem arising in home health care or home care service providers. The problem is quite challenging due to its uncertainties in terms of travel and service times derived from changes in road traffic conditions and customer health status in practice. We first model the problem as a stochastic programme with recourse, where the recourse action is to skip customers without services if the caregiver arrives later than their latest starting service time (i.e. hard time window requirements). Then, we formulate the problem as a set partitioning model and solve it with a branch-and-price (B&P) algorithm. Specifically, we devise an effective discrete approximation method to calculate the arrival time distribution of caregivers, incorporate it into a problem-specific label algorithm, and use a removal-and-insertion-based heuristic and the decremental state-space relaxation technique to accelerate the pricing process. Finally, we conduct numerical experiments on randomly generated instances to validate the effectiveness of the discrete approximation method and the proposed B&P algorithm.