Prioritized single nurse routing and scheduling for home healthcare services

Abstract

We study a real-life problem in which a nurse is required to check upon patients she is responsible for either by home visits or phone calls. Due to the large number of patients and their varying conditions, she has to select carefully which patients to visit at home for the upcoming days. We propose assigning priorities to patients according to factors such as the last visit time and the severity of their condition so that the priorities of unvisited patients increase exponentially by day. The solution to this problem should simultaneously specify which patients to visit on each day of the planning horizon, as well as the sequence of the visits to the selected patients on each day that obeys patients' time window requests. The objective is to maximize the total priority of the visited patients primarily and to minimize the total traveling time secondarily. After having observed the computational limits of an exact formulation, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm and a matheuristic to generate near optimal solutions for realistic-sized instances. We measure the quality of both algorithms by computing the optimality gaps using upper bounds generated by Lagrangean relaxation. Tests on real-life data show that both algorithms yield high quality solutions, but the matheuristic outperforms ALNS in large instances. On the other hand, the ALNS algorithm provides very short running times, while the running times of the matheuristic increase exponentially with problem size. (C) 2019 Elsevier B.V. All rights reserved.