A Hybrid Heuristic-Exact Optimization for Large-Scale Home Health Care Problem

During the COVID-19 pandemic, numerous people experiencing illness or senescence choose to receive home health care (HHC) services. However, a rapid increase in patients makes it a challenge to reasonably allocate nurses to provide HHC services under the condition of a paucity of nurse resources and patient time window constraints. To solve the large-scale HHC problem, a hybrid heuristic-exact optimization algorithm is proposed with three novel contributions. First, a framework of hybrid heuristic-exact optimization is designed to solve the large-scale problem where a reasonable solution is difficult to obtain under constraints. Second, a multi-objective mixed-integer linear programming modelization is formulated to get a more diverse nurse assignment. Finally, an improved branch and bound algorithm is proposed to speed up computation for the large-scale problem. Computational results on different HHC instances from 25 to 1000 patients demonstrate that the proposed algorithm can optimize the HHC problem with more than 100 patients and can provide various assignments for different numbers of nurses, which the common algorithm cannot optimize.