关键词: 家庭护理人员调度, 模糊机会约束规划, 变邻域搜索, 集合划分模型

Abstract: In recent years, a continuing decline in the global fertility rate and an increase in life expectancy have made the issue of population ageing more prominent. To meet the demands brought about by the growth of the ageing population, while respecting the traditional will of the older citizens, the home-based elderly care service model is gradually taking over at this stage. As an important form of its function, the home health care aims to provide convenient medical and life care services to the older and disabled citizens through professional home care teams. It has been proven to deliver outcomes comparable to those provided by hospitals or skilled nursing facilities, while also offering greater accessibility and flexibility. However, there is currently a shortage of professional caregivers in China, and clients are usually dispersed in different regions, with the driving time of caregivers taking up a larger proportion of the overall working time. The reasonable and efficient caregiver routing and scheduling has become one of the key issues in the home health care operation and management.
There are many uncertainties in real-world environments. Therefore, gradually, studies have begun to incorporate uncertainty factors to make the research questions more relevant to real-world situations. Most current home health care studies use stochastic methods, and a few studies use robust optimization to deal with these uncertainties. Stochastic methods usually require modeling random variables and simulating their probability distributions based on historical data. However, when information is difficult to obtain or sufficient information is lacking, it is difficult to portray its probability distribution. Robust optimization, although it does not require probability distributions of uncertain parameters, is unable to deal with parameters that involve subjectivity and ambiguity. When dealing with this kind of information, it is necessary to apply fuzzy methods to determine uncertain variables based on the past experiences of experts and caregivers.
In this study, to address the home health care routing and scheduling problem with fuzzy times, a fuzzy chance-constrained programming model is established with vehicle capacity, time window, skill level, and caregiver overtime constraints. An uncertain programming theory is introduced, where the travel and service times are described as triangular fuzzy numbers. Most current studies use exact algorithms or meta-heuristic algorithms as solution methods. Although the exact algorithm can find the optimal solution to the problem, its efficiency gradually will decrease when the scale increases, making it difficult to determine the solution in a reasonable time. Meta-heuristic algorithms, although they have efficient problem-solving capabilities, may ignore high-quality routes that do not improve the solution quality or violate constraints during the search process. To combine the advantages of both methods, a matheuristic is proposed by combining hybrid variable neighborhood search and the set partitioning model. The proposed algorithm combines variable neighborhood search and late acceptance hill-climbing to enhance the local search ability when ensuring search efficiency. The set partitioning model is used to further improve the overall search performance based on the candidate feasible routes.
Finally, numerical experiments based on adjusted Solomon benchmark instances validate the performance of the proposed algorithm, and sensitivity analysis reveals the impact of the decision maker’s risk preference on the routing and scheduling plan. Decision makers may be able to develop plans with lower operating costs if their attitudes toward time window and caregiver overtime constraints are risky. However, if the decision maker is too cost-effective, it may lead to untimely service delivery and longer working hours of caregivers, which in turn may affect the long-term operation of the home health care center. Therefore, decision makers need to develop reasonable plans based on the actual situation and previous management experience. Future research could consider teamwork of caregivers and introduce methods such as machine learning to further improve the algorithm’s solution performance.

Key words: home health care routing and scheduling, fuzzy chance-constrained programming, variable neighborhood search, set partitioning model