资源描述：
《动态团队定向问题的模型及其优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第45卷第6期西安交通大学学报Vol45No62011年6月JOURNALOFXIANJIAOTONGUNIVERSITYJun.2011动态团队定向问题的模型及其优化算法柯良军,尚可,冯祖仁(西安交通大学机械制造与系统工程国家重点实验室,710049,西安)摘要:针对物流配送系统优化设计中关键难题之一的团队定向问题,提出了一种部分顾客需求动态到达的动态团队定向问题,并建立了该问题的模型.采用把规划周期分成一系列时间段的策略,将动态问题转化成一系列的静态子问题求解.提出了一种蚁群算法,其特点是利用上一时间段的信息来加速算法寻优能力,并用一种基于分支定
2、价的离线精确性算法来求解动态团队定向问题.实验结果表明,与基于分支定价的离线精确性算法相比,所提出的蚁群算法能在1ks内求解4个测试算例,并且在2个算例中得到的最好解优于离线精确性算法的解.关键词:动态团队定向问题;蚁群算法;分支定价中图分类号:TP3016文献标志码:A文章编号:0253987X(2011)06000106OntheModelandOptimizationAlgorithmforDynamicTeamOrienteeringProblemKELiangjun,SHANGKe,FENGZuren(StateKeyLaboratoryforManufa
3、cturingSystemsEngineering,XianJiaotongUniversity,Xian710049,China)Abstract:Adynamicteamorienteeringproblemofpartialdynamicarrivalcustomersisstudied,andamodeloftheproblemisestablishedtodealwiththeteamorienteeringproblem,whichisoneofthemostcriticalproblemsintheoptimizationdesignforlogisticdi
4、stributionsystem.Thedynamicproblemisconvertedintoaseriesofstaticsubproblemsbypartitioningtheplanninghorizonintoaseriesoftimesegments.Anantcolonyoptimization(ACO)basedalgorithmisproposedtosolvetheresultingproblem.Theprominentcharacteristicofthealgorithmistousetheinformationobtainedfromthel
5、asttimesegmenttoenhancethesearchbehavior.Anexactofflinealgorithmbasedonbranchandpriceisalsopresentedtosolvetheproblem.ExperimentalresultsandcomparisonswiththeexactofflinealgorithmbasedonthebranchandboundshowthattheproposedACObasedalgorithmcansolvefourtestinstanceswithin1000seconds,andthatth
6、esolutionsoftwotestinstancesobtainedbytheproposedACObasedalgorithmarebetterthanthoseobtainedbytheexactofflinealgorithm.Keywords:dynamicteamorienteeringproblem;antcolonyoptimization;branchandprice团队定向问题(TOP)是一类特殊的物流配送收益收集问题.团队定向问题这一名称是由Chao[2]路径优化问题.该问题是指在满足一定约束条件下,等于1996年确立的.近几年,国内外学者针对该为
7、了服务一组具有一定报酬的顾客,规划车辆行程问题提出了许多高效的算法,文献[34]中分别提出[1]以最大化车队的总收益.1994年,Butt等最先研了列生成和分支定价两种精确性算法.由于团队定究团队定向问题,不过他们称这类问题为多路最大向问题是一类NPhard问题,现有研究主要集中于收稿日期:20110104.作者简介:柯良军(1976-),男,副教授.基金项目:国家自然科学基金资助项目(60905044);教育部博士点基金资助项目(20090201120042);国家重点基础研究
