资源描述：
《随机需求情形VRP的退火网络解法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2002年3月系统工程理论与实践第3期 文章编号:100026788(2002)0320109205随机需求情形VRP的退火网络解法123袁 健,刘 晋,卢厚清(1.南京航空航天大学宇航学院,江苏南京210016;2.五邑大学管理学院,广东江门529020;3.南京航空航天大学机电学院,江苏南京210016)摘要:随机需求情形下的车辆路由问题(VRP)是一种普遍存在而求解较为困难的运筹学问题L模拟退火算法(SA)和Hopfield神经网络解法是解决该问题的两个较好的方法L本文采用一种改进了的平均场退火方法(MFA),该方法将模拟
2、退火算法(SA)和Hopfield神经网络解法相结合,加速了神经网络的收敛并具有与模拟退火算法(SA)相当的精度L关键词:游路问题;随机需求;退火网络;平均场退火中图分类号:O24;U116文献标识码:AaAnnealedNeuralNetworksApproachtotheVehicleRoutingProblemwithStochasticDemands121YUANJian,LIUJin,LUHou2qing(1.NanjingUniversityofAeronauticsandAstronutics,Nanjing210
3、016,China;2.WuyiUniersity,Jiangmen529020,China)Abstract:Variousvehicleroutingproblems(VRP)areencounteredinmanyservicessystemssuchasdelivery,customerspick2up,repairandmaintenanceservices.MostofexistingVRPresearcheshavebeenconcentratedinthecaseofdeterministicdemands.Be
4、causeofpracticalneeds,theresearchesonvehicleroutingproblemwithstochasticdemandsbegantodrawmuchattentionathomeandabroad.Amodifiedversionofmeanfieldannealingalgorithm(MFA)isderivedtosolvetheVRPwithsomekindofstochasticdemands,whichisacombinationofneuralnetworksandsimula
5、tedannealingapproach.Thebehaviorofthealgorithmistestedwithnumericalexamples.Theresultsshowthatthealgorithmhasgoodperformanceinbothglobalandlocalsearching.Itisbelievedthattheconcurrentandadaptivemechanismsofneuralnetworkmakethealgorithmsoefficient.Keywords:VRP;stochas
6、ticdemand;annealedneuralnetwork;meanfieldannealing1 引言车辆路由问题(VRP)即从一个服务中心D(depot)向离散分布在某一区域的n个服务需求点派遣“车辆”,要求确定派出车辆的数目和各车辆的行走路线L根据服务点的需求量是确定性的还是随机的,VRP可分为确定性VRP和随机VRPL近年来,VRP研究非常活跃,代表性的方法有Teodorovic等解决随机VRP[1][2][3]的模拟退火法;Popovic模拟随机需求的贝叶斯算法;Milosavljevic等的模糊集合方法;Gold
7、en等的[4]自适应记忆算法及文献[5]提出的Hopfield神经网络解法L文献[5]采用文献[1]中将随机需求问题中的加权平均路程作为代价函数的方法,提出了一种Hopfield神经网络解法L该方法中将表示总路线上服务点次序的n×n排列矩阵的元素映射成Hopfield神经网络的神经元状态L当网络收敛时,神经元的状态不再a收稿日期:2000206226资助项目:航空基础科学基金(97J52091)©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.110系统
8、工程理论与实践2002年3月发生变化L如果这时的神经元状态矩阵满足合法路径对排列矩阵的要求,则得到一条最优路径L该方法在寻求最优路径的试验中以较多的机会得到许多不合法的路径L当服务点的数目增加时,徒劳的运算也随之增加,因此效率不够理想L另一方面,Hopfield
