An exact solution method for home health care scheduling with synchronized services
研究了多技能护理人员为患者提供同步服务的家庭医疗调度问题，提出分支定价切割算法，在标准测试和实际案例中多数能快速找到最优解，并分析了关键参数的管理启示。
Abstract We study the home health care scheduling problem that considers the synchronized services of multiskilled caregivers necessitated by the simultaneous service requirements of patients. A characteristic feature of the problem is that there is a threshold on the maximum difference between the start times of the pairwise synchronized services at a patient, which enables flexible imposition of various synchronization constraints. We first derive some structural properties of the problem, based on which we provide a set‐partitioning formulation of the problem and devise a branch‐and‐price‐and‐cut solution algorithm. We develop a column generation scheme to obtain lower bounds for the problem, in which we design a labeling algorithm together with some enhancement strategies to address the pricing subproblems, and use the 2‐path inequalities and limited‐node‐memory subset row inequalities to strengthen the lower bounds. To test the algorithm, we apply it to solve the instances generated according to the well‐known Solomon's benchmark data set and real‐world instances. The results demonstrate that the algorithm can find the optimal solutions in most situations within reasonable computational times, confirming its efficacy. Finally, we perform sensitivity analysis of the optimal solution to some key model parameters and discuss the management implications of the results.