求解车辆路径问题的改进遗传算法.pdf

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

1、ComputerEngineeringandApplications计算机工程与应用2010，46（36）219⦾工程与应用⦾求解车辆路径问题的改进遗传算法程林辉，王江晴CHENGLin-hui，WANGJiang-qing中南民族大学计算机科学学院，武汉430074CollegeofComputerScience，South-CentralUniversityforNationalities，Wuhan430074，ChinaE-mail：clh333@163.comCHENGLin-hui，WANGJi

2、ang-qing.Improvedgeneticalgorithmforvehicleroutingproblem.ComputerEngineeringandApplications，2010，46（36）：219-221.Abstract：Vehicleroutingproblemisatypicalcombinationaloptimizationproblem.GeneticalgorithmisoneofthemethodsusedtosolveVRP.Aimingatthedefectsofpr

3、ematureconvergenceintheevolutionprocessofgeneticalgorithm，thisthesisdesignsanimprovedgeneticalgorithm，referringtheadvantagesofimmunealgorithmwhichusesantibodyconcentrationre-strictiontokeeppopulationdiversityandtheindividualchoiceapproachofsimulatedanneali

4、ngalgorithm.Theimprovedge-neticalgorithmisusedtosolveVRPinthethesis.Someexperimentdataprovetheeffectivenessofthealgorithmandauthen-ticatethesearchefficiencyandsolutionqualityofthealgorithm.Keywords：geneticalgorithm；vehicleroutingproblem；combinationaloptimi

5、zation摘要：车辆路径问题是一个典型的组合优化类问题，遗传算法是求解此类问题的方法之一。针对遗传算法容易出现“早熟”现象的问题，借鉴免疫算法通过抗体浓度抑制以保持种群多样性的优势以及模拟退火算法的个体选择策略，提出了一种改进的遗传算法，并将其用于解决车辆路径问题。实验验证了算法的有效性以及求解的效率和解的质量。关键词：遗传算法；车辆路径问题；组合优化DOI：10.3778/j.issn.1002-8331.2010.36.061文章编号：1002-8331（2010）36-0219-03文献标识码：Ａ中

6、图分类号：TP3011引言习性等智能特性，可用于解决组合优化、机器学习、自适应控车辆路径问题（VehicleRoutingProblem，VRP）[1]是一个制等智能问题。经典的组合优化问题，最早由著名学者Dantzig和Ramser于在研究遗传算法的基本思想和优化原理的基础上，为更1959年提出。由于该问题将理论研究和实际应用紧密地联系好地求出满足问题各个约束条件的解、提高解的质量和算法在一起，自提出以来就引起了包括计算机科学、运筹学、组合的收敛速度，借鉴免疫算法中抗体浓度抑制的思想以及模拟数学等多个学科

7、专家学者的高度重视。到目前为止，用于求退火算法的个体选择策略，针对VRP问题提出了一种改进的解车辆路径问题的方法已可划分为三类，即精确优化方法、传遗传算法，并进行了相关的程序设计和实验验证。统启发式方法、智能优化算法。目前，国内外的研究者基本都集中在对智能优化算法的研究上[2-6]。随着国内外研究人员的2VRP问题建模共同努力，求解VRP问题的智能优化算法在理论研究方面逐VRP问题一般定义为：对于一系列的客户点，组织合理的渐取得了一定的进展，但这些智能算法在求解时间和解的质车辆行驶路线，使车辆在满足一定的约

8、束条件（如货物的需求量上都还需要做进一步的改进和完善。量、车辆的容量限制、货物的送达时间、车辆的行驶时间等）遗传算法（GeneticAlgorithm，GA）是智能优化算法的一下，能够有序地通过它们，并达到一定的目标（如里程最短、费种，它是基于自然选择和遗传变异等生物进化机制而发展起用最少、使用车辆尽量少等）。来的高度并行、随机、自适应的全局性概率搜索算法。作为一主要研究的是容量受限的VRP问题（Capacita