Home health care scheduling and routing problem: Mathematical models and meta-heuristics algorithms

The COVID-19 pandemic, which affects the world, has created many problems in every sector, especially in the health sector. Regardless of their level of development, all countries have searched for safe, sustainable, and viable solutions for their citizens with chronic diseases or diseases that require care, as well as trying to reduce the effects of the epidemic. Home health care (HHC), a service that can meet this emerging need, can be defined as a health service that allows people to be visited at home by healthcare personnel for non-emergency health problems. There are two important parties in the HHC, the healthcare personnel providing this service and the patients requesting the service. Especially in social states like Turkey, the majority of the financial burden of health services is covered by the state. For this reason, efficient planning of services and delivery to patients without any issues is an important problem that needs to grant satisfaction of both parties. In Turkey, the increasing demand and legal regulations for HHC has created a need to develop new approaches for the problems that arise during the planning of the service, as it is delivered by many hospitals. In the system under consideration, the services provided by the hospital, the need to visit the same patient more than once during the day, and determining the routes to provide these services with limited resources required the problem to be considered as a special case of the Multi-Trip Vehicle Routing Problem (MT-VRP) in the literature. This thesis is the first study that aims to find a solution to the routing problem by defining the HHC system in Turkey in this context. To understand the real-life system and work with real-life data, the HHC unit of Gölbaşı State Hospital in Ankara is chosen as the pilot hospital. The constraints, assumptions, and objective function of the model developed for the HHCRSP have been determined specifically for the HHC system in Turkey and the operation in the pilot hospital. In this thesis, four different, unique mathematical models were developed according to the number of serving teams being single or multiple and the node/edge based definition of the auxiliary decision variables in the proposed model. In addition, the model performances are analyzed with test problems produced according to the information received from the pilot hospital. For solving large-scale test problems where mathematical models are unable to provide solutions in practical time, four meta-heuristic algorithms are developed within the scope of the thesis. The first algorithm is based on Local Search (LS) and the second algorithm is based on simulated annealing (B-SA). In the third algorithm, the initial solution is generated according to the Greedy Randomized Adaptive Search Procedure (GRASP) and the algorithm is named GRASP-SA. The last algorithm was coded as GRASP-SA-heating. Algorithm performances are compared with statistical analysis according to the determined performance criteria. According to the numerical analysis results, it is seen that mathematical models can only find solutions for small-sized test problems, and suitable solutions are obtained in reasonable time with the proposed meta-heuristic algorithms for test problems with 40 or more patients. Among the meta-heuristic algorithms, the GRASP-SA algorithm showed better performance in terms of solution quality. The LS algorithm, on the other hand, performed better in terms of solution time. The aim of the proposed models is to provide quality service to patients by using hospital resources efficiently in addition to provide a systematic and scientific method to seek solutions for the HHC planning problem.