Dynamic routing and scheduling for home healthcare services with cooperating multiple service providers

The importance of home healthcare services has been increasing globally with aging population and the rise of remote activities in our lives. In this thesis, we focus on a daily routing and scheduling problem for home healthcare services considering patient priorities defined according to their health conditions and the dynamic emergence of urgent patient visit requests during the day which is handled by the cooperation of multiple service providers. We optimize multiple objectives in a lexicographic goal programming (LGP) framework. The LGP approach is used for both the static and dynamic problems. The solution to the static problem identifies an initial schedule and a routing plan for each healthcare service provider (HSP) separately. On the other hand, the dynamic problem optimizes the schedules and routes of all HSPs and schedules dynamic emergent patients in addition to the patients scheduled in the initial plan. By means of the dynamic problem, the routing and scheduling plans of the HSPs are re-optimized simultaneously each time an emergent patient arrives. For both problems, a mixed integer linear programming (MILP) model and a greedy randomized adaptive search procedure (GRASP), followed by a variable neighborhood search (VNS) procedure for local improvement, are developed together with a hybrid approach that utilizes both the MILP model and the proposed heuristic. The three approaches are tested through a case study that considers COVID-19 patients in a district of Istanbul. In order to show the effectiveness of cooperation and compare the proposed solution methods, several performance metrics are analyzed through extensive simulation runs. We observe that i) our proposed heuristic approach provides solutions with quality close to or better than those obtained by the MILP run within a time limit, while running in short times, and ii) the cooperation strategy improves system performance significantly in a dynamic setting.