（系统工程专业论文）集成化的公交运营计划编制方法研究.pdf

中文摘要 摘要：随着世界各地城市现代化程度的提高，城市交通拥堵问题日益严重，发展 公共交通是解决这一问题的重要途径之一。运营调度管理是公交企业的核心业务， 驾驶员调度作为公交调度管理中的重要组成部分，关系着整个调度计划的人员使 用效率和运营成本。科学合理的调度方案可以减少运营成本，提高调度管理的效 率和水平。 本文首先介绍了传统的顺次化车辆驾驶员调度问题的模型与算法，讨论了车 辆、驾驶员调度问题集成化的潜在效益。以此为基础，综合考虑车辆调度问题和 驾驶员调度问题的目标及约束，建立集成化调度模型。本文利用拉格朗日松弛与 列生成法相结合的拉格朗日启发式算法对集成化问题进行下界估计，同时得到与 此下界相对应的行车计划；然后利用遗传算法求解驾驶员调度的集合覆盖问题， 生成覆盖所有车辆任务且总成本最小的班次计划。最后本文选取了北京公交第四 分公司的真实客流数据对所设计的模型和算法进行了实验。实验结果证明了集成 化算法的适用性。 关键词：集成理论；运营计划编制；列生成法；拉格朗日松弛；遗传算法 a b s 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 l 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 i no r d e rt os o l v et h ep r o b l e m s ，t h ep u b l i c t r a f f i cs h o u l db eh i g h l yd e v e l o p e d ，m e a n w h i l e ，p u b l i ct r a f f i cs y s t e mm u s tb ei m p r o v e d c o n t i n u a l l yt of a c et h ei n c r e a s i n g l yt r a f f i cp r e s s u r e d r i v e rs c h e d u l i n gp r o b l e mi sa n i m p o r t a n tf a c t o rt oi m p r o v et h ep u b l i ct r a f f i cc a p a c i t ya n de f f i c i e n c y g o o dd r i v e r s c h e d u l en o to n l yb em o r ef a i r , r e a s o n a b l ea n de f f e c t i v ef o rd r i v e r s ，b u ta l s os a v et h e c o s to ft h eo p e r a t i o n s t h et h e s i sd e a l s 谢t hm o d e l s ，r e l a x a t i o n sa n da l g o r i t h m sf o ra ni n t e g r a t e da p p r o a c ht o v e h i c l ea n dc r e ws c h e d u l i n g p o t e n t i a lb e n e f i t so fi n t e g r a t i o na l ed i s c u s s e da n da n o v e r v i e wo ft h el i t e r a t u r ew h i c hc o n s i d e r sm a i n l yp a r t i a li n t e g r a t i o ni sp r o v i d e d w e p r o p o s en e wm a t h e m a t i c a lf o r m u l a t i o n sf o ri n t e g r a t e dv e h i c l ea n dc r e ws c h e d u l i n g p r o b l e m sa n dc o r r e s p o n d i n gl a g r a n g i a nr e l a x a t i o n sa n dl a g r a n g i a nh e u r i s t i c sa l e d i s c u s s e dt os o v l et h ep r o b l e m s t os o l v et h el a g r a n g i a nr e l a x a t i o n s ，w eu s ec o l u m n g e n e r a t i o na p p l i e dt os e tp a r t i t i o n i n gt y p eo fm o d e l s t h et h e s i si sc o n c l u d e d 、) l ，i ma c o m p u t a t i o n a ls t u d yu s i n gr e a ll i f ed a t a , w h i c hs h o w st h ea p p l i c a b i l i t yo ft h ep r o p o s e d t e c h n i q u e st op r a c t i c a lp r o b l e m s k e y w o r d s ： i n t e g r a lt h e o r y , s c h e d u l i n g ；c o l u m ng e n e r a t i o n ；l a g r a n g i a nr e l a x a t i o n ； g e n e t i ca l g o r i t h m 图目录 图3 1 分级调度组织模式1 2 图3 2 行车计划制定流程1 2 图3 3 行车时刻表的确定1 4 图3 4 驾驶员调度方式示意图1 8 图3 - 5 标注了换班机会的行车计划。19 图3 - 6 连续驾驶段示意图2 0 图3 7 驾驶员调度示意图2 0 图3 8 五峰型线路昼夜性客流变化峰值曲线2 2 图4 1 顺次化运营计划编制机理2 5 图4 2 车辆调度问题网络图2 9 图4 3 双向竞标算法示意图3 2 图5 1 运营计划编制的4 个相关阶段4 5 图5 2 集成化问题求解思路4 8 图5 3 拉格朗日启发式算法流程图5 3 图5 5 网络g 示意图5 5 图6 13 3 4 线路某工作日全时段、全站点客流量分布图。5 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：繇学巾 签字日期：册子年6 月岁日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：硼学彤 签字日期：础年6 月5 日 致谢 本论文的工作是在我的导师关伟教授的悉心指导下完成的，关伟教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来关伟 老师对我的关心和指导。 尹相勇、孙宏声、卫振林老师对我的论文提出了很多宝贵意见，在此向三位 老师致以真诚的感谢。 马继辉老师在学习上和生活上都给予了我很大的关心和帮助，在此向马老师 表示衷心的谢意。 毕军、李宝文老师悉心指导我完成了实验室的科研工作，并在学习上和生活 上给予了我很大的关心和帮助，向两位老师表示衷心感谢。 在实验室工作及撰写论文期间，何蜀燕、翟东伟、陈鹏、贾洪旭、郑鑫、陈 石、付鹏威等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的 感激之情。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 1 1研究背景 2 0 0 3 年，美国的洛杉矶市停止了其规模庞大的轨道交通建设，而将资金用于 建设城市快速公交网络。而早在1 9 9 8 年，波哥达市长就拒绝采用建设轨道交通及 高架道路的投资方案来缓解该市的交通拥堵问题，他采用了建设大容量快速公交 系统及建设自行车专用路网来改善城市交通，取得了不错的效果。因此，常规公 共汽车交通仍作为各个城市的地面客运中的主力军，并随着信息技术的发展而更 加便利，针对公共汽车客运的各方面的研究也从来都是交通研究的热点。 多年的研究表明，建立先进的公共交通系统，提高道路通行能力和公交车辆 运营管理水平，是解决城市交通问题的一个重要途径。而衡量公共交通系统管理 水平的标准主要是其调度水平的高低。对于公交企业来说，其核心业务是向公众 提供运营服务。由于公交企业的运营资源有限，因此，合理、高效地利用现有资 源来最大限度地满足公众的出行需要对公交企业至关重要，它可能为公交企业带 来巨大的成本节约，这就是被广为关注和研究的公交调度问题。为了与实时调度 相区别，本文称该问题为公交运营计划编制问题。 利用计算机编制运营计划的研究开始于上个世纪6 0 年代，迄今已有很多运营 计划编制方法和系统被研制出来，其中许多得到了成功应用。但在我国该领域的 研究与应用基本上还是空白。国内目前的公交企业大都采用手工方式编制运营计 划，由于编制运营计划是一项非常复杂的工作，如果通过手工来排，一位非常有 经验的管理人员也要花费三到五天的时间才能完成。而且由于运营计划完全用人 工方式完成，所以很难印证其正确性和有效性。因此由人工方式完成的运营计划 也就成了一个摆饰，很难在调度人员的日常工作中起到非常有意义的指导作用。 近年来随着竞争意识的加强，竞争环境日趋形成，越来越多的公交企业开始 认识到提高运营资源利用率的重要性，并着手寻求适用的工具。以2 0 0 8 年奥运会 为契机，以北京、上海、青岛、大连、中山、内蒙为代表的几大城市先后进入智 能公共交通系统的建设阶段。新的管理方式将改变人们对交通工具的认识，也将 改变人们的生活工作方式。在智能公交系统建设前的所有繁琐复杂的手工操作将 由计算机代替，同时也将为乘客提供更高质量的服务与便利。 “大公交刀运营环境下，公交运营系统是一个复杂的系统，对运营计划编制 工作而言，需要考虑包括有车辆、人员、线路、站场、劳动规则和调度模式等多 方面的影响。因此，运营计划编制工作要同时满足客观运营条件的限制和主观效 益指标的要求，是一件非常复杂的工作，采用手工方式是肯定不适合的，即使是 采用计算机软件来编制运营计划，也需要一个非常高效的调度算法作为技术支持。 因此可以说，一个运营计划编制软件系统的研究，关键是算法研究。 公交运营计划编制一般分为四个主要的过程，分别是：发车频率确定并建立 时刻表，车辆调度、劳动配班和劳动排班。后两个过程合称驾驶员调度。在公交 实际工作中，时刻表的建立和劳动排班的完成都是费时费力的工作，但是，考虑 到前者已有相当成熟的算法，后者的实现仅仅是逻辑问题，因此国内外对运营计 划编制问题的研究往往集中在制定车辆计划和生成劳动班次上。本文下面的章节 所提到的驾驶员调度问题都是指劳动班次生成问题。 作为城市运输领域一个经典的n p h a r d 问题，运营计划编制一直为国内外专 家所重视。受限于问题的规模，目前国内外研究和系统实现中通常分两步解决该 问题。首先根据发车车次安排车辆计划，然后将车辆计划作为输入条件，生成合 理的劳动班次覆盖车辆计划。关于求解集成化的车辆人员调度问题对降低运营成 本所起的作用，f r e l i n g 在 1 】中已经做了论证，因此本文将重点讨论如何提高此集 成化问题的求解效率。 另外，在国内关于公交调度的理论研究上，很多学者已经尝试使用各种启发 式算法进行求解，但是在利用计算机进行公共交通调度方法方面的研究与国外先 进水平还有较大差距。同时，虽然国外已经成功地开发并应用了一些解决运营计 划编制问题的软件，但是对于现有的模型方法并不能盲目的照搬到国内，国内外 在管理模式，调度方式等有着很大的不同，对于调度计划问题的建模常常都是从 实际调度情况出发的，所以如何结合国内调度现状来分析车辆和驾驶员调度问题 是本文的目的之一。 目前国内对智能化运营计划编制方法的研究都在探索阶段，研究思路多以顺 次独立解决车辆调度问题和驾驶员调度问题为主。本文分析了运营计划编制各流 程间的相互影响，对车辆人员集成化调度的潜在效益、模型、求解及算法适用性 进行了探讨，旨在对传统的顺次化车辆人员调度方法进行优化，并为智能化运营 计划编制方法的研究提供新的思路。 1 2论文结构和主要内容 根据研究内容，本文一共分为六章： 2 第一章是概述，主要介绍运营计划编制问题的研究背景，文章的体系结构和 主要内容： 第二章对运营计划编制问题研究的发展进行综述，分别讨论了国内外关于发 车间隔及时刻表确定、车辆调度、驾驶员调度的相关研究成果，介绍了集成化问 题的研究现状，并对这些研究成果进行分析评价； 第三章将对公交运营组织与调度业务作简要的介绍。主要包括调度作业简介、 运营计划编制流程介绍，以及公交客流规律对运营计划编制的影响。在介绍运营 计划编制流程时，对公交相关具体业务及术语作了较详细的介绍。 第四章对智能化的公交运营计划编制系统的关键技术进行研究。首先介绍了 基于时段划分的发车频率确定方法，然后分别对车辆计划及驾驶员调度问题的模 型与算法进行重点研究。对车辆计划问题，本文将其看作准分配问题，并利用组 合竞拍算法求解该问题；对驾驶员调度问题，本文继续沿用“生成 与“选择” 机制，首先生成可行班次集合，然后利用拉氏启发式算法结合遗传算法求解集合 覆盖问题。 第五章将车辆计划问题和驾驶员调度问题结合起来讨论，建立集成化调度模 型。利用拉格朗日启发式算法对集成化问题的下界进行估算，并得到与此相对应 的行车计划计划；最后基于此行车计划计划求解驾驶员调度问题。 第六章为实例分析，利用北京市公交公司车辆线路数据检验模型与算法的适 用性； 第七章为得出的结论，将对全文进行总结，概括本文的主要工作，并对今后 研究运营计划编制问题提出展望。 3 2 国内外研究理论与方法综述 2 1国外研究情况 2 1 1 行车时刻表 公交时刻表编制是公交调度中的一项关键性工作，历来是公交调度研究工作 中的热点问题，它既关系到乘客对公交的满意度，也关系到公交公司的运营效益。 对于公交时刻表编制的研究，目的就是编制出满足乘客需求，同时也能使得公交 公司运营效益最大的时刻表。 公交时刻表是由公交发车频率或者是发车时间间隔来确定的。从上个世纪八 十年代开始，就有众多国外学者，用数学规划方法研究如何确定发车频率。f u r t h 和w i l s o n ( 1 9 8 1 ) 【3 8 】采用了在总的成本，公交运力和载客率确定的约束条件之下， 使得乘客等待时间最少，社会效益最大的数学模型来确定公交发车频率。c e d e r ( 1 9 8 4 ) 【1 6 】给出了四种不同发车频率确定方式，其中有两种方式是基于在某个站 点某个时间段统计得到的乘客到达数量来确定，用客流量最大的那个时间段的某 个站点乘客到达的数量除以所期望的公交载客量就得到发车频率。另外两种方式 是基于某个时间段内，整个线路乘客的周转量来确定，用线路通过的乘客周转量 除以所期望的载客量得到发车频率。c e d e r 和s t e m ( 1 9 8 4 ) 【2 0 】对于该问题，建立 了一种整数规划模型，使用启发式算法，借助计算机程序，实现了模型的求解过 程。k o u t s o p o u l o s ，o d o n i 和w i l s o n ( 1 9 8 5 ) 【1 4 】在f u r t h 模型的目标函数之中，加 入了刻画乘客舒适度的一种量化成本值，区分了在不同时间段的不同的需求，得 到了一个非线性优化模型，并且改进了该模型得到了一个线性模型，从而简化了 模型的求解过程。c e d e r ( 1 9 8 6 ) 1 9 】研究了基于不同类型的发车时间间隔和不同方 式所确定的发车频率以及特殊情况下的发车需求来编制公交时刻表编制的三种不 同方式；a d e b i s ，o 和x uj r j 研究了行车间隔对公交服务水平的影响，如何通过间 隔控制来改善公交服务的可靠性，维护行车时刻表的正常执行。 2 1 2 车辆计划 当公交时刻表确定之后，剩下的问题就是为时刻表中确定的每个车次安排车 辆。每条线路上的客流量随着时间的变化而变化的，因而发车频率在不同的时间 5 段也有变化，那么在不同的时间段一条线路对车的数量需求是不一样的。车辆调 度问题就是在满足给定时刻表中所确定的车次需求，使得车辆的总数量最小。 g a v i s h 和s h i f t e r ( 1 9 7 8 ) 【5 】将调度问题转化成了在满足行车班次需求约束条件 下，使得车辆数量以及车辆在运行过程中空驶时间最小的数学模型，并且给出了 模型的求解算法。在这个模型中，假定在同一个区域内的运行的公交车辆停放在 同一个站场。b o d i n 和g o l d e n ( 1 9 8 1 ) 【1 3 】采用两阶段法对该问题( s i n g l ed e p o t 舡d e s c h e d u l i n g ，s d v s ) 进行了求解。而当在模型中加入其它约束时，例如线路对于行 驶时间的约束，该问题就变成了n p 难题( 不确定多项式问题) ，只能通过启发式 算法进行求解。 b e n o s s i 【9 】等人研究了区域内有多个停车站场情况下的车辆调度问题( m u l t i p l e d e p o tv e h i c l es c h e d u l i n g ，m d v s ) 。建立了在满足发车班次需求的条件下，使得车 辆数量最少和每辆车停放在恰当地点从而减少运行成本的数学模型。并且证明该 问题也是一个n p 难题。m d v s 问题为多线调度的实现提供了可能。 l a m a t s c h ( 1 9 9 0 ) 1 2 】将m d v s 问题转化成为一个多种货物从不同的源点 ( o 啦；i n s ) 运往不同的目的地( d e s t i n a t i o n ) 的网络流量问题，并且给出了2 5 0 个 班次，2 个站场以及2 0 0 个班次，3 个站场的车辆调度方案。 m e s q u i t a 和p a i x a o ( 1 9 9 7 ) 1 5 】将模型进行了简化，使用分枝定界法进行求解。 在解决m d v s 问题中，最成功的是l o b e l ( 1 9 9 7 ) 。他采用一种称为拉格朗日定价 ( l a g r a n g e a np r i c i n g ) 的特定列生成法，解决一个非常复杂的实际问题。他的模型 中没有考虑线路运行时间的约束，他的模型与f o r b e se ta l ( 1 9 9 4 ) 的模型十分类似。 h a g h a n i 和b a n i h a s h e m i ( 2 0 0 2 ) 【3 】给出了有线路运行时间约束的m d v s 问题 的0 1 规划模型和算法。在他们的模型中，将车次根据发车时间的不同分成三个 集合：上午班次( m o r n i n gt r i p s ) ，中午班次( m i d d a yt r i p s ) 和下午班次( a f t e r n o o n t r i p s ) 。还根据车辆空载时间与连续运行时间的约束将车次划分成站场相容班次 ( d e p o tc o m p a t i b l et r i p s ) 和路线相容班次( s t r e ；e tc o m p a t i b l et r i p s ) ，如果车辆在执 行完前一个班次回到站场后再执行新的班次，则称这两个班次是站场相容班次， 如果车辆在执行完一个班次直接执行下一个班次，因为如果回到站场后再执行下 一个班次，是一个不太可行或者成本太高的方案，则这两个班次为路线相容班次。 在这个车次分类基础上，建立了有时间约束的m d v s 问题的o l 规划模型。 2 1 3 驾驶员调度问题 最早利用计算机进行驾驶员调度研究开始于上世纪6 0 年代，经过多年的发展， 形成了很多先进的成果和应用软件，回顾整个发展过程，这些方法主要可以分为 6 两大类：启发式算法和数学规划方法。这两种方法并不是互相排斥的，相反，数 学规划方法中经常用启发式方法来求解；在启发式方法中又需要者数学规划方法 来建模。 2 1 3 1 纯启发式算法 早期对公交驾驶员调度问题深入研究的主要有美国的e l i a s t 6 和英国利兹大学 的w e a v e r 8 】和w r e n 1 0 】等人，当时的系统有相对成熟的t r a c s ( t e c h n i q u ef o r r u n n i n g a u t o m a t i cc r e ws c h e d u l i n g ) ，和r u c u s ( r u n c u t t i n ga n ds c h e d u l i n g ) ， 还有采用交互式的c o m p a c s ( c o m p u t e ra s s i s t e dc r o ws c h e d u l i n g ) 。解决方法采 用的是启发式方法，当时计算机的功能还不够强大，另外，数学规划设计者对驾 驶员调度问题的理解也不够成熟。早期大多数基于启发式算法的驾驶员调度系统 生成时刻表的方法与当时人工排班的方法很相似，对于调度计划的修改往往采取 人工和系统交互的方法，实际上对于调度计划的改进十分的有限。 启发式方法的系统在一些应用方面取得了成就，原因在于他们比较适用于独 立的公司，因此，它可以按照公司的需求进行设计。尽管如此，这种系统还是需 要了解专业知识和公司的特殊需求，系统的普适性较差，并且在面对新的环境和 用户时要进行相当大的修改。直到8 0 年代，人们渐渐意识到单纯依靠启发式算法 无法很好的解决驾驶员调度问题的，所以纯启发式算法目前已经基本被淘汰了， 取而代之的是结合启发式算法的数学规划方法。 2 1 3 2 数学规划方法 在7 0 年代后期，数学规划方法开始流行起来。现有的大多数的驾驶员调度系 统都建立在数学规划方法的基础上，其中驾驶员调度问题经常被建模成为一个集 覆盖或者集分割问题。 基于数学规划的公共交通驾驶员调度方法习惯被称为“生成与选择”模式， 实际上但并不是纯粹的整数规划方法。这种模式主要包含两个阶段：“生成 和 “选择。其求解步骤如下：首先采用启发式方法依据劳动法规生成全部好 的驾驶班次，构成一个大的解元素集合；然后采用整数线性规划方法选择一个子 集，使该子集中的全部元素结合起来能够构成一个可行解( 即，覆盖全部的车辆运 营工作) ，同时，要求这个解满足一定的目标函数，如：采用最少的驾驶班次，并 且或者，具有最小的运营成本。 生成一个有效班次集合是基于“生成与选择 模式的驾驶员调度方法的基础。 对一个实际问题，包含全部有效班次的集合通常太大以至于超出当前l p 的求解能 力。因此，目前的做法是凭借经验仅仅生成“好的班次，具体方法包括：增加 7 一系列的“软限制条件 与劳动法规共同制约班次的有效性，进而降低生成的有 效班次个数；利用启发式方法筛选掉部分换班时间点来缩小问题规模；利用启发 式方法进一步筛选掉己生成的但不太“好 的班次。 在“选择”阶段最为关键的是建立一个合适的模型。包含1 1 段车辆工作( 两 个连续的换班时间点之间的工作称为“小驾驶段 ) 和m 个有效班次的驾驶员调 度问题一般可以被模型为如下一个集覆盖问题。在优化的过程中需要考虑可行的 班次的集合及其成本。集覆盖寻找一个覆盖所有车辆工作的班次集合，并且可行 解的成本最小。 2 1 3 3 元启发式算法 进入9 0 年代以来，为了克服数学规划方法的局限性，当数学方法继续发展的 同时，一系列新的研究方法应运而生，其中，元启发式方法( 主要包括：禁忌搜 索、模拟退火和遗传算法等) 和约束规划方法( 均被归属于人工智能方法) 较为 活跃，它们试图能够处理更大规模的实际问题。但时至今日，用于解决公交调度 计划问题的人工智能方法大部分仍然同数学规划方法一样将调度计划问题模型为 集合覆盖或集合切分问题。也就是说，他们仍然延续着数学规划方法中的“生成 与选择模式，即，首先生成一个大的解元素集合，然后，从中选择一个子集， 这个子集中全部元素结合起来要求能够构成一个可行解，同时，要求这个解要满 足一定的目标函数，如：具有最小的成本。这些采用了“生成与选择一模式的新 型的人工智能方法求解速度可能会快于i l p 方法，并且被期望可以处理更大规模 的问题。 遗传算法( g e n e t i ca l g o r i t h m ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d 教授等 人于1 9 7 5 年首先提出来的，遗传算法的基本架构来自达尔文的进化论，经由基因 的编码、复制、交叉、变异、取代来达到进化的目的。 b e a s l e yj e 【3 0 】在使用遗传算法解决驾驶员调度问题时，首先将问题建立成一个 集覆盖的模型，集覆盖问题可以表示为一个m * n 的0 1 矩阵，以行来代表求解的 单位值，也就是为可行班次的集合。而列表示每行所包含的属性，也就是所有的 连续驾驶段集合。目标主要在求解能以最少的行数即包含所有的属性。在使用遗 传算法求解驾驶员调度问题的时候，基本上还是套用数学规划方法中的模型，只 是在具体求解方法上有所不同。 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 的思想最早在1 9 8 6 年由 g l o v o r 提出【蚓，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是 对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁忌 准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证 8 多样化的有效探索以最终实现全局优化。相对于遗传算法，t s 是又一种搜索特点 不同的元启发式( m e t a - h e u r i s t i c ) 算法。迄今为止，t s 算法在组合优化、生产调 度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数 全局优化方面得到较多的研究，并大有发展的趋势。禁忌搜索基本工作原理是由 禁忌表中记录一些过去的搜寻轨迹( m o v e ) ，每次搜寻策略必须先与此禁忌表比较， 因此可避免循环解的产生。此外由于每次搜寻到的解并不一定比前一解为佳，因 此必须另行记录一个到目前为止的最优解，作为搜寻结束后的解答。 2 1 4 车辆驾驶员调度集成化问题 随着运营计划编制问题的深入研究以及公交系统本身的发展完善，大量新的 方法不断涌现。比如说针对整数规划模型的列生成、分支定价法、集合分割、启 发式算法、遗传算法等。此外，求解方式也从开始的车辆人员的分离式方案转换 为解决车辆人员排班的集成式方案。文献 2 1 2 9 都是针对集成式方案的研究与实 践。 文献 2 2 ，2 3 研究了使用基于列生成的分支定价方式求解大整数规划问题的方 法，其主要思想是将问题看成一个主问题( m a s t e rp r o b l e m ) ，然后利用列生成产生 多个子问题( s u bp r o b l e m ) 并求解，最后通过合并子问题获得主问题的解。虽然 该方法能够找到比较满意的解，但由于受到主问题规模的限制导致该方法仅能应 用于较小规模问题的求解。使用该方法求解的时间复杂度也比较高，很难满足实 际的需要。虽然在排班算法中线性规划、线性松弛 3 4 1 有着广泛的应用，但由于实 际应用中产生的大量变量和约束条件使得算法发生退化【3 3 】。文献 3 9 提出了一种新 的列生成算法一动态约束聚集算法。它有效地减少了规划过程生成的变量及约 束，降低了主问题的分解规模，大大缩短了线性规划的时间，提高了该方法的求 解效率。 但是，由于集成求解致使问题规模扩大，导致大量的求解算法效率低下。因 此通过将问题进行合理分割，然后利用现有方式针对分割后的子问题进行求解也 成为一种比较可行的方式。文献【2 4 】便是在这一思想的指引下进行了大量不同分割 方法的研究与试验，并最终通过大规模的试验证明了分割方法的有效性。 2 2国内研究情况 国内进行公交调度相关的研究已经近二十年左右的时间。近年来，对于公交 运营计划的编制问题，国内的很多研究方向主要集中在通过建立数学模型并结合 9 运筹学等学科的相关知识，同时借助计算机，利用各种算法来确定各个时段的发 车次数、发车间隔，并给出公交公司需要的总的车辆数、班次数。 早期的相关研究主要集中在调度模式的模型研究上，1 9 8 5 年，蒋光震、何显 慈在公共交通线路组合调度模型一文中，介绍了基于乘客分布的公交线路静 态区间调度模型3 1 1 。1 9 8 8 年，张席洲【3 2 】在硕士论文公交调度系统分析、建模与 优化中，针对公交调度优化问题进行了探索性研究。1 9 9 5 年，同济大学陈继军 结合上海市“8 5 攻关项目公交动态调度系统研究，对调度理论和调度系统设计进 行了详细研究【3 6 】。1 9 9 8 年，西安公路交通大学孙芙灵依据西安市部分公交客流调 查数据，探讨了几种确定发车间隔的方法【3 7 1 。 随着发车间隔模型和算法的不断成熟，对公交驾驶员调度模型和算法的研究 有了进一步的深入。 北京航空航天大学张飞舟【3 5 】对公交车辆智能调度及相关技术进行了研究，提 出了运用遗传算法和混合遗传算法优化车辆调度的方法。对于遗传算法的应用与 国外相关研究的方法类似，也是将问题建立成一个集覆盖的模型，集覆盖问题可 以表示为一个m * n 的0 1 矩阵，以行来代表求解的单位值，也就是为可行班次的 集合。 沈吟东【加】等近年来对公共交通驾驶员调度问题进行了描述，指出构成其复杂 性的影响因素，对驾驶员调度方法进行了简要评述。对基于整数规划的方法进行 了分析，评价其求解模式、数学模型并指出其存在的局限性。最后还指出对于我 国研究者，应结合国内实际情况，从融合多种人工智能方法、“构造式”的超启发 式方法两个方向，来对驾驶员调度问题进行深入研究。2 0 0 5 年又对基于整数规划 的t r a c si i 系统的整数规划模型和求解方法进行分析，并指出其局限性以及进一 步研究公交驾驶员调度问题的方向。 2 0 0 6 年，山东大学王鹏飞【4 l 】结合我国实际对车辆人员排班问题进行了详细分 析，并进行了模型设计，尝试使用改进的遗传算法求解该问题。同时，利用竞标 算法提高求解效率并生成符合我国实际的初始班次，使算法支持多种班型。 2 0 0 7 年，翟东伟【l l 】结合我国实际对驾驶员调度问题进行了详细分析，并进行 了模型设计，尝试使用禁忌搜索算法结合遗传算法求解。从某种程度上证明了禁 忌搜索与遗传算法混合策略能够在求解大规模的问题时，对逃离局部最优解，快 速获取全局最优解有一定的帮助。 i o 3 公交运营组织与调度业务 3 1调度作业与公交客运 在我国大部分城市交通系统中，公共交通客运的特点是定时、定线、定站。 所谓定时是指公共交通线路的首末车时间、发车间隔等是根据运营作业计划事先 确定的；所谓定线是指公共交通的线路走向按照客流规律设置；所谓定站是指公 共交通线路所途经的停站地点是根据客流需要选定的，它们都具有相对稳定性， 是衡量公交服务水平的指标。因此，它们在一定时期内都不能轻易改变。 在公共交通运输管理工作中，调度作业是核心的内容，是实现定时、定线、 定站的基本保证。 3 1 1 调度作业的组成 调度作业可以分成两大部分：调度组织以及作业计划实施。调度组织的具体 工作是进行运营计划编制，是整个公交公司资源运作的基本指导；实施作业计划 即指实时指挥调度，是实现调度组织目标的必需途径。 调度组织过程中，各线站的调度部门首先在上级运调部门的指导下，根据客 流变化规律、线路运营条件、企业运输能力以及企业社会效益、经济效益指标的 要求编制出行车时刻表，并通过行车时刻表的实施，将分散作业的各个车组纳入 计划运营的轨道，使公共交通线路运营工作有计划、有节奏地进行。同时，通过 调度系统对线路运营状态的监控和现场适时、合理的调度指挥，保持运营生产的 稳定性，从而保证公交企业顺利完成客运任务和各项经济、技术、服务指标。 3 1 2 多级运营调度组织体系 公交运营调度一般根据企业规模的大小，采用二级或三级调度的组织形式。 企业规模较大，运营线路、车辆、人员多，可设三级调度制，调度机构由公司总 调室、分公司( 车场) 调度室和线路( 车队) 调度组构成。总公司调度室主要负责定 期汇总各区域、各线路的客流动态资料，审核分公司行车时刻表，遇全市重大活 动时，拟定全市线路的行车组织方案；分公司调度室负责定期组织客流调查，整 理客流资料，均衡各线路运力，提出行车时刻表的编制要求和有关指标控制；线 路调度组负责经常对客流目测调查，编制行车时刻表，根据生产任务编排班次并 负责贯彻执行日运营计划。以北京市公交总公司为例，其组织模式、行车计划制 定流程如图3 - 1 、图3 - 2 所示。 第一级 第二级 第三级 总公司 客1客2一新奥 3 2 运营计划 l 队2 队 3 队 一 图3 - 1 分级调度组织模式 f i g 3 - 1s c h e d u l ew i t hr e l i e fs t a t i o n 审批行车计划 制定生产任务 下达生产任务 总公司调度中心 上t 客运部调度室 ji 1r 线调 上 司乘人员与车辆 行车计划 运营日报表 行车时刻表 编排劳动班次 图3 - 2 行车计划制定流程 f i g 3 - 2s c h e d u l ew i t hr e l i e fs t a t i o n 运营计划是公交运营调度作业的核心和先导，公交企业的资源的运作效率主 要是在这一环节体现出来。 公交企业的主体资源有三大类：一是作为工具的运营车辆；二是作为工具使 用者的驾驶员；三是作为营运平台的线路和站场。运营计划就是在一定的限制条 件下，合理配置各项不同特性和数量的资源，来最大限度地满足特定的调度和管 理目标。简单地说，就是安排由哪一位驾驶员负责哪一台车辆在哪一条线路上如 何行驶，每一个资源单位都必须做好安排和计划，然后交与相关调度执行人员和 1 2 驾驶员执行，同时向公众公布乘车时刻表。 运营计划的编制主要有以下步骤：行车时刻表的生成、车辆计划和班次计划 的生成，以及人员的轮替。首先设计路网，根据客流数据确定公交线路的时刻表； 然后根据时刻表编制车辆计划以满足客流需求；继而制定相应班次计划，安排一 组驾驶员来完成一日内的全部车辆任务：最后通过班次轮替，实现班次安排的公 平性和科学性。 3 2 1 行车时刻表 行车时刻表是公共交通管理系统中一份重要的计划表，是调度员工作以及车 辆正常运行的基本依据。一个有价值、效率高的行车时刻表体现了乘客候车时间 短、乘车舒适性( 乘客的利g i ) 和低成本的服务( 公交公司的效益) 两方面的均衡；编 制一个好的行车时刻表应很好地处理公交车的供给和乘客的需求之间的关系。 3 2 1 1 车次与发车间隔 首先明确一些概念。 车场：存放车辆的站点，实际生活中一般是线路的首末站或首站； 控制点：线路两端用来控制发车间隔的站点，实际生活中代表线路的首末车 站； 车次( t r i p s ) ：从a 开往对端b 的行驶行为称为自a 站发出的一个车次。每个 车次包含一组起始、结束时间、地点信息； 发车间隔( i n t e r v a l ) ：同一控制点两相邻车次的间隔时间。 编制行车时刻表最关键是确定发车间隔，发车间隔关系到乘客与公交公司两 方面的利益，从乘客的角度考虑，发车间隔短比长要好，这样乘客的等车时间少 且乘坐较舒适；另一方面，公交公司希望满载率越高越好，把发车间隔控制在一 定的时间段内，在某种程度上，两者之间的利益是对立的口。 间隔时间与行车时刻表的关系如图3 3 所示。 1 3 时段发车间隔 5 ：4 0 6 ：0 17 6 ：0 1 6 ：1 36 6 ：1 3 6 ：2 3 5 6 ：2 3 6 ：3 14 6 ：3 1 6 ：3 73 序号离站时间到站时间 10 5 ：4 00 7 ：0 4 20 5 ：4 70 7 ：1 1 30 5 ：5 40 7 ：1 8 40 6 ：0 10 7 ：2 5 5 0 6 ：0 70 7 ：3 1 60 6 ：1 3 0 7 ：3 7 70 6 ：1 80 7 ：4 2 80 6 ：2 30 7 ：4 7 90 6 ：2 70 7 ：5 1 1 00 6 ：3 10 7 ：5 5 l l 0 6 ：3 40 7 ：5 8 1 20 6 ：3 70 8 o l 图3 - 3 行车时刻表的确定 f i g 3 - 3d e t e r m i n a t i o no f r m e t a b l e 3 2 1 2 行车时刻表的种类 ( 1 ) 不同季节的发车时刻表 季节的变化，对乘客的乘车规律产生影响。春秋季是旅游、购物的季节，低 峰客流量较其他季节大。夏季气候炎热，早晚高峰时间客流量不集中，晚间客流 量较大。此外，还有社会上各单位作息时间的变更，大、中、小学假期等等影响 因素。根据不同季节客流规律的变化，要调整和重新编制行车时刻表。在一年中， 原则上有春、夏、秋、冬四个季节的发车时刻表。 ( 2 ) 不同日期的发车时刻表 由于一周内平日、周末、公休日的客流量具有一定的变化，因此对于不同的 日期也需要有不同的行车时刻表。平日的五峰出现时间比较固定，每天各个区的 客流量变化不大；公休日工作客流小，游览区、商业区的客流量大，低峰时间投 入的运力大于平日；周末主要表现在晚高峰客流上升的时间早，客流量略大于平 日晚高峰的客流量，需提前加车。 3 2 2 车辆计划 车辆计划( b l o c k ) ，是运营车辆有序的工作计划。一个车辆计划包含了一条线路 在一天内有次序地进行车辆调度的时刻表，参与运营的车辆从驶出车场开始，到 驶回同一个车场结束。 全日行车计划确定了满足一定的客运服务水平所需配备的车辆数、车型以及 各车辆在全天单独运营情况，即每一辆车何时出场，承运哪些车次，何时回场等 等。一个车辆计划是多辆车辆发车情况的集合。 1 4 行车计划编制是在已知发车时间表的条件下将车辆分配到每一条线路中去， 考虑的目标是最小车辆数和最小车辆运营成本，减小车辆运营成本的方法主要通 过减少车辆空驶时间和停站时间。 3 2 2 1 发车类型 一辆车的车次根据服务需要，可以分为不同的调度方式，即发车类型。 ( 1 ) 按车辆运行与停站方式划分，发车类型有以下几种： 正常发车：车辆由线路首站或者末站发车，载客运营，到达对端站，这种发 车类型称为正常发车； 空驶发车：车辆由车场驶出到达线路开始运营，以及结束运营工作后驶回车 场的过程中，一般不载客，称为“空驶 ； 区间发车：车辆由首站或者末站发出后，载客运营，未到达对端站就返回， 称为区间发车； 包专车：为接送有关单位职工上下班或学生上下学而组织的一种专线调度形 式。车辆可按定时间、定路线、定班次和定站点的原则进行运输。 快车：为适应沿线长乘距乘车需要，采取的一种跨站快速运行的调度形式， 包括大站( 快) 车与直达( 快) 车两种； 跨线车：为平衡相邻线路之间客流负荷，减少乘客转乘而组织的一种跨线运 行的调度形式。 表3 1 是一辆车的行车计划示例，其中停站时间表示运营车辆在到达停站点 之后，开始下一段工作之前，在停站点允许的停留时间，其中包含了最常见的前 三种发车类型。 表3 1 行车计划表示例 t a b l e3 - 1s a m p l eo fv e h i c l es c h e d u l e b l o c k1 - 车辆计划l ： 班次：l 从场站a 出发： 0 5 ：3 1 地点到达时间出发时间停站时间 a0 5 ：3 1 b 0 6 ：0 3 0 6 = 0 7 ：4 a 0 6 - 4 6 0 6 5 9 ：1 3 b 0 7 ：3 3 0 7 3 7 ：4 a0 8 ：2 30 8 ：2 6 ：3 c 0 8 ：5 4 0 8 ：5 5 ：1 a 0 9 ：3 3 0 9 - 4 2 ：9 c i o ：1 0 1 0 ：l l：l a 1 0 ：4 6 1 0 ：5 6：1 0 b l l ：3 2 l l ：3 7：5 a 1 2 - 2 1 1 2 ：2 7：6 c 1 2 - 5 5 1 2 ：5 6：l a 1 3 ：3 1 1 3 ：3 6区间：5 a1 4 ：0 01 4 ：0 5：5 a1 5 - o l1 5 ：1 2：i l c1 5 ：4 01 5 ：4 1：l a1 6 ：2 11 6 - 2 7：6 c1 6 - 5 51 6 ：5 6：l a1 7 ：3 61 7 ：3