A Kernel Search for a Patient Satisfaction-oriented Nurse Routing Problem with Time-Windows

We study a variant of the Nurse Routing Problem where each patient may require more than one service at possible different times during the day. Each executed service yields a profit, and an additional reward is gained if all services associated with a patient are fulfilled. The problem looks for nurse routes, each one not exceeding a predefined working time limit, that maximize the global collected service profits plus the patient rewards, while respecting the time windows associated with services. We first provide a compact Mixed-Integer Linear Programming formulation for the problem. Then, we develop an Iterative Kernel Search to solve the problem heuristically. Finally, we compare the heuristic performance on several instances with that of the plain model solved through a state-of-the-art exact solver and strengthened by the separation of valid inequalities. The obtained results clearly show that our heuristic algorithm finds fairly good solutions in terms of quality, despite the use of shorter computational times.