Abstract: The study focuses on the scheduling issue of home healthcare workers, incorporating constraints related to mixed time windows and medical supplies into the model. A branch-and-price algorithm is designed for solving the problem, with the branch process and labeling algorithm are improved within the algorithm. In the numerical experiments, the proposed branch-and-price algorithm is compared with the Adaptive Large Neighborhood Search (ALNS) algorithm and CPLEX in terms of performance. The branch-and-price algorithm finds optimal solutions in over 80% of the cases, whereas CPLEX achieves this in less than 20% of the cases. Moreover, in large-scale instances, the branch-and-price algorithm show an improvement of over 15% compared with ALNS algorithm. Sensitivity analysis is conducted on key parameters in the model. Experimental results indicate that different parameters for patient-caregiver matching and penalties for time window violations both impact operational costs; mixed time windows are more efficient than soft and hard time windows, with the total cost under mixed time windows being about 2% lower than that under hard time windows, while also avoiding extreme scenarios; the constraint of carrying medical supplies can affect the total cost by up to 40%, making it a necessary consideration for this constraint in the model.

Key words: home healthcare, synchronized service, mixed time window, medical supplies, branch and price