




已阅读5页,还剩58页未读, 继续免费阅读
(管理科学与工程专业论文)基于免疫遗传算法的公交线网优化研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
大连理工大学硕士学位论文 摘要 城市公共交通是城市交通系统的重要组成部分,是连接城市居民工作、学习、休闲 等活动的纽带,对城市的发展、经济的繁荣起着十分重要的作用。改革开放以来,我国各 大城市在经济与城市建设快速发展的同时,城市人口迅速增长,对城市交通的需求日益 增加。由于城市交通基础设施建设速度落后于交通需求的增长速度,城市交通状况日趋 恶化,城市交通问题己成为制约城市发展的一个瓶颈。城市公交线网优化研究的宗旨在 于,在现有城市道路网络和公交运力的基础上,通过对城市公交线网进行合理布局,对现 有公交运力进行优化组合,最大程度地发挥系统的性能。因此,公交线网优化是解决大城 市交通拥挤、出行难问题的一项投资少、见效快、易于实施的有效措施。 基于这一背景,本文针对公共交通网络的设计需求,研究公共交通网络设计中的优 化问题,以便改善公共交通网络,提高公共交通的效率。 模型和优化算法是公交线网优化问题中最关键的课题。本文在对以往研究成果进行 综述的基础上,确定了以出行时间最小为目标,以线路长度、乘客换乘系数、非直线系 数和线路满载率为约束的优化模型,并根据最短路及驴最短路算法生成线路,结合生物 免疫行为特性,将改进的免疫遗传算法应用在公交线网优化过程中,并通过测试路网进 行验证。最后,对丹东市居民的出行特征以及公交现状进行分析,根据调查得到的居民 出行0 d 矩阵,利用t r a n s c a d 进行客流分配,根据客流分布情况对丹东市公交网络进行 适当调整。 本文提出的基于免疫遗传算法的公交线网优化算法可试用于调整公交线网规划。 关键词:公交规划;线网优化;t r a n s c a d ;免疫遗传算法 基于免疫遗传算法的公交线网优化研究 o p t i m i z a t i o no f t r a n s i tn e t w o r kd e s i g nb a s e do n i m m u n eg e n e t i c a l g o r i t h m a b s t r a c t u r b a i lt r a n s p o r t a t i o ni st h et i ef o rt h er e s i d e n tt oe n g a g ei nk i n d so fa c t i v i t i e si nd a i l y l i f e , i t p l a y sag r e a tr o l ei nt h ee c o n o m ya n du r b a nd e v e l o p m e n t w i t ht h ed e v e l o p m e n to ft h e u r b a nc o n s t r u c t i o n ,u r b a np o p u l a t i o ng r o w sf a s t ,w h i c hm a k e st h ed e m a n do fu r b a nt r a f f h c i n c r e a s em o r er a p i d l y b e c a u s eo ft h eu n b a l a n c eb e t w e e nt h es p e e do ft r a n s p o r t a t i o nf a c i l i t i e s c o n s t r u c t i o na n dt r a f f i cd e m a n di n c r e a s e m e n t ,t h es i t u a t i o no fu r b a n t r a n s p o r t a t i o n i s d e t e r i o r a t i n gd a yb yd a y ,w h i c hh a sb e c o m eab o t t l e n e c kr e s t r i c t i n gu r b a nd e v e l o p m e n t t h e o b j e c t i v eo fo p t i m i z i n gt r a n s i tn e t w o r ki st om a k eg o o du s eo ft h ee x i s t i n gt r a n s p o r tr e s o u r c e s a n di m p r o v et h ee f f e c t i v e n e s so ft r a n s i ts y s t e mb yo p t i m i z i n gt h et r a n s i tn e t w o r kl a y o u t o b v i o u s l y ,t r a n s i to p t i m i z a t i o ni sa ne f f e c t i v em e a s u r et h a tc o s tl e s sa n de a s i e rt oi m p l e m e n t b a s e do nt h ed e m a n do ft r a n s i tn e t w o r kd e s i g n ,t h er e s e a r c ho ft r a n s i tn e t w o r kd e s i g ni n t h i st h e s i si si n t e n d i n gt om a k et h et r a n s i tn e t w o r kb e t t e ra n di m p r o v et h ee f f i c i e n c yo ft h e p u b l i ct r a n s p o r t a t i o n m o d e la n do p t i m i z a t i o na l g o r i t h mi st h ec r u c i a lp a r to ft r a n s i tn e t w o r kd e s i g np r o b l e m , a f t e rs e r i e so fs u m m a r ya n da n a l y s i so ft h er e s e a r c hi nt h i sf i e l d ,t h i st h e s i sp r o p o s e sam o d e l t om i n i m i z et h et o t a lt r a v e lt i m eo fp a s s e n g e r s ,州t hr o u t el e n g t h ,n o n l i n e a rc o e f f i c i e n t , t r a n s f e rc o e f f i c i e n ta n dl o a df a c t o ra sc o n s t r a i n s r o u t e sw i l lb eg e n e r a t e da c c o r d i n gt ot h e s h o r t e s tp a t ha n dk s h o r t e s tp a t ha l g o r i t h m i m p r o v e di m m u n eg e n e t i ca l g o r i t h mi su s e dt o o p t i m i z et h en e t w o r k ,a n dt h em e t h o di st e s t e db ya l le x a m p l en e t w o r k ; f i n a l l y ,b a s e do nt h eo dd e m a n dm a t r i xt h a ti ss u r v e y e df r o md a n d o n gc i t y ,t h i st h e s i s a n a l y z e st h et r i pc h a r a c t e r i s t i c sa n dt h es t a t u so fp u b l i ct r a f f i ci nd a n d o n g ,a n dm o d i f i e st h e b u sr o u t e sa c c o r d i n gt ot h et r i pd i s t r i b u t i o nw h i c hi sd o n eb yt r a n s c a d k e yw o r d s :t r a n s i tp l a n n i n g ;n e t w o r ko p t i m i z a t i o n ;t r a n s c a d ; i m m u n e g e n n e t i ca t g o r i t h m l l 大连理工大学学位论文独创性声明 作者郑重声明:所呈交的学位论文,是本人在导师的指导下进行研究 工作所取得的成果。尽我所知,除文中已经注明引用内容和致谢的地方外, 本论文不包含其他个人或集体已经发表的研究成果,也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处,本人愿意承担相关法律责任。 学位论文题目:基王鱼瘗遗笾篡洼鲍金塞垡圆选焦盈究 作者签名:弓整厂囊色扯日期:二望措上月勺 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定,在校攻读学位期间 论文工作的知识产权属于大连理工大学,允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版,可以将 本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目: 作者签名: 导师签名: 大连理工大学硕士学位论文 1绪论 1 1研究背景 1 1 1 城市公共交通现状 城市公共交通是城市中供公众使用的经济方便的各种客运交通方式的总称【l j 。根据 中华人民共和国建设部颁布的城市道路交通规划设计规范,城市公共交通是指根据城市 发展规模、用地布局以及道路网规划,在客流预测的基础上,确定公共交通车辆数、 线路网络、换乘枢纽及场站设施用地等,使公共交通客运能力满足客流高峰的需求【2 j 。 广义的公共交通规划包括,在考虑公交系统与土地利用及整个城市发展关系的基础上, 制定公交系统目标与设计达到该目标的策略。城市公共交通是现代城市的动脉,是城市 活动中不可缺少的重要手段。作为一种生产力,公共交通与发展国民经济互相促进,起 着先行的作用,同时它与人民生活密切相关,担负着十分重要的使命。城市交通状况如 何,往往是衡量城市经济发展程度、科学技术水平、城市建设工作的重要标志【3 j 。 城市公共交通系统是与城市社会、经济、环境密切相关的、复杂的大系统,有着多 变量、多目标的特点。本文研究所指公交为公共汽车交通。 近年来,随着城市建设步伐加快,机动车保有量迅速增长,大城市基本上都在面临 着交通拥挤带来的各种问题。大力发展公共交通已成为公认的解决城市交通问题的根本 出路。针对我国目前的现状,公共交通的发展迫在眉睫,2 0 0 5 年9 月2 3 日国务院办公 厅转发了关于优先发展城市公共交通的意见d i , 其中明确要求:强化城市规划的指导 作用,确定城市交通发展的战略和目标,保证城市公共交通发展的用地需求。要认真 编制城市公共交通专项规划,明确各种公交方式的功能分工、线网及设施配置、场 站布局及规模等。 城市公共交通的核心问题,是交通网络的合理布局与车辆、资源的合理配置与调度。 而网络优化是公共交通系统工程的一个重要组成部分。对于任何一个城市的公共交通系 统,其网络布局的优劣是决定该系统品质的主要因素之一。 城市公交线网的规划与设计是一项复杂的工作,受到城市路网结构、客流需求、车 队规模、交通条件等各种因素的影响。但是,长期以来,城市的公共交通线路规划一直 是凭经验进行布设和调整的。作为有限的公共资源,公共交通系统在不断发展的过程中, 暴露出了一系列的问题,如运送速度低、行车准点率低、客流不均衡、运营效率不高等, 这些都导致了公共交通方式的吸引力逐渐下降,也刺激部分公共交通向私人交通( 自行 基于免疫遗传算法的公交线网优化研究 车、小汽车交通) 转换,从而使得本来就不合理的客运交通结构愈加不合理。因此,系 统地开展公交网络优化设计的研究具有相当的紧迫性。 1 1 2 城市公共交通的主要问题 我国各大城市目前所确立的公共交通发展战略基本情况如下:以公共汽车、电车为 主体,以出租车、轮渡等交通方式为辅助;以轨道交通为主骨架,以快速公交为辅骨 架。但是,由于公交网络的特性和交通的复杂性,人们对于公交网络设计问题的认识还 不够全面,定性的思考多于定量的分析,从而导致公交线网的规划与设计在各种层面还 存在很多问题和不足1 5 1 。 1 1 2 1 应用层问题 交通问题的本质是需求与供给不平衡,公共交通作为城市的基础设施,线网布设是 否合理,在很大程度上正是由需求与供给之间的不平衡导致的,具体表现在以下几个方 面: ( 1 ) 随着交通需求的增长,很多公共交通网络的运力无法与公众出行需求保持平 衡。一方面,许多城市公共交通服务在高峰期间营运能力不足,拥挤严重,而平峰期 间却出现运力严重过剩的情况;另一方面,许多城市都存在公交线路走向与客流主流向 不一致的情况。这样,城市的公交服务不仅不能满足乘客的出行需求,不能给公交运营 商带来更大的效益,还造成了资源的浪费。 ( 2 ) 目前对公交客流分析的方法过于复杂,很难揭示客流需求本质,进而致使网 络优化难以实现。公共交通客流分配是四阶段法的最后一步,也是最重要的环节,对于 公交现状的分析与评价,线网的布设,乃至公交线路未来客流预测等方面具有重大的 影响。公共交通线路、站点等的分析也都是基于客流分布展开的,研究接近现实的客流 分配方法己成为工程应用中的重要课题。 ( 3 ) 公交线路功能、规模及评价等依据不足。公共交通线路的设置与客流大小、 车队规模、道路及其交通条件等因素紧密相关,如何科学合理地确定线路走向及规模, 并对其进行评价,目前在工程上也尚无成型的方法。 1 1 2 2 理论层问题 公交网络规划与设计的理论方面主要存在如下几点不足: ( 1 ) 对于公交网络、线路以及站点的规划与设计大多处于定性和经验层面,缺乏 定量的理论支持。公交系统服务能力、公交车通行能力等基础理论研究虽然取得了一 定的成果,但在综合的一体化研究方面成果较少。 ( 2 ) 公交线网优化是多目标优化问题,而且线网优化的多个目标之间往往是冲突 大连理工大学硕士学位论文 的,如运营商对成本的追求与出行者对便捷性的要求等,传统的多目标优化方法不易实 现对其优化。 ( 3 ) 由于公交网络设计的决策变量具有离散特性,其优化约束条件对求解的合理 性、计算速度和效率都有很大影响,所以公交网络设计的求解算法有待于进一步开发。 1 2 研究目的与意义 1 2 1 研究目的 本文基于对公交网络的设计需求,研究公交网络设计问题,其目的主要体现在以下 几个方面: ( 1 ) 研究公共交通线路及站点等基本元素规划的问题,为改善公共交通网络,提 高公共交通的效率奠定基础; ( 2 ) 研究并分析公交线网优化所涉及到的优化目标和约束条件,为建立更好的优 化模型提供足够的理论依据; ( 3 ) 研究用于公交线网设计的优化算法,为线网优化提供优化效果更好的方法, 指导城市公共交通网络规划,为城市整体规划提供依据。 1 2 2 研究意义 目前我国正处在公共交通发展的关键时期,近年来关于公交线网优化设计的研究也 逐渐受到重视,虽然国外在这方面也有相应的研究,但由于出行者的出行习惯、道路条 件、交通条件等的差异,其规划、设计理论和经验与我国存在差异。因此,结合我国实 际情况,开展公交线网优化设计理论研究,在完善理论上以及实用价值上都将具有深远 意义1 5 j 。 ( 1 ) 理论意义 交通系统理论层面 研究公交系统在交通系统中的地位、作用,提出理想条件下的公交线路及枢纽网络 布局模式; 公交线网优化设计主要有方案改进型、方案生成型两种方法,通过对基本问题的分 析,有助于进一步完善工程应用和理论研究的方法体系; 方案生成型方案是基于线路优选、搜索进行公交线网优化设计的方法,这种方法对 简化公交线网优化设计过程、提高公交线网优化辅助决策具有重要意义; 研究公交线路规划的基本问题,形成更加实用的公交线网、线路、站点规划设计方 法与技术,可以为工程规划提供更加丰富的理论依据和决策支持; 基于免疫遗传算法的公交线网优化研究 数学优化方法层面 公交线网优化设计是一类组合优化问题,其解空间受路网规模的影响,会随着路 网规模的增大呈指数增长【6 】。研究证明:随着解空间的增大,局部最优解的数量会相应 的增加,从而导致增加问题求解的难度和精度。具体来讲7 1 1 8 】: 怎样设计合理有效的优化目标函数及约束条件; 进行线网设计时需要考虑相关的乘客及运营商的运营成本,这些因素会造成问题解 的非凸集与非线性; 线路设计的非连续性增加了组合优化问题的求解难度,属于n p h a r d 问题; 由于线网优化属于多目标优化问题,怎样对各种优化目标进行平衡。 很明显,这些问题已无法通过传统的优化方法完全解决,本文将在建立优化模型的 基础上,对优化设计的求解算法进行进一步研究,以保证理论模型的可行性和有效性。 ( 2 ) 实用价值 论文从公交线网的基本元素着手,从站点选择、线路生成两方面,研究方案生成性 公交线网优化设计,提出新的公交线网优化设计方法,以更好的辅助和支持公交系统规 划、管理决策人员制定运输系统整体效率更高的公交线网方案,实现对交通资源更好的 配置。 1 3 研究现状 从2 0 世纪2 0 年代,公交线网问题被首次提起【9 】,公交线网规划逐渐成为一个备受 关注的问题。随着研究算法的发展,国内外许多学者和机构对公交线网优化问题进行了 研究。 1 3 1 研究算法的发展 从传统的运筹学优化方法到智能算法,优化算法的发展在一定程度上促进了公交线 网优化设计问题的研究。 1 ) 传统算法 传统算法主要是指运筹学中的线性规划、整数规划、动态规划及分枝定界等方法, 由于算法的复杂性都比较大,所以应用范围比较有刚1 0 1 。 2 ) 遗传算法 遗传算法( g a ) 是一种基于生物和进化机制的适合于复杂系统优化计算的自适应 概率优化技术,通过对多个个体的迭代搜索逐步找出问题的最优解。由于遗传算法在应 用中展现出了简单通用、健壮性强、适于并行处理以及高效、实用的特点,逐渐成为重 一4 一 大连理工大学硕士学位论文 要的智能算法之一。 3 ) 模拟退火算法 模拟退火算法( s a ) 是基于m o n t ec a r l o 迭代求解策略的一种随机寻优算法,其出 发点是基于物理退火过程与组合优化之间的相似性。s a 由某一较高初温开始,利用具 有概率突跳特性的m e t r o p o l i s 抽样策略在解空间中进行随机搜索,伴随温度的不断下降 重复抽样过程,最终得到问题的全局最优解【l 。s a 的优点:通用、易实现、实验质量 高、初值鲁棒性强。同时,s a 也存在一定的缺点:要找到最优解,需要较高的初温、 较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样,这样会导致算法优化 进展缓慢,过程较长。 4 ) 禁忌搜索算法 禁忌搜索算法( t s ) 的基本思想就是在搜索过程中,将近期的历史上的搜索过程存 放在禁忌表中,防止算法重新进入,这样就有效的防止了搜索过程的循环。t s 是对局 部邻域搜索的一种扩展,是一种全局逐步寻优算法。与传统的优化算法相比,t s 算法 的主要特点是:( 1 ) 在搜索过程中更可以接收劣解;( 2 ) 新解不是在当前解的邻域中随 机产生,选取优良解的概率远远大于其他解。t s 也有明显的不足:( 1 ) 对初始解有较 强的依赖性;( 2 ) 迭代搜索过程是串行的,仅是单一状态的移动,而非并行搜索。 5 ) 蚁群算法 蚁群算法是2 0 世纪9 0 年代发展起来的一种模仿蚂蚁群体行为的智能化算法。该算 法引入正反馈并行机制,具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法 结合等优点。蚁群算法是一种通用型随机、分布式的优化方法,不仅适合当前的串行计 算机,而且适合未来的并行计算机;同时它是全局优化方法,不仅可以求解单目标优化 问题,而且,也可以应用于多目标优化问题的求解。当然,它也有缺点:初期信息素匮 乏,求解速度慢。 6 ) 混合算法 不同的优化算法在解决问题上有着独到的特点,同时也有一些自身的缺陷,通过算 法的结合,以长补短,便可提高性能。例如,蚁群算法的正反馈机制使其具有强大的局 部搜索性能,但其全局优化性的优劣在很大程度上与挥发系数的选择有关,如选择的不 合适则易使算法陷入局部最优,而禁忌算法则具有强大的全局优化性能,这样二者结合 起来,就会大大提高效率。 1 3 2 国外研究现状 关于公交线网优化的观点,最早由国外学者提出,对公交线网规划的研究国外也起 基于免疫遗传算法的公交线网优化研究 步较早。国外的研究可以分为三个阶段,第一阶段,6 0 年代初,这个时期,概念刚开始 形成,所采用的方法只是对布设公交线网应当遵循的原则进行了定义,很少使用量化的 分析。第二阶段,7 0 - 8 0 年代,主要运用系统工程和运筹学的相关原理、方法,在固定 的目标函数下对线网进行优化布设:第三阶段9 0 年代至今,各种优化算法被应用到线 网优化中。 l a m p k i n 和s a a l m a j l s 【1 2 】提出的优化模型是这样对线网进行优化的:首先,以乘客直 达率最高为目标,用一种基于骨架法的启发式算法产生路网,然后,考虑到出行时间、 车队和车辆容量,用一种随机的贪婪搜索算法制定发车频率。 s i l m a n 等【1 3 】也用了一种骨架法研究线网优化问题。在预算条件下,以出行时间和拥 挤度最小为目标。首先,选取路线终点,然后用最小路径法连接这些终点,并使连线尽 量经过不同小区,以获得最小的出行时间并限制线路长度为目标设计路网。然后,考虑 到车队大小,以降低出行时间以及拥挤带来的不便为目标进行发车频率设定。 d u b i o s 等人1 1 4 】采用启发式搜索方法建立了线网生成模型和发车概率确定模型,该 方法在进行发车频率方案的优化设计时,考虑了变需求情况的影响。 b a r r a 等【1 5 】提出一种约束满足模型,用1 1 种约束条件来定义问题。提出用c p 法( 过 程控制) 研究线网设计,由于c p 只能解决规模较小的案例,所以不能给出比较真实的 结果。但是,为寻求更好的结果提供了一种思路。 b 铡和m a h m a s s 砌【1 6 】提出了一种基于人工智能的线网优化方法,将线网优化分为 路径生成算法、线网分析过程以及路线改善算法三部分。 x i o n g ,s c h n e r d e r 1 。7 】提出了累计遗传算法,是对普通遗传算法的改进。此方法在处 理问题过程中收集非支配解集,并返回此解集。另外,运用神经网络替代旅客出行分配 算法来评估适值函数,以便得到更加准确的结果。 p a t t n a i k 等【18 】提出了一种基于遗传算法的方法。目标是尽量减少运营商的成本和乘 客的旅行时间,约束条件是车头时距。此方法首先产生一个候选路网,然后通过遗传算 法,从此候选路网中选择并确定路网。 m u r r y 1 9 j 用l o c a t i o ns e tc o v e r i n gp r o b l e m 和m a x i m a lc o v e r a g el o c a t i o np r o b l e m 建立模 型,缩减现有网络中的站点数量;然后考虑到服务范围的最大化,通过ah y b r i ds e t c o v e r i n gp r o b l e mf o r m u l a t i o n 模型,选择最优位置设置站点,扩展网络。特点可扩展服 务和可达性。 g u a n t 2 0 j 以城市轨道为研究对象,运用线性o 1 规划模型,用标准分枝定界法,试图 同时解决公交线路规划和乘客换乘问题。但是,由于在这个阶段,无法获得发车频率和 行车时刻表,客流分配不是很准确,从而影响了整个问题的求解效果。 大连理工大学硕士学位论文 1 3 3 国内研究现状 国内关于公交线网优化的研究始于8 0 年代,较早进行这方面研究的有吴稼豪等【2 , 对城市公共交通网络优化问题的模型和算法进行了比较系统的叙述;后来,各种算法 也相继应用到线网优化中,取得飞快发展。 刘清等提出一种广义的a 木算法,将所有满足约束条件的可行路线组成候选路网, 然后通过评价结果,确定最优路网。此方法灵活性及可扩展性比较高。 林柏梁等【2 3 1 基于组合优化,提出了优化公交网络设计的非线性0 一l 规划模型,以所 有乘客的出行时间和要实现公交网络的资金投入为费用目标函数,在满足车站容量限制 的条件下,最小化目标函数获得公交线路。 王志栋【2 4 1 建立了多目标数学模型,选取一个最主要的目标作为方程的目标函数, 并将其它目标函数作为约束条件来考虑,这样,多目标规划问题就转换成了单目标规划 问题,然后采取相应的方法将非线性目标函数及约束转换成线性函数。 韩印等人【2 5 】提出城市公交线网调整优化的p o s 算法,通过逐条预选与搜索的方法优 化成网。 单连龙、高自友【2 6 1 根据城市公交网络的具体特点,提出一个双层规划模型来描述连 续平衡公交网络设计问题。上层模型为一个标准的公交网络设计模型,下层模型是一个 公交网络平衡配流模型,并设计了基于灵敏度分析的求解算法。该方法的缺点是在进行 公交客流分配时未考虑公交线路的共线、线路通行能力限制等问题,优化效果与实际差 别比较大。 王炜2 7 1 提出一种采用“逐条布设,优化成网 的思想进行线网优化,这种方法以直 达客流量最大为目标。 刘好德,杨晓光【6 j 提出一套基于路线优选的方案生成型公交线网优化设计方法,该 方法以出行时间最小,需求满足率最大为目标。 邬开俊等网在利用蚁群算法进行优化求解过程中,提出一种以图论中的支撑树来表 示问题解的方法,该方法避免了公交线网的辐射型检查,将算法的搜索域限定在可行解 域,从而改善了蚁群算法的搜索效率。 1 4 研究内容与结构 1 4 1 研究内容 本文在总结国内外相关研究的基础上,结合我国城市公交线网存在的问题,以实现 基于免疫遗传算法的公交线网优化研究 社会总出行时间最小为目标,研究城市公交线网的优化方法及模型。 1 在界定研究内容及提出进行公交线网优化的原则的基础上,对公交线网优化的各 种目标及约束条件进行总结,并以出行时间最小为目标建立了优化模型。 2 提出了影响公交线网优化的因素及公交线网优化的思路,探讨了公交线网优化的 方法,介绍了解决优化问题的各种方法和算法。 3 根据最短路及驴最短路算法生成线路,结合免疫行为特性,将遗传算法应用在公 交线网优化中,并通过测试路网进行了验证。 4 根据提出的城市公交线网优化模型和方法,在对丹东市公交客流分析的基础上, 利用免疫遗传算法对丹东市的公交线网进行了优化分析。 1 4 2 技术路线 论文基于系统最优化的观点,运用系统工程学、交通工程学和运筹学、最优化理论 及数值分析等手段,建立了一套比较合理的、效果明显的公交网络优化设计的基本理论 和技术方法。具体的技术路线如图所示。 大连理工大学硕士学位论文 栅觥吵 相关理论研究相关应用现状 1 0 公交线网优化内容和目标 j 交需求规j d 交通o d 数据 交通,、区划分 i 公交出行分布 公交出行分担 i - j约束条件限制 最终优化线网 增加补充线路 y 图2 1 逐条布设线网优化技术路线图 f i g 2 1 t e c h n i c a ll i n eo fl a y i n go u tn e t w o r ko n eb yo n e 1 6 一 确 定 骨 架 线 网 确 定 基 本 线 网 确 定 补 充 线 网 i川ijliiiliiljlij 大连理工大学硕士学位论文 2 5 公交客流分配方法 交通分配是将各交通小区的o d 需求量分配到网络中的每条线路上,并求出每条线 路上的交通量。通常,交通网络中的每个o d 对间可能存在多条可行路径,交通分配就 是为了解决如何将交通流合理地分配到各条线路上的问题1 3 3 】。 按模型的行为原理划分,交通分配模型可分为如下类型【3 4 】。 图2 2 交通分配模型的分类 f i g 2 2 c l a s s i f i c t i o no ft r a f f i cd i s t r i b u t i o nm o d e l s 公交客流分配有非均衡和均衡两类方法,两种方法的不同之处在于非均衡类方法通 常不考虑交通拥挤造成的车辆停靠延误以及线路运输能力的限制。 ( 1 ) 非均衡类公交客流分配 全有全无分配模型:此类模型的前提是路网具有足够大的运能,流量增长不会 对阻抗产生影响,出行者总是选择最短路径作为出行线路。这种模型只是适合 应用于两点之间出行需求相对较少的状况。 多路线概率分配模型:前提是不考虑公交运输能力和拥挤的影响,根据不同的 可选线路的出行费用,按比例分配公交客流。 优化策略:前提是不考虑公交运载能力,此方法不考虑竞争路段的相对出行时 间,根据线路发车频率按比例分配客流。 路径搜索:前提是不考虑公交运载能力,与类似,此方法以减少候车时间为 目的,根据发车频率按比例分配。 基于免疫遗传算法的公交线网优化研究 ( 2 ) 均衡类公交客流分配模型 公交线路的运载能力是有限的,当发生拥挤时,乘车舒适度会下降,无法保证所有 乘客上车。当发生这些情况时,均衡类公交客流分配采用引入惩罚函数的方法来保证优 化效果。 均衡类公交客流分配模型在计算出行成本时,加入了惩罚函数,使得乘客的出行 费用更加逼真。此方法中的线路选择是基于出行者的离散选择行为进行的,在存在多条 可选公交线路的情况下,即使最优的公交线路没有达到饱和,出行者也会以一定概率随 机选择一条可选线路作为出行路线。 表2 1 是公交客流分配各类模型的对比情况。 表2 1公交客流分配基本模型汇总 t a b 2 1 s u m m a r yo ft r a n s i td i s t r i b u t i o nm o d e l s 类型 子类方法特点适用 非 单路径全有全无分配单从乘客个人意愿出发 无出行路径上公交行程 平 程时间等信息的环境 挤衡 多路径概率分配 考虑个人意愿与出行路有出行路径上公交行程 非 多路径 径公交通行情况时间等信息的环境 考虑个人意愿与出行路有出行路径上行程时间 拥 l o g i t 概率分配 径公交通行情况等信息的环境 平 考虑个人意愿与出行路 衡 约束分配模型径公交通行情况,并考 距离、时间代价信息完整 虑容量限制的均衡模型 的i t s 环境 拥 即使容量不是问题,也距离、时间代价信息完 挤 随机用户均衡在o d 间选择最合理路整、精确、实时的i t s 径 ( a p t s ) 环境 随着研究的深入和各种因素的影响,公交分配问题己不再是一个单纯的问题,而是 逐渐形成一个系统【3 5 】。 大连理工大学硕士学位论文 3 公交线网优化设计模型 3 1 公交线网优化设计模型 3 1 1 基本假设 公交线网优化设计就是在特定优化目标的基础上选择线路并最终形成网络的过程, 为了提取并简化问题,本文进行如下假设: ( 1 ) 假设需求( o d 数据) 是固定的; ( 2 ) 假设系统中所有线路的公交车辆行驶速度固定,本文设为2 0 k m h ; ( 3 ) 假设所有车辆载客能力固定; ( 4 ) 假设出行者可以在任意公交站点换乘。 通常情况下,可以将公交出行者在一次出行过程中( 由产生点f 到吸引点,) 的路径选 择分为三种情况【3 6 】: 1 ) 直达:直接由产生点f 到达吸引点,表示为f 一,; 2 ) 换乘一次:经由站点k 中转完成出行,表示为f 一研: 3 ) 换乘两次:经由站点毛和毛中转两次完成出行,表示为f 一毛一毛一,。 通常,乘客在出行时可以容忍的最大换乘次数为2 次,因此本文假设出行者在一次 出行中最多换乘2 次。并将出行者的公交出行分为具体细分为如下三类 3 , 3 7 1 : ( 1 ) i 类公交出行:直达线路,即o 次换乘+ o 次长步行,表示为“0 + 0 。 ( 2 ) i i 类公交出行:通过一次换乘或通过一段长距离步行然后直达。 1 次换乘+ 0 次长步行:表示为“1 + 0 ; 0 次换乘+ 1 次长步行:表示为“0 + 1 。 ( 3 ) i i i 类公交出行: 2 次换乘+ o 次长步行:表示为“2 + 0 ; 1 次换乘+ 1 次长步行:表示为“1 + 1 ; 0 次换乘+ 2 次长步行:表示为“0 + 2 。 3 1 2 目标函数模型 公交线网优化目标主要分为系统最优、用户最优,包括出行时间、费用成本等。本 文主要考虑以乘客出行时间( 主要包括步行时间,等车时间,乘车时间三部分,还可能 包含换乘时间和长距离步行时间) 最小为目标,建立公交线网优化目标函数: 基于免疫遗传算法的公交线网优化研究 一 m i n 【,七( t ,o ) = 【0 ;! 蟛( t ) 】 ( 3 1 ) i , j = l ,i j 其中: 嘴( 丁) 一路网t 终结点f ,之间出行时间; q o d 需求矩阵; 七一换乘系数。 按照3 1 1 中公交出行分类,磴( 丁) 可以表示为: u ( 丁) = 互i ) + 夏j 1 ) + t i i i ) 约束条件: 线路长度:5 乞1 5 , 非直线系数:车1 4 线路满载率:q q 圳5 昂一l ,+ 2 毋一l f + 3 v 2 一l 乘客换乘系数: a 弓 妒 1 5 车队大小:“ 其中: 乞一线路g 的长度( k m ) ; 吒一线路起讫点间空间直线距离( k m ) ; q 口一线路g 上的最大客流; q m 双一线路通行能力; 么一站点数量; 昂一扩,毋一l ,b - j 一从公交站f 到歹的直达人数,1 次换乘人数,2 次换乘人数; ,一线路g 上的车队大小; 一可分配到线路g 上的最大车辆数目。 ( 3 2 ) 大连理工大学硕士学位论文 3 2 线路生成算法 公共交通网络是由公交站点和站点间的路段组成的。优化路网的过程就是从所有可 行的线路集合中选择最优的线路组成最终的网络,所谓的所有可行线路集合就是所有连 接起讫站点的线路集合,可以视为全解空间,而通过特定的优化算法得到的公交线网候 选线路集合即为解空间。 3 2 1 起讫点选择 交通小区的乘客运送是由经过该交通小区的公交线路完成的,如果交通小区高峰时 段的乘客产生量超过经过该区线路的站点的运载能力之和,那么该区需要设置公交线路 的起讫站点。因此,可根据交通小区中间站点的运载能力设置起讫站点,当某交通小区 的交通产生量超过站点运载能力时,就认为需要设置起讫站剧3 引。 在进行起讫站点的选择时,可以根据以下三个条件: ( 1 ) 按公交需求分配量选择。如果一个交通小区的公交产生量超过该区内所有站点 的运载能力之和,那么考虑在此小区设置公交起讫站点。 站点的运载能力为: s = b * 6 0 h j ( 3 3 ) 其中: b 一高峰小时平均每车从站点搭载的乘客数; 忽一高峰小时发车间隔。 起讫站点的运载能力( 人次高峰小时) 为: c o d = 6 0 r r ( h a ) ( 3 4 ) 其中: 尺一公交车额定载客数( 铰接车为1 2 9 人,单节车为7 2 人) ; ,一高峰小时满载率,取o 8 5 ; 忽一高峰小时发车间隔; t 一线路上最大断面流量与起讫站点的断面流量之比,k o = 1 5 2 0 。 若某交通区舶总发生量( 或吸引量) z 超过该交通区的中间站点运送能力s ,其超 过量为z = 巧- s , ,则当( 七一0 5 ) c d d d f i c 。t h e n b e g i n d od i s t a n c eu p d a t e d 3 d 码a n dp r e d t j ) := t ; e n d e n d e n d 图3 1 d i j k s t r a s 最短路算法伪码 f i g 3 1 p s e u d o c o d eo f d i j k s t r a ss h o r t e s ta l g o r i t h m 3 2 2 2 卜最短路算法 在优化公交线路过程中,为了服务更多的客流,需要同时运用卜最短路算法生成部 分候选线路集,以增加线路优选的空间。 y e n 4 2 在1 9 7 1 年就提出了卜最短路算法,其算法的最大特点是描述简单、容易实 现。其主要过程可以描述如下: 第一步,基于最短路算法寻找两点间的最短路径; 第二步,将所有最短路分为两段,在起讫点之间任选一点作为截点,并且保证所有 非起讫点都被选取一次。起点至截点路径作为第一段,截点至终点路径作为第二段。 对于第二段路径应满足两个条件: ( 1 ) 不能是环路,且不能完全通过已经包含在最短路径中的节点; ( 2 ) 不能完全通过此前已经找到的驴l 短路。 涉及到的卜短路算法的数学符号: f 一网络节点编号,i = i ,2 ,n ,1 为起点,为终点; l f 一,f j l 一从l 到胸一条无环路路路径; m 一第七短路包含的节点个数; 饼一第七短路的第价节点: 大连理工大学硕士学位论文 a 。= 1 一鹾一鳞一醢一。一,k = 1 ,2 ,k 一从1 到的第尼短路; 彤_ 爿2 的第一部分,从节点1 到第r 个节点f 与第k - 1 路御卜1 相同部分; 酽一组腑的第二部分路段。 驴最短路算法描述如下: a l g o r i t h mk - s h o r t e s tp a r t h ; b e g i n - 基于d i j k s t r a :s 算法搜索最短路= 1 一g gi j ld g :一、- ,k _ - 1 72 ,足 储存到a 集合 j 睁1 ; 胼尼; 一x i l e 犯k b e g i n 卢p 1 f o re a 幽f = l ,2 ,3 ,( t 一1 ) 血 检查由岔t 的前f 个节点组成的子路径是否为a ( j = l ,2 ,卜1 ) 的子路径,如 果是,令厦- - 0 3 ,口为止的廿1 个节点;否则无变化 应用d i j k s t r a :;算法搜索从第f 个节点g 到j i i r 的最短路1 至f jq :的路径为霉,g 到的路径为p 组合z ? 与p 作为f 到集合且 搜索口集中最短路径,从口中移除并加入a 集,保瞽口集其他元素; e n d e n d 图3 2k 最短路算法伪码 f i g 3 2 p s e u d o c o d eo fk - s h o r t e s ta l g o r i t h m 起讫站点及候选线路确定之后,计算每条候选路线的目标函数值出行时间,进 一步缩小搜索的解空间。 3 3 公交客流分配方法 3 3 1 公交客流分配假设与前提 本文在选择公共交通线路出行时,以用户最优( u o u s e r s o p t i m a l ) 为原则。 公交客流分配主要包括:公交出行路径的选择和公交客流在路径上的分配。进行如 下假设: ( 1 ) 出行者总是按到达目的地所需的换乘次数最少的目标选择线路( 即按i ,i i ,i i i 类出行的顺序选择) ; ( 2 ) 存在同类出行路径的情况下,出行者只选择最优路径; 基于免疫遗传算法的公交线网优化研究 ( 3 ) 如果存在多条同类出行线路,以最短路出行时间的一定百分比( 本文定为1 2 0 ) 为上限。 3 3 2 公交客流分配过程 公交客流分配受公交线路的影响,如果起讫站点之间没有直达线路,那么乘客的出 行路径可能是由多条线路组合而成,按照3 1 - 1 中提到的路径分类方式与假设条件,公 交出行路径搜索及客流分配流程如图3 3 所示。 图3 3 公交出行路径搜索及客流分配过程 f i g 3 3 p r o c e s so fp a t hs e a r c h i n ga n dt r i pd i s t r i b u t i o n 大连理工大学硕士学位论文 3 3 3 公交出行路径搜索与客流分配 根据3 3 1 假设,搜索不同模式的公交出行路径并计算各路径的出行时间;同时将 客流分配到路径上。 3 3 3 1i 类公交出行 对于一个o d 对( f ,d ,令魍表示所有经过韵公交线路,r s ,表示经过,的所有公 交线路,公交客流分配模型检查两组线路集r s 与尺s ,的交集,如果尼霉n r s j g ,说 明存在同时经过f ,的线路,即可提供直达公交线路。 如果存在多条线路满足r s , n r s j ,那么选择不同线路的客流量为: c m = 芝吒 慨的 m2 赢吒 的 ,e 鹪n r 岛 其中: 乙一出行者的全程时间; 如一选择线路七的客流量。 此类出行的出行时间表示为: 乃= 2 t w a 豇q - t w a f f + ( 3 6 ) 如果r s , n e 3 ,= a ,则两个小区间没有直达线路,转入下一类出行模式进行搜索。 3 3 3 2i i 类公交出行 如果小区形心厶,之间没有直达线路,那么察看出行者能否通
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高级文秘类:武汉律协面试题库精 编职位资料库
- 生理学课程讲解
- 甘肃省宁县二中2026届化学高三第一学期期中达标测试试题含解析
- 体检项目病症解读
- 采购主任中层岗位竞聘动态
- 无血清培养技术
- 血液病抗菌药物临床应用指南
- 2026届北京市西城区北京市第四中学化学高一第一学期期中预测试题含解析
- 涉税资料管理规定解读
- 细胞示踪技术研究进展
- 全国中学教师《初中数学》说课教学比赛-主题:《等腰三角形的性质》说课-一等奖课件
- 回顾长征路课件
- 为什么你的学生不思考?主题班会分享
- 医疗废物交接登记表(诊所、医务室、卫生所等)
- 气雾培技术行业市场突围建议书
- 2025届云南省施甸县第一中学物理高一下期末学业水平测试试题含解析
- python程序设计-说课
- ISO15614-1 2017 金属材料焊接工艺规程及评定(中文版)
- 学生床上用品采购投标方案(技术方案)
- 2023年河南省中考数学试卷及答案
- 热力公司招聘考试笔试真题
评论
0/150
提交评论