A Heuristic Logic-Based Benders Method for the Home Health Care Problem

We propose a heuristic adaptation of logic-based Benders decomposition to the home health care problem. The objective is design routes and schedules for health care workers who visit patient homes, so as to minimize cost while meeting all patient needs and work requirements. We solve the Benders master problem by a greedy heuristic that is enhanced by the propagation facilities of constraint programming (CP). We solve the subproblems entirely by CP and generate logic-based Benders cuts that exploit problem structure. Many of the subproblem constraints are included in the master problem to compensate for the difficulty of designing strong Benders cuts, but they serve as guidance for the heuristic rather than constraints to be satisfied. We also experiment with local search in the master problem to hasten the discovery of a feasible solution. We report preliminary computational results for realistic problem instances.