基于改进蚁群算法的车辆路径优化.pdfVIP

《电气自动化)2010年第32卷第1期 智能控制技术 基于改进蚁群算法的车辆路径优化火 VehicleRoutingOptimizationBasedonImprovedAntColonyAlgorithm 兰州理工大学电气工程与信息工程学院 (兰州 730050) 曹 洁 屈 展 (LanzhouUniversityofTechnology，LanzhouGansu730050，China) CaoJie QuZhan 摘 要：针对基本蚁群算法易陷于局部最优解及道路交通流易产生拥塞等缺陷，提出了～种改进蚁群算法。结合实时交通信息，以时间最 短建立了动态路径规划的 目标转换模型，应用改进蚁群算法求解车辆最短路径，对于求解过程中出现局部最优解，引入了随机蚂 蚁这一概念，同时基于Greenshields模型处理了正反馈 以及个体最优策略造成的拥塞现象。 关键词 ：路径规划 蚁群算法 动态路径规划 随机蚂蚁 拥塞 Abstract：Inthispaperanimprovedantcolonyalgorithm isproposedtoovercometheshortcomingsofthebasicantcolonyalgorithm，suchasthe trafficcongestionofroadtrafficflow，beingpronetofallintopartialoptimum andSOOil．A dynamicrouteplanningtargetconversion modelisestablishedwithreal—timetrafficinformationandtheshortest—timepath．Animprovedantcolonyalgorithm isappliedtofmdout theoptimum pathbasedonthemodelintheshortestpossibletimeaccordingtothereal—timetrafficinformation．Whenthelocaloptimum isappeared，astochasticantconceptisintroduced，andGreenshieldsmodelisusedtodealwithpositive~edbaekandcongestioncaused bylocaloptimum policy． Keywords：routeplanning antcolonyalgorithm dynanfierouteplanning stochasticant congestion [中图分类号】TP391．9 [文献标识码]A [文章编号]1000—3886(201o)ol一0038—03 随着人们对路径寻优问题的研究，提出了许多用以解决该类 为了解决正反馈以及个体最优策略造成大量的车辆 向最短路 问题的进化算法，如遗传算法、启发式算法、禁忌有哪些信誉好的足球投注网站法、模拟退火 径蜂拥而去，造成的全局劣等解，产生的拥塞现象。本文主要以旅行 算法等 “]。蚁群算法是意大利学者M．Dorgo，V．Maniezzo等人提出 时问最少作为规划准则，这样就可以很好地滤去道路的拥塞问题， 的，它是一种新型的模拟进化算法。用蚁群算法求解旅行商问题、 同时又兼顾了道路物理距离最短以及一些突发交通事件等信息|Sl。 分配 问题、调度问题 、指派问题等，均取得了一系列较好的试验结 2．1．1 拥塞的确定 果 】。如今 ，蚁群算法 已经成为一个备受关注的研究热点和前沿性 拥塞可以用描述速度 、密度 、车流量等交通参数的Green． 课题，本文尝试改进基本的蚁群算法，解决基本算法在求解最短路 shields模型来描述。 径中出现的问题，从而达到车辆路径的最优。 Greenshields模型如下 ‘卜p (