随机递归算法求解车辆路径问题

《随机递归算法求解车辆路径问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2008年11月系统工程理论与实践第11期文章编号:100026788(2008)1120142207随机递归算法求解车辆路径问题121步立新,罗文钰,冯允成(11北京航空航天大学经济管理学院,北京100083;21香港中文大学决策科学与企业经济学系,香港)摘要:车辆路径问题(VRP)是组合优化中一个典型的NP难题,对于中等规模以上的问题,目前大多采用禁忌搜索、遗传算法和模拟退火等亚启发式算法,在吸取这些算法精髓的基础上,提出了一种新的并且简洁而高效的启发式算法.计算结果表明,在27个国际标准算

2、例中应用该算法取得了2个解优于当前最优解,其余相当接近当前最优解.需要指出的是所有这些结果是在该算法应用同一组参数得到的.关键词:车辆路径问题;随机递归;优化算法中图分类号:TP18;O221文献标志码:ARandomrecursionheuristicsfortheVRP121BULi2xin,JaphetS.Law,FENGYun2cheng(11SchoolofEconomicsandManagement,BeijingUniversityofAeronautics&Astronautic

3、s,Beijing100083,China;21DepartmentofDecisionSciencesandManagerialEconomics,TheChineseUniversityofHongKong,HongKong,China)Abstract:TheVehicleRoutingProblemisawell2knownNP2hardproblem,whichisoftensolvedbymeta2heuristicsliketheTabuSearch,GeneticAlgorith

4、morSimulatedAnnealing.TheRandomRecursionAlgorithminspiringfromthesealgorithmsisproposed,whichisfast,robustandeffective.Thecomputationalresultsofthe27benchmarkinstancesshowthealgorithmiseverypowerfulthat2solutionsaresuperiortothebestthatalreadyhadbeen

5、foundandothersarequiteapproachingtothebest.Itshouldbenotedthatalltheresultsarecalculatedunderthesamesetofparameters.Keywords:VRP;randomrecursion;optimizationalgorithm1引言车辆路径问题(VRP)的定义是,有一批地域相互分离的客户和一个货场,已知各客户及货场之间的相互距离,以及客户的货物需求,现有若干可供派送的车辆,运载能力给定,需要

6、确定一组出发和结束于货场并满足客户货物需求的行车路线,目标是使所用车辆最少,总的行车距离最短.VRP是典型的NP难题,其解空间随着问题的规模呈指数增长,使用遍历所有状态空间的搜索算法对于中等规模问题在计算时间上已经不可接受,对于这类问题,人们普遍采用启发式或亚启发式算法,以在可以接受的时间内寻求一[1～3][4][5,6]个满意解.目前广泛使用的亚启发式算法有禁忌搜索(tabusearch)、遗传算法(geneticalgorithm)和[7]模拟退火算法(simulatedannealing)

7、等.以上亚启发式算法有一个共性,一方面它们都在强化局部邻域最优搜索,另一方面,又力求跳出局部最优,以期在更广的范围内寻找或是接近全局最优解,这是一对相互影响而又矛盾的因素.模拟退火算法通过模拟温度的逐步降低,在初始温度以较大的概率接受退化的当前最优解,以跳出局部最优解,而在温度降低后,逐步减小跳出局部最优的概率,使算法收敛于一个局部最优,从理论上说如果温度降低无限缓慢,这个局部最优就是全局最优.但搜索过程不可能无限长,模拟温度也不可能无限缓慢降低,实际上该算法的搜索空间很有限,遇到全局最优解的概

8、率也很低.在禁忌搜索算法中,当前解通过随机邻域变换游荡于巨大的状态解空间中,虽然通过禁忌当前最优解,成功地避免了当前解陷入局部最优,但是当前解遇到或接近全局最优解的概率非常低,因为搜索的范收稿日期:2007201227资助项目:国家自然科学基金NSFC(70271011);国家教育基金(2002000624)作者简介:步立新(1969-),男,河北人,博士,从事仿真、系统优化等方面研究.第11期随机递归算法求解车辆路径问题143[8]围只占整个状态空间的很小一部分,该算法的效率并不高.Rocha