Evde bakım hizmetleri için önceliklendirilmiş rotalama ve çizelgeleme: Statik ve dinamik eniyileme

Home healthcare services provide medical assistance to people at their residences. There are many companies worldwide that provide this type of service with a dedicated crew of health professionals. In the problem that motivated our research, nurses check upon the conditions of patients using nutritional products. Each nurse has a set of skills and a set of patients assigned to her. Home healthcare services require solving an optimization problem to decide the set of patients to serve each day of a planning horizon and the sequence in which patients are going to be visited during their requested time windows. In the first part of the thesis, we study a deterministic and static problem. Due to a large number of patients and their varying conditions, a nurse must 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 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. We provide insights by quantifying the trade-offs two objectives on the real data set complemented with various realistic parameters. In the second part of the thesis, we study an extension of the home healthcare scheduling and routing problem where urgent patient visit requests emerge during a day, while an optimized plan is implemented. We define a dynamic optimization framework to increase the effectiveness and efficiency of the visits during the entire planning horizon. At the beginning of the planning horizon, our ALNS algorithm runs to determine which patients to visit on each day of a multi-period planning horizon and in which order to visit them to maximize the total priority of visited patients and to minimize the total routing time. Then, on each day some emergent patients with urgent conditions arrive dynamically. The emergencies are accumulated until predetermined re-optimization times. When a re-optimization time comes, the current plan is re-optimized with the accumulated new arrivals in addition to the remaining existing ones by a multi-period static mixed-integer programming (MIP) model. Solutions generated with respect to different processing rules for handling the new arrivals are evaluated with respect to several performance measures, including the waiting time of urgent patients and the number of patients whose visit times are delayed. Extensive computational tests are performed on real data sets via simulation studies.