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

摘要： 针对家庭护理服务配送中的护理人员行驶时间和服务时间的不确定性问题,引入不确定规划理论并进行模糊化处理,同时考虑了车辆容量、时间窗、技能匹配以及护理人员加班时间等现实约束,建立了最小化行驶成本和护理人员成本的模糊机会约束规划模型。为求解该模型,基于模糊模拟方法,提出了一种混合变邻域搜索算法和集合划分模型相互嵌套迭代的数学启发式方法。该算法通过混合变邻域搜索和延迟接受爬山算法以提高局部搜索能力和搜索效率,基于获取的可行候选路径,利用集合划分模型,增强算法整体搜索能力。最后,通过数值实验验证了算法的有效性,敏感性分析揭示了决策者的风险偏好对调度方案的影响。

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