Algorithms For Resource Scheduling In Home Health Care

With the increasing aging of population in China,the demand of the elderly for home health care services continues to increase.Home health care routing and scheduling is one of the challenge problems in home health care services.However,few existing works pay attention to the factors such as whether the service needs of the elderly are met,whether the service is timely,and whether the elderly are satisfied with the service,but ignore the budget and preference of elderly in choosing caregivers.Therefore,considering the above factors comprehensively,how to propose an effective home health care resource scheduling algorithm is of great significance for reducing the operating cost of home nursing institutions and improving the quality of home health care services for the elderly with limited mobility.Aiming at the above factors,this paper establishes a home health care routing and scheduling model,and proposes a home health care routing and scheduling with cost optimization problem and a home health care routing and scheduling with service quality optimization problem.For the first problem,this paper considers the constraints such as service price,service time and service skills,how to arrange feasible routes for caregivers,so as to minimize the total operating cost of home health care organizations;This paper proposes the second problem by introducing the constraint of the selection of the elderly on caregivers,so as to maximize the service quality provided by home health care organizations for the elderly.Moreover,this paper provides the proof for its NP-hardness by reducing the problem to the multi-depot vehicle routing problem.This paper proposes a greedy algorithm with service time priority,a customized genetic algorithm and a customized tabu search algorithm to solve the above two optimization problems,respectively.The greedy algorithm strategy proposed in this paper is to minimize the operating cost（maximize the service quality）by assigning the caregiver with the minimum operating cost（maximum service quality）to the elderly with the earliest time of starting service.To fit in the multi-period property,customized genetic algorithm is customized to optimize the initial solution.In addition,for the cost optimization problem,this paper customizes the neighborhood generation rules and tabu list of the customized tabu search algorithm,and optimizes the results obtained by the greedy algorithm.Through theoretical analysis,the greedy algorithm with service time priority is computationally efficient.In this paper,the three proposed algorithms are compared with baseline algorithm and random algorithm respectively by experimenting with three groups of examples of different sizes on the opensource dataset.Experimental results show that the proposed greedy algorithm with service time priority,customized genetic algorithm and customized tabu search algorithm are far superior to the baseline algorithm and random algorithm in terms of effect.Compared with the baseline algorithm,greedy algorithm with service time priority,customized genetic algorithm and customized tabu search algorithm are reduced by 45.8%,53.0% and 57.7% in operating cost of home health care organizations,respectively.In terms of service quality of home health care organizations,the greedy algorithm with service time priority and the customized genetic algorithm improved 31.7% and 65.7% respectively compared with the baseline algorithm,and 65.7% and 126.3% respectively compared with the random algorithm.