基于免疫遗传算法的车辆路径优化问题

《基于免疫遗传算法的车辆路径优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第29卷第3期2010年9月中南民族大学学报（自然科学版）JournalofSouth-(^entralLniversityforNationalities(Nat.Sci.Edition)Vol.29No.3Sep.2010基于免疫遗传算法的车辆路径优化问题程林辉，吴立锋，张潇(中南民族大学计算机科学学院，武汉430074)摘要在研宄免疫遗传算法基本理论的基础上，设计了一种用于求解车辆路径优化问题的免疫遗传算法，并进行了实验测试，实验结果表明算法具有良好的全局搜索能力，并且能够有效地克服遗传算法在进化过程中由于种群多样性降低而出现早熟收敛现象的缺点.关键词遗传算法；免疫遗传算

2、法;车辆路径问题中图分类号TP301文献标识码A文章编号1672-4321(2010)03~0089-4VehicleRoutingOptimizationProblemBasedonImmuneGeneticAlgorithmChengLinhui，WuLifeng，ZhangXiao(CollegeofComputerScience，South-CentralUniversityforNationalities，Wuhan430074，China)AbstractThispaperproposedanImmuneGeneticAlgorithmtoVehicleRoutin

3、gProblembystudyingtheoptimizationtheoriesofIGA.ExperimentalresultsverifythegoodglobalsearchcapabilityofIGA.Theyalsoshowthatn;Acaneffectivelyover(mmethedefectsofprematureconvergencecausedbythedecreaseofpopulationdiversityintheprocessofevolutionofgeneticalgorithm.Keywordsgeneticalgorithm；immun

4、egeneticalgorithim；vehideroutingproblem收稿日期2010-)6-30作者简介程林辉（1980-，女，硕士，讲师，研宄方向：演化计算，E-mail:clh333@163.com基金项目中南民族大学自然科学基金资助项目（YZQ07〜6).11问题背景及常用算法车辆路径问题（VehicleRoutingProblem，简称VRP)最早是由著名学者Dantzig和Ramser于1959年提出的⑴，它一般可描述为:对于一系列的送货点和（或)卸货点，配货中心组织合理的车辆行驶路线，使车辆在满足一定的约束条件(如货物的需求量、车辆的容量限制、货物的送达时

5、间、车辆的行驶时间等)下，能够有序地通过它们，并达到一定的目标(如费用最少、里程最短、使用车辆尽量少等).目前，VRP问题在人们生活的很多方面都己经有了广泛的应用，如超级市场的商品供应、工业产品运输、交通运输路线安排等，并取得了极大的效益.VRP问题是一个典型的组合优化类问题，具有很高的计算复杂性，己被证明属于NP难问题，因此自提出以来就引起了多个领域的专家学者们的关注，并先后涌现出一批用于求解该问题的方法，如精确算法、传统启发式算法、智能优化算法等.显然，精确算法与传统启发式算法并不太适合解决复杂的VRP问题，目前，绝大多数研宄者采用智能优化算法，比如遗传算法⑵、免疫算法1

6、31、免疫遗传算法[4,5]、蚁群算法[6]、模拟退火算法171等.本文在分析了遗传算法及免疫算法各自优缺点的基础上，设计了求解VRP问题的免疫遗传算法，并进行了相关的程序设计，通过与其它算法的实验结果进行比较和分析，验证算法的有效性及优势.2VRP问题建模VRP问题要求任何一辆车在行驶路径上所装载的货物总量不能超出车辆的最大负载限制.假定第3期程林辉，等：基于免疫遗传算法的车辆路径优化问题93^Drk(i-1)rki+Drknkrk〇)，(5)的免疫遗传算法的基本步骤如图1所示.更新抗体群新型智能优化算法，它具有良好记忆功能、自我调lis3i2:1初始抗1体群产生served

7、-所有车辆都相同，并且载货能力也相等，求解过程还必须同时满足:所有车辆均由单一配货中心出发，最后再回到原处，且每个客户点只被一辆车访问一次且需求量能被满足.假设己知一个配货中心(用0表示)和n个客户点（1，2,…，n)，每个客户点需求量设为q,(i=1，2,…，n)，客户点i到j的距离是Dj(i，j=1，2,…，n)，配货中心每辆车的负载能力均限制为Q，假设M为实际所使用的车辆数，设nk为第k(k=1，2,…，M)辆车所经过的客户点总数，用集合{vk.

8、0彡i彡rn}来表示第k辆车所经过的各