基于分支定价算法的多时间窗家庭医护人员调度问题研究

Home Health Care Scheduling with Multiple Time Windows Based on Branch and Price Algorithm

为了减少医护人员调度成本,提高客户满意度,研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗,并对不同时间窗具有不同偏好的特性,建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解,并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试,将所提出的算法与CPLEX对比,验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现,客户提供多个可接受服务的时间窗能有效降低调度成本。

In order to reduce the scheduling cost of health care workers and improve customer satisfaction,the home health care scheduling problem is studied.Considering multiple time windows of customers'acceptable service and different preferences for different time windows,a mathematical model is established with the objective of minimizing total operating cost and maximizing the satisfaction degree.Based on the Dantzig-Wolfe decomposition principle,the model is reconstructed into a set partitioning master problem and a shortest path subproblem with multiple time Windows.The problem is solved by branch and price algorithm,where the column generation is embedded into a branch-and-bound framework.According to the characteristics of problems with multiple time windows,a random greedy algorithm to quickly obtain the initial solution and an improved label-setting algorithm to solve the subproblem are designed.The effectiveness of the proposed algorithm is verified by comparing with CPLEX through 50 testing numerical examples.Finally,by comparing the results with single time window and multiple time window examples,it is found that the scheduling cost can be effectively reduced when customers provide multiple acceptable service time windows.