基于蚁群算法的公交出行方案分析Word文件下载.docx
- 文档编号:737779
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:133
- 大小:2.58MB
基于蚁群算法的公交出行方案分析Word文件下载.docx
《基于蚁群算法的公交出行方案分析Word文件下载.docx》由会员分享,可在线阅读,更多相关《基于蚁群算法的公交出行方案分析Word文件下载.docx(133页珍藏版)》请在冰点文库上搜索。
111
ABSTRACT
Nowadays,thedevelopmentofpublictransithasbecomeoneofthemostimportantmethodstosolvethetrafficproblems,asthesituationofcongestionisgettingworsedaybyday.However,itisveryimportantforthepassengerstofindareasonabletripplaninthegrowingpublictransitnet.Anditisalsoanimportantpartofpassengerinformationsystem.
Onthebasisofresearchachievements,theresearchesaboutthepublictripplanand
relatedalgorithmsareasfollows.
Firstly,thestructureofurbantransitisstudied.Thecharacteristicsofconventionalpublictransit,railwaytransitandBRTtransitareanalyzedandcompared.Then,themathematicalmodelandtopologicalstructureofurbantransitnetworkarestudied.
Secondly,thegeneralizedcostofpublictransitisstudied.Basedontheinfluencingfactorsincludingtime,cost,transferandcomfort,thegeneralizedcostmodelandthepathoptimizationmodelareproposed.
Thirdly,thepathchoosingalgorithmisstudied.Basedonthealgorithmsthatexist,
theprincipleofantcolonyalgorithmisintroduced,andthenthesettingofinitializationandparametersareanalyzed.Afterthat,themethodtosearchthetransittripplanusingantcolonyalgorithmisputforward.Anexampleisgiven.
Finally,based011theresearchesabove,theurbanpublictransitsyStemisdesigned
andthetripplanbetweentwogivenstationsissearchedrealistically.
KEYWORDS:
PublicTransit;
GeneralizedCost;
TripPlan;
AntColonyAlgorithm
CLASSNO.-[U491;
图目录
图l本文研究的技术路线图.5
图2城市客运交通系统构成..6
图3具有6个节点的图示例11
图4同一线路两个方向上同名站点抽象成一点12
图5不同线路同名站点抽象成一点12
图6公交网络基本构成元素14
图7公交网络出行方案表示图15
图8公交网络拓扑关系图16
图9乘客出行心理因素分析18
图10基于换乘次数最小的公交最短路径算法.25图11双桥试验示意图27
图l2蚁群算法流程图.28
图13不同蚂蚁数量情况下最优Hamilton回路长度趋势33
图14不同蚂蚁数量情况下的CPU运行时间(ms)趋势33
图15不同启发信息系数的最优Hamilton回路长度趋势34
图16不同伪随机比例因子的最优Hamilton回路长度趋势35
图17不同局部更新系数的最优Hamilton回路长度36
图18不同蒸发系数的最优Hamilton回路长度37
图19算法主程序流程图一41
图20蚂蚁构建路径模块流程图.42
图2l算例网络.43
图22出行方案广义费用分布.46
图23广义费用随迭代次数的变化.47
图24系统功能模块.50
图25地图元素的基类一派生类的关系.5l
图26城市公交实体网络.53
图27添加公交逻辑线路.54
图28公交出行广义费用影响因素权重设置.54
图29输入查询起、终点.55
图30公交出行方案查询结果显示.55
表目录
表1公共交通特性对比分析表10
表2站点字段表15
表3线路字段表16
表4连接弧字段表16
表5需要考虑的初始化及参数设置3l
表6不同蚂蚁数量下Hamilton回路长度和运行时间。
32
表7不同启发信息系数下Hamilton回路长度。
34
表8不同伪随机比例因子下Hamilton回路长度..35
表9不同局部更新系数下Hamilton回路长度..36
表10不同蒸发系数下Hamilton回路长度37
表1l算法参数设置.39
表12算例线路表..44
表13算例中算法参数设置表..45
表14蚁群算法出行方案.45
表15Dijkstra算法最优方案。
47
表16基于换乘次数最小算法最优方案.48
学位论文版权使用授权书
本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。
特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。
同意学校向国家有关部门或机构送交论文的复印件和磁盘。
(保密的学位论文在解密后适用本授权说明)
学位论文作者签名:
南岛导师签名:
亲吁
签字日期:
2∞g年乡月/,眇同签字日期:
雳阳锣年舌月∥日
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得北京交通大学或其他教育机构的学位或证jfS而使用过的材料。
与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。
签字日期:
参劬9年参月一日
67
致谢
在北京交通大学求学的生活即将结束,回顾这六年来的点点滴滴,让我感慨万千。
大学生活不但提高了我的专业水平,而且启发和拓展了我对于做人、做事的一些新的认识和思考。
这些收获与很多人的关心和帮助是分不开的。
本论文的工作是在我的导师宋瑞教授的悉心指导下完成的,读研期间,宋老师不仅在专业学习上为我们传道解惑,更教会了我们学习和工作的方法与做人的品格,在此衷心感谢两年来宋老师对我的关心和指导。
在撰写论文期间,许旺土、林建新、赵航、安健、王保华、白惠涛、孙杨等同学对我论文中的很多研究工作给予了热情的帮助。
在此向他们表达我的感谢之情。
另外也感谢我的父母和亲人,由于他们的理解和支持使我能够在学校专心完成我的学业,我所取得的所有成绩都与父母的辛勤培养分不开。
1绪论
1.1研究背景
随着我国城市化进程的不断加快,大城市机动车保有量逐年增多,由此带来的交通拥堵、交通事故、环境污染等问题严重影响了我国城市的发展、人民群众生活水平的提高。
而在城市交通体系的构成中,公共交通相对于小汽车交通在占用道路空间、运输成本、能源消耗以及环境污染等方面都有相当明显的优势。
因此,公交优先已经成为世界上解决大城市交通问题的主要措施之一。
城市公交系统的不断发展,将会有越来越多的常规公交线路、快速公交线路和轨道交通线路,越来越多的人将选择公共交通作为主要的出行方式。
预计在2020年,北京市出行总量将达到5200万"
--'
5500万人次/日,而中心城区公共交通出行占客运出行总量的比例由2000年的27%,提高到50%以上,其中轨道交通及地面快速公交承担的比重占公共交通的50%以上【ll。
对于乘客来说,公交线路的增加固然可以带来更多的出行选择,但另一方面也给乘客出行带来了极大的困扰。
无论对于当地人还是外来人员在进行公交出行路线选择时都是很困难的。
因此,如何从众多的出行备选方案中找到一条从出发地到达目的地的从距离、时间、经济、换乘、旅行舒适度、安全性等多方面综合考虑的最优方案就显得尤为重要。
这里的最优方案建立在城市综合公交网络的基础上,并且不只局限于某一种交通方式,而是在城市综合交通体系下包括各种交通方式内部及不同交通方式之间换乘的方案。
因此,对于公交出行方案的研究可以在很大程度上解决乘客出行过程中遇到的实际困难,提高乘客的出行效率。
同时,对于推广公交优先政策、确定科学合理的公交管理体系和提高公交系统的效率也具有重要作用。
1.2研究现状
1.2.1公交出行广义费用理论研究现状
广义费用是指:
企业因生产经营活动和其它活动而发生的全部经济利益总流出。
广义费用应用到交通运输领域,多见于公路交通网络规划中,是基于网络规划中对于道路服务水平的一切属性的综合评价的需要。
公交出行广义费用一般从费用和时间角度出发,对可定量化表示的指标进行处理。
在理论上把广义费用定义为与道路服务水平有关的旅行时间和道路长度这两个属性的线性组合;
或者单纯将换乘次数作为乘客出行路径选择的主要因素,对一些重要的定性问题只作参考说明。
而往往一些定性影响因素对出行决策也起到很大作用,例如出行过程中的安全性、乘车舒适程度等,这些因素在以往评价时研究不够深入。
因此,对于公交出行方案的决策,需要一种能够综合反映出诸因素对方案比选的不确定性、模糊性,深刻地反映出各方案的优劣的方法,使定性问题定量化、定性与定量相结合来进行方案评价。
1.2.2路径选择算法国内外研究现状
对于道路交通网络两点间最短路径的搜索,目前已有上百种成熟的算法(最著名的就是D0ks仃a算法)。
但现有的最短路径算法一般不能直接运用于公交网络的路径选择中,因为公交乘客在出行的过程中不仅要考虑出行距离,还要考虑换乘次数、出行时间、乘坐安全性和舒适性等其它因素。
国外对公交出行路径选择算法的研究伴随公交客流分配的研究而发展。
AndersonJ提出了名为Volvo方法的公交路径选择算法,该算法将换乘次数少作为公交乘客出行路径选择的首要目标进行搜索【2】;
NicholasKoncz等提出了公交网络静态多路径优选的算法,并以换乘次数为主要约束条件进行路径选择研究,但该算法只能搜索一次及二次换乘的情况,而不能处理二次换乘以上的情况【3】;
Nguyen、DiM等结合出行策略理论、有效路径算法和超级网络理论,发展了基于超级路径和策略优化理论的公交网络有效超级路径搜索算法,该方法不需要枚举所有的出行策略,同时能够生成多条优选路径,但当两点距离较远时,该方法产生的“有效”路径过多,而其中很大部分是基本不被乘客考虑的路径【4】;
EH.LBovy等研究了在多模式运输网络中乘客选择出行路径的行为特征【5】。
随着一些城市公交乘客信息系统的建立,国内一些学者也开始对公交网络路径选择算法进行研究。
张国伍在扩展Floyd算法的基础上,提出了公交网络多条最短路径算法,该算法一次可以搜索出所有的站点间的多条最短路径,但在只需选择两点问路径的情况下应用效率较低嘲;
王祖祥等研究了公交网络中乘客换乘次数
最小约束下的最短路算法,并给出了多条路径集的生成技术【‘7】;
杨新苗等进行了公交乘客出行心理的调查,提出了以D0ks仃a算法为基础,以换乘次数最少为主要目标,以出行距离最短为次要目标的出行路径选择模型,但是对于影响公交出行的
其它因素并未进行研刭副;
近年来一些学者将现代启发式优化算法引入到该类问题
的研究中来,例如李文勇等使用蚂蚁算法求解公交出行路径选择问题【9】,但该研究
2
只是涉及到常规公交一种交通方式,不能有效表达不同方式之间的换乘,而且只是以最小换乘次数为约束,并没有综合考虑影响乘客出行的其它因素。
杨励雅等利用遗传算法进行了公交出行选择路径的研究【101。
此外,对于公交网络中两点间多条最优路径的选择是该类问题研究的另一个难点。
由于公交乘客出行路径选择心理的复杂性,往往单一的乘车路径并不能满足所有乘客的需要。
例如,一些乘客希望选择换乘次数最少的乘车路径,而另外一些乘客则倾向于选择出行距离更短的乘车路径。
因此,不能只为用户提供单一的出行方案,还应提供一定数量的合理各选路径供出行者根据实际情况进行选择。
Qi均i11wu等使用图论中K最短路径算法(KSP)求解公交网络中多条备选路径的
选择问趔11】,但KSP算法产生的多条路径往往过于相似,很难称是真正意义上的
备选方案。
近些年来,随着网络技术的不断发展,国内出现了很多公交查询的电子地图网站,如Mapbar、Bjbus、51ditu等。
已经可以为出行者提供丰富的出行信息,包
括:
显示城市的电子交通地图,同时具备放大、缩小、漫游等功能;
查询某条公
交线路的具体停靠站点;
查询给定起、讫站点间的最优公交线路(包括公交线路、换乘地点及换乘线路、经过站点)。
在这些功能当中,对于乘客来说最具意义的无疑就是查询给定起、讫点之间的出行方案。
而在实际应用中我们发现,由于系统采用的搜索算法不同、费用的计算方法不同,同样的出行问题在不同系统中得到的结果是不相同的,而且有些查询结果明显不合理。
综上所述,在目前的公交出行方案研究方面存在以下主要问题:
(1)主要以换乘次数为主要约束条件进行出行方案的研究,其它如出行距离、出行时问、安全性以及舒适性等因素考虑较少,而这些因素也是乘客出行必须考虑的,有时也是十分重要的。
(2)通常只是在一种交通方式下研究,对于包括常规公交、快速公交和轨道交通的城市综合交通系统下的公交出行方案研究较少。
(3)在算法研究方面主要以Dijkstra及其改进算法为主,由于该算法执行速
度较慢,而且在运行过程中不能考虑换乘次数,通常会出现两点问需要换乘很多
次才能到达的结果,而多次换乘在实际应用中是没有意义的。
1.3本文研究主要目标和内容
1.3.1研究目标
3
本文将在分析我国大城市公共交通构成及特点的基础上,对影响乘客出行选
择的因素及相关算法进行综合分析。
(1)分析乘客出行心理,考虑时间、费用、换乘、舒适性等影响因素,给出
城市综合公共交通体系下的出行广义费用模型和公交出行决策模型:
(2)研究目前存在的蚁群优化算法,针对城市交通网络的特点,确定算法的
初始化设置方法和各种参数的取值,并提出利用蚁群算法搜索公交出行方案的具体方法和步骤;
(3)结合理论研究进行城市公交出行查询系统设计,并实现用蚁群算法搜索出符合人们需要的出行方案。
1.3.2研究内容
全文分为六章,第一至四章围绕本研究的主要内容进行了理论分析,第五章是系统设计部分,最后一章是本文研究的总结和展望。
第一章为绪论部分。
主要阐述了有关公交出行方案的广义费用及路径搜索算法的研究现状,提出了本论文的研究目标、研究内容和研究思路;
第二章为城市公交系统构成及网络描述。
分析对比了目前我国大城市公共交通方式的构成和特点,分析了公交网络的特点,重点对公交网络的数学模型和拓扑结构进行研究;
第三章为公交出行广义费用及决策模型研究。
通过对乘客出行选择影响因素的分析,研究了公交出行的广义费用体系,并提出在常规公交、轨道交通和快速公交三种公共交通方式下的公交出行广义费用模型及乘客公交出行决策模型;
第四章为蚁群算法在公交出行方案问题中的应用研究。
这部分在研究已有算法的基础上,分析了蚁群算法的原理、特性及参数设置问题,提出新的初始化信息素和启发信息的设置方法,并通过实验的方式研究了参数大小对于算法结果及效率的影响,之后提出了利用蚁群算法搜索公交出行方案的方法及步骤,并结合算例进行具体分析。
第五章为城市公交出行查询系统设计及实现。
利用Vc++从底层开发城市公交系统,介绍了系统的主要模块及相关类的构成。
之后利用以上几章提出的理论和算法进行给定站点之间的出行方案生成。
第六章为结论部分。
总结本文所作的工作,并对存在的问题及今后的研究进
行展望。
本文的技术路线如图l所示。
4
理论部分
算法部分
-.一_
~应用部分
图l本文研究的技术路线图
Fig.1Technicalrouteofthisdissertation
5
2城市公交系统构成及网络描述
2.1城市公交系统构成及特点
改革开放以来,随着我国经济的快速发展,包括公共交通在内的城市基础设施建设投资有了巨大的增长,促使我国公交事业得到了前所未有的大发展。
一方面,常规公交车的发展在数量上和方便程度上有了极大的提高,但由于我国城市公共汽车长期以来过分强调“公益性"
,而忽视其“经营性”,在服务质量、时间性、舒适性和安全性等方面亟待提高。
另一方面,人们对于出行方式的选择越发多样化,近些年来大量建设的轻轨、地铁等交通方式无论在服务质量和安全、舒适性上都要好于常规公交。
同时,由于城市轨道交通具有投资大、建设周期长等特点,出现了一种介于常规公交与轨道交通之间的一种新的交通方式,即快速公交,它同时具有常规公交灵活性和轨道交通的快捷性。
从交通服务的对象来分,居民出行方式可以分为私人交通和公共交通。
公共交通方式主要体现在其为公众服务的性质,表现为服务对象的公众化和不确定性,一般是指常规公共汽(电)车、轨道交通和快速公交等;
私人交通方式主要体现在为特定个体服务的性质,表现为服务对象的个体化和确定性,一般指步行、自行车、摩托车和小汽车等。
因此,我国大城市客运交通系统组成中的出行方式结构如图2所示。
图2城市客运交通系统构成
Fig.2Structureofurbantransit
6
2.1.1常规公交系统
我们目前所说的常规公交一般包括普通公共汽车、电车和小公汽三种。
由于城市轨道交通系统投资昂贵、技术要求高、建设周期长,要成为城市客运交通的骨干还有一个过程。
因此,常规公交仍是目前我国城市公交的主要方式,为城市的中、低收入居民提供低价格的出行机会,在一般中、小城市几乎占据90%以上的份额,在大城市公共交通中比例也达到70%以上。
因此,常规公交的发展状况在很大程度上反映了一个城市的公共客运交通系统整体水平。
近年来,我国城市常规公共汽车得到了很大的发展,主要表现在公共汽车数量和营运线路长度的增长上。
在一些经济发达的大城市,公共汽车的线网密度已达到了相当高的程度,居民出行可步行5分钟到达公共汽车站,居民出行的二次换乘率逐年下降。
作为政府倡导的绿色交通方式,电车近年来在各大城市也得到了长足的发展,其营运旱程增长迅速。
在一些偏远的线路上,小公汽在很大程度上解决了市民的出行难问题。
但与此同时,私人小汽车交通迅速发展,大大增加了小汽车对路面使用的需求,加剧了道路交通的紧张状况,对于没有公交专用道路及优先通过权的常规公交影响严重,结果是常规公交车车速下降、正点率无法保障、失去了与小汽车等私人交通方式的竞争优势,导致私人交通出行比例增加、公交出行比例下降,呈现出某种恶性循环的状态。
常规公交系统具备下列主要特征:
(1)票价低廉
票价较低是常规公交同其它交通方式相比的优势,轨道交通票价一般为2—3元,而大多数常规公交的票价为l元左右。
如北京目前实行的公交一卡通制度,起步价成人票为0.4元,学生票仅为0.2元。
(2)服务范围广由于常规公交同轨道交通和快速公交相比,受行驶空间的约束较小,可以为
更大范围的乘客提供门到门的服务。
因此,常规公交也是其它交通方式接驳、供
给和延伸的主要方式。
(3)车速较慢
常规公交主要行驶在流量高的城市主要道路上,容易受交通阻塞的影响。
随着城市机动车保有量的逐年增加,常规公交的运营速度不断下降,高峰时段尤为明显。
上世纪50年代,常规公交的平均运营速度为25km/h左右,60年代开始下降,平均时速在20km/h左右。
目前,我国大城市常规公交运营速度仅为12。
18km/h[121。
7
(4)服务水平较低长期以来,服务水平低已经成为影响常规公交发展和人们选择其出行的重要
因素。
首先,在卫生、乘坐舒适性、服务态度等方面同其它交通方式确实存在较大差距。
其次,在线路上与其它车辆混杂行驶,易受交通阻塞和信号影响,正点率低,尤其是在高峰小时,准时性很难保证。
2.1.2轨道交通系统
城市轨道交通是大城市公共交通客运系统的骨干,是以大众化、大运量为特征的安全、舒适、快速、准时的交通方式。
它采用独立的专用轨道,高密度运行,为城市内部中长距离运输提供服务。
轨道交通系统具备下列主要特征:
(1)较大的运输能力
城市轨道交通由于采用了高密度的运转方式,列车发车间隔时间短,行车速度高,列车编组车辆数多,具有较大的运输能力。
单向高峰小时运输能力轻轨为l~4万人,地铁为4-6万人,市郊铁路可达6~8万人【131。
(2)较高的准时性城市轨道交通系统处于封闭状态,车辆在专用行车道上运行,不受其它交通
工具干扰,既不会产生拥堵现象,也不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 算法 公交 出行 方案 分析