We 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 objective of this Nurse Routing Problem (NRP) is to maximize the overall daily benefit for the patients to receive the required services, while satisfying the scarce resources available to provide the assistance (number of nurses, time, and so on).

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 non-independent people (elderly people and disabled individuals) highly improving the quality of their life.

We further complicate the problem by considering some realistic constraints imposed by the provider or by the patients, such as workload restrictions, service priorities, and potential incompatibilities among pairs of services for a single patient in the same day.

We cast this setting as a variant of the multi-vehicle traveling purchaser problem (MVTPP) and model it through mathematical programming techniques. After evaluating several different solution strategies, finally we focus on a branch-and-price exact solution approach based on a set-covering reformulation of the problem.

Computational experiments on a considerable set of benchmark instances (adapted from other application contexts to our nursing home service problem) are in progress. Preliminary results seem promising in proving our branch-and-price efficiency.