（交通运输规划与管理专业论文）基于线网结构的公交协同研究.pdf

c o l l a b o r a t i v eb a s e do nt h es t r u c t u r eo fp u b l i ct r a f f i c n e t w o r k b y che nx i a b e ( c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n t r a n s p o r t a t i o np l a n n i n ga n dm a n a g e m e n t l n c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y s u p e r v i s o r p r o f e s s o rh u a n g z h o n g x i a n g m a y ，2 0 1 1 k j 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全 意识到本声明的法律后果由本人承担。 作者签名： 侈c 冢 日期：咖，年j 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究 所将本论文收录到中国学位论文全文数据库，并通过网络向社会 公众提供信息服务。 本学位论文属于 1 、保密口，在一年解密后适用本授权书。 2 、不保密四。 ( 请在以上相应方框内打“ ) 作者签名： 陟霞 日期：0 2 9t - 年j 月玎日 导师签名，删日期：年，月玎日 摘要 本文从两个方面围绕公交线网的协同展开研究。一是从时刻表的角度 出发，通过以公交线网上同步车辆最大为优化目标，构建时刻表模型；二 是从线网动力学的角度出发，提出要实现公交线网上同步流形稳定，需要 完成的工作。公交协同调度时刻表编制的问题属于复杂组合优化问题，因 此，本文首先系统地介绍了复杂组合优化问题的定义及其求解方法，详细 地介绍了遗传算法；然后从单线公交调度和线网协同调度两个方面介绍了 公交调度的主要工作。 基于以上准备工作，首先从公交线网结构层面上提出了换乘点的换乘 权重系数，建立了时刻表模型，并设计了遗传算法验证了该模型的有效性。 由于公交线网上车辆的同步不仅与发车时刻表有关，还与线网的结构相关， 本文又进一步构建了公交运行网络的车辆状态方程，并验证了公交运行网 络的车辆运行的动力学行为属于时滞动力学网络的离散模型。 关键词：协同调度；公交时刻表；换乘网络；遗传算法；同步；动力学； 状态方程 a b s t r a c t i nt h i sp r o je c t ，t w oa s p e c t so fas t u d ya r o u n dt h ep u b l i ct r a n s p o r t a t i o n n e t w o r ko fc o l l a b o r a t i o n f i r s t ，f r o m t h e p e r s p e c t i v e o fs c h e d u l e ，o n s y n c h r o n i z e dt r a f f i ct h r o u g ht h el a r g e s tp u b l i ct r a n s p o r t a t i o nn e t w o r ka s t h e o p t i m i z a t i o ng o a l ，b u i l d i n g s c h e d u l em o d e l ；t h es e c o n d l i n eo fn e t w o r k d y n a m i c sf r o mt h ep e r s p e c t i v eo fp u b l i ct r a n s p o r t a t i o nn e t w o r kp r o p o s e dt o a c h i e v es t a b i l i t yo nt h es y n c h r o n i z a t i o nm a n i f o l d ，n e e d st ob ed o n ew o r k b u s s c h e d u l e sp r e p a r e db yt h ec o l l a b o r a t i v es c h e d u l i n gp r o b l e m sa r ec o m p l e x c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m ，t h e r e f o r e ，t h i sp a p e rs y s t e m a t i c a l l y i n t r o d u c e st h ed e f i n i t i o no fc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n d i t ss o l u t i o nm e t h o d ，g e n e t i ca l g o r i t h mi sd e s c r i b e di n d e t a i l ；a n df r o mt h e s i n g l e b u ss c h e d u l ea n dr o u t en e t w o r kc o o p e r a t i v es c h e d u l i n gi n t r o d u c e dt h e t w om a i nb u ss c h e d u l i n g b a s e do nt h ea b o v ep r e p a r a t i o n s ，t h ef i r s tl e v e lf r o mt h ep r o p o s e dt r a n s i t n e t w o r ks t r u c t u r e ，t h et r a n s f e rp o i n to ft h ew e i g h tt r a n s f e rc o e f f i c i e n t ，t h e e s t a b l i s h m e n to fas c h e d u l em o d e la n dg e n e t i ca l g o r i t h mi sd e s i g n e dt ov e r i f y t h ev a l i d i t yo ft h em o d e l s i n c et h es y n c h r o n i z a t i o no fv e h i c l e so nt h ep u b l i c t r a n s p o r t a t i o nn e t w o r k n o to n l yw i t ht h ed e p a r t u r es c h e d u l e ，b u ta l s o o n n e t w o r ks t r u c t u r er e l a t e dt of u r t h e rb u i l dt h i sn e t w o r ko fp u b l i ct r a n s p o r t v e h i c l e sr u n n i n ge q u a t i o no fs t a t ea n dv e r i f yt h eb u sr u n n i n gt h en e t w o r k d y n a m i cb e h a v i o r o fv e h i c l e sa r er u n n i n go nt i m et h ed i s c r e t em o d e lo f d y n a m i cn e t w o r kl a g k e yw o r d s ：s y n e r g i s t i cs c h e d u l i n g ；b u ss c h e d u l e ；t r a n s f e r n e t w o r k ； g e n e t i ca l g o r i t h m ；s y n c h r o n i z a t i o n ；d y n a m i c s ；e q u a t i o no f s t a t e h 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 引言l 1 1 1 研究背景1 1 1 2 课题研究来源2 1 2 研究意义2 1 2 1 理论研究意义_ 2 1 2 2 现实研究意义3 1 3 研究的历史与现状3 1 3 1 公交线网协同调度研究3 1 3 2 公交线网结构5 1 4 研究内容与技术路线6 1 4 1 内容6 1 4 2 技术路线7 第二章复杂组合优化问题及其优化算法 2 1 组合优化问题的定义和复杂性计算9 2 1 1 组合优化问题定义9 2 1 2 复杂组合优化问题的计算复杂性1o 2 1 3 复杂组合优化问题的优化算法10 2 2 遗传算法1 1 2 2 1 遗传算法的数学理论1l 2 2 2 遗传算法的特点及基本流程15 2 2 3 遗传算法的不足与改进1 9 2 3 本章小结2l 第三章公交线网协同调度理论 3 1 公交线网协同调度2 2 3 1 1 单线公交调度2 2 3 1 2 公交线网协同调度2 3 3 1 3 二者的辨证关系2 4 3 2 单线公交调度发车频率模型2 4 3 2 1 模型假设2 4 3 2 2 建立模型2 5 3 2 3 满意度计算2 5 3 3 公交协同发车时刻表编制模型构建2 8 3 3 1 模型假设2 8 3 。3 3 协同参数定义2 8 3 3 4 时刻表生成模型2 9 3 4 公交线网协同调度的线网结构设计3 0 3 5 本章小结3 1 第四章基于线网结构的公交协同调度时刻表模型 4 1 公交线网协同调度换乘网络拓扑结构3 2 4 1 1 城市公共交通网络的描述3 2 4 1 2 公交线网协同调度换乘网络结构3 3 4 2 公交线网协同调度时刻表模型3 4 4 3 模型求解3 5 4 3 1 模型求解借助的软件平台3 5 4 3 2 算法设计3 6 4 4 算例及算例分析3 9 4 6 本章小结4 0 第五章公交线网的同步现象初探 5 1 复杂网络的同步动力学行为4 1 5 1 1 同步概述4 1 5 1 2 同步的数学描述4 2 5 1 3 同步判据4 3 5 2 公交线网的同步探讨4 5 5 2 1 动力学系统4 5 5 2 2 公交线网上同步探讨4 7 5 2 3 研究公交运行网络的同步流稳定性的意义4 7 5 3d 、结4 7 第六章总结与展望 6 1 本文工作总结4 9 6 2 对未来工作的展望5 0 参考文献51 致谢5 6 附录a ( 攻读硕士期间发表的论文及科研情况) 5 7 厂 第一章绪论弟一早珀下匕 1 1 引言 1 1 1 研究背景 城市交通系统是人类活动的基本条件之一，是城市繁荣、有序和高速 发展的主要支撑条件。但是，城市在快速发展过程中遇到了日益严重的交 通问题，严重影响了城市的经济提升和运行效率，也给人们的工作和生活 带来了诸多不便与损害，已经成为制约城市可持续发展的主要瓶颈。因此， 科学地“诊治”城市交通“病”是我国社会、经济发展过程中提出的重大 需求。而“诊治 城市交通“病 的关键是，从理论上系统全面、深入彻 底地研究城市交通网络结构、城市交通需求和城市交通流的演化机制。机 制清楚了，才可以从本质上认识交通拥堵、交通环境污染和交通安全事故 的产生根本原因，认识未来城市交通网络的演化趋势，提出切实可行的缓 解和预防城市交通拥堵的对策和措施，并为科学地制定城市交通的发展战 略规划、设计和发展先进的交通管理与控制技术打下坚实的理论基础。分 析各发达国家的处理城市交通拥堵问题的策略，大力发展城市公共交通成 为大家解决这一问题的一剂良药。 城市公共交通主要包括公共汽车、地铁、出租车、无轨电车、有轨电 车等。地铁虽然具有载量大、正点率高、安全舒适、对环境污染少等优点， 但因其造价高、投资大、工期长等因素，发展难度相当高，除香港和大阪 外，其他各国的地铁几乎都有营业性亏损。出租车灵活、方便，但是能源 浪费性大。公共汽车相比其他公共交通方式而言，具有设施简易、投资少、 见效快等优点，尤其是从库里蒂巴发展起来的快速公交系统( b u sr a p i d t r a n s i tb r t ) 正在开创城市公共交通大容量、低成本的新时代，并逐步成 为全球城市交通事业的发展方向之一。 因此，解决目前我国城市交通拥堵问题还需要大力发展公共汽车。从 2 0 世纪8 0 年代开始，我国的经济一直持续高速增长，而城市公共交通的建 设和发展一直滞后于社会经济和居民生活的需要。为此，我国政府制定了 一系列政策，明确了以公共交通为主的城市交通发展战略。国内公共汽车 的硬件环境已经引起了各部门的重视，达到了相应的水平，但由于经营机 制、管理水平等软环境不匹配，城市公共交通的发展现状不尽如人意。而 公共汽车发展的软件环境的核心是公共汽车运营调度管理( 下文简称：公 交调度) 。只有当软件环境匹配时，硬件环境才能够正常发挥其作用，进 而从根本上解决城市交通拥堵问题。 1 1 2 课题研究来源 本课题的研究内容来源于国家自然科学基金资助项目“城市交通网络 可靠性研究”，项目编号：5 l0 7 8 0 4 4 。 1 2 研究意义 公共交通运输是国民经济中重要物质生产部门，公共交通运输产业的 发展与经济发展相类似，要依靠体制创新、技术进步、产业结构的调整， 通过公共交通运输政策的制定与实施，实现公共交通运输的绿色、可持续 发展。因此对公共交通运输研究的意义可以大致分为理论研究意义和现实 研究意义两类。 1 2 1 理论研究意义 随着公交优先战略等一系列绿色、可持续的公交发展政策的实施，现 实中对公交线网协同调度理论与方法的需求己十分强烈。 第一，将复杂网络中的相关理论引入到公交线网协同调度理论研究。 复杂网络研究的目的是理解网络拓扑结构对复杂系统中各种动力学行为的 影响，不仅要认识系统中个体或各组成部分的行为，更重要的是要探索他 们共同作用下的整体行为。城市交通系统的运行效率受到多方面因素的影 响，要想从整体、宏观的角度去了解城市交通网络，就需要对系统各个部 分之间的相互作用有一个清晰的认识。城市交通网络具有与其他复杂网络 相似的一些拓扑性质，但是又具有不同于其他复杂网络的显著特性，如自主 性、选择性、适应性和动态性。因此将复杂网络理论引入到公共交通的理 论研究是可行的。已经有研究表明，城市公交网络可以拓扑得到一个具有 小世界特性的复杂网络，这方面的研究还在不断的发展。本文将借助复杂 网络的理论分析公交线网结构，建立公交时刻表模型，同时还分析了公交 线网协同与公交线网结构之间的关系，为公交线网的协同调度提供新的思 考方向。 第二，基于改进的遗传算法对公交线网协同调度模型进行寻优，验证 模型的有效性。遗传算法可移植、并行性强、搜索效率高，改进后的遗传 算法，更加适合于公交调度问题的求解。 第三，公交线网优化对于改善公交调度和促进公交车辆同步而言，是 一项投资少、见效快、易于实施的有效措施。本文将从线网结构出发，分 2 析公交线网上的同步与公交线网结构的关系，为公交线网优化提供新想思 路。 基于此，本文将从两个角度促进公交车辆的同步，减少乘客的换乘等 待时间。一是时刻表的编制，运用复杂网络相关理论，建立公交线网调度 模型，生成公交协同调度时刻表；二是从公交线网结构出发，运用复杂网 络的同步理论，分析公交线网结构与公交车辆同步之间的关系。 1 2 2 现实研究意义 公交线网协同调度是以整个区域内的公交线路为研究对象，它的实现， 必将在一定程度上缓解目前城市交通的拥堵，从整体上提高城市公共交通 服务水平，为“绿色交通 发展战略的全面实施提供了理论和技术上的支 持和保障。 对于政府而言，城市公共交通运营调度模式的改进，必然会提升城市 的综合实力，创造更大的社会效益，使得城市交通更加畅通、居民出行环 境得到改善、使得城市交通运行效率提高，总而言之，让城市的竞争力上 升一个台阶。对于公交企业来讲，城市公交运营调度模式的改进，必然会 给企业带来更大的经济效益。有统计数据表明，公交线网协同调度模式与 单线调度模式相比，将节约l0 - - - 2 0 的运力资源。公交线网协同调度可 以有效的解决现有公交运营模式中的问题：人员可以集中管理，提高了企 业的工作效率；计划可以统一编制，实现了运输资源在整个区域的优化配 置；借助定位系统等软件，增强了调度人员处理和应付突发事件的能力。 对于城市居民而言，城市公共交通的发达程度直接与他们的生活质量相连。 无论一个人出行采用公共交通还是私人交通，公交的畅通与否将直接影响 他们出行的便捷与经济。公共交通与私人交通之间是一种竞争合作关系， 公共交通的良性发展将为私人交通提供更为舒适的行车环境。因此，采用 更有效的公交调度模式，可以为居民提供更加舒适的出行服务，提高出行 效率。 1 3 研究的历史与现状 国内外学者已经对公交调度的线网结构、调度模型及其算法、评价原 则等方面做了大量研究，本文将分类概述。 1 3 1 公交线网协同调度研究 公交调度的主要活动包括公交线网设计、时刻表编制、行车计划编制 和司售人员排班等四个主要部分。19 7 6 年，r a p p 和g e h n e r 曾尝试通过一 3 种图形交互公交来使公交线网中的换乘延误最小。在过去的三十年中，国 内外对公交线网协同调度已经取得了一些成熟的研究成果，有一部分还被 成功地运用到实际公交调度工作中。综合起来主要体现在两个个方面：一 是调度模型的优化目标和算法；二是研究方法。 调度模型的优化目标主要是运营费用、线网中最大协同化两个方面， 其中运营费用包括乘客的出行时间( 含换乘等待时间) 和运营商的运营成 、 本。 k l e m t 和s t e m m e ( 19 8 8 ) n ，以整个路网的换乘时间最小为优化目标， 建立了一个整数规划模型，d e s i l e t s ( 19 9 0 ) ，定义了广义费用，以费用最 小为目标提出了一个与k l e m t 等价的模型，p a t t n a i k 等( 19 9 8 ) 以费用最 小为目标，以发车频率和满载率为约束建立模型，优化了发车频率。随着 遗传算法的广泛运用，c h a k r o b o r t y ( 19 9 5 ) 等人采用遗传算法求解调度问题， 验证了遗传算法是求解简单的交通系统优化问题的一种行之有效的方法。 牛学勤等( 2 0 0 3 ) ，提出了以公交企业满意度、乘客满意度为目标的发车频 率优化模型。何迪( 2 0 0 9 ) ，以乘客在区域内的换乘时间最小为目标建模， 并采用遗传算法进行求解。 以上研究均是以整个路网的费用最小为优化目标进行研究，而费用最 小为优化目标，不能确保换乘点的换乘车辆数最大，将降低换乘的效率。 v a nn e s 等( 19 8 8 ) 指出在给定车队大小条件下，以满足最多直达乘客量 为优化目标进行公交线网的优化设计。2 0 01 年，c e d e r 和t a lt ，基于某公交 线网，提出了最大协同化的运筹学模型，优化目标是整个研究区域内各站 点同时达到的车辆数最大化，将其转化为一个m i p 问题，并设计了启发式 求解算法，对问题进行求解。c e d e r 选择了以色列某一简单的公交线网作为 研究对象，验证了以上协同过程。但模型没有反映路网各换乘站对全路网 协同化目标的贡献大小，而在实际的公交线网中，不同的换乘站点上的同 步对整个公交线网协同的影响可能存在很大的区别。比如：一个拥有1 0 条 公交线路的换乘站点与一个只拥有两条公交线路的换乘站点，它对整个是 应进行区分与评价，然后建立模型。刘志刚等( 2 0 0 7 ) t - l l ，的研究弥补了这 一缺陷，从系统的角度出发，建立了区域公交调度双层规划模型，用站点 的权重来区分各站的对整个路网协同化目标贡献，同时设计了嵌套式算法 优化可行解。但在进行权重系数标定时，没有考虑路网的结构特点，而n e l s o n 和m a x w e l l 的研究表明，路网的调度策略与路网结构有关。鉴于公交线网 具有复杂网络属性d s - s ，本文第四章将分析说明运用复杂网络节点度的相关 属性设计换乘节点的权重系数，建立公交线网协同调度模型。 4 公交调度的研究方法很多，s t e e n b r i n k ( 19 7 4 ) 提出了传统的数学规划法。 c h o u ( 19 8 4 ) 将系统的方法引入到公交网络规划中。c e d e r 和w i l s o n ( 19 8 6 ) 列 将采用双层优化方法设计公交网络。d u s a n ( 19 9 4 ) 等将模糊逻辑引入到航线 备选路径的确定中，并用模糊线性规划方法确定航班间隔。到9 0 年代，人 们将人工智能引入到公交调度中，b a a j 和m a h m a s s a r i ( 19 9 5 ) i ”，设计了人工智 能和运筹学混合算法，将人工智能中车辆路径搜索启发式算法和运筹学中 的公交系统分析方法结合起来。 1 3 2 公交线网结构 公交线路网络是指将城市中各个交通节点( 站点或区域交通重心) 之 间，用车、线集合将其连接起来。而公交线网设计及优化是指在现有公交 站点、网络基础上的基于特定目标函数的最优化问题，是对已有或初始公 交线路集的改进与优化。面对现实中大多公交站点的不可迁移性以及一些 固有线路的不可调整性，公交线网优化也是一项投资少、见效快、易于实 施的有效措施，也为后来的公交时刻表编制以及公交区域调度提供更优化 的平台和前提。 n e l s o n 等( 19 81 ) ，从客流的角度提出了四种不同的换乘策略：1 简 单的时间换乘同步；2 脉冲式客流条件下行车计划编制；3 线路在脉冲式 客流条件下的行车计划编制；4 区域在脉冲式客流条件下的行车计划编制。 其中策略1 的目标是使两辆公交车能够同时到达同一站点；策略2 则是从 整个线网的角度考虑分析问题；策略3 和策略4 区别在于时间和空间的区 别，策略3 实施的限制条件为非高峰时段，而策略4 是把某个地理区域内 的公交线网作为研究对象。 近二十年之后，m a x w e l l ( 19 9 9 ) n ”从公交线网的角度，也提出了四种 换乘策略，主要内容为：一是对于任何公交线网，采取密集发车，则不需 要协调；二是对于有主线和支线的公交线网，采取主线和同步换乘支线相 结合；三是线网结构为单一中心的辐射型线网，则所有的同步都出现在中 心站点；四是线网结构为有固定间隔的多个同步换乘枢纽。 两者的区别在于前者主要考虑了路网中客流的到达情况，而后者主要 从路网结构角度分析问题，但是两者均说明不同的线网结构，应该采取不 同的换乘策略，这样才能确保获得更优的同步效果。而有效的公交换乘协 同调度是在合理的调度时刻表和线网结构必须同时生效的基础之上实现 的。换而言之，若想提高公交线网中换乘站点的同步车辆数，减少乘客换 乘等待时间，可以从时刻表的确定和公交线网结构两个方面入手，综合考 5 虑。正是受公交线网对换乘同步的影响启发，本文第五章分析：公交车辆 同步与公交线网结构的内在关系。 s i l m a n 等( 19 7 4 ) n 引提出了以乘客出行时间和不舒适最小为优化目标， 进行线网设计。到9 0 年代，b a a j 和m a h m a s s a r i ” 借助人工智能方面的 相关技术，建立了一整套线网优化解决方案，并依据论文建立的方法，按 照不同的均衡目标，分析了网络在不同用户要求权重条件下的网络评价指 标。而s h i n ( 19 9 4 ) ”在b a a j 的基础上，设计了一个换乘中心。两种的区别 在于，后者采用的是传统方法，前者在优化过程中可以同时选择多个换乘 中心，考虑了换乘对优化目标的影响。到2 1 世纪初期，n a g m c h a i 和l o v e l l ( 2 0 0 3 ) 心们进一步基于换乘对公交线网结构设计进行研究，优化过程中，作者 设计了大量的遗传算子进行基于遗传算法的组合优化寻优，结果在一个小 规模的路网中得到验证。冯树民( 2 0 0 5 ) t 川从节点、线路和线网三个方面对公 交线网结构优化的约束条件和目标函数进行了研究，以公交运营费用投入 最少和居民出行时间最短为目标建立了公交线网优化模型。以上的研究均 是从路网优化的角度出发。复杂网络的兴起与发展，为众多领域的研究提 供了新的研究方法，也为交通领域的研究打开了一扇窗，人们已经将它引 入研究交通网络结构的研究，j u l i a n 和j a n u s z ( 2 0 0 3 ) t 圳研究发现，波兰的2 2 个城市公共交通网络具有小世界特性。国内公共交通网络结构虽然与国外 存在差别，但是陆化普”、李英t 2 4 1 等以廊坊、济宁、上海等城市公共交通网 络为基础进行研究，发现国内的公共交通网络同样具有小世界特性，同时 还发现上海市的公共交通网络是一个无标度复杂网络。复杂网络的功能可 以通过其上的动力学过程的特性来反映，同步流就是复杂网络动力学行为 的一种表现形式，复杂网络上同步动力学研究，是将拓扑结构与耦合的动 态系统局部特性之间的相互影响和网络的同步联系在一起。因此，可以通 过调整网络结构来实现网络上的特定动力学形式。国内外已经对复杂网络 上的同步动力学模型心”m ，、同步动力学行为的判据卜 ，、以及促进同步流稳 定的方法n 等开展了大量研究。 1 4 研究内容与技术路线 1 4 1 内容 基于上述内容，本论文主要围绕如何促进公交线网上公交车辆的同步 最大化而展开，同时，通过实证进一步验证了模型的有效性。因此，本文 首先回顾了公交调度模型、算法以及换乘策略等方面的发展；然后介绍了 本文研究所涉及的相关基础理论知识一一遗传算法以及公交线网协调调 6 度；最后，在此基础上，从两个角度分析公交线网上的同步问题。各章基 本内容如下。 第二章，主要介绍了复杂组合问题的定义以及复杂性计算和遗传算法 数学原理、优越性等，为第四章模型的求解做理论准备。 第三章，围绕公交调度展开，介绍了公交调度工作的主要内容、单线 公交调度发车频率模型、线网协同调度的时刻表模型，以及公交线网设计， 从而引出了促进公交线网上车辆同步最大化的两个方面，一是时刻表的编 制，二是公交线网结构。第四章和第五章分别从这两个方面进行了分析。 第四章，本章基于复杂网络理论对公交线网协同调度问题开展研究。 通过构建公交线网协同调度换乘复杂网络，并针对模型的特点，设计了基 于遗传算法的求解方法，用算例验证了模型和算法的有效性。 第五章，本章是整篇论文的一个开放章节；从公共交通网络的结构出 发，分析公交线网拓扑图上各节点状态，借助复杂网络的同步理论，探讨 在公交线网上同步流形稳定需要做的工作，为公交线网上协同最大化提供 了新的研究方向。主要内容包括两个方面，一是公交运行网络上动力学状 态方程的建立；二是指出推进公交运行网络上同步流稳定需要做的工作。 第六章，本章主要是对本论文所做的工作进行总结，并指出不足和有 待发展的环节，为以后工作的开展提供思考方向。 1 4 2 技术路线 本文的技术路线如图1 1 所示。 7 图1 1 论文技术路线图 8 第二章复杂组合优化问题及其优化算法 优化问题的种类繁多，涉及的工程领域很广，一般将其分为两类：组 合优化问题和函数优化问题，其中组合优化问题是属于离散最优化问题。 2 1 组合优化问题的定义和复杂性计算 2 1 1 组合优化问题定义 组合优化问题是一个最大化( 最小化) 问题，它由以下三部分构成： 1 问题集合：k ； 2 对于任何一个问题后都有一个有限的可行解集q ，q = q ，s 2 ， ； 3 目标函数厂，它对每一个问题j i 和每一个可行解墨赋予一个有理数 f ( k ，口) ； 组合优化的最大化问题表示为： f ( k ，s ) f ( k ，岛) ( 2 1 ) 组合优化的最小化问题表示为： f ( k ，j ) sf ( k ，s i ) ( 2 2 ) j 为问题的最优解或是近似最优解 在排序、调度、分类、决策等问题的处理过程中往往会涉及到组合优 化。经典的组合优化问题有：旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、 加工调度问题( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b s h o p ) 、o - l 背包问题 ( k n a p s a c kp r o b l e m ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、图着色问题( g r a p h c o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 等。 组合优化问题一般具有较精确的数学描述，且具有很强的工程代表性， 但在实际工程中，解空间的状态非常多，计算复杂度高，由于可行解随着 问题的规模呈指数增长，导致搜索空间出现组合爆炸。通常在实际工程中， 将这一类组合爆炸的组合优化问题称为复杂组合优化问题。 正是由于复杂组合优化问题具有以上一系列特点，所以无法用枚举法 法来获取问题的最优解。在长期的实践工作中，人们为了能够获取大规模 问题的最优解或是近似最优解，研究设计了一些新的优化算法。在下面的 内容中将详细介绍组合优化问题的计算复杂性与主要的优化算法。 9 1 0 2 2 遗传算法 优胜劣汰是自然界生物延续生存的永恒法则，而实现这一法则的宏观 原因是生物体内的基因受自然界的作用；微观原因是由于基因自身的选择、 复制、交叉、变异等过程进行而发生。遗传算法( g e n e t i ca l t h o r i t h m s 简称： g a ) 正是人们受自然界这一现象启发而研究发现的新型优化算法，它是一 种自适应全局优化概率搜索算法。 遗传算法最早是由美国密执安大学的h o l l a n d 提出，h o l l a n d 教授依 据6 0 年代对自然和人工自适应系统的研究，受生物进化论的启发而提出的。 在随后的几十年中，遗传算法得到了长足的发展，并在模式识别、机器学 习、神经网络、自动控制、图像处理、v l s i s 设计、遗传学等领域取得了成 功的运用。 本章将从遗传算法中的数学理论、遗传算法的特定和基本流程、以及 遗传算法在组合优化问题中的运用等三个方面对遗传算法进行介绍。 2 2 1 遗传算法的数学理论 遗传算法是通过对种群中个体的迭代搜索逐步获取问题的最优解，为 了从理论上分析该算法的全局收敛性，h o l l a n d 建立了模式定理与隐含并行 性概念，为遗传算法的理论研究奠定了基础。本节将介绍这两方面的知识， 为下文的研究做理论准备。 2 2 1 1 模式定理 首先介绍模式定理中的几个基本概念，然后分析证明模式定理。 1 基本概念 模式定理中一个涉及四个基本概念：模式( h ) ；通配符( ) ；模式 的定义长度( 6 ( h ) ) ；模式阶( o ( h ) ) 。 模式( s c h e m a ) ：某些位置上具有相似特征的个体编码串所组成的子 集，然后将具有不同特征位置上的编码用通配符( ) 表示，所获得的一个 结构体成为模式，用日表示。 以二进制编码为例，个体编码串由两个符合组成，表示为v _ o ，l l ，模 式则由三个字符组成，用v h - - o ，l ，) 表示。对于子集 1 0 0 0 1 ，1 0 0 11 ，1 0 1 1l ，1 0 1 0 1 ) ， 每个染色体的长度，为5 ，模式h = 1 0 * 1 。模式中通配符木个数与子集总染色 体个数的关系：通配符数目为刀，v 中元素的个数为m ，则模式所对应的子 集中所含的染色体个数为，”，若采用的是二进制编码，则关系式为2 ”。 由此可见：模式的引入，实现了简明的描述具有相似结构特点个体的 编码串。 模式的定义长度( s c h e m ad e f i n i n gl e n g t h ) 是指模式中第一个确定值 位置到最后一个确定值之间的距离，用6 ( 日) 表示。 以二进制编码为例，6 ( 1 木l 奉幸) = 2 ；6 ( o 宰宰1 ) = 4 ；对于只含有一个确定 值的编码串，如1 掌奎木，木木l 幸，幸 幸宰1 等，为了方便计算，令其模式定义长 度为1 。 模式阶( s c h e m ao r d e r ) 是指模式中，具有确定值位置的数目，用d ( 日) 表示。 同样以二进制编码为例，模式阶o ( z 1 就是模式日中0 和1 的数目。如 o ( 11 0 ) - 3 ；o ( 枣1 木。幸) = 2 。由此可知，当某个编码串的长度固定时，模式 阶值越大，该模式所对应子集中元素越少，因此该模式的确定性越高。 模式的定义长度6 ( 日) 和模式阶o ( z ) 是为定量的模式运算做准备。 模式定理 对于某遗传算法，采用比例选择策略，交叉概率p c ，变异概率p 册，且p 埘 取值较小，8 ( z ) 和o ( z ) 分别为模式的定义长度和模式阶，为编码串长度， 那么( f + 1 ) 代种群p ( t + 1 ) 含有的模式日中元素个数的期望e 口hn p ( t + 1 ) 口，则 不等式成立： e 口1 ) | i 砟+ 1 ) i 帮卜箬- 0 ( 观 ) 式中， 日厂、e ( t + 1 )表示第r 代种群与模式日匹配个体的集合； i h n p ( t + 1 ) i 表示h n p ( t + 1 ) 集厶m 中个体的数目； f ( t )表示第r 代个体的适应度值； f ( t t ，t )表示第f 代中含有模式日的个体的适应度值。 2 2 1 2 隐含并行性 遗传算法运行过程中，每代都处理了m ( m 为种群中个体的数目) 个 个体，由模式定理可知，每个个体中含有多个不同的模式，所以每代运行 过程中实际上是处理了比m 要多的模式数。那么每代处理的模式数与种群 是个体数之间是否存在关系? 隐含并行性定理n 引正好说明了这一问题。 隐含并行性定理：长度为i 的编码串，c 为编码串中所含模式的长度， 0 o ) 为时间离散状态的离散m a r k o v 链，简称m a r k o v 链。 定义2 ：称p x ( 刀) = ，i x ( 聊) = f ，n 聊) 为m a r k o v 链的转移概率，记为 弓( m ，刀) 。 乞( 所， ) 具有两条性质： 乃( m ，疗) 0 ( 2 - 4 ) 弓( m ，刀) 0 ( 2 - 5 ) 定义3 ：对于m a r k o v 链，如果 弓( m ，历+ 1 ) = 尸 x ( 朋+ 1 ) = i x ( 肌) = f ) = 弓且( f ，) ( 2 - 6 ) 即从状态i 出发转移到状态- 的转移概率与时间起点无关，则称这 类m a r k o v 链为齐次m a r k o v 链。 定义4 ：对于齐次m a r k o v 链，称b 为一步转移概率，全部转移概率 弓( ，) 所组成的一个矩阵尸= ( 弓) 称为一步转移概率矩阵，或称为随机矩 阵。 2 基本遗传算法收敛于最优解的概率小于1 定理1 ：基本遗传算法收敛于最优解的概率小于1 。 基本遗传算法是指不采用任何保留最优个体策略的遗传算法，本文将 利用上一节中的相关定义，证明定理一。 首先将种群的状态集合s 分为包括最优个体的状态集合s 和不包含最 优个体的状态集合最。且有： s = s ，u 瓯且( s ，r 、最= 妒) ( 2 7 ) 要证明进入s ，的稳定概率小于1 ，若用反证法证明，则需证明： l ，啪i m 尸 c 最) 2 0 ( 2 8 ) 状态1 经过选择、交叉、变异操作后转移到状态j ，且j i 。三种算子 的转移概率分别为勘，勺，m q ，对应的随机矩阵为s = 勺 ，c = 勺 ，膨= ) ，且 遗传算法的各个过程是相互独立的，那么种群的转移矩阵r = s c d = 吩 ，易 证明冗正定。 第t 种群中，种群的状态为j 的概率为弓( f ) 为： p j ( t ) = z p t ( 0 k j( t = o ，1 ，2 ，) ( 2 9 ) “e 遗传算法的搜索过程为齐次m a r k o v 链，所以弓( ，) 状态分布不初始状态 无关，则： 弓( ) = ( y o ( 2 1 0 ) t e j 由于_ ，则j 有可能是最中的一个状态，所以： l 。一i m p c 瓯) o ( 2 - 1 1 ) 1 4 本结论与开始假设矛盾，所以说：基本遗传算法有利于最优解的概率 小于1 。但是人们在运用遗传算法时，仍然希望该算法能够以概率1 收敛于 最优解，下文将分析证明收敛于最优解的前提条件。 3 采用保留最优个体策略的遗传算法能以于概率1 最优解 定理2 ：采用保留最优个体策略的遗传算法能以于概率1 最优解。 对于状态e + ( f ) = 彳( f ) ，尸( f ) ，其中，a ( t ) 是当前种群中适应度