（系统工程专业论文）多场站公交行车计划编制模型与算法研究.pdf

mj 一，。 一。 l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 套越洋 - 签字日期：y p 年易月易日 日 侈 月壶眇，6 彳 年鎏伽 ，p 名 ： 签 期 师 日 导 字 签 i v 中图分类号： u d c ： r e s e a r c ho 作者姓名： 导师姓名： 学位类别： 学科专业： 北京交通大学 2 0 10 年6 月 致谢 本论文的工作是在导师关伟教授的悉心指导下完成的，关伟教授严谨的治学 态度和科学的工作方法给了我极大的帮助和影响，使我更加明白了如何发现和解 决问题，如何做人做事。在此谨向关老师致以最崇高的敬意，并衷心感谢两年来 关老师对我的关心和指导。 马继辉、李宝文和黄爱玲老师在学习上和生活上都给予了我很大的关心和帮 助，在此向马老师、李老师和黄老师表示衷心的谢意。 此外，林磊、任淑云、牛虎、张原、杨杨等同学在实验室工作及撰写论文期 间给予了热情帮助，在此向他们表达我的感激之情。同时，曾鸣、杨进、肖华刚、 岳鼎、吴连翠等同学对我的学习工作生活给予了很大的关心和支持，感谢他们的 关心和照顾。 衷心感谢我的父母给予我的平凡而伟大的爱。他们的朴实和善良深深的影响 着我，他们的勉励和支持不断地激励着我。 最后，感谢所有帮助和关心我的人。 i v 中文摘要 摘要：随着世界各地城市现代化程度的提高，城市交通拥堵问题日益严重，发展 公共交通是解决这一问题的重要途径之一。编制行车计划是公交企业的核心业务， 关系着整个调度计划的车辆使用效率和运营成本。科学合理的编制行车计划可以 减少运营成本，提高调度管理的效率和水平。 多场站行车计划编制问题是以运营时刻表为基础，确定区域内各场站的车辆 运营任务，保证以最小的车辆运营费用完成时刻表中所有任务车次，同时要求单 个车次仅能被一辆车执行一次。多场站行车计划编制问题属于n p 难题，精确解求 法一般不能解决实际中的大规模问题，因此提出各种启发式算法来求解此问题。 本文在前人研究的基础上应用基于逆差函数的启发式过程求解多场站行车计 划编制实际问题。首先，介绍了现有行车计划编制问题的模型与算法，讨论了编 制行车计划的实际约束条件。其次，以此为基础，基于逆差函数理论，建立编制 行车计划的逆差函数模型。第三，本文采用三阶段生成最终行车计划，阶段一通 过空驶调度和弹性发车求解严格车队规模下限，严格车队规模下限可有效降低第 二阶段启发式过程的遍历次数；阶段二应用启发式过程求解最小车队规模，求解 过程以降低逆差函数的峰值为目标，逐个场站单位减小需用车辆数，得到最小车 队规模和最新时刻表；阶段三利用f i f o 规则构建单车计划，即车次链。最后首先 基于假设数据进行仿真计算，验证算法的有效性，然后选取了北京公交集团3 条 线路的真实时刻表对所设计的模型和算法进行实验。其结果证明了本文设计的模 型与算法的适用性。 关键词：公共交通；多场站行车计划编制问题；逆差函数；空驶车次；可变行车 计划；先到先发规则 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 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 d e v e l o p i n gu 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 e t h ep r o b l e m s ，t h ep u b l i ct r a f f i c s h o u l db eh i g h l yd e v e l o p e d ，i nt h em 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 v e h i c l es 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 s c i e n t i f i ca n d r e a s o n a b l ev e h i c l es c h e d u l i n gc a nn o to n l ys a v et h ec o s to ft h eo p e r a t i o n s ，b u ta l s o i n c r e a s et h ee f f i c i e n c ya n dl e v e lo fd e p a r t u r em a n a g e m e n t g i v e nas e to ft i m e t a b l e dt a s k s ，t h em u l t i p l ed e p o tv e h i c l es c h e d u l i n g p r o b l e m ( m d v s p ) c o n s i s t so fd e t e r m i n i n gt h el e a s tc o s ts c h e d u l e sf o rv e h i c l e sa s s i g n e d t os e v e r a ld e p o t sa tt h es a m et i m ee a c ht a s ki sa c c o m p l i s h e de x a c t l yo n c eb yav e h i c l e b e c a u s em d v s pi sn p - h a r d ，e x a c tm e t h o d so f t e nc a n n o ts o l v el a r g ei n s t a n c e s e n c o u n t e r e di np r a c t i c e f o rt a c k l i n gt h e s ei n s t a n c e s ，v a r i o u sh e u r i s t i ca p p r o a c h e sh a v e b e e nd e v e l o p e d o nt h eb a s i so ft h ep r e v i o u ss t u d i e s ，t h i sp a p e ru s e st h eh e u r i s t i cp r o c e d u r eb a s e d o nt h ed e f i c i tf u n c t i o nt os o l v et h ef a c t u a lp r o b l e mo fm d v s p t h i st h e s i ss u m m a r i z e s t h et h e o r i e sa n dm o d e l so ft h ev e h i c l es c h e d u l i n gp r o b l e mh o m ea n da b r o a d ，a n d a n a l y z e st h ec o n s t r a i n t si np r a c t i c e o nt h i sb a s i s ，t h i sp a p e rb u i l d s t h em o d e lo f m u l t i p l ed e p o t sv e h i c l es c h e d u l i n gp r o b l e mw i t ht h et h e o r yo fd e f i c i tf u n c t i o n a t h r e e s t a g es o l v i n g p r o c e s s i sp r o p o s e dt og e n e r a t et h ef i n a lv e h i c l es c h e d u l e ，a n df i r s t l y as t r o n g e rf l e e t - s i z el o w e rb o u n dw h i c hc a nr e d u c et h ee r g o d i ct i m e so ft h eh e u r i s t i c p r o c e d u r e i n s t a g e - t w oe f f e c t i v e l y i sf o u n db yd e a d h e a dd i s p a t c ha n dv a r i a b l e t r i p d e p a r t u r et i m e s e c o n ds t a g eu s et h e h e u r i s t i cp r o c e d u r et o s o l v et h em i n i m a l n u m b e ro fr e q u i r e dv e h i c l e sw h i c ha i m sa tl o w e r i n gt h ep e a kv a l u eo ft h ed e f i c t f u n c t i o no fe a c hd e p o tb yd e c r e a s i n gt h en u m b e ro fr e q u i r e dv e h i c l eu n i t t h et h i r d s t a g ei sc o n s t r u c t i n gv e h i c l es c h e d u l e sb yu s i n gf i r s t - i n f i r s t - - o u t r u l ew i t ht h en e w t i m e t a b l eg e n e r a t e di ns t a g eo n e a tl a s t ，t h i st h e s i st a k e saa l g o r i t h mv a l i d i t yc h e c k b a s e do nh y p o t h e t i c a ld a t a ，a n dm a k e sa ne x p e r i m e n tb a s e do nt h er e a lt i m e t a b l e so ft h e 3r o u t e sf r o mb e i j i n gb u sc o m p a n y , a n dt h er e s u l tp r o v e st h ea p p l i c a b i l i t yo ft h em o d e l a 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 ，m u l t i p l ed e p o tv e h i c l es c h e d u l i n gp r o b l e m ， d e f i c i tf u n c t i o n ，d e a d h e a dt r i p ，v a r i a b l es c h e d u l e ，f i r s t i n - f i r s t - o u t ( f i f o ) 1 v l i l 目录 中文摘要v 6 l 】j i s t r a c t v i i 1 引言1 1 1研究背景1 1 2 论文结构和主要内容2 2行车计划编制问题的理论与方法综述5 2 1国外研究情况5 2 1 1 单场站行车计划编制问题( s d v s p ) 5 2 1 2 多场站行车计划编制问题( m d v s p ) 6 2 1 3 车辆人员计划集成编制问题( c s p ) 9 2 2国内研究情况l o 2 3本章小结1 2 3行车计划编制问题分析1 3 3 1公交调度计划概述1 3 3 2公交时刻表构成及表示1 4 3 3关键术语1 5 3 4行车计划1 6 3 4 1 行车计划构成要素1 7 3 4 2 单线行车计划编制流程1 7 3 4 3 多场站行车计划编制流程1 8 3 5多场站行车计划1 9 3 5 1 问题描述1 9 3 5 2 数学模型1 9 3 5 3 问题求解2 1 3 6本章小结2 2 4 基于逆差函数理论的多场站行车计划编制模型优化2 3 4 1 逆差函数理论f 4 1 2 3 4 1 1 定义及符号2 3 4 1 2 逆差函数表示2 3 4 1 3 剩余函数。2 5 4 2车队规模优化原理2 5 附录b 7 9 附录c 。9 3 作者简历9 7 独创性声明9 9 学位论文数据集1 0 1 图4 5 左向调整原理示意图3 0 图4 - 6 行车计划编制模型总体求解思路3 l 图4 7s 及s 。求解示例3 3 图4 8求解流程3 5 图4 9站求解流程3 7 图4 1 0r 1 规则选择场站流程3 9 图4 1 1u r d h c 子过程算法流程图4 l 图4 1 2 插入空驶车次算法流程4 3 图4 13u r s c 子过程算法流程图4 5 图4 1 4 调整发车时间算法流程图4 7 图4 15 最小化车队规模综合算法流程图4 9 图4 1 6 应用f i f o 建立车次链示例5 2 图5 1优化前后逆差函数6 4 图5 2 应用f i f o 构建的车次链6 4 图5 3 三条线路的分布示意图6 5 x n 1 引言 1 1研究背景 随着世界各地城市化程度的提高，城市交通拥堵问题日益严重，公共交通的 重要地位显得更加突出。北京市2 0 0 9 年8 月1 6 日公布了北京市建设人文交通 科技交通绿色交通行动计划，全力打造“公交城市一，到2 0 1 5 年使公交出行比例 达到出行总量的4 5 ，以此来破解由于机动车和人1 5 1 不断增长而带来的城市交通 拥堵困局【1 1 。城市公共交通方式包括定时定线行驶的公共汽车、地铁、出租车等。 公共汽车是一种最常见的交通工具，拥有机动性能好、投资少、操纵轻便等特点， 适用于不同层次的乘客。目前在我国，常规公共汽车交通仍作为各个城市的地面 客运中的主力军，是客流运力的主要提供者，并随着信息技术的发展而更加便利， 针对公共汽车客运的各方面的研究也从来都是交通研究的热点。 城市公共交通首先以提供安全、快捷的交通服务为出发点，依靠科技进步， 创新管理，提高公交系统的生产效率。多年的研究表明，建立先进的公共交通系 统，提高道路通行能力和公交车辆运营管理水平，是提高城市公共交通服务水平 和运营管理水平，解决城市交通问题的一个重要途径。而衡量公共交通系统管理 水平的标准主要是其调度水平的高低。对于公交企业来说，其核心业务是向公众 提供运营服务。由于公交企业的运营资源有限，因此，合理、高效地利用现有资 源来最大限度地满足公众的出行需要对公交企业至关重要，它可能为公交企业带 来巨大的成本节约，这就是被广为关注和研究的公交调度问题。 利用计算机编制行车计划的研究开始于上个世纪6 0 年代，迄今已有很多行车 计划编制方法和系统被研制出来，其中许多得到了成功应用。但目前国内的公交 企业大都采用手工方式编制行车计划，手工编制行车计划是一项非常复杂的工作， 而且很难印证其正确性和有效性，很难在调度人员的同常工作中起到有意义的指 导作用。 近年来，一些大城市先后进入智能公共交通系统的建设阶段，“北京公交智能 调度与管理系统目前在北京公交集团内部已应用三年。智能公交系统将把繁琐 复杂的手工操作转由计算机代替。“大公交运营环境下，公交运营系统是一个复 杂的系统，对运营计划编制工作而言，需要考虑包括车辆、人员、线路、站场、 劳动规则和调度模式在内的等多方面的影响。因此，运营计划编制是一件非常复 杂的工作，即使是采用计算机软件来编制运营计划，也需要一个非常高效的调度 算法作为技术支持。因此可以说，对一个运营计划编制软件系统的研究，关键是 算法的研究。 公交运营计划编制一般分为四个主要的过程，分别是：发车频率确定及建立 时刻表、车辆行车计划、生成劳动班次和司售人员劳动排班。车辆行车计划编制 问题也称车辆静态调度问题或车辆计划编制问题，生成劳动班次和司售人员劳动 排班也称驾驶员调度问题。本文主要研究车辆行车计划编制问题，下文简称行车 计划编制问题。 行车计划编制问题主要研究内容为：在已知时刻表的基础上，为所有车次分 配最佳执行车辆，并为每辆车安排执行车次，使运营成本最低。此问题一直为国 内外专家所重视，特别是在区域调度情况下，车辆的运营轨迹从一维( 单条线路) 变成了两维( 一个区域) ，编制行车计划已经超出了人工能够应付的范围，其属于经 典的n p 难题，其可行解数量极大，国内外的研究重点都针对此问题的求解算法。 c e d e r 在文献 2 】中基于图视化的逆差函数法( d e f i c i tf u n c t i o n ) 论证了最小车队规 模的求解过程，其过程易于理解，但是此方法对于求解大规模问题求解效率仍需 提高。本文应用逆差函数易于理解的原理，改进c e d e r 求解过程，在进一步优化结 果的基础上讨论了如何提高算法效率。 虽然国外已经成功地开发并应用了一些解决运营计划编制问题的软件，但由 于国内外交通环境不同，现在国外的智能系统在国内并不适用，结合国内公交调 度现状建立适合我国城市交通环境的公交运营计划编制系统是智能交通的研究方 向，也是提高国内公交运营效率与节费运营成本的有效手段。本文所述的改进求 解过程及求解算法可为智能行车计划系统的实现提供一定的指导，这也是本文的 研究目的之一。 1 2 论文结构和主要内容 根据研究内容，本文一共分为六章： 第一章是概述，主要介绍公交行车计划编制问题的研究背景，文章的体系结 构和主要内容。 第二章对公交行车计划编制问题的发展进行综述，分别讨论了国内外关于单 场站、多场站行车计划编制问题、车辆人员集成编制问题，对其应用的模型与方 法进行综述，并对这些研究成果进行分析评价。 第三章对公交行车计划编制问题进行分析。首先简要介绍公交运营组织与调 度业务，主要包括调度计划简介、运营计划编制流程介绍、公交时刻表简介及公 交行车计划编制流程介绍。针对多场站公交行车计划编制问题，讨论并分析其常 用的几种模型与算法。 2 第四章是全文的重点，主要讨论求解多场站行车计划编制问题的模型与算法： 首先，引入逆差函数理论，重点介绍逆差函数的相关概念、图视化表示法及其镜 像函数一剩余函数；其次，分析基于逆差函数理论编制行车计划过程中应用的优 化原理，并建立综合求解过程模型；然后逐一讨论三个子模型：车队规模下限求 解模型生成严格下限，车队规模减小优化模型求解最小车队规模，车次链构建过 程确定车辆任务。 第五章为算例分析，首先进行示例分析，验证了算法的有效性，然后以北京 公交线路的实际时刻表和线路基本信息为主要输入数据，对多场站行车计划编制 模型与算法的适用性进行了实证分析。 第六章为得出的结论，将对全文进行总结，概括本文的主要工作，并对今后 研究行车计划编制问题提出展望。 4 2 行车计划编制问题的理论与方法综述 车辆行车计划编制问题主要研究内容为：在给定时刻表的条件下，为所有车 次分配最佳运营车辆，并为每辆车安排需执行的车次链，以达到运力资源的优化 配置。由于线路上的客流量是随着时间和空间的变化而变化的，因此不同的运营 时段具有不同的发车频率和不同的需用车数量。车辆行车计划编制问题就是在满 足给定时刻表中所确定的车次需求，使得车辆的总数量最小。 公交运营调度分区域调度( 也称跨线调度) 和单线调度。区域调度允许车辆、 人员在多条线路上运营，从直观的角度看，当某线路处于高峰运营时段，即可从 处于低峰运营时段的线路抽调车辆和人员，从而节约运营资源。区域调度涉及到 多线路多场站，因此在编制运营计划时，要编制区域时刻表及多场站行车计划。 根据运营调度范围的大小，公交行车计划编制问题可以分为单场站行车计划编制 问题( s i n g l ed e p o tv e h i c l es c h e d u l i n gp r o b l e m ，s d v s p ) 和多场站行车计划编制问 题( m u l t i p l ed e p o t v e h i c l es c h e d u l i n gp r o b l e m ，m d v s p ) 。 2 1国外研究情况 2 1 1单场站行车计划编制问题( s d v s p ) s d v s p 是编制公交运营计划中的典型问题，其可以理解为m d v s p 的子问题， 即： 一个中心场站，多个车次，每个车次均有不同的线路与起止时间： 如果一个车次的开始时间大于另一车次的开始时间，则此两个车次可由同 一车辆执行； 优化目标是满足相关约束的条件下使执行所有车次需要的车辆数最小 事实上，s d v s p 可以被描述为一个最小费用流问题，线性指派对问题，运输 问题，近似指派问题或匹配问题1 3 】。 s a l z b o m ( 1 9 7 2 ) 提出了单线最小车队规模模型，指出模型中三个实际不成立的 假设，发车频率是一个时间的连续函数；单程点在所有时段不变；线路为放射状 线路。c e d e r 扩展了s a l z b o m 的模型，对于确定场站时刻表，分别求解首术站单个 车次与在同场站发车的下个最早可行连接车次之间存在的运营车次数n 。和n 。，最 早可行连接车次根据场站之间空驶时间确定的。其提出定理，针对首术站所有车 次，如果不允许跨线调度和插入空驶车次，刀。和，z 。最大值即为线路所需车辆数。 在编制实际公交车辆计划中，不仅会插入空驶车次，同时会微调发车时间以减小 需用车辆数，这种方法应用起来会非常复裂4 1 。 g a v i s h 和s h i f t e r ( 1 9 7 8 ) 5 1 首先定义了大型公交企业的行车计划编制问题，其 将单场站行车计划编制问题转化成了在满足车次需求约束条件下，使需用车辆数 量最小，车辆在运行过程中空驶时间最小及车辆空闲时间最小的数学模型，并且 给出了模型的求解算法。 b o d i n 和g o l d e n ( 1 9 8 1 ) 【6 】采用两阶段法对单场站行车计划编制问题进行了求 解。而当在模型中加入其它约束时，例如线路对于行驶时间的约束，该问题就变 成了n p 难题，只能通过启发式算法进行求解。 f r e l i n g ，r ，a p m w a g e l m a n s ( 1 9 9 9 ) 【7 】等人将单场站行车计划编制问题描述 为近似指派对问题，并提出竞拍算法( a u c t i o na l g o r i t h m ) 求解。此算法采用先生 成车次链然后再组合的策略进行求解，计算其结果优于当时的一些其它求解方法。 h a a s e ，d e s a u l n i e r s 和d e s r o s i e r s ( 2 0 0 1 ) 【8 】提出适用于没有车辆使用上限限制 的单场站行车计划编制问题，该模型仅包含任务车次变量和车辆固定费用。模型 引入车辆计数约束，用以提供某一时段车辆需用数量下限。论文提出了一种基于 加速策略的分析定价法，对车辆人员集成问题进行求解。 f r e l i n g 等( 2 0 0 1 ) 9 】建立了单场站单车型的行车计划编制问题的准指派模型，并 用贪婪算法求解。准指派问题是一个削减规模的线性规划问题，不考虑问题中的 某些点和与之相应的弧。贪婪算法是一种不追求最优解，只希望得到较为满意解 的方法。贪婪算法一般可以快速得到满意的解，因为这种算法省去了为找最优解 要穷尽所有可能而必须耗费的大量时间，且贪婪法不要求回溯。作者提出了四种 不同的算法并比较它们的效率：用于求解准指派问题的现有的贪婪算法；用于求 解准指派问题的改进贪婪算法；可交换的两阶段的准指派模型；用于削减问题规 模的基于核心的算法。 2 1 2多场站行车计划编制问题( m d v s p ) 2 1 2 1 多场站行车计划编制问题( m d v s p ) 多场站调度是指允许跨线运营，区域公交可以提高公交运营效率，减少运营 成本，但是区域计划的编制问题却极为复杂，多场站行车计划编制问题属于n p 难 题，国内外的研究主要用两种模型表示此问题：多货物流网络模型和集分割模型。 此问题求解非常复杂，为了得到问题的精确解，很多学者投入了大量精力。 早期自二十世纪7 0 年代至9 0 年代，国外的学者提出了一些启发式求解方法。 6 例如，b o d i n 等( 1 9 8 3 ) 【1 0 】提出了两阶段启发式过程求解多场站行车计划编制问题： 首先按单场站车辆计划求解方法编制行车计划，然后按运输问题求解方法把行车 计划分配到不同的场站。 b e r t o s s i ( 1 9 8 7 ) i l l 】，m e s q u i t a 和p a i x a o ( 1 9 9 2 ) 12 1 ，l a m a t s c h ( 1 9 9 0 ) 1 3 】等人 均提出用拉格朗日启发式算法求解多场站行车计划编制问题。l a m a t s c h 将m d v s 问题转化成为一个多货物从不同的源点( o r i g i n s ) 运往不同的目的地( d e s t i n a t i o n ) 的网络流量问题，并且给出了2 5 0 个班次，2 个站场以及2 0 0 个班次，3 个站场的 行车计划方案。 d e l la m i c o ( 1 9 9 3 ) 1 4 1 基于最短路问题研究了几种启发式算法，优化目标是使 m d v s 问题所需车辆数最小。算法分阶段进行，每阶段中新增加车辆的任务都得 以确定。算法定义了一个禁用弧集，之后在网络图中搜索不包括禁用弧的可行回 路。通过在网络子集而不是整个网络中应用最短路算法，来提高算法的效率。通 过将整个问题分解为几个部分问题的方法，以削减问题规模，并对基本算法进行 了一些修正，以节约计算时间。修正方法包括，例如，将求解车次的再分配问题 替换为单场站行车计划编制问题；重组部分车次；不同场站每个车次对的内部再 分配等。 自二十世纪9 0 年代，多场站行车计划编制问题研究焦点集中于求解问题的精 确解，因此一些学者提出和精确分支定界法和精确列生成法。 r i b e i r o 和s o u m i s ( 1 9 9 4 ) 1 5 】将m d v s 问题转化为有边界约束的集分割问题， 并用列生成技术求解下限；b i a n c o 等( 1 9 9 4 ) 【l6 】将多场站行车计划编制问题转化 为有附加约束的集分割问题。首先，基于图论和线性规划理论，通过不断逼近的 启发式过程解决二元线性松弛：其次，在考虑原问题基础上，减少变量集合；第 三，通过分支定界法求解大量削减的集分割问题。他们应用上述方法解决了3 0 0 个车次，6 个场站的实例。 m e s q u i t a 和p a i x a o ( 1 9 9 7 ) 1 7 】将多场站行车计划编制问题模型进行了简化， 使用分支定界法进行求解。而后l 6 b e l 【1 8 i9 】比较成功的求解了m d v s 问题，他讨 论了多场站车辆行车计划编制问题及其松弛问题，将问题转变为线性规划问题以 应用分支定界法求解。并提出了一个特殊的多货物流问题模型，提出了一种称为 拉格朗日定价的列生成法求解；该方法基于两种不同的拉格朗同松驰。应用启发 式算法确定解的上下限，最终的求解结果被证明为实际的优化解。但模型中没有 考虑线路运行时间的约束。l _ 届b e l ( 1 9 9 7 ，1 9 9 8 ) 和k l i e w e r 等( 2 0 0 6 ) 2 3 】成功地 求解多达7 0 0 0 个车次的实际公交系统中多场站行车计划编制问题。 m e s q u i t a 和p a i x a o ( 1 9 9 9 ) 2 0 】基于多货物网络流模型，使用搜索树方法求解 m d v s 问题。该算法包含两种不同类型的决策变量。第一类描述了车次间的连接， 7 以得出车次链，另一类描述了将车辆分配到场站。该方法构建了一个简洁的多货 物网络流模型，该模型只包含一类变量和少量的约束，求解使用分支定界法。 b a n i h a s h e m i 和h a g h a n i ( 2 0 0 0 ) t 2 l 】研究了基于实际的大规模多场站行车计划编 制问题的求解算法。为了解决现实中可能存在的诸如燃油消耗之类的约束，问题 中考虑了额外的运行时间约束。作者对问题及约束条件进行了建模，提出了相应 的精确解求解算法。此外作者提出了几种启发式求解方法。启发式算法的每次迭 代过程将把不合理的车次链换成合理的车次链。该方法在大城市的应用表明，需 要减少变量和约束条件的数目。文献采用了削减问题规模的技术，如通过修正方 法，将原问题转化为一组单场站行车计划编制问题。 h a g h a n i 和b a n i h a s h e m i ( 2 0 0 2 ) 1 2 2 j 给出了有线路运行时间约束的多场站行车 计划编制问题的0 1 规划模型和算法。此模型中，将车次根据发车时间的不同分成 三个集合：上午车次集合( m o r n i n gt r i p s ) ，中午车次集合( m i d d a yt r i p s ) 和下午 车次集合( a r e m o o nt 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 e t r i p s ) ，如果车辆在执行完前一个车次回到站场后再执行新的车次，则称这两个车 次是站场相容班次，如果车辆在执行完一个车次直接执行下一个车次，则这两个 车次为路线相容班次。在此车次分类基础上，建立了有时间约束的m d v s p 的0 1 规划模型。 近些年一些学者提出了求解多场站行车计划编制问题的元启发式算法。p e p i n 等人( 2 0 0 8 ) 【2 4 】总结了五种求解m d v s p 的启发式方法：分支一切割法( t r u n c a t e d b r a n c h a n d c u t ) ：拉格朗日启发式算法( l a g r a n g i a nh e u r i s t i c ) ；列生成法( t r u n c a t e d c o l u m ng e n e r a t i o n ) ；大规模领域搜索法( l a r g en e i g h b o r h o o ds e a r c h ) ；禁忌搜索 法( t a b us e a r c h ) 。其中前三种方法已被大量应用，后两种方法为第一次提出的元 启发式算法。文中基于此五种方法进行实例验证，比较分析应用此五种方法的平 均计算时间和最优解；分析每种方法的适用范围和适用环境，其中大规模领域搜 索法是以求解时间和求解结果为目标的相对较好的方法。 l a u r e n t 等人( 2 0 0 9 ) 2 5 】提出了求解多场站行车计划编制问题的另一种元启发 式算法：迭代局部搜索算法( i t e r a t e dl o c a ls e a r c ha l g o r i t h m ) 。算法中包含了一些 重要的特征：应用一个有效的竞拍算法快速高效的生成好的初始解；一个有力的 邻域生成架构；应用邻域抽样技术可以保证计算时间和求解结果之间的均衡。作 者应用3 0 个多场站行车计划编制实例进行算法验证，结果表明此算法相比文献 2 4 】 提出的两种元启发式算法更有竞争力。 2 1 2 2 有时间窗的多场站行车计划编制问题( m d v s p t w ) 有时间窗的行车计划编制问题是行车计划编制问题的一种特殊情况，即可以 变化车次的发车时间。发车时间有其调整范围标准，基于调整的时刻表，可以得 到更优的需用车辆数。 b i a n c o 等( 1 9 9 5 ) 【2 6 】第一次提出有时间窗的多场站行车计划编制问题 ( m u l i t d e p o tv e h i c l es c h e d u l i n gp r o b l e m sw i t ht i m ew i n d o w sm d v s p t w ) 及其解 法，并应用其提出的解法对1 2 0 个车次和5 个场站的公交调度系统实例仿真。 g u yd e s a u l n i e r s 等( 1 9 9 8 ) 【27 】讨论了有精确等待时问费用的m d v s p t w ，其 建立了有整数非线性多货物网络流模型，其求解方法采用了融合分支定界方法的 列生成框架，对于中小型公交调度系统( 3 0 0 个车次，5 个场站) 实例，可以得到 最优解，对于大型实例( 6 0 0 个车次，5 个场站) ，在合理时间内可以求得高质量 的启发式解。 c e d e r ( 2 0 0 2 ) 【2 】使用逆差函数原理求解m d v s p t w ，其优化过程以单位减小 场站需用车辆数为目标，其优化原理为调整车次发车时间或插入空驶车次逐个降 低目标场站逆差函数高峰值，直至所有场站的高峰都不能降低，过程结束。调整 后的最大逆差函数值即为目标场站的需用车辆数。口， h a d j a r 等( 2 0 0 9 ) 2 8 】使用了基于列生成的分支定价法解决m d v s p t w 。文章 中使用时间窗动态减少技术加速了该算法的求解速度。时问窗从节点转移到弧上 可利用对偶信息得到最小的发车时间可变区域。仿真结果证明这一过程可以加速 列生成过程减少总求解时间，同时此分支定价法求解结果优于上述文献的求解结 果，其在随机生成的实例中( 9 0 0 个车次) 进行了实验计算。 2 1 3车辆人员计划集成编制问题( i v c s p ) 随着智能交通在实际应用中的迫切需求及理论界对运营计划编制问题的深入 研究，大量新的方法不断涌现。比如说针对整数规划模型的列生成、分支定价法、 集合分割、遗传算法等。此外，求解方式也从开始的车辆人员的分离式方案转换 为解决车辆人员排班的集成式方案【2 9 】。车辆人员集成问题要同时满足：使所有车 次均分配到执行车辆，所有运营车辆均分配到司售人员，使总运营费用最小。 对于编制集成计划的研究与实践，国外的学者提出一些数学及求解算法。对 于单场站问题，f r e l i n g 【3 0 3 1 】等人最早用准指派整数规划模型描述行车计划编制问 题，并用集分割问题描述人员计划编制问题。其求解算法应用列生成方法。使用 基于列生成的分支定价方式求解大整数规划问题的方法，其主要思想是将问题看 9 成一个主问题，然后利用列生成产生多个子问题并求解，最后通过合并子问题获 得主问题的解。该方法能够找到较满意的解，但由于受到主问题规模的限制，其 仅能应用于较小规模问题的求解。使用该方法求解的时间复杂度也比较高，很难 满足实际的需要。 对于多场站问题，h a s s e ，d e s a u l n i e r s 和d e s r o s i e r s 3 】提出仅包含任务变量和表 示车辆固定费用的描述模型。该模型适用于没有车辆可供应量约束的单场站问题。 模型引入车辆计数约束，用以提供某时段需用车辆数下限。基于上述模型可以求 解最优行车计划及劳班配班。文中提出一种基于加速策略的分支定价法，并介绍 了两种定价模式精确模式和启发式模型，最后应用不同分支采用不同定价模 型的分支定价法，对车辆人员计划集成编制问题进行算例分析。 h o l l i s ( 2 0 0 6 ) 等【3 2 】提出了集覆盖数学模型描述多场站车辆人员计划集成编 制问题，他们应用基于列生成的启发式算法求解。针对特殊的运营情况，即每一 车次链仅与一个可行班次相关，v a l o u x i s 和h o u s o s 3 3 】应用其提出的启发式算法 在希腊的一些公交公司进行了实例验证。m e s q u i t a 等( 2 0 0 8 ) 【3 4 】将车辆人员计划 集成编制问题描述为结合集分割覆盖的多货物流模型，其求解算法分两阶段，预 处理阶段定义车次集合和获得初始班次集合，第二阶段，使列生成法求解线性松 弛问题。 2 2国内研究情况 国内进行公交调度相关的研究已经二十多年的时间。近年来，我国对于公交 静态调度和动态调度的研究都有了初步进展。行车计划编制问题属于静态调度， 国内的很多研究方向主要集中在通过建立数学模型并结合运筹学等学科知识，借 助计算机，利用各种算法来生成行车计划。 早期李跃鹏、腾继涛【3 5 】等应用遗传算法进行公交行车计划编制问题研究，他 们基于单车运营任务由一组运营人员完成的假设上，首先构造了最小费用目标函 数，其中考虑了时间、资源配置、油耗等综合因素，然后采用遗传算法进行求解， 其仿真结果得出最少的需用车辆数，但是没有形成行车计划。 沈吟东 3 6 1 等2 0 0 3 年对公共交通驾驶员调度问题进行了描述，指出构成其复杂 性的影响因素，对驾驶员调度方法进行了简要评述。对基于整数规划的方法进行 了分析，评价了其求解模式、数学模型并指出其存在的局限性。最后还指出对于 国内研究人员，应从国内公交运营实际情况出发，从融合多种人工智能方法、“构 造式 的超启发式方法两个方向，来对驾驶员调度问题进行深入研究。 2 0 0 6 年北京交通大学杨威【3 7 】研究了区域调度时刻表生成模型，以多线路区域 1 0 调度为对象，建立区域时刻表优化模型，给出相应算法求解，实现区域协同发车。 针对生成的协同时刻表，建立多场站行车计划编制问题整数规划模型，并使用拉 格朗日松弛方法对模型进行分解，将问题转为指派问题，使用准分配算法对模型 求解。 2 0 0 6 年王海星【3 8 】在提出应用蚁群算法求解有时间窗的行车计划编制问题。其 对已有蚁群算法求解车辆路径问题( v r p ) 的模型进行改进，对算法中相应的转 移规则和轨迹更新规则进行重新设定，改进了算法转移策略和信息素更新策略。 论文将算例分析结果与遗传算法、粒子群算法进行比较，验证了模型和算法的正 确性、适用性和高效性。 2 0 0 6 年，山东大学王鹏飞1 3 9 】讨论了多发车方案的车辆人员计划集成编制问题， 文中建立了问题的准分配模型，并用两阶段算法求解：第一阶段通过使用改进的 竞拍算法确定车辆发车类型，并保证目标函数最小：第二阶段根据确定好的发车 方案，使用改进的遗传算法求解问题的近似最优解，并通过集合分割技术来提高 求解效率。 2 0 0 7 年，刘志刚m 】以使用车辆总数和车辆总空驶时间最小为目标的多场站行 车计划编制问题归结为一类约束极强的车辆调度问题( v s p ) ，给出了目标函数和 车场容量、车场存量以及续驶时间等约束条件，并设计了基于新解的表达方式的 禁忌搜索算法的模型解法。 2