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

Key words: home health care, multiple time windows, improved the label-setting algorithm, column generation, branch and price