资源描述：
《第10卷第4期辽宁工程技术大学学报(社会科学版)vol10》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第10卷第4期辽宁工程技术大学学报(社会科学版)Vol.10,No.42008年7月JournalofLiaoningTechnicalUniversity(SocialScienceEdition)July2008“集合燃烧”算法在公交网络查询中的应用1112王,于丽娜,郑保华,闫心丽(1.沈阳药科大学药学院,辽宁沈阳110016;2.沈阳药科大学基础学院,辽宁沈阳110016)摘要:针对如何快速查找满足乘客不同需求的最佳路线问题,提出了可以快速查找最优路线的“集合燃烧”算法。以北京公交车线路网为例,使用Matlab编程实现了“集合燃烧”算法。与其他
2、传统算法相比,此算法处理信息量更大,运行速度更快。“集合燃烧”算法还可用于处理其他需更换交通方式的路线决策问题。关键词“:集合燃烧”算法;公交网络;最优路线;Matlab中图分类号:TP301.6文献标识码:A文章编号:1008-391X(2008)04-0380-03“Aggregate-combustion”arithmeticanditsapplicationinthequerysystemoftransitnetwork1112WANGFangyang,YULina,ZHENGBaohua,YANXinli(1.PharmaceuticsCol
3、lege,ShenyangPharmaceuticsUniversity,Shenyang110016,China;2.BasicCollege,ShenyangPharmaceuticsUniversity,Shenyang110016,China)Abstract:Foranytransitnetwork,thecoreissueofquerysystemishowtofindthebestpathquickly.Thisarticleabstractsanempowermapwhichincludestransitimpedanceinforma
4、tion.“Aggregate-com2bustionarithmetic”,basedonthematrixofthemap,canbeusedforthesearchforthebestpath.WeuseMatlabtosearchforthebestpathintransitnetworkofBeijing.Incomparisontootheralgorithms,theresultcanbefiguredoutmorequicklywithmoreinformation.Itisalsousefulfor“aggregate-combus2
5、tionarithmetic”tosolveotherdecision-makingproblems.Keywords:“aggregate-combustionarithmetic”;transitnetwork;bestpath;Matlab对于城市公交网络,如何快速查找最佳路线是费用等因素。也有文献报道用“燃烧”算法解决这类公交查询系统的核心问题。在处理该问题时,往往问题,该算法由起始点依次求出直达、一次转乘、二将整个公交网络抽象为一个有向赋权图,认为公交次转乘的站点并将这种逐层扩散的算法形象的称为网络最优分析同其他网络分析一样,是以最短路为“燃
6、烧”,每一次“燃烧”后比较终点站是否在这些站[2]基础的最优路线查找。但这种思路在实际操作中存点中。在这种“燃烧”算法的基础上进行改进,设在两个问题:第一,公交网络最短路所利用的Dijk2计了“集合燃烧”算法。利用这种算法可同时由起点stra算法编程实现较为困难,因为对于通常采用的和终点依次得到直达站点集合、可供一次转乘的车最短路径算法(Dijkstra算法)来说,它建立在以总次集合、一次转乘能到站点集合等信息,每“燃烧”一站点数为维数的邻接矩阵上,算法的时间复杂度为次判断起、终点的“燃烧”范围是否有交集,并比较可[1]维数的三次方,对于越来越庞大的城
7、市公交网络行路线的公交阻抗,最后求出最优路线。这种算法系统,这种算法耗时长,占用内存量大;第二,公交网未见文献报道。以北京公交车线路网为例,使用络最优分析同一般网络分析相比有很大差异,人们Matlab编程实现了“集合燃烧”算法,与其他传统算在选择路线时不可能仅以路线最短或某一种加权路法比较,此算法的优点在于其处理信息量更大,运行线最短为选择标准,而应以转乘次数结合路线上的速度更快。公交阻抗为指标。公交阻抗主要包括路线的耗时、收稿日期:2008-03-01作者简介:王(1988-),女,安徽阜阳人,主要从事应用数学研究。第4期王,等“:集合燃烧”算法在公
8、交网络查询中的应用3811公交网络信息的矩阵描述表以A(B)为引燃点的一次燃烧站点集合,燃烧经
