资源描述：
《基于多目标模拟退火的团队定向问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《自动化与仪器仪表》2017年第5期(总第211期)∗基于多目标模拟退火的团队定向问题毕志升(广州医科大学基础学院广东广州,511436)摘要:团队定向问题是车辆路径问题的一个重要衍生问题,是运筹学中著名的NP问题。然而,当前对于团队定向问题的研究主要集中在单目标优化,不利于体现代价和收益的折中取舍,也无法根据实际情况选择合适的方案。首先从代价和收益的角度,通过两个目标考察团队定向问题。然后运用基于Pareto支配接受准则的多目标模拟退火算法进行求解。在6个Chao数据集上的实验结果表明,基于Pareto支
2、配接受准则的多目标模拟退火算法能有效求解团队定向问题,所得的极端解与单目标优化下的已知最优解相近,所得的Pareto前沿在各个目标函数上有较好的多样性和收敛性。关键词:车辆路径问题;团队定向问题;多目标优化中图分类号:TP18文献标识码:ADOI编码:10．14016/j.cnki．1001-9227．2017．05．041Abstract:Theteamorienteeringproblemisanimportantvariantsofthevehicleroutingproblem,whichisafa
3、mousNPprobleminoperationsresearch.However,thecurrentresearchontheteamorienteeringproblemmainlyfocusesonsingle-objectiveoptimization,whichisnotconducivetoreflectthetrade-offbetweenpriceandprofit,andcannotchoosethesuitablefinalsolutionaccordingtotheactualsit
4、uation.Beaimedattheseproblems,twodifferentviews,costandbenefitarelookedintotheteamorientationproblemfirstly.Then,themultiobjectivesimulatedannealingusingPareto-dominationbasedacceptancecriterionisusedtosolvethisproblem.ExperimentalresultsonsixChao’sdataset
5、sshowthat,themultiobjectivesimulatedannealingusingPareto-dominationbasedacceptancecriterioncansolvetheteamorienteeringproblemeffectively.TheextremesolutionofParetofrontisclosedtotheknownoptimalsolutionundersingleobjectiveoptimization.AndtheobtainedParetofr
6、onthasgooddiversityandconvergenceoneachobjectivefunction.Keywords:vehicleroutingproblem;teamorienteeringproblem;multi-objectiveoptimization[6]缺少实际的现实意义。然而,TOP可以看作是一种代价0引言和收益的权衡问题,当收益的增加远远赶不上代价的增加车辆路径问题(VehicleRoutingProblem,VRP)是时,是否继续追求微薄的收益是值得商榷的。单一的最优[1
7、]Dantzig和Ramser在1959年提出的一个著名的运筹学解无法体现代价和收益的权衡,在最终方案的选择上,单问题,被广泛应用于物流配送、车辆路线规划等现实问一最优解失去了选择和取舍的余地。从这个角度上讲,分[2][3-4]题。半个世纪以来,VRP衍生出了很多变种,团队析代价和收益的关系,根据实际情况在一系列权衡和取舍[5]中选择折中方案是有现实意义的。另一方面,从不同的角定向问题(TeamOrienteeringProblem,TOP)就是其中[7]之一。度考察同一个节点可能存在多种不同的收益,应用多
8、目不同于其它类型的VRP,TOP并不要求得到的路径集标优化求解TOP也是有必要的。合访问所有节点,而是期望通过付出有限的代价,从节点本文从多目标优化的角度考察TOP,在保留原有代价中尽可能多地获得收益。这样的例子在现实生活中十分约束的前提下,运用基于Pareto支配接受准则的多目标模常见。例如公共交通规划。公共交通的投入是有限的,交拟退火算法(MultiobjectiveSimulatedAnnealingUsi
