工业工程

工业工程 ›› 2023, Vol. 26 ›› Issue (3): 107-115,133.doi: 10.3969/j.issn.1007-7375.2023.03.012

• 系统建模与优化方法 • 上一篇    下一篇

基于分支定价算法的多时间窗家庭医护人员调度问题研究

李妍峰, 罗楠, 向婷   

  1. 西南交通大学 经济管理学院，四川 成都 610031
  • 收稿日期:2021-10-21 发布日期:2023-07-08
  • 作者简介:李妍峰(1980-),女,四川省人,副教授,博士,主要研究方向为物流优化、交通优化。
  • 基金资助:
    国家自然科学基金资助项目(72071161,71571150)；四川省科技厅应用基础研究重大前沿项目资助(2017JY0225)；西南交通大学智慧物流与供应链管理研究生导师团队资助项目(YJSY-DSTD201918)；四川省科技厅应用基础研究资助项目(2020YJ0220)

Home Health Care Scheduling with Multiple Time Windows Based on Branch and Price Algorithm

LI Yanfeng, LUO Nan, XIANG Ting   

  1. School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China
  • Received:2021-10-21 Published:2023-07-08

RichHTML

22

PDF

1488

摘要： 为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解，并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试，将所提出的算法与CPLEX对比，验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现，客户提供多个可接受服务的时间窗能有效降低调度成本。

关键词: 家庭医护, 多时间窗, 改进标签算法, 列生成, 分支定价

Abstract: In order to reduce the scheduling cost of health care workers and improve customer satisfaction, the home health care scheduling problem is studied. Considering multiple time windows of customers' acceptable service and different preferences for different time windows, a mathematical model is established with the objective of minimizing total operating cost and maximizing the satisfaction degree. Based on the Dantzig-Wolfe decomposition principle, the model is reconstructed into a set partitioning master problem and a shortest path subproblem with multiple time Windows. The problem is solved by branch and price algorithm, where the column generation is embedded into a branch-and-bound framework. According to the characteristics of problems with multiple time windows, a random greedy algorithm to quickly obtain the initial solution and an improved label-setting algorithm to solve the subproblem are designed. The effectiveness of the proposed algorithm is verified by comparing with CPLEX through 50 testing numerical examples. Finally, by comparing the results with single time window and multiple time window examples, it is found that the scheduling cost can be effectively reduced when customers provide multiple acceptable service time windows.

Key words: home health care, multiple time windows, improved the label-setting algorithm, column generation, branch and price

中图分类号: