doi:10.3969/j.issn.1007-7375.2023.03.012基于分支定价算法的多时间窗家庭医护人员调度问题研究李妍峰，罗楠，向婷(西南交通大学经济管理学院，四川成都610031)摘要:为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解，并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试，将所提出的算法与CPLEX对比，验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现，客户提供多个可接受服务的时间窗能有效降低调度成本。关键词:家庭医护；多时间窗；改进标签算法；列生成；分支定价中图分类号:TP301文献标志码:A文章编号:1007-7375(2023)03-0107-09HomeHealthCareSchedulingwithMultipleTimeWindowsBasedonBranchandPriceAlgorithmLIYanfeng,LUONan,XIANGTing(SchoolofEconomicsandManagement,SouthwestJiaotongUniversity,Chengdu610031,China)Abstract:Inordertoreducetheschedulingcostofhealthcareworkersandimprovecustomersatisfaction,thehomehealthcareschedulingproblemisstudied.Consideringmultipletimewindowsofcustomers'acceptableserviceanddifferentpreferencesfordifferenttimewindows,amathematicalmodelisestablishedwiththeobjectiveofminimizingtotaloperatingcostandmaximizingthesatisfactiondegree.BasedontheDantzig-Wolfedecompositionprinciple,themodelisreconstructedintoasetpartitioningmasterproblemandashortestpathsubproblemwithmultipletimeWindows.Theproblemissolvedbybranchandpricealgorithm,wherethecolumngenerationisembeddedintoabranch-and-boundframework.Accordingtothecharacteristicsofproblemswithmultipletimewindows,arandomgreedyalgorithmtoquicklyobtaintheinitialsolutionandanimprovedlabel-settingalgorithmtosolvethesubproblemaredesigned.TheeffectivenessoftheproposedalgorithmisverifiedbycomparingwithCPLEXthrough50testingnumericalexamples.Finally,bycomparingtheresultswithsingletimewindowandmulti...
