Abstract: The aging population in China is characterized by a large number of elderly people, a rapid rate of aging,and significant disparities. As a result, there is a swift increase in the medical needs of the elderly. In this context, community-based home care is garnering increasing attention due to its unparalleled advantages. It allows seniors to enjoy services at home, ensuring their psychological health. Additionally, it provides professional services tailored to meet the complex daily needs of the elderly. However, China’s community-based home care is still in its infancy, facing challenges such as the shortage of medical staff and outdated scheduling technology. The home health care routing and scheduling problem is an important aspect of community-based home care, in which a team of medical personnel is dispatched by medical institutions to provide services to patients at home while minimizing operational costs under various constraints. The scheduling issue has profound theoretical and practical significance for the development of community-based home care. Therefore, this paper reviews the shortcomings of current research at home and abroad and proposes the home health care routing and scheduling problem considering synchronized services and the transportation of medical supplies.
This study investigates a category of Home Health Care Routing and Scheduling Problems, which integrates the cases where patients require simultaneous services, and healthcare workers need to carry various types of medical supplies, thus rendering the model more congruent with real-life scenarios. Additionally, time windows and patient-caregiver matching constraints are considered, for which a Mixed Integer Programming (MIP) model is formulated. Subsequently, an analysis of the model characteristics is conducted, decomposing the original problem into the master and pricing subproblems utilizing the Dantzig-Wolfe decomposition, and a Branch-and-Price algorithm is designed for problem-solving. Initially, the study employs a greedy algorithm to generate a starting solution. To assure the feasibility of the solution, a branching strategy that combines arc branching with time window branching is utilized during the branching process. Secondarily, a bidirectional labeling algorithm is adopted for solving subproblems, which enhances the label dimensions and optimizes the dominance criteria to accommodate the problem’s distinctive features. The numerical experiments indicate the efficacy of the proposed algorithm.
In conclusion, a comparative performance analysis between the Branch-and-Price algorithm and CPLEX demonstrates that the former exhibits significant advantages in instances of varying sizes and types, substantiating the efficiency and robustness of the algorithm presented in this paper. In a sensitivity analysis section, the study initially examines the patient proportion requiring synchronous services, revealing that an increase in this proportion escalates operational costs with a non-linear trend. The sensitivity analysis is then conducted of the maximum carrying capacity for medical supplies, showing that the maximum capacity has a considerable impact on operational costs. Healthcare providers must balance the total costs with the maximum carrying capacity of medical supplies to devise a more rational scheduling plan.
The problem model studied in this article is a static deterministic one; future research is inclined towards dynamic stochastic models. Consequently, future studies could consider uncertainties such as the total quantity of medical supplies needed by patients, the variability of service times for patients, and the unpredictability of travel times for healthcare workers. Additionally, models that account for the dynamic nature of patient demands could be considered, where new requests emerge during the scheduling process, and existing patient requests may be canceled at any moment. From an algorithmic perspective, the use of exact algorithms in this study has led to potential issues with extended runtimes and lower solution quality when solving large-scale instances. Therefore, improving the efficiency of exact algorithms is a focal point for future research.

Key words: home health care, synchronized services, medical supplies, vehicle routing, branch and price

摘要： 随着我国老龄化程度不断加深,家庭医护服务得到了越来越多的关注。家庭医护人员调度问题是一类NP难问题,目前多数依靠经验手动求解,而调度方案的优劣直接影响医护机构的运营成本。因此,构建贴近实际的问题模型并设计有效的求解算法至关重要。本文研究了一类家庭医护人员调度问题,问题中考虑了患者需要同步服务以及医护人员需要携带不同类型医疗物资的情形使得模型更贴近实际,对此建立了混合整数规划模型。然后根据模型特征设计了分支定价算法进行求解,在分支过程中,本文使用对弧分支和对时间窗分支相结合的策略处理同步约束,其次在双向标签算法中扩展标签维度以适应问题特性。最后,将分支定价算法与CPLEX做性能比较,结果表明在不同规模和类型的算例下分支定价算法都有显著优势。然后对同步服务患者比例和医疗物资最大携带量做了灵敏度分析。结果表明,同步服务患者比例和医疗物资最大携带量都会对总成本造成较大影响,根据结论为家庭医护机构提供了参考性建议。

关键词: 家庭医护, 同步服务, 医疗物资, 车辆路径, 分支定价