The Nurse Routing Problem with Workload Constraints and Incompatible Services

Among the health care applications, nursing home services play a central role because of the growing request for long-term home care observed in the recent years. Nursing care providers can guarantee a wide variety of medical and supporting services for not-independent people such as elderly people and disabled itidividuals, highly improving the quality of their life. We propose and study an optimization problem that aims at scheduling the daily services performed by a set of nurses to a set of patients and, simultaneously; at routing the nurses in their visiting tours. The problem is further complicated by considering potential incompatibilities among pairs of services for a single patient in the same day. Through mathemaatical programming techniques, we model the problem as a variant of the multi vehicle traveling purchaser problem (MVTPP) and evaluate different solution strategies. Finally, we focus' on the applicability of a promising branch-and-price solution approach based on a set-covering reformulation of the problem.