蚁群算法优化车辆路径问题的研究

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

1、第27卷第2期贵州大学学报(自然科学版)V0l_27No．22010年4月JoumalofGuizhouUnive~ity(NaturalSciences)Apr．2010文章编号1000—5269(2010)02-0115—04蚁群算法优化车辆路径问题的研究宋鸽，王子牛，刘磊(1．贵州大学计算机科学与信息学院，贵州贵阳550003；2．贵州大学信息化管理中心，贵州贵阳550003；3．中铁六局天津铁路建设有限公司，天津300140)摘要：通过引入蚁群算法来解决物流中的车辆路径问题。针对具体实例运用计算机编程得出系统的最优解，并与优化前进行对比，指出优化比率，从而减少物流配

2、送成本，提高效益。关键词：物流配送；优化；蚁群算法中图分类号：U495；0221．7文献标识码：B随着经济全球化步伐的加快和通信信息技术间，不考虑车辆每次最大行驶里程，不考虑运输时的发展，物流这个服务行业已经成为了一个跨地的规章制度等。此外，补充的约束条件是：车辆完域，跨行业，跨国界的复合型产业。成任务之后要回到原点，也就是配送中心，运输两在物流诸多环节中，配送占有重要的地位。配节点间为对称路径，即A点到B点与B点到A点送质量的好坏，直接影响到企业的利润、形象，以及所付出代价是相等的，并且节点间是任意可达的。客户的满意度等。物流配送路线的优化问题，是评2蚁群算法定配送质量好

3、坏的重要标准。因此，本文以目前研蚁群算法最早是由意大利学者M．Dofigo提出究较多的蚁群算法为核心，来探索车辆优化组合问的，它来自于对蚁群的行为研究，通过研究蚂蚁集题，使运输路线最优，从而减少成本，提高效益。体寻径时，利用称为“外激素”的生物信息激素选1问题描述择后继行为的智能过程形成。蚁群优化算法就是物流配送方案目标是要达到配送效益最高或对自然界中蚂蚁的寻食过程进行模拟而得出的一配送成本最低，配送里程最短，配送服务水准最优种模拟进化算法。它具有较好的并行性、协作性和以及配送劳动的消耗最小。而常见的配送路线约鲁棒性，寻优特性好等特点。蚁群算法已用于解束条件则有以下几个：决

4、多种组合优化问题，例如最短路径寻优问题、收货人对货物品种、规格和数量的要求TSP问题、二次分配问题、运输调度问题等。收货人对货物送达时间或时间范围的要求2．1算法基本描述道路运行条件的制约给定n个城市的TSP问题，人工蚂蚁数量为车辆最大装载能力的限制m，这些蚂蚁具有记忆功能，并具有以下特征：车辆最大行驶里程数的限制以及司机的最长(1)根据信息素浓度和启发式信息，用相应的工作时间的限制转移概率选择下一个城市。在建立系统模型时，前面提到了有许多因素需(2)将已经走过的城市放人记忆表中，记忆表要考虑，但为了简化问题，提出以下假设：里的城市将不再被选择为下一个城市。(1)第一个假设

5、：一个配送中心(2)第二个假设：多辆汽车的配送路线优化(3)完成一次循环后，根据整个路径的长度来(3)第三个假设：考虑车辆载重量释放相应的信息素，并更新走过的路径上的信息其他假设：假设货物在运输途中是不会变质损素。坏的，不考虑货物回收需求，不考虑司机的工作时蚂蚁选择下一个城市的转移概率为：收稿日期：2009—12一O8作者简介：宋鸽(1985一)，女，河南驻马店人，硕士研究生，研究方向：智能信息处理，Email：hilary403@163．tom．+通讯作者：王子牛，Email：znwang@gzu．edu．cn．贵州大学学报(自然科学版)第27卷信息启发式因子：反映了蚂蚁

6、在运动过程中P：=J{∑：(￡)叼(￡)allowedk(1)所累积的信息量在指导蚂蚁群搜索中的相对重要【ootherwise程度。期望启发式因子：反映了期望启发式信息在其中，r代表路径之间的信息索，代表路径ij指导蚁群在搜索过程中的相对重要程度。之间的启发信息，在TSP问题中，通常’7=1／d，在蚁群算法模型中用参数P：表示信息素挥发即路径的长度。allowed表示蚂蚁k还没有访问因子，则1一P就是信息素残留因子。的节点的集合，每次循环将已经访问的节点从列表信息素强度Q：为蚂蚁循环一周时释放在所经中剔除。参数，为问题所考虑的权重。路径上的信息素总量。信息素的更新：3实例仿

7、真(￡+)=P·To-(￡)+(1一p)·∑AT；3．1功能设计(2)建立的模型从功能上来说，主要包括以下几随着时间的推移，经过个时刻，蚂蚁完成一点：①地图上节点、路径的显示功能，②可以随意添次循环，以前留下的信息素将逐渐消逝，用参数1一加或删除节点，③选定的节点可以设置需求量约P表示信息消逝程度，P是一个取值范围在0到1的束，④可以手工调整相关参数，⑤能够演示路径变常数，△丁表示第k只蚂蚁本次循环中留在路径化将计算结果清晰表示出来。上的信息量。3．2模型实现M．Dorigo曾提出三种信息素增量的算法：模型需要为企