分支定价算法求解携带医疗资源的家庭医护人员调度问题

Branch and Price Algorithm to Solve Home Health Care Scheduling Problem with Medical Resources

针对携带医疗资源的家庭医护人员调度优化问题,综合考虑医疗资源、弹性服务时间窗、医患技能等级匹配等特征,以最小化运营成本和弹性时间窗惩罚成本为目标构建数学模型。并根据Dantzig-Wolfe分解原理将模型重构为基于访问路径的主问题和若干带资源约束的最短路子问题模型。根据问题特征设计了分支定价算法来求解该问题。小规模算例结果表明医疗资源特性对医护人员路径调度有重要影响,而弹性时间窗可以有效降低总成本;多种算例的运算结果证明了分支定价算法求解的高效性。

With the accelerating trend of population aging in China,in order to alleviate the pressure of elderly care for residents and meet the medical security requirements of different groups,the country is actively responding to the aging population.The country also vigorously promotes home health care signing services and home-based elderly care services,with home health care being the main service content.In this service,the home health care is available for patients to provide medical services.Decision makers need to develop the optimal scheduling plan for the home health care while considering various factors.This type of problem is known as home health care routing and scheduling problem.In the process of home health care services,home medical staff need to carry different medical resources to provide services to patients,such as thermometers,blood pressure monitors,gastric tubes,drugs,etc.Similar to thermometers,they can be reused,while instruments such as drugs and gastric tubes are disposable items.Medical resources have both reusable and disposable properties.The total amount of medical resources that home medical staff can carry is limited.Carrying medical resources during scheduling can affect the doorstep route of home medical staff.Therefore,considering the nature of home health care routing and scheduling problem of home medical staff has important practical significance.Previous studies have not considered the scheduling of medical resources.Some have simultaneously considered the scheduling of medical personnel and medical resource vehicles,and established a mathematical model to minimize travel costs and service costs.Others have considered the vehicle routing problem for scheduling traditional Chinese medicine resources in home health care services.They have studied the routing problem of pickup and delivery vehicles with time windows in home health care services.It refers to the distribution of drugs and medical devices from the pharmacy of a home care company to patients,and the extraction of biological samples and unused drugs and medical devices from patients.We consider the need for medical staff to bring medical resources for on-site services,dividing medical resources into reusable resources(such as medical equipment)and disposable resources(such as drugs).An integer programming model is established to minimize operating costs and penalty costs for flexible service time windows,taking into account constraints such as medical resources,flexible time windows for patients receiving services,doctor-patient matching,and working time constraints for medical staff in the problem.And a branch and pricing algorithm is designed to solve the mathematical model.This algorithm is a combination of column generation and branch and bound.The column generation algorithm finds the optimal solution of the relaxation problem at the node as the lower bound of the node,and then uses the branch and bound algorithm to find the integer solution.The core of the column generation algorithm lies in solving the pricing sub-problem.This article proposes an improved label algorithm to solve the sub-problem of whether medical resources are repeatable,in order to improve the algorithm speed.We analyze the efficiency of this algorithm through a large number of experimental examples.Through case analysis,it is found that the maximum capacity and flexible time window have a significant impact on the routing of home health care.The upper limit of medical resources that each healthcare worker can carry is crucial.By adjusting the on-site path of medical staff,we can allocate resources reasonably to medical staff to work within their capabilities.Medical nursing center managers can adjust the maximum amount of medical resources that medical staff can carry,taking into account the workload and door-to-door path of medical staff.The flexible time windows not only make scheduling paths more flexible but also reduce overall scheduling costs.Nursing center decision-makers can encourage customers to provide flexible service time windows to reduce scheduling costs.The efficiency of the branch and pricing algorithm is verified by testing and comparing it with CPLEX in different scale cases.Future research can consider home health care routing and scheduling problem based on medical resource scheduling in multi-cycle scenarios,and design more effective algorithms to solve it.