基于遗传算法的车辆路径问题extendsim仿真与优化

《基于遗传算法的车辆路径问题extendsim仿真与优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于遗传算法的车辆路径问题ExtendSim仿真与优化　　摘要：文章首先介绍了物流领域中经典的车辆路径问题（VRP），以及解决该问题的算法，然后论述了遗传算法在解决VRP上的应用，并详细地叙述ExtendSim仿真软件如何对某一VRP进行建模优化，最后得出最优方案。验证了这一仿真优化方法是解决VRP的一种有效途径。　　关键词：车辆路径问题；遗传算法；ExtendSim；仿真；优化　　中图分类号：U116.2文献标识码：A　　Abstract：Thisarticlehasintroducedtheclassi

2、calvehicleroutingproblem（VRP）inthefieldoflogisticsandthealgorithmwhichcansolvetheproblemfirstly，thendiscussesthathowtoapplygeneticalgorithmtosolvingVRP，anddescribeshowExtendSimsimulationsoftwareconstructamodelandmakeaoptimizeforancertainVRPindetail，withthi

3、smethod，finallyconcludestheoptimalsolution，andprovesthatthesimulationoptimizationmethodisaneffectivewaytosolvetheVRP.　　Keywords：vehicleroutingproblem；geneticalgorithm；ExtendSim；simulation；optimization　　我国国家标准《物流术语》（GB/T18354-2006）中，给物流下的定义是：“物流是指物品从供应地向接收地

4、的实物流动过程。根据实际需要，将运输、存储、装卸、搬运、包装、流通加工、配送、信息管理等基本功能实施有机结合。”物流有多方面的功能，而运输和储存保管则是其主要功能。在整个物流活动过程中，运输是其中各项子活动的核心活动，它是第三利润源的主要的源泉[1]。　　日本在20世纪70年代就对物流有深刻的认识了，日本早稻田大学的西泽修教授在其著作中把物流称作不为人知的利润源泉，他认为，物流能为企业创造价值，是企业的利润源泉。石油危机后这一观点得到证实，物流也因而在企业管理中得到更加重视。目前我国生产型企业的物流成本占到

5、总成本的20%～30%，而发达国家的则为10%左右[2]。因此，为了降低企业经营成本，获得更多的利润，必须尽量降低物流成本的比重，这对于国民经济的更好发展具有十分重要的作用。　　在商品经济社会中，人们的生活质量与商品消费息息相关，而商品的价格直接影响人们的生活水平，如果商品价格不合理，超出人们普遍的可接受范围，那么人们的生活幸福度将会大大降低。而商品价格的构成部分除了有生产成本，还有更重要的一部分是物流成本，并且物流成本中的运输费又占了较大的比重。商品运输需要耗费大量的能源动力，消耗越多，花费成本越高，如果

6、运输组织的不合理，就会加大运输成本，因而抬高物流成本，商品价格也因而升高，结果是不仅降低企业的利润，也间接提高人们的生活成本。　　所以，运输问题是物流领域中值得研究的关键问题。其中车辆路径问题（VehicleRoutingProblems，VRP）是运输问题中的一个热点问题。该问题是指：在物资流通过程中，每个需求点的位置和需求量已知，供方如何调度车辆和安排行车路径向需方供应物资，使得在满足需方需要的同时也达到某些关键目标（如车辆数尽量少、花费时间尽量少、费用最少、路程最短等）。　　学者们很早就开始对车辆路径

7、问题进行了研究，积累了丰富的研究成果。在20世纪50年代末，车辆路径问题首先被G.Dantzig和J.Ramser[3]提出，两位学者根据如何运送汽油到加油站这个现实中的问题，利用数学方法对其建立模型，并得出求解算法。在1964年，Clark和Wright这两位学者研究了G.Dantzig和J.Ramser的方法后，认为后者的方法有改进的空间，并最后提出了Clark-Wright节约算法（即C-W算法）。从此VRP成为运筹学领域的研究热点。五年后，Christofides与Eilon又想出新的方法，他们应用

8、2-opt和3-opt处理VRP，取得较好的效果。到1981年，Fisher、Jaikumar和Gullen、Ratliff、Jarvis提出不同的研究方法。前者主要利用数学规划，来对VRP进行最优化处理，后者则是运用人机互动的启发式方法处理VRP。到90年代，学者们开始利用人工智能构造大量的启发式算法来解决VRP，如禁忌搜索发、模拟退火法、遗传算法等。首先采用遗传算法（GeneticAlgorithm，GA）的