资源描述：
《并行蚁群算法在公交线网优化中应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第47卷第2期大连理工大学学报VOl.47,NO.22OO7年3月JOurnalOfDalianUniversityOfTechnOlOgyMar.2OO7=================================================================文章编号:1OOO-86O8(2OO7DO2-O211-O4并行蚁群算法在公交线网优化中应用于滨1,2,杨忠振2,程春田1(1.大连理工大学土木水利学院,辽宁大连116O24;2.大连海事大学交通规划研究所,辽宁大连116O26D摘要:针对实用有效的
2、公交线网优化模型很少的现状,提出了一个以直达客流密度最大为目标的公交线网优化模型.该模型以换乘次数最少~单位长度运送客流量最大为优化目标,线路长度~非直线系数等作为约束条件.为求解该模型,并综合考虑优化质量和通信开销,采用了基于粗粒度模型的并行蚁群算法.数值实验验证了模型及算法的合理有效.关键词:公交线网优化;直达客流密度;蚁群算法;粗粒度中图分类号:U491.1文献标识码:AO引言展到解决不均衡的TSP~@AP和job-shop调度问题中.为了克服在Ant-@中可能出现的停滞现城市公交线网设置得是否合理直接影响居民象,SttZl
3、e等[5]提出了max-min蚁群算法,称做出行所需的时间~换乘次数以及系统运行成本.MMAS.它对基本蚂蚁算法(ASD进行了3点改因此,国内外许多学者对公交线网的优化作了大进:D为了更加充分地进行寻优,各路径信息素量的研究.例如Ceder等[1]将三阶段法(出行分初值设为最大值Z一次循环后只有修改最max,@配~规划路径和发车间隔D引入到公交线网设计短路径的蚂蚁才进行信息素增加,@为了避免算中;~asselstro"[2]提出了一个两阶段同时优化路m法过早收敛于非全局最优解,将各路径的信息素线和频率的方法;王炜等[3]提出一个以
4、直达乘客浓度限制在[Z等[6]提出了min,Zmax].Gambardella量最大为目标的逐条布设~优化成网'的方法一种被称做~AS-@AP的蚁群算法,这个算法主等.本文以整体线网为研究对象,以出行者对公要的不同在于它直接修改解决方案.Botee等[7]交的需求为依据,方便居民出行为目的,并兼顾公对参数n~o~B~0的选择进行了深入的研究,用遗交企业的经营效益,建立一个以直达客流密度(单传算法求参数的最优组合.吴庆洪等[8]提出了具位长度运送的乘客数D最大为目标的公交线网优有变异特征的蚁群算法,在基本蚁群算法中引入化模型.变异机
5、制,充分利用了2-交换法简洁高效的特由于网络设计问题是一个NP-hard问题,使点.陈崚等[9]提出了一种基于分布均匀度的自适用传统的算法很难求解.大量的研究表明,模拟应蚁群算法,该算法根据优化过程中解分布均匀生物的启发式算法非常适合这种超大规模的优化度,自适应地调整路径选择概率的确定策略和信问题.蚁群算法就是利用群集智能解决组合优化息量更新策略.问题的典型例子.蚁群算法是受自然界中蚁群找蚁群算法研究的历史比较短,如面对规模较寻食物的行为启发而提出的一种基于种群的模拟大的实际问题它的搜索效率不高,因此还存在许进化算法.它属于随机搜
6、索算法,是由Dorigo多有待改进的地方.本文通过借鉴比较成熟算法等[4]提出的一种新型的优化算法.比较有代表性(并行遗传算法等D的经验,充分发挥蚁群算法的的蚁群算法的研究有Dorigo等[4]的研究,他们用内在并行性,开发并行蚁群算法来提高算法的求蚁群算法解决TSP问题,然后进一步把该方法扩解质量和搜索效率,从而求解公交线网优化模型.收稿日期:2OO5-O6-1O;修回日期:2OO6-12-2O.基金项目:国家自然科学基金资助项目(5O479O55;5O278O11D.作者简介:于滨(1977-D,男,博士生,E-mail:mi
7、nlfishyahoo.com.cn.212大连理工大学学报第47卷1公交线网优化模型2算法设计以直达客流密度(单位长度运送的乘客数)蚁群算法在优化公交网络时,首先初始化各最大为目标的公交线网优化模型如下,边的信息素分布,然后从起点释放出P只蚂蚁,出发寻找终点.在每一步中,每只蚂蚁移动一次,到PzjIzjzENjEN达下一节点.蚂蚁从相邻的~在该循环中没有被maxDOd=AghlghIgh其访问过的~且该路段含有一定的信息素的节点gENhENLmin{LOd{Lmax中,按照转移规则求得每一点的转移概率,来选择Sum下一节点.当所
8、有蚂蚁都找到终点,则一次循环@Od>@mingII结束,每条边上的信息素按更新策略更新.这样Od{gmaxbnn重复循环,直到所有的线路都布设完毕或者循环Od{bmaxklkl次数达到限值为止.S..<@Od<@max(1)Vlgh>0.5km2.
