Title: Dynamic Routing and Scheduling for Home Healthcare Services with Cooperating Multiple Service Providers

Speaker: Mert Parçaoğlu

Time: August 12, 2022 16:00

Thesis Committee Members:

Prof. Dr. F. Sibel Salman (Advisor, Koç University)

Prof. Dr. Lerzan Örmeci (Koç University)

Prof. Dr. Özgür M. Araz (University of Nebraska-Lincoln)


The importance of home healthcare services has been increasing globally with aging population and the rise of remote activities in our lives. Due to the increasing demand for home healthcare services, an important decision to be taken under limited service capacity is which patients will access the limited service resources. Furthermore, the urgent patients should be given priority and patient visits should be scheduled according to the health conditions of the patients. In this thesis, we focus on a prioritized routing and scheduling problem for home healthcare considering a large number of patients to be cared for, the urgency of their health conditions defined by priorities, and the dynamic emergence of visit requests due to emergencies, under the cooperation of multiple service providers for better utilization of total service capacity by a centralized planning approach.

Each healthcare service provider (HSP) is assigned a patient cluster, and for each of them an initial daily plan to visit patients selected from their assigned cluster at the beginning of the day is created. In this static problem, each HSP is in charge of his patient list for continuity of care purposes.  On the other hand, when the more realistic dynamic case is considered, while the initial plan is being executed for each HSP, dynamically occurring urgent patient requests arrive. The studies in the literature follow an approach where these requests are assigned to the HSP of the related cluster and are included in the plan of the HSP. However, these changes in the initial plan may cause HSPs to postpone patient visits scheduled in the initial plan, change the visit times, and perform overtime. In order to avoid these problems, we propose a joint optimization problem for all HSPs, where HSPs may cooperate and serve patients from another HSP’s list. For this purpose, we formulate a model that re-optimizes all routes according to multiple objectives in a lexicographic goal programming framework.  The objectives are to maximize the total priority of the visited patients, minimize the total arrival time changes in the schedule, minimize the total overtime of the service providers, and minimize the total travel time of the service providers. In addition, we consider time-dependent travel times.

The lexicographic goal programming (LGP) approach is used for both the static and dynamic problems for daily scheduling and routing. The solution to the static problem identifies an initial schedule and a routing plan for each healthcare service provider (HSP) separately. The dynamic problem considers dynamic emergent patients in addition to the patients scheduled in the initial plan and modifies the initial plans created by the static problem solution. By means of the dynamic problem, the routing and scheduling plans of the HSPs are re-optimized simultanously 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 developed 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 different solution methods, several performance metrics are analyzed through extensive computational experiments, where simulation runs with various instance sizes and parameter settings are performed. We summarize the performances of the proposed approaches, namely, MILP and GRASP+VNS for the static problem, the performances of the three approaches, namely, MILP, GRASP+VNS and hybrid, for the dynamic problem. We quantify the benefits from HSPs’ cooperation by a comparison to the model solution that does not allow cooperation. Our major observations from our computational study are that i) our designed GRASP+VNS approach provides solutions with quality close to or better than those obtained by the MILP run within a time limit, runs in short times, for both static and dynamic problems, and ii) the cooperation strategy improves system performance significantly in a dynamic setting.