第29卷第8期计算机集成制造系统Vol.29No.82023年8月ComputerIntegratedManufacturingSystemsAug.2023DOI:10.13196/j.cims.2023.08.030收稿日期:2021-07-15;修订日期:2021-09-13。Received15July2021;accepted13Sep.2021.基金项目:国家自然科学基金资助项目(71702016);重庆市教育委员会人文社会科学资助项目(17SKJ034);重庆市教育委员会科学技术研究资助项目(KJQN201900634,KJQN201900625)。Foundationitems:ProjectsupportedbytheNationalNaturalScienceFoundation,China(No.71702016),theHumanitiesandSocialScienceResearchFoundationofChongqingMunicipalEducationCommission,China(No.17SKJ034),andtheScienceandTechnologyFoundationofChongqingMunicipalEducationCommission,China(No.KJQN201900634,KJQN201900625).带有配额的在线旅行维修工问题蹇洁,张景露,吴腾宇,何林(重庆邮电大学现代邮政学院,重庆400065)摘要:为了将应急物资公平且迅速地送往受灾点,本文提出救援车辆装载能力有限且不必返回出发点的在线旅行维修工问题。使用在线算法分析求解,证明了该问题在正半轴网络和一般网络上的下界。分别对正半轴网络上的情形设计了BlindlyTurnLeft(BTL)算法,对一般网络上的情形设计了逆杠杆算法,给出上述在线算法的竞争比并分析了其竞争性能,与前人研究的在线旅行维修工问题对比发现,逆杠杆算法的竞争性能更优。最后通过数值仿真对受灾网络规模、受灾点数量和配送车辆容量进行敏感性分析,研究得到逆杠杆算法更适用于网络规模、车辆容量和受灾点密度较大的情形。关键词:应急救援;在线算法;竞争分析;旅行维修工问题中图分类号:C935文献标识码:AOnlinetravelingrepairmanproblemwithQuotasJIANJie,ZHANGJinglu,WUTengyu,HELin(SchoolofModernPosts,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)Abstract:Totransportemergencysuppliestothecrisisattackedlocationsfairlyandquickly,aimingatthelimitedca-pacityandnomadicvehicle,theonlinetravelingrepairmanproblemwithquotaswasintroducedandsolvedwithon-linealgorithm.Lowerboundsoftheproblemonthepositivehalf-lineandgeneralnetworkswereproved.TheBlindlyTurnLeft(BTL)algorithmwasdesignedformetricspaceofpositivehalf-line,andtheinverseleveragealgorithmwaspresentedformetricspaceofgeneralmetricspace.Thencompetitiveratiowasgivenforthetwoalgorith...
