Prioritized single nurse routing and scheduling for home healthcare services

Çınar, Ahmet and Salman, F. Sibel and Bozkaya, Burçin (2021) Prioritized single nurse routing and scheduling for home healthcare services. European Journal of Operational Research, 289 (3). pp. 867-878. ISSN 0377-2217 (Print) 1872-6860 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


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.
Item Type: Article
Uncontrolled Keywords: Adaptive large neighborhood search; Home healthcare; Lagrangean relaxation; Matheuristic; OR in health services; Prioritized patients
Divisions: Sabancı Business School > Operations Management and Information Systems
Sabancı Business School
Depositing User: Burçin Bozkaya
Date Deposited: 16 Aug 2022 20:25
Last Modified: 16 Aug 2022 20:25

Available Versions of this Item

Actions (login required)

View Item
View Item