A Mathematical Model for Multi-trip Home Health Care Routing Problem with Time Windows

Abstract

The Home Health Care routing problem (HHCRP) is an extension of the vehicle routing problem (VRP) considering scheduling and routing simultaneously to perform home health care (HHC) services. These services may be examining the patients, preparing a diet plan, applying physical therapy, and picking up the blood samples. In this paper, HHCRP has been addressed for a public hospital in Ankara, Turkey, that provides HHC services with limited resources. There are teams that consist of a doctor, a nurse, a dietitian, a physiotherapist and a vehicle driver. The multiple tours of those teams are searched by considering time windows to meet patient demands on time. This problem is defined as the multi-trip home health care routing problem with time-windows (MT-HHCRP-TW). In this study, a mixed integer linear programming model to minimize the total travelling time is proposed. Test problems that are generated based on real data for computational analysis and results are discussed. Main contribution of this paper is to define a specific HHC system as a multi-trip home health care routing problem with time windows and to propose a mathematical model with polynomial size decision variables and constraints for this problem. © 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.