Mobile healthcare service routing and scheduling problem: Solution approaches

After the industrial revolution, population migration from village to city, rural poverty and inequities in healthcare access have made it necessary for governments to provide public services everywhere and to change the health policy in order to improve people's wellbeing. It is not possible to build a hospital in every village, especially sparsely populated settlements. On the other hand, governments, must ensure that people have equal access to healthcare services. To tackle this issue, Ministry of Health of Turkey has enforced to give mobile healthcare services (MHS) in rural areas by approximately 7.5 thousand doctors located in approx. 3.4 thousand medical centers. These doctors work 8 hours a day and give MHS to approx. 9 million people each month. This study considers Turkish rural healthcare delivery system as a Multi-depot Time Constrained Periodic Vehicle Routing Problem (md-TCPVRP) and presents a mixed-integer linear programming formulation and heuristic algorithm for the problem. The goal is to determine the doctors' daily routes for each month. Objective is minimizing the total route distance under some constraints, such as maximum workhours, route duration, minimum service time per visit, assigning dedicated doctors to villages. To solve this problem firstly a mathematical model is developed. In order to investigate the performance of the mathematical model and heuristic algorithms computational experiments are carried. Md-TCPVRP, on the other hand, belongs to the class of NP-hard problems. As a result, two hybrid heuristic algorithms based on greedy heuristic algorithm, greedy randomized adaptive search algorithm, and record-to-record travel (RRT) are developed to produce good solutions to medium and large sized problems in reasonable time. These hybrid algorithms are different in terms of creating the initial solution and are named ARAAP_KK and ARAAP(K)-KK. The performance of the developed mathematical model and heuristic algorithms are compared using MHS data from 18 districts in Ankara obtained from the T.C. Ministry of Health. The mathematical model improved the monthly route length in ten districts by an average of 15.6% over the current real life application. ARAAP_KK, which performed the best of the three heuristic algorithms, resulted in a 22.3% improvement in the same 10 districts compared to the current real life application, and a 16.5% improvement in 18 districts of Ankara.