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

doi:10.3969/j.issn.1007-7375.2023.03.012

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

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

李妍峰, 罗楠, 向婷

西南交通大学经济管理学院，四川成都 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

School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China

Received:2021-10-21 Published:2023-07-08

摘要/Abstract

摘要： 为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于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

中图分类号:

TP301

李妍峰, 罗楠, 向婷. 基于分支定价算法的多时间窗家庭医护人员调度问题研究[J]. 工业工程, 2023, 26(3): 107-115,133.

LI Yanfeng, LUO Nan, XIANG Ting. Home Health Care Scheduling with Multiple Time Windows Based on Branch and Price Algorithm[J]. Industrial Engineering Journal, 2023, 26(3): 107-115,133.

参考文献

[1] LIU R, XIE X L. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[J]. European Journal of Operational Research, 2013, 230(3): 475-486
[2] EVEBORN P, FLISBERG P, RONNQVIST M. Laps care: an operational system for staff planning of home care[J]. European Journal of Operational Research, 2006, 171(3): 962-976
[3] CISSE M, YALCINDAG S, KERGOSIEN Y, et al. OR problems related to home health care: a review of relevant routing and scheduling problems[J]. Operations Research for Health Care, 2017, 13-14: 1-22
[4] FIKAR C, HIRSCH P. Home health care routing and scheduling: a review[J]. Computers & Operations Research, 2017, 77: 86-95
[5] MUTINGI M, MBOHWA C. Multi-objective home care worker scheduling: a fuzzy simulated evolution algorithm approach[J]. IIE Transactions on Healthcare Systems Engineering, 2014, 4(4): 209-216
[6] MARTIN E, CERVANTES A, SAEZ Y, et al. IACS-HCSP: improved ant colony optimization for large-scale home care scheduling problems[J]. Expert Systems with Applications, 2020, 142: 1-36
[7] LIU R, YUAN B, JIANG Z. Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements[J]. International Journal of Production Research, 2017, 55(2): 558-575
[8] REDJEM R, MARCON E. Operations management in the home care services: a heuristic for the caregivers' routing problem[J]. International Journal of Flexible Manufacturing Systems, 2016, 28(1-2): 280-303
[9] MANKOWSKA D S, MEISEL F, BIERWIRTH C. The home health care routing and scheduling problem with interdependent services[J]. Health Care Management Science, 2014, 17(1): 15-30
[10] ANDREA T, MANFRED G, PATRICK H. Securing home health care in times of natural disasters[J]. Operations Research Spektrum., 2011, 33(3): 787-813
[11] HIERMANN G, PRANDTSTETTER M, RENDL A, et al. Metaheuristics for solving a multimodal home-healthcare scheduling problem[J]. Central European Journal of Operations Research, 2015, 23(1): 89-113
[12] BERTELS S, FAHLE T. A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem[J]. Computers & Operations Research, 2006, 33(10): 2866-2890
[13] DANTZIG G B, WOLFE P. Decomposition principle for linear programs[J]. Operations Research, 1960, 8(1): 101-111
[14] FEILLET D. A tutorial on column generation and branch-and-price for vehicle routing problems[J]. 4OR-A Quarterly Journal of Operations Research, 2010, 8(4): 407-424
[15] FEILLET D, DEJAX P, GENDREAU M, et al. An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems[J]. Networks, 2004, 44(3): 216-229
[16] LOACHIM I, GELINAS S, SOUMIS F, et al. A dynamic programming algorithm for the shortest path problem with time windows and linear node costs[J]. Networks, 1998, 31(3): 193-204
[17] LI J L, QIN H, BALDACCI R, et al. Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows[J]. Transportation Research:Part E, 2020, 140: 1-22
[18] BARNHART C, JOHNSON E L, NEMHAUSER G L, et al. Branch-and-price: column generation for solving huge integer programs[J]. Operations Research, 1998, 46(3): 316-329
[19] ZHANG Z Z, LUO Z X, QIN H, et al. Exact algorithms for the vehicle routing problem with time windows and combinatorial auction[J]. Transportation Science, 2019, 53(2): 427-441
[20] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	陈彦博, 陈峰, 文若霖. 电商仓储订单分批和路径优化问题的分支定价算法研究[J]. 工业工程, 2022, 25(2): 86-94.
[2]	江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.