欢迎来到天天文库
浏览记录
ID:34516531
大小:224.44 KB
页数:3页
时间:2019-03-07
《非线性常微分方程边值问题的最优化算法18708》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、2142010,46(5)ComputerEngineeringandApplications计算机工程与应用蜂群优化算法在车辆路径问题中的应用杨进-,马良zYANGJin,MALiang21.上海理工大学理学院,上海2000932上海理工大学管理学院,上海2000931.SchoolofScience,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China2.SchoolofManagement,UniversityofShanghaiforSc
2、ienceandTechnology,Shanghai200093,ChinaE—mail:yan~in一78@hotmai1.comYANGJin。MALiang.Waspcolonyalgorithmforvehideroutingproblem.ComputerEngineeringandApplications,2010.46(5):214—216.Abstract:VehicleRoutingProblem(VRP)isthetypicalNP-hardproblemincombinatorialoptimiz
3、ation.Thispaperproposesanewalgorithm,waspcolonyalgorithm,forvehicleroutingproblemthroughcomparingthetwotargetfunction:vehiclenumberandtotaldistance.Seriesofbenchmarkproblemsaretestedandverifythevalidityofthealgorithmthroughcomparingtheresultswiththeotheralgortihm
4、s.Thewaspcolonyalgorithmhasjustbeguntodevelopandduetonowitisonlyusedinfewproblemsathomeandabroad.Thereforethispapernotonlyexpandstheapplicationscopeofthewaspcolonyalgorithmbutalsogivesanewmethodtosolvethevehicleroutingproblem.Keywords:VehicleRoutingProblem(VRP);w
5、aspcolonyalgorithm;optimization摘要:车辆路径问题(VRP)是组合优化中典型的NP难题。根据车辆路径问题的实际情况,考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,故不仅是拓宽蜂群算法的应用范围的有效的尝试,同时也给车辆路径问题提供了一种新的解决方法。关键词:车辆路径问题;蜂群算法;优化DOI:10.3778/j.i
6、ssn.1002—8331.2010.05.065文章编号:1002—8331(2010)05—0214—03文献标识码:A中图分类号:TP18l引言其在较大规模的VRP问题上的优越性。另外,目前关于蜂群算车辆路径问题(VehicleRoutingProblem,VRP)是物流配法的文献较少,且大部分都仅仅局限在将其应用在车间作业调送优化中的关键问题[11。比如在物流配送供应领域中,一个常见度问题忙_卅。故该文不仅是拓宽蜂群算法的应用范围的有效尝的问题是:已知有一批客户,各客户点的位置坐标和货物需求试,同时也给车辆路径问
7、题提供了一种新的解决方法。已知。供应商有若干可派送的车辆,每辆车的运载能力是给定的。每辆车都从起始点出发,送完若干客户点的货后回到起始2问题概述及数学模型点。要求就是要以最少的车辆数,最小的车辆总行程来完成货VRP一般可描述如下:在约束条件下,设计从一个或多个物的派送。该问题自1959年Dantzig等人首先提出以来,至今初始点出发,到多个不同位置的城市或客户的最优送货或路径已经衍生出多种不同类型的问题。著名的旅行商问题(P)也分配,即要设计一个费用最小的路线集且满足:是它的一个特例。TSP是NP难题,后来VRP也被证明
8、是NP(1)每个城市或客户只被一辆车访问一次;难题。理论上,目前仅能求出较小规模问题的最优解。而某些启(2)所有车辆从起点出发再回到起点;,找到满意解的实用方法。尽管如此,(3)一些约束被满足。对于较大规模的问题,有些应用较广的启发式算法如蚁群算法最通常的约束包括容量限制(CVRP)、时间限制(VRZrW)等,也未必
此文档下载收益归作者所有