关键词: 家庭医疗护理人员调度, 速度时变, 双目标优化, NSGA-II算法, 自适应选择机制

Abstract:

In recent years， due to the global aging population， home health care （HHC） has received increasing attention. Over the years， operations research tools have contributed significantly to reduce the operational cost and improve the service quality of HHC services. Moreover， the problem of urban traffic congestion caused by the increase of car ownership in China is becoming increasingly serious， so it is interesting to consider the time-varying speed in HHC issues.Based on this observation， it aims to investigate the Home Health Care crew scheduling problem that simultaneously considers the patient's preference for the level of qualification of caregivers and the time-varying speed. In such a problem， there is a set of caregivers at the HHC to perform the service for a set of patients. Each caregiver has a specific qualification level to represent their ability to perform the service for patients. Each patient requires a service time and a caregiver with qualification level to perform the service， and has a service time window \left[E{t}_i,e{t}_i,L{t}_i\right] defining the time range for caregivers to start services at patient i. When caregivers arrive at patient i’s location earlier than E{t}_i， they need to wait until E{t}_i， and the start service time later than L{t}_i is not allowed. When the start service time falls within \left[e{t}_i,L{t}_i\right]， there is no penalty cost for early service. However， when the start service time falls within \left[E{t}_i,e{t}_i\right]， there will be a penalty cost proportional to the length of time ahead of e{t}_i. A caregiver with a low qualification level can serve the patients with high qualification levels， but this will incur a level preference penalty cost. Moreover， the travel speed of a caregiver when traversing an arc is related to the time entering the arc. The goal is to determine the assignment of caregivers and patients and the service routes of caregivers so as to minimize simultaneously the total operating cost and the total level preference penalty cost.To solve the problem， an improved non-dominated sorting genetic algorithm based on adaptive selection mechanism is devised. Based on the non-dominated Genetic Algorithm， the developed algorithm employs the non-dominant rank of chromosomes to calculate the corresponding adaptive selection probability， and increases the probability of high-quality chromosomes participating in the crossover to improve the quality of offspring chromosomes. To further improve the algorithm search efficiency， three improved strategies， including hybrid initial solution generation strategy， caregiver-patient matching crossover strategy， and variable neighborhood search strategy are introduced.Extensive numerical studies illustrate the following conclusions　① Time-varying speed has a significant impact on the solution. When the travel speed in peak hours is lower， more caregivers are required for serving the patients， and larger time window violation cost is incurred. ② If the target user group of the HHC center is a high-income group， the qualification level penalty preference decision can be selected to provide patients with their preferred qualification level of medical services， and the high operation cost can be alleviated by increasing the service cost. On the contrary， if the target user group of the HHC center is a low-income group， the operation cost preference decision can be adopted to give priority to the cost factor to provide patients with HHC services at a relatively low price. ③ All the improvement strategies are beneficial to the performance of the developed algorithm and complement each other， and using all the three strategies performs the best.

Key words: home health care crew scheduling, time-varying speed, bi-objective optimization, NSGA-II algorithm, adaptive selection mechanism