（系统工程专业论文）区域公交时刻表生成的模型与方法研究.pdf

中文摘要 摘要：随着世界各地城市现代化程度的提高，城市交通拥堵问题同益严重，发展 公共交通是解决这一问题的重要途径之一。日益增长的城市居民公交出行需求同 相对落后的公交基础设施及管理手段之间的矛盾是城市公交系统发展的主要矛 盾。作为当今城市公共交通发展趋势的公交区域调度模式的提出为这一矛盾的缓 解提供了很好的思路。而编制出能够最大限度减少乘客在线路交叉点处换乘等待 不满意度的公交时刻表是实现公交调度区域化的关键任务之一。 本文首先结合国内外区域时刻表生成问题的研究发展历史，对国内外区域时 刻表的理论与模型进行了综述，并分析了现有模型的不足。然后结合国内公交运 营的实际情况，将乘客期望换乘时间和乘客换乘不满意度引入到区域公交时刻表 生成的问题中，并提出公交换乘方式的概念。在此基础之上，本文建立了区域公 交时刻表生成的多目标模型，将问题转换为获取单线客流需求与区域整体满意度 之间的最优平衡。并根据模型的特点，利用带精英策略的非支配遗传算法进行求 解，取得一组p a r e t o 最优解，使得公交管理者有机会结合实际情况，在单线客流 需求和区域服务质量之间做出权衡与选择。本文最后选取北京公交集团三条线路 的真实客流数据对所设计的模型和算法进行了实验，其结果证明了本文设计的模 型与算法的适用性。 关键词：公共交通；乘客期望换乘时间；乘客换乘不满意度；公交换乘方式；多 目标决策模型；p a r e t o 最优：n s g a i i a bs t r a c t a b s t r a c t ：t r a f f i cp r o b l e m sa r ed e t e r i o r a t i n gm o r ea n dm o r es e r i o u s l yb e c a u s eo f f a s t e ra n df a s t e ru r b a n i z a t i o ni nt h ew o r l d t h ei m b a l a n c eb e t w e e nt h eu r b a nr e s i d e n t s p u b l i ct r a n s p o r t a t i o n t r a v e ld e m a n da n dt h er e l a t i v eb a c k w a r d o ft h e p u b l i c t r a n s p o r t a t i o n i n f r a s t r u c t u r ea n dm a n a g e m e n tm e a n si st h e p r i m a r yp r i n c i p a l c o n t r a d i c t i o no ft h eu r b a np u b l i ct r a n s p o r t a t i o n t h ee m e r g e n c eo ft h er e g i o n a l o p e r a t i n gm o d e l ，a so n eo ft h ec u r r e n td e v e l o p m e n tt r e n d so ft h eu r b a np u b l i c t r a n s p o r t a t i o ns y s t e m ，p r o v i d e st h eo p p o r t u n i t yt or e s o l v et h ec o n t r a d i c t i o n t od e v e l o p at i m e t a b l e ，w h i c hc a ns h a r p l yr e d u c et h ew a i t i n gt i m ew h e np a s s e n g e r sa r eg e t t i n g t r a n s f e ra tt h ec r o s s i n gs t a t i o nb e t w e e nl i n e s ，i so n eo ft h ek e yt a s k st or e a l i z et h e r e g i o n a lo p e r a t i n g t h i st h e s i ss u m m a r i z e st h et h e o r i e sa n dm o d e l so ft h er e g i o n a lt i m e t a b l ea th o m e a n da b r o a d ，a n da n a l y z e st h ed i s a d v a n t a g e so ft h em o d e l s t h e na c c o r d i n gt op r a c t i c a l s i t u a t i o ni nc h i n a ，i n t r o d u c e sp a s s e n g e re x p e c t e dt r a n s f e rt i m ea n dp a s s e n g e rt r a n s f e r d i s s a t i s f a c t i o nt ot h ep r o b l e mo fr e g i o n a lt i m e t a b l e ，a n dp u t sf o r w a r dt h ec o n c e p to f p u b l i ct r a n s p o r t a t i o nt r a n s f e rm a n n e r o nt h i sb a s i s ，t h i sp a p e rb u i l d st h em u l t i o b j e c t s m o d e lo fr e g i o n a lt i m e t a b l ea n dc o n v e r t st h ep r o b l e mt og e t t i n gb e s tb a l a n c eb e t w e e n t r a f f i cd e m a n do fs i n g l el i n ea n dt h ew h o l es a t i s f a c t i o no nt h er e g i o n a c c o r d i n gt ot h e c h a r a c t e r i s t i c so ft h em o d e l ，t h i st h e s i sg e t sag r o u po fp a r e t oo p t i m u mb yu s i n gn s g a 2 a n dt h es o l u t i o n sg i v et h ep u b l i ct r a n s p o r t a t i o no p e r a t o r sa no p p o r t u n i t yt om a k ea t r a d e - o f fa n dc h o i c eb e t w e e ns i n g l el i n ed e m a n da n dr e g i o n a ls e r v i c e a tl a s t ，t h i st h e s i s m a k e sa l le x p e r i m e n tb a s e do nt h er e a lt r a f f i cd e m a n dd a t a ，a n dt h er e s u l tp r o v e st h e a p p l i c a b i l i t yo ft h em o d e la n da l g o r i t h m k e y w o r d s ：p u b l i ct r a n s p o r t a t i o n ；p a s s e n g e re x p e c t e dt r a n s f e rt i m e ；p a s s e n g e r t r a n s f e r d i s s a t i s f a c t i o n ；p u b l i ct r a n s p o r t a t i o nt r a n s f e rm a n n e r ； m u l t i o b j e c t i v e d e c i s i o nm o d e l ；p a r e t oo p t i m a l ；n s g a i i l 图目录 图3 1 公交调度的四步法原理示意图1 4 图3 2 单线路时刻表的编制流程2 2 图3 3 区域时刻表的编制流程2 4 图3 4 两条线路的交叉节点图2 5 图4 1 现有模型中描述的线路交叉现象3 0 图4 2 现实中常见的线路交叉现象3 1 图4 3 某一换乘站点的车辆到达、离开以及乘客等待时间图3 3 图4 4 模型总体思路4 0 图4 5 线性时间满意度函数曲线4 0 图4 6 乘客换乘不满意度的函数曲线4 1 图4 7 多目标优化问题的p a r e t of r o n t 4 4 图4 8 区域公交时刻表生成模型的求解流程图5 0 图5 - 1 三条线路的分布示意图5 7 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：1 白力 签字嗍卅年6 月q 同 导师签名：夏彳f 答字日期：研私月节 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名彳力 签字嗍妒歹年石月7 日 8 7 致谢 本论文的工作是在我的导师关伟教授的悉心指导下完成的，关伟教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此谨向关老师致以最崇 高的敬意，并衷心感谢两年来关老师对我的关心和指导。 马继辉、李宝文老师在学习上和生活上都给予了我很大的关心和帮助，在此 向马老师和李老师表示衷心的谢意。 此外，李桂萍、何蜀燕、付鹏威、舒国辉、肖倩、苟喜霞、林磊、牛虎等同 学在实验室工作及撰写论文期问给予了热情帮助，在此向他们表达我的感激之情。 衷心感谢我的父母给予我的平凡而伟大的爱。他们的朴实和善良深深的影响 着我，勉励和支持不断地激励着我。 最后，感谢所有帮助和关心我的人。 1 引言 1 1 研究背景 随着世界各地城市化程度的提高，城市交通拥堵问题同益严重，公共交通的 重要地位显得更加突出。城市公共交通方式包括定时定线行驶的公共汽车、地铁、 出租车等。公共汽车是一种最常见的交通工具，拥有机动性能好、投资少、操纵 轻便等特点，适用于不同层次的乘客；地铁的优点是运量大、速度高、污染少、 占用土地少，但相对投资大并且需和其它方式配合集散乘客；出租车方便、灵活， 但运输效率低并且加重道路负担，造成能源浪费。相比较而言，公共汽车在建设 和使用成本上比其他几种公交方式都有优势，这也是公共汽车在我国城市交通中 始终占主要地位的根本原因。从国外的经验来看，部分大城市停止了规模庞大的 轨道交通建设，而将资金用于建设城市快速公交网络。而实践也证明，通过建设 大容量快速公交系统来改善城市交通能取得良好的效果。 因此目前在我国，常规公共汽车交通仍作为各个城市的地面客运中的主力军， 并随着信息技术的发展而更加便利，针对公共汽车客运的各方面的研究也从来都 是交通研究的热点。在本文中，以下若不特殊指明，公共交通( 公交) 均指公共 汽车运输。 现阶段国内的公交运营调度一般根据企业规模的大小，采用二级或三级调度 的组织形式。企业规模较大，运营线路、车辆、人员多，可设三级调度制，调度 机构由公司总调室、分公司( 车场) 调度室和线路( 车队) 调度组构成。总公司调度室 主要负责定期汇总各区域、各线路的客流动态资料，审核分公司行车时刻表：分 公司调度室负责定期组织本公司管辖线路的客流调查，提出行车时刻表的编制要 求和有关指标控制；线路调度组负责对管辖线路进行客流目测调查，编制行车时 刻表，根据生产任务编排班次并负责贯彻执行日运营计划【l 】。 换句话说，国内的运营模式是各车队、各分公司只负责自己管辖的线路，这 样就造成了在一个城市、一个区域中多条线路“各自为政的现象。在为每条线 路编制时刻表时，只根据单条线路的客流调查数据划分时段，确定发车时刻，并 按照客流最大断面确定配车数。这种运营方式导致了各分公司和车队以自己单位 的利益为重，线路之间很少有协调工作，当乘客需要在多条线路间进行换乘时， 将有可能造成长时间的等待。这种情况多次发生之后，在乘客印象中公交的服务 质量大打折扣，于是大量乘客采取其它方式出行，如出租车、私家车、地铁等， 造成了公交乘客的大量流失，不利于整个城市交通系统的发展。 公交时刻表编制是公交调度中的一项关键性工作，历来是公交调度研究工作 中的热点问题，它既关系到乘客对公交的满意度，也关系到公交公司的运营效益。 对于公交时刻表编制的研究，目的就是编制出满足乘客需求，同时也能使得公交 公司运营效益最大的时刻表。利用计算机编制运营计划的研究开始于上个世纪6 0 年代，迄今已有很多运营计划编制方法和系统被研制出来，其中许多得到了成功 应用。上个世纪7 0 年代，国外开始有人尝试对交通网络系统的时刻表进行了协调 和优化【2 】，但是区域时刻表问题真正成为研究的重点是在近十年。这段时间内，各 种模型和算法被用于区域时刻表的生成问题，包括混合整数规划、多目标决策等 等。总体看来，关于公交时刻表编制问题的研究路线主要是围绕如何确定合理的 发车频率来展开，通过各种不同的方法合理确定发车频率进行时刻表优化。而区 域调度中公交时刻表的编制则需要在满足单条线路客流需求的基础之上，尽可能 考虑乘客在换乘时的便利，提高公交服务的区域性整体质量。 国内对利用计算机进行公共交通调度方法方面的研究与国外先进水平还有较 大差距。国内目前的公交企业大都采用手工方式编制调度计划，调度模式几乎全 部采用单线路模式，即以线路为运营组织单位，人员及车辆按线路固定配置，以 线路为单位编制运营调度计划，线路配车按线路最大断面确定，首末站驻车、管 理、调度。和应用情况相对应，在国内关于公交调度的理论研究更多的是局限在 单线调度模式上，其中关于调度计划的研究也几乎全部是针对单线路调度模式。 其研究模式基本都是：针对单一线路，运用统计学方法，建立客流分析模型，求 得发车时间间隔，以此确定调度计划。但单线路调度模式从根本上是一种低效益 的运作模式，基于单线路调度的调度计划研究，从公交企业的应用实践来看，调 度计划计算机编制与手工编织相比优化的效果非常有限，不能满足公交企业的实 际需求。 区域调度模式在我国尚处于理论探索和示范应用的初级阶段，对于与之相关 的核心模型与算法的微观层面的研究还基本处于“照搬”国外模型的状态。而实 际上，国内外在管理模式，调度方式等有着很大的不同。因此如何结合国内调度 现状来分析区域公交时刻表的生成问题是本文的目的之一。 本文将结合国内实际情况，综合考虑单线客流需求和整体区域服务质量的提 高，对乘客在换乘等车时的满意度变化做出研究，建立了区域公交时刻表生成的 多目标模型，并利用带精英策略的非支配遗传算法进行求解。希望能为国内区域 公交时刻表的研究提供新的思路，为公交运营单位带来帮助。 2 1 2 论文结构和主要内容 根据研究内容，本文一共分为六章： 第一章是概述，主要介绍区域公交时刻表编制问题的研究背景，文章的体系 结构和主要内容。 第二章对区域时刻表生成的模型与方法进行综述；不限于公共汽车交通，从 区域时刻表生成问题的研究方法入手，对国内外的研究现状进行了总结，并对这 些研究成果进行分析评价。 第三章对公交时刻表的编制业务进行了介绍。主要包括行车计划与时刻表的 介绍、公交客流规律对时刻表编制的影响和发车间隔的计算方法，并在最后对区 域公交时刻表的编制问题进行了详细地描述。 第四章是全文的重点；首先在区域公交时刻表生成的这一问题中，引入了乘 客期望换乘时间和乘客换乘不满意度，并结合国内公交运营的实际情况，提出换 乘方式的概念，使得模型能适用于双向和单向的调度模式；然后建立了多目标模 型，一方面考虑满足单条线路的客流需求，尽量减少与原始发车时刻的偏差，另 一方面，建立乘客换乘时的不满意度函数，使得区域整体的换乘不满意度最小； 最后，设计了适用于这一多目标模型的n s g a i i 算法。 第五章为实例分析，选取北京公交集团三条线路的实际数据，应用本文设计 的模型和算法生成了这一区域的公交时刻表，对模型与算法的适用性进行了检验。 第六章为得出的结论，将对全文进行总结，概括本文的主要工作，并对今后 研究区域时刻表生成的问题提出展望。 3 2 区域时刻表生成的理论与方法综述 国内目前的公交企业大都采用手工方式编制调度计划，调度模式几乎全部采 用单线路模式，即以线路为运营组织单位，人员及车辆按线路固定配置，以线路 为单位编制运营调度计划，线路配车按线路最大断面确定，首末站驻车、管理、 调度。这种以线路为单位的单线路调度模式是一种小而散的调度模式。它不利于 资源的有效利用，造成各线路相互独立。由于各线路分布在不同的车队甚至分公 司，均按各自的最大断面配车，不考虑与其他线路的协调问题，在出现线路交叉， 乘客需要换乘时，就有可能造成很长的等待时间，降低了公共交通的服务质量。 和应用情况相对应，在国内关于公交调度的理论研究也是局限在单线调度模 式上，其中关于调度计划的研究也几乎全部是针对单线路调度模式的。其研究模 式基本都是：针对单一线路，运用统计学方法，建立客流分析模型，求得发车时 间间隔，以此确定调度计划。但单线路调度模式从根本上是一种低效益的运作模 式，基于单线路调度的调度计划研究，从公交企业的应用实践来看，调度计划计 算机编制与手工编织相比优化的效果非常有限，不能满足公交企业的实际需求。 目前国外已经有一些理论方面的研究，但是对于现有的模型方法并不能盲目 的照搬到国内，国内外的管理模式，调度方式等有着很大的不同，所以如何结合 国内调度现状来分析区域时刻表的编制问题是本文的目的之一。 2 1 国外研究情况 早在7 0 年代，国外开始对给定交通网络的时刻表进行协调和优化，并在近十 年取得了相对成熟的研究成果，主要分为混合整数规划模型和多目标决策模型两 大研究方向。下面将结合区域时刻表的研究历史对国外的研究情况进行综述。 1 9 7 6 年r a p p 和g e h n e r t 2 】描述了一个用于最小化交通网络中换乘延迟的图形化 交互工具。在一定的运营成本约束下，这一工具通过对原始发车时间进行一系列 的调整，对整个交通网络系统的时刻表进行了协调和优化。优化过程考虑了多条 线路不同的发车间隔和首末站停车时间。 n e l s o n t 3 】在1 9 8 1 年提出了两辆公交车同时到达某一换乘站点的目标，并给出 了四种换乘方式。但是这些方法的应用仅限于非高峰时段，或在小范围区域内使 用。1 9 8 7 年a b k o w i t z l 4 也给出了两辆公交车同时到达某点的实例分析，并研发出 基于四种换乘策略的计算机程序，使用者需要根据实际情况来选择使用某种策略 程序。 5 1 9 8 4 年c e d e r l 5 】给出了四种不同发车频率确定方式，其中有两种方式是基于在 某个站点某个时间段统计得到的乘客到达数量来确定，用客流量最大的那个时间 段的某个站点乘客到达的数量，除以所期望的公交载客量就得到了发车频率( 这也 是目前我国公交企业普遍采用的确定发车间隔的方法) 。另外两种方法是基于某 个时间段内，整个线路乘客的周转量来确定，用线路通过的乘客周转量除以所期 望的载客量得到的发车频率。这四种方法为c e d e r 开展进一步的区域调度时刻表研 究奠定了基础。 1 9 8 7 年m 6 h r i n g 等人【6 】首次从乘客和时刻表编制者两个不同角色的角度出发 来考虑区域时刻表生成的问题。文献中指出乘客在等待时通常感觉时间是平常的 两倍，强调了换乘等待时间的重要性。对乘客而言，如果在进行换乘时无需等待， 公共交通的服务质量就得到了极大的提高，而这要求时刻表编制者在制定行车计 划时，就能同时考虑多条线路的发车时刻。而另一方面，为了达到同步换乘的效 果，时刻表编制者往往需要对原始时刻表进行很多调整，而这又不得不付出偏离 原始客流调查依据的代价。因此，时刻表编制者必须考虑，用一定程度的偏离来 换取同步换乘的效果，是不是值得的。 早期的这些研究成果对区域调度的时刻表问题进行了探索，并对公共交通的 客流规律和统计方法、行车组织方式等重要因素进行了研究，为今后学者的研究 奠定了坚实的基础。 2 1 1 混合整数规划模型 混合整数规划( m i x e di n t e g e rp r o g r a m m i n g ) 是指一类同时包含整数变量和连续 变量的优化问题，其一般数学表达如下【7 】： m i n f ( x ，j ，) ， s g f ( x ，y ) 0 ，i i = 1 ，2 ，k ) ， 厶x u i ，l 2 y u 2 ， x r ”，y z 用 其中：x 是n 维连续变量，y 是m 维整数变量。变量的上界和下界为 厶= ( ，? ，z ：, - - - ，：) u i = ( i ，“：1 ，”：) ； l ：= ( 誓，譬，e ) ，u ：= i l ，“：2 ，“三) 混合整数规划是n p 一完全问题，其求解算法具有指数复杂性。以色列专家c e d e r 将混合整数规划引入到区域公交时刻表的编制问题中，并使用启发式算法对模型 进行求解。 6 2 1 1 10 1 混合整数规划模型 1 9 8 9 年c e d e r 和s t e r n t 8 j 对于区域时刻表问题建立了一种整数规划模型，使用 启发式算法，借助计算机程序，实现了模型的求解过程。在此基础上，c e d e 9 9 】【1 0 1 在1 9 9 9 年至2 0 0 1 年间，研究了基于不同类型的发车时间间隔和不同方式所确定 的发车频率，以及特殊情况下的发车需求来编制公交时刻表的三种不同方式。他 还以同时到达换乘枢纽的车辆数最大化为目标，建立了混合整数规划模型、设计 了能在可接受时间内得出结果的遗传算法，并将以色列某公交公司的一个给定公 交网络作为案例，使用实际运营数据验证了该模型的有效性。 这些研究成果在前人基础上取得了较大的进步，其所设计的模型和算法能够 快速实现换乘枢纽多线路的发车间隔优化。但是，由于模型建立在很理想的情况 下，离实际应用( 尤其是目前在国内的应用) 还有一定的距离，具体来说，主要 存在以下几个方面的局限： ( 1 ) 模型与国内公交运营实际情况有一定差距 将区域时刻表的编制问题归纳为一种0 1 混合整数规划【1 0 1 。问题的目标函数 描述为 m if kme m a x z 。一g t n j ：- j ( 一j ：- jj 一j 【一 其中 捌渊9 珊17 札 m 表示某一给定公交网络中的线路总数； k ，q 代表网络中的两条线路( 1 k m ，1 q m ) ； 疋表示线路k 在时间区间 o ，t 之间计划发车的次数； e 表示线路q 在时间区间【o ，t 】之间计划发车的次数； z 蝴是一个二进制变量，当线路k 的第i 次发车与线路q 的第j 次发车同时到 达节点n ( 也就是线路k 与线路q 的某个交叉点) 时，这个变量记为l ，否则记为0 。 从这点描述可以看出，这一模型建立在理想状况的基础之上。然而，国内的 实际情况是：换乘车站往往是大站，有的甚至同时有十几条线路相交，车辆进站 完成乘客的上下车活动时，一般都有进站先后顺序和固定的停车位置。有时乘客 需要从车站的后方走到车站前方，才能完成换乘。当换乘方向相反时，甚至还需 要穿过马路，到对面坐车。也就是说，从上一辆公交车到换乘发生地点( 或车站) ， 是有一段距离的，并且每个换乘站的换乘距离不一样，对应的换乘时间也不一样。 根据上述的国内实际情况，即使是两条线路的两辆车同时到达某一线路交叉 点，并不能代表乘客能进行无等待的换乘。这一模型虽然提供了一个很好的思路， 但是在某种程度上，并不适用于国内的公交现状。 ( 2 ) 没有对等待的乘客群体进行区分 7 在这一模型中，凡是没有同时到达线路交叉点的情况都记为0 。但是在实际生 活中，需要等待才能换乘的情况并不是完全一致的。举例来说，刚下车就能换乘， 是乘客最理想的状况；但现实是往往需要等待才能换乘，等待时间不等，可能从1 分钟到3 0 分钟，在这个等待时间区间中，乘客的满意度是在发生变化的，等待的 时间越长，满意度就越低。如果仅根据车辆同时到达的o 一1 变量来衡量目标函数的 值，是不符合实际情况的。 2 1 1 2 其他混合整数规划模型 不论是哪一种服务，它的最终评价者始终是服务的使用者。随着时间的推移、 对公交服务的研究深入，各国的学者开始考虑人的因素，以下两个模型已经注意 到从公共交通的服务对象乘客的角度来阐述区域时刻表的问题。 2 0 0 2 年l i e b c h e n 和m 6 h r i n g t l l 】首次使用混合整数规划模型来求解同步换乘问 题。在这一模型中，换乘乘客被分成两组，一组需要等待换乘，另一组进行无等 待换乘。此模型对无等待换乘的乘客数目进行了优化。但是，和c e d e r 建立的模型 一样，对于等待换乘的乘客群，文中没有进行区分和评价。在这篇论文中等待1 分钟后换乘的乘客和等待l o 分钟才得以换乘的乘客没有任何区别，是进行模型的 优化计算时，两种情况相同对待。 2 0 0 4 年w o n g i l 2 】对m t r 系统( 香港地铁) 的时刻表进行了同步优化。w o n g 建立了m i p 模型，并使用启发式算法对模型进行了求解。最后，提出了“刚好错 过”( i u s tm i s s ) 的概念，在这一特殊情况下，乘客的满意度达到最低。此文献没 有将这一概念用到目标函数中，只是对其进行介绍，作为一个考虑的因素。这一 概念的提出给后来的学者以及本文的研究，都给予了极大的启示。 2 1 2 多目标决策模型 新加坡国立大学( n u s ) 的副教授c s c h a n g 从9 0 年代起开始研究新加坡地 铁的调度问题【1 3 】。【1 6 】。而这所大学的研究人员花三年的时间开发了一套软件包 i t m s ，用来评估自动列车运行的表现【1 5 1 。软件包分为自动列车控制器( a t c ) 和停 站时间控制器( d t c ) 两部分。其中d t c 建立在p a r e t o 最优集的基础上，可以在 突发事件下为决策者提供可选的停站时间方案集合【l 6 1 。 在这些系统研究的基础之上，c s c h a n g 开始带领他的学生c m k w a n 和f a n y a n g 研究地铁时刻表【1 7 】【2 0 1 。2 0 0 4 年，c mk w a n 和c s c h a n g t l 8 】通过对实际工作 的研究，将地铁时刻表的编制划分为两个步骤：第一步是根据客流等信息提出满 8 足客运需求的整体时刻表，第二步是根据地铁公司的资源以及发车时的实际情况， 对整体时刻表进行微调。这两个步骤类似于国内单条线路公交时刻表编制方法的 基本流程。文献中建立了时刻表生成的多目标模型，并首次提出了乘客不满意度 这一观点。这一模型的目标包括，一方面使得地铁公司的运营成本最小，另一方 面使得在某条线路等待的乘客的不满意度最小。最后通过多目标进化算法对模型 进行求解，并将实验结果与实际使用的时刻表做了对比。 f a ny a n g 等人【1 9 】贝u 在2 0 0 7 年通过对地铁时刻表和发电站频率的现实问题，对 多目标问题求解的算法做了进一步研究。2 0 0 8 年，c mk w a n 和c s c h a n 9 2 u j 在2 0 0 4 年的研究基础上对地铁时刻表的同步问题进行了研究，建立了多目标模型，根据 乘客等待时间的不同来衡量乘客的换乘不满意度，并充分利用了前一篇文献中对 地铁时刻表的优化结果。 2 1 3 其他模型与算法 l e e k k - t 和s h o u f e l d ，e m t 2 1 1 于1 9 9 4 年提出了换乘枢纽协调调度的时刻表编 制和动态调度模型，研究了公交起点站和终点站实时调度控制中，对即将发出的 公交车实行屯车策略，确定优化的发车间隔，并将枢纽协调调度时刻表编制模型 分为了两个步骤，第一步不考虑调度实施层面的协调关系，仅通过对各条线路车 辆发车间隔的优化实现换乘客流候车时间的最小化，其相关的支持技术是公交本 线车辆运行实时控制，对发车间隔大的线路要控制其车辆运行正点率，对发车间 隔密集线路要控制其车辆运行间隔的均衡；第二步是从时刻表编制和调度实施两 个层面考虑对多条公交线路进行协调调度，建立待协调线路集，然后以线路发车 间隔和离站松弛时间为决策变量建立相关成本目标函数，对待协调线路集的时刻 表进行联合优化，并在调度实施中通过驻站时间控制来实现相关线路的协调动态 控制。 d a d u n a 和v o s s 冽在1 9 9 5 年研究了列车同步换乘问题，他们用等待换乘的乘 客数目来衡量列车网络中的总换乘时间，并考虑了列车的停站时间和发车次数等 因素。除此之外，还根据早晚高峰和乘客类型的不同，对换乘站进行了权重标记。 最后使用禁忌搜索优化工具对整个网络的时刻表进行了同步调整。 2 0 0 4 年f l e u r e n t 2 3 】在区域时刻表编制问题中引入了三种换乘时间类型：最小 时间、最大时间和理想时间。综合这三个概念，形成了同步换乘问题的复合质量 指标，并建立了网络流的模型。在这一模型中，网络中每条弧线的成本即为同步 换乘质量指标。最后使用拉格朗同松弛和启发式机制对问题进行了求解。 9 2 2 国内研究情况 近年来，对于公交运营计划的编制问题，国内的研究方向主要集中在通过建 立数学模型并结合运筹学等学科的相关知识，同时借助计算机，利用各种算法来 确定各个时段的发车次数、发车间隔，从而建立公交时刻表。而由于国内的公交 运营模式为单线调度模式，因此对于区域调度这部分的研究，大都处于理论摸索 和学习阶段，其科研成果主要集中在近两年。部分文献专注于区域公交时刻表的 编制问题，但大都参照了c e d e r 的0 1 规划模型，因此在实际应用时，也具有和此 模型一样的缺陷，不能满足国内公交企业的实际需要。 2 0 0 3 年，邹迎等人【2 4 】分析了北京公交运营组织与调度的现状和问题，提出了 区域运营组织与调度的初步设想。对支持区域运营组织与调度的关键技术作了进 一步描述。并对运营组织与调度区域化的效益进行了分析。同年杨晓光等人 6 2 1 研 究了公交换乘时间最短调度问题，提出公交出行时间由公交乘行时间、步行时间 和候车时间( 包括换乘候车时间) 组成。以总的公交出行时间最短为目标，分单 站点和多站点两种情况提出了优化换乘时间的线性规划模型。但是，这一研究限 于两条公交线路间换乘相关的情况。 2 0 0 4 年，尹相勇【2 5 】重点分析了区域调度涉及的问题和应对措施，在此基础上 建立了研究的整体框架，提出并建立了公交区域行车计划模型和公交区域调度局 部优化模型。以实际运营与行车计划偏差量最小为调度目标，提出并分析了发车 时间间隔、司售人员工作时间、发车次序、客流量变化4 类偏差量的特点，建立 了基于行车计划的公交区域调度局部优化模型并设计了算法。在时刻表编制这一 子问题中，模型强调首末站行车时刻表中不同时段的公交车辆发车时间、发车时 间间隔等因素满足该时段最大断面客流量所需的配车数等参数，但是模型中没有 体现多条线路之间的协调关系。 2 0 0 7 年，刘志刚等人【2 6 】在c e d e r 的研究基础上，将以乘客换乘时间最少为目 标的区域公交时刻表的编制问题，归结为一类特殊的带有协同系数且无容量约束 的0 1 背包问题，并定义了协同系数，建立了相应的数学模型，给出了基于嵌套式 的禁忌搜索算法的模型解法。同年，石琴【27 】等人建立了以车辆相遇总次数最大为 第一目标，以多辆车同时相遇的机会最大为第二目标的双目标优化模型。采用启 发式算法对模型进行求解，得出具有最大同步性的发车时刻表。结果表明：该模 型实现了同时到达网络中换乘点的公交车的数量最大，从而使乘客可以在最短的 等待时间内在换乘点从一条线路转到另一条线路上。由于这两位学者的研究是在 c e d e r 模型的基础之上改进得出的，因此也没有从根本上避免其缺点。 同年，邹迎对区域行车计划的编制方法进行了研究，其研究成果与上述二人 l o 的研究成果出发点不一样。文献中以多条公交线路的区域调度为对象，建立了基 于社会总体效益最优为目标( 综合乘客等车、车内费用及公交公司成本最小) ，对多 条线路的车辆调度形式和发车时刻同时进行优化的模型，提出了“逐条配班，优 化成网”的求解思想【2 引。但是文献并没有对“乘客等车”这一成本做出具体的定 义，侧重点放在节省运营车辆、运营时间，减小公交公司的成本，而不是提高公 交服务的质量上。 2 3 本章小结 本章没有局限于公共汽车交通的区域时刻表生成问题来进行文献综述，而是 对公交、地铁等多种交通系统的区域时刻表生成问题的研究成果进行了归纳、描 述。通过这部分的总结和分析工作，了解到现有模型的缺陷；同时，前人的研究 成果中提出了“刚好错过 的概念【1 2 1 ，并在建立模型时区分对待等待时间不同的 乘客，并对乘客的满意程度进行了定量计算【2 0 1 ，这一思想在本文的建模工作中起 到了非常重要的启发作用。另外，关于多目标模型求解算法研究方面的文献【2 9 】【3 0 1 ， 对本文的模型求解也有很大的帮助。 3 区域公交a - t n 表编制问题 在我国大部分城市交通系统中，公共交通客运的特点是定时、定线、定站。 所谓定时是指公共交通线路的首末车时间、发车间隔等是根据运营作业计划事先 确定的；所谓定线是指公共交通的线路走向按照客流规律设置；所谓定站是指公 共交通线路所途经的停站地点是根据客流需要选定的，它们都具有相对稳定性， 是衡量公交服务水平的指标。因此，它们在一定时期内都不能轻易改变。在公共 交通运输管理工作中，公交调度计划是核心问题之一，是实现定时、定线、定站 的基本保证。 公交企业需要定时完成客流调查，结合企业内部的资源，进行生产计划的编 制并进行作业计划的实施。简单地说，就是确定每天的发车时刻，并安排由哪位 驾驶员负责哪台车辆在哪条线路上如何行驶，每一个资源单位都必须做好安排和 计划，然后交与相关调度人员和驾驶员执行，同时向公众公布乘车时刻表。 3 1 公交调度计划的基本原理 公交调度计划问题涉及到合理分配公交企业的资源。而调度计划就是在一定 的限制条件下，合理配置各项不同特性和数量的资源，来最大限度地满足特定的 调度和管理目标。公共交通调度计划的原理为四步法【3 1 1 ，包括路网规划设计、时 刻表的生成、车辆调度和劳动配班。其制作过程如下：首先根据客流调查的资料， 来合理设计路网，保证交通流的平衡；然后根据各峰谷时段对车辆的需求量以及 车辆满载率等参数，确定公交线路的时刻表；再次进行车辆调度，将发车时间安 排到具体的车辆；最后进行驾驶员和售票员的配班调度。整个流程如图3 1 所示。 在国内大部分城市中，公交企业所使用的四步法，只有第一步涉及到某一区 域，其他三步均是以线路为组织单位的，偶尔会在车队内部进行微小的调整。从 现阶段的情况来看，路网设计这一步已经基本确定，只有在某一区域情况发生大 的变化( 例如，公园等公共设施的新建、拆迁) ，影响到区域的客流分布时，才 会对路网进行调整。而后面三步，则构成了公交企业r 常使用的生产作业计划一 行车计划。 1 3 图3 1 公交调度的四步法原理示意图 f i g 3 - 1t h ef o u r - s t e pp r i n c i p l eo f p u b l i ct r a n s p o r ts c h e d u l i n g 3 2 公交r , 3 亥l j 表概述 3 2 1 行车计划与时刻表 公交行车计划( p u b l i ct r a n s p o r ts c h e d u l i n g ) 是城市公共交通企业管理的重要 基础工作之一，它是在现行运营管理模式下根据运营生产特点，全面分析运营生 产条件和乘客在现阶段的要求而确定出合理的运营服务水平之后编制的，是用以 组织和指导公共交通运营生产的全过程，从而保证城市交通系统完成人们在城市 范围内的位移这一基本功能得以充分实现的生产作业计划。公交行车计划包括时 刻表、车辆计划以及班组计划。 时刻表( t i m e t a b l e ) 按照线路当前客流量变化的情况，投入使用的车辆数量 以及预订服务水平指标等因素确定线路的当前发车间隔。客流量和指标参数是随 着时刻不同而变化的，发车间隔也需要做相应的改变来满足客流变化的需求。 车辆计划在时刻表的基础上，确定了满足客流量情况所需配备的车辆数以及 1 4 各车辆在全天的运营情况，即每一车辆何时出场，承运哪些车次，何时回场等等。 班组计划确定了完成全天客运量任务所需配备的班组数，以及各班组的工作 任务，包括何时上班，承运哪些车次，何时就餐，掉头休息时间，何时下班等等。 需要注意的是，在国内的公交企业中，工作人员经常将行车计划称为“时刻 表 ，这种说法将时刻表的概念进行了广义化，是不完全准确的。公交调度的四 步法必须按部就班地进行，下一步的计划用到上一步的结果。也就是说，在路网 设计基本不发生变化的情况下，调度计划的制作基本是按确定时刻表、车辆调度 和劳动排班的顺序进行。 对于广大乘客来说，他们只关心公交企业给出的时刻表，而并不会注意每一 时刻是由哪一辆车、哪一组驾驶员和售票员来运行的。而与此同时，与公交企业 利益息息相关的车辆计划和班组计划也必须建立在时刻表的基础上。因此，时刻 表是公交行车计划的基础，也是公交企业与乘客的接口。 公交时刻表可以从两个方面进行分类【l 】： ( 1 ) 不同季节的发车时刻表 季节的变化，对乘客的乘车规律产生影响。春秋季是旅游、购物的季节，低 峰客流量较其他季节大。夏季气候炎热，早晚高峰时间客流量不集中，晚间客流 量较大。此外，还有社会上各单位作息时间的变更，大、中、小学假期等等影响 因素。根据不同季节客流规律的变化，要调整和重新编制行车时刻表。在一年中， 原则上有春、夏、秋、冬四个季节的发车时刻表。 ( 2 ) 不同日期的发车时刻表 由于一周内平日、周末、公休日的客流量具有一定的变化，因此对于不同的 日期也需要有不同的行车时刻表。平日的五峰出现时间比较固定，每天各个区的 客流量变化不大；公休日工作客流小，游览区、商业区的客流量大，低峰时间投 入的运力大于平日；周末主要表现在晚高峰客流上升的时间早，客流量略大于平 日晚高峰的客流量，需提前加车。 3 2 2 公交客流及其规律 客流是指出行需要乘坐公共交通车辆以实现其位置移动而达到出行目的的乘 客群。也可以解释为：客流是在公共交通线路某一方向、某一断面上在一定时间 内用某种交通工具来实现位置移动的乘客的总称。公交调度四步法的前两步，路 网设计和时刻表编制都建立在公交客流数据的基础之上。 一份行车时刻表一般要执行3 个月，行车时刻表变更后，乘客要摸索乘车规 律，司售人员也要随之安排要工作和生活，因此行车时刻表不会轻易变动。那么， 1 5 提高行车时刻表的编制质量就至关重要了，编制前应对下一期运行环境、客流规 律的变化有预见性，资料、数据要丰富准确，根据客流规律