（交通信息工程及控制专业论文）基于GA的列车自动调整算法在CBTC系统中的应用研究.pdf

中文摘要 摘要：随着城市轨道交通列车运行控制技术的迅速发展，基于通信的列车运行控 制( c o m m u n i c a t i o n s - b a s e dt r a i nc o n t r o l ，c b t c ) 技术已经成为了列车运行控制系 统技术的发展方向。应用c b t c 系统实现移动闭塞，打破了传统的固定闭塞对于 追踪间隔的限制，使得列车的追踪间隔前所未有的缩短，行车密度大大增加，运 输效率显著提高，但同时也使得列车运行调整的难度进一步增加，对列车自动调 整提出了新的挑战。因此，进行列车自动调整算法在c b t c 系统中的应用研究是 非常具有现实意义的。 鉴于此，针对列车运行调整的组合优化特性结合c b t c 系统的行车特点，本 文提出了基于g a ( g e n e t i c a l g o r i t h m s ，遗传算法) 的列车自动调整算法，完成了的相 关研究，并进行了相应的仿真测试。 首先，论文通过对城市轨道交通的特点，移动闭塞的特点，运行调整问题本 身的特点等进行细致深入的分析，提出了一个改进的列车自动调整模型。 然后，在所建模型的基础上，针对c b t c 系统中列车自动调整特点，选用遗 传算法进行模型的求解分析。论文详细阐述了改进的遗传算法在运行调整问题中 的应用过程。区别于传统的利用列车序号进行编码的方式，提出了根据时间进行 实数编码的方式。改进的算法还采用了最优个体保留的选择策略，两点交叉的交 叉策略以及遗传算法育种器的变异算子，并且采用无参数的罚函数进行了约束条 件的处理。 最后，论文以北京地铁八通线的运输组织情况为背景，构建一个仿真测试环 境。根据实际的八通线基础线路数据以及运营情况结合c b t c 系统的应用，进行 了单车严重晚点和列车群晚点时的仿真试验。仿真试验的结果表明本文所提出的 基于g a 的列车自动调整算法对于采用c b t c 系统的繁忙线路的单车调整和列车 群调整有着很好的可行性和有效性。 关键词：c b t c ；移动闭塞；a t s ；列车自动调整；遗传算法；仿真分析； 分类号：u 2 9 2 a b s t r a c t a b s t r a c t ： w i t ht h er a p i dd e v e l o p m e n to fu r b a nr a i l w a yt r a f f i ca u t o m a t i ct r a i nc o n t r o l t e c h n o l o g y , c b t c ( c o m m u n i c a t i o n b a s e dt r a i nc o n t r 0 1 ) i st h et r e n do f u r b a nr a i l w a y t r a f f i cc o n t r o ls y s t e mi nt h ef u t u r e t h em o v i n gb l o c kt e c h n o l o g yb a s e do i lc b t c b r i n g sn e wc h a l l e n g et oa u t o m a t i ct r a i nr e g u l a t i o n ，b e c a u s eh i g h e rt r a f f i cd e n s i t ya n d s h o r t e rh e a d w a yo ft r a i n sr e s u l ti nm o r ed i f f i c u l t yf o rt r a i no p e r a t i o na d j u s t m e n t s ot h e c o r r e l a t i o ns t u d yh a sp r a c t i c a ls i g n i f i c a n c e i nv i e wo ft h i s ，s t u d ya l g o r i t h m so fa u t o m a t i ct r a i nr e g u l a t i o nb a s e do ng a ( g e n e t i c a l g o r i t h m s ，g a ) c o n s i d e r i n gc o m b i n a t o r i a lo p t i m i z a t i o no ft r a i no p e r a t i o na d j u s t m e n t a n df e a t u r eo fc b t cs y s t e m ，t h e n ，c o r r e s p o n d i n gs i m u l a t i o ni sc a r d e do u t f i r s to fa l l ，m o d e lo fa u t o m a t i ct r a i nr e g u l a t i o np e r t i n e n t l yi sp u tf o r w a r dt h r o n g a n a l y z i n gc h a r a c t e r i s t i c so fu r b a nr a i l w a yt r a f f i c 、m o v i n gb l o c ka n dt r a i no p e r a t i o n a d j u s t m e n t s e c o n d l y , b a s e do nt h em o d e la n dc h a r a c t e r i s t i c so fa u t o m a t i ct r a i nr e g u l a t i o no f u r b a nr a i l w a yt r a f f i c ，g ai ss e l e c t e dt og e ts o l u t i o no ft h em o d e l a p p l i c a t i o np r o c e s so f g ai sd e t a i l e dd e s c r i p t i o n d i f f e r e n tf r o mt r a d i t i o n a lc o d i n gm e t h o db yt r a i ns e r i a l n u m b r e a lc o d i n gi sp u tf o r w a r da c c o r d i n gt ot i m e g ai si m p r o v e db yu s i n ge l i t i s m i n s e l e c t i o n , t w o - p o i n tc r o s s o v e r ，m u t a t i o no p e r a t o r w i t hb r e e d i n gd e v i c e , a n d c o n s t r a i n e dc o n d i t i o n sv i ap a r a m e t e r - f r e ep e n a l t yf u n c t i o n sm e t h o d a tl a s t ，b a s e do nb a t o n gl i n eo fb e i j i n gm e t r oi nc h i n a , s i m u l a t i o ne n v i r o n m e n ti s c o n s t r u c t e d i nt h ep a p e r , t h es i m u l a t i o ni sc a r r i e do u tu n d e rt r a i ns e r i o u sd e l a ya n dt r a i n g r o u pd e l a ya c c o r d i n gt op r a c t i c a ll i n ed a t aa n do p e r a t i o n a ls i t u a t i o no fb a t o n gl i n e c o m b i n e dw i t hc b t cs y s t e m s i m u l a t i o nr e s u l t sp r o v ea l g o r i t h m so fa u t o m a t i ct r a i n r e g u l a t i o nb a s e do ng a i se f f e c t i v ea n df e a s i b l ef o rb u s yl i n e k e y w o r d s ：c b t c ；m o v i n gb l o c k ；a t s ；a u t o m a t i ct r a i nr e g u l a t i o n ； g e n e t i ca l g o r i t h m s ；s i m u l a t i o na n a l y s i s c l a s s n 0 ：u 2 9 2 图索引 图1 典型的c b t c 系统框图【3 1 2 图2c b t c 系统的基本结构4 图3a t s 系统的基本结构6 图4 列车自动调整原理图7 图5c b t c ( 移动闭塞) 与传统固定闭塞比较示意图娜1 。1 4 图6 轨道交通运行图示例2 1 图7 复线铁路示意图2 5 图8 遗传算法基本原理图3 0 图9 染色体的编码格式3 8 图1 0 遗传算法交叉方式示意图4 0 图1 1 北京地铁线路图4 3 图1 2 运行图编辑功能图示4 7 图1 3 新建空图4 7 图1 4 仿真基本运行图4 8 图1 5 列车自动调整模块关系图4 9 图1 6 遗传策略流程图5 0 图1 7 仿真控制流程图5 2 图1 8 不同的遗传代数对算法收敛性的影响。5 4 图1 9 总晚点情况变化图5 5 图2 0 调整结果显示5 6 图2 1 总晚点情况变化图5 7 图2 2 调整结果显示5 8 表索引 表1 列车运行调整参数取值疆8 1 1 7 表2 常用的选择操作算子哺4 1 3 2 表3 常用的交叉操作嘲1 3 3 表4 常用的变异操作阳1 3 3 表5 常用适应度函数3 4 表6 常用的约束条件3 5 表7 八通线站间距及运行时间4 4 表8 列车运行间隔( 往土桥方向) 4 4 表9 列车运行间隔( 往四惠方向) 4 5 表l o 列车编号与表号的匹配关系5 3 表1 l 车站编号与车站i d 匹配关系5 3 6 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：舞确囱 导师签名：张虏 签字日期： 扩驴年占月少日 签字日期：腓6 月t 1 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：莸固l ，角签字日期：修驴年多月p 日 6 7 致谢 时光荏苒，两年的研究生生活已经接近尾声。在这两年的时光里，不仅得到 了学业的成就，更得到老师的指导与鼓励以及同学的帮助与关心，这一切都使我 获益匪浅。在这里，我要向我的导师，所有指导和关心过我的老师以及伴我一路 走来的同学，致以最诚挚的谢意! 本论文的工作是在我的导师唐涛教授的悉心指导下完成的，唐老师渊博的学 识、一丝不苟的治学态度、雍容大度的学者风范、敏锐的科学思维和丰富的学术 研究经验使我终生受益。他在百忙之中对我的研究工作精心指导，严谨而认真的 科研态度和忘我的敬业精神是我一生中学习的楷模。在此，由衷的感谢我的导师 唐涛教授两年来对我的指导和关心，向他致以我最诚挚的感谢! 轨道交通控制与安全国家重点实验室的郜春海、张建明、黄友能、马连川、 周达天、刘波等老师悉心指导我参与实验室的科研工作，在学习上和生活上都无 私的给予了我很大的关心和帮助，在此向各位老师表示衷心的谢意! 苟径、牛儒、刘超、陆启进、孙琳、刘硕等师兄师姐对于我的科研工作和论 文都提出了许多的宝贵意见，在此对他们的耐心指导表示衷心的感谢。 在实验室工作及撰写论文期间，滕竹、戚蹯、杨旭文、王伟、李家平、高强 周、李晓燕、夏夕盛等同学以及参与c b t c 项目的所有同学对我论文中的研究工 作给予了热情帮助，在此向他们表达我的感激之情。 另外要感谢我的家人和我的男友，是他们一直以来默默的支持我，鼓励我。 是他们的理解与关怀让我能够专心地完成学业。 最后，衷心感谢为评阅论文和参与论文答辩而付出辛勤劳动的各位专家学者， 感谢您的宝贵意见! 1 引言 1 1 论文研究背景和意义 随着世界各国经济与技术的发展，城市轨道交通作为一种新型的城市交通运 载工具，以其方便、快捷、舒适、安全、准时、节能、污染小等优点越来越受到 人们的重视，得到了积极的发展。近几十年间，随着中国经济的腾飞，在城市轨 道交通的建设方面投入了大量的人力物力，北京编制的轨道交通网络规划，共计 2 0 条线，1 0 0 0 余m 。与此同时，全国范围内城市轨道交通都在大踏步的发展， 天津、上海、广州等地地铁相继开通，深圳、重庆、大连等地也已经规划。全国 共1 5 座城市编制的轨道交通网络规划线路相加，总里程近3 0 0 0 k m 【1 1 。 随着城市轨道交通的迅速发展，轨道交通的新技术大量涌现。在这样的背景 下，基于通信的列车运行控制系统( c o m m u n i c a t i o n s b a s e dt r a i nc o n t r o l ，简称 c b t c ) 迅速发展，成为今后轨道交通信号系统的主要的发展方向之一。 近年来，c b t c 系统在世界各国轨道交通领域广泛应用，我国也积极的进行着 相关的研究和应用。尽管我国的起步较晚，但近几年来也获得了飞速地发展。到 目前为止，香港、广州、武汉等城市轨道部分线路已经使用了c b t c 系统，而大 部分的在建线路以及一些老线路都准备应用c b t c 系统或者进行c b t c 改进。 我国城市轨道交通需求量巨大，正迫切需要对c b t c 系统的各项关键技术进 行研究。北京交通大学的轨道交通控制与安全国家重点实验室承担了2 0 0 4 年北京 市科技计划项目城市轨道交通c b t c 系统的集成研究。本文就是在这一课题 的背景下完成相关研究的。 c b t c 系统在城市轨道交通中的应用，打破了传统的固定闭塞对于追踪间隔的 限制。使得列车的追踪间隔前所未有的缩短，行车密度大大增加，运输效率显著 提高。但与此同时，也对列车自动调整提出了新的挑战。列车自动调整是c b t c 系统中列车自动监控( a u t o m a t i ct r a i ns u p e r v i s i o n ，a t s ) 子系统的一项重要功能， 为了配合c b t c 系统进一步提高区段通过能力，改善a t s 子系统的系统功能，提 高列车运行指挥的效率，对列车自动调整相关问题进行研究是非常具有现实意义 的。 另外，就城市轨道交通的列车运行调整的相关理论研究而言，主要有仿真模 拟的方法，运筹学的方法，优先调度的方法等，但是对于c b t c 系统的列车运行 调整来说它们都在一定程度上存在着缺陷，无法完全适应c b t c 系统实时性、动 态性的要求。而遗传算法以其自身的隐并行性以及较强的鲁棒性等优良的特性近 年来不断得到学者们的青睐。鉴于此，本文选择遗传算法作为工具对列车自动调 整问题进行了深入细致的研究。 1 2 c b t c 系统的技术概述 1 2 1c b t c 系统的特点 在传统的铁路信号中，长期以来都是使用轨道电路来传输列车控制信息的， 即基于轨道电路的列车控制系统( t r a c kc i r c u i tb a s e dt r a i nc o n t r o l ，t b t c ) 。在铁 路运输1 0 0 多年的发展历程中它起到了不可磨灭的作用，有效的保证了行车安全， 提高了行车效率。但是随着经济的快速发展，对交通运输的效率以及安全性，舒 适性提出了越来越高的要求，与此同时，t b t c 的缺点也越来越明显。 自2 0 世纪6 0 年代起，世界各国相继出现了大批的新型列车运行控制系统及 相关理论，实现地车的双线传输成为了研究和开发的主流。1 9 9 9 年，电气和电子 工程师协会轨道交通运输车辆接口委员会( i e e er a i lt r a n s i tv e h i c l ei n t e r f a c e s t a n d a r d sc o m m i t t e e ，i e e er t v i s c ) 制定并颁布了c b t c 技术标准i e e es t d 1 4 7 4 1 1 9 9 9 ( i i e e e 基于通信列车控制的性能和功能要求( 第一版) 。该标准详细 定义了c b t c 系统的功能，并规定了c b t c 系统的列车运行间隔、安全性和可用 性等技术指标【2 】。这是世界上第一个标准的c b t c 系统的定义。 i e e ec b t c 标准列举了典型的c b t c 系统的功能框图，如图l 所示 图1 典型的c b t c 系统框图【3 1 f i g u r e1t y p i c a lc b t cs y s t e ms t r u c t u r e 3 】 2 整个系统包括“c b t c 地面设备 和“c b t c 车载设备 ，地面和车载设备通 过“数据通信网络”连接起来，构成系统的核心。功能框图中还单独列出了“联 锁”功能模块，该功能模块与c b t c 地面设备连接。最后，在c b t c 设备的基础 上，增加a t s 模块，用于实现系统的a t s 功能。以上所说的是c b t c 的典型结构， 实际的系统可能由于不同的设备提供商、不同的工程需要而有所差异。但是，所 有c b t c 系统均采用数据通信网络连接c b t c 地面和车载设备，实现a t p 功能， 其控制列车安全运行的核心是一致的p j 。 c b t c 系统从根本上将基于轨道电路的单向信息传输，改变为基于通信的双 向、连续、大容量信息传输。总的来说，因其具有以下几个方面的突出优点而倍 受关注： 1 ) 信息的传输量大，这是c b t c 系统的一个突出特点。由于提供双向的轨道n 车数据通信，使得信息的传输量大大增强，移动闭塞得以实现，并且为实现列 车在不同速度下列车超速防护( a t p ) ，列车自动运行系统( a t 0 ) 或列车自 动监控系统( a t s ) 等功能提供了必要的条件。 2 ) 生存期成本大大降低。由于减少或取消了轨道电路和地面色灯信号机等设备， 从而使安装和维修费用降低。 3 ) 提高了运营效率。通过移动闭塞的方式，有效减少列车的运行间隔。大幅度提 高了线路通过能力和列车平均运行速度，提高了运营效率。 4 ) 调整方式更加灵活。c b t c 系统支持双向运行，系统在运营时，可以根据需要， 使用不同的运行调整策略，并且可以同时运行不同编组长度、不同性能的列车。 1 2 2c b t c 系统的结构及基本原理 近年来，各国相继投入力量研制基于通信的列车控制系统c b t c ，具有代表性 的主要有法国国铁的a s t r e e ，日本铁道综合技术研究所的c a r a t 系统，欧洲铁 道联盟研究所的e t c s 系统和美国加拿干线铁路协会的a t c s 系统【6 】等。 我国也不例外，国家计委早在2 0 0 0 年就将城市轨道交通车辆和列车运行控制 设备列为国产化的重点，专门立项进行攻关，并要求新建城市轨道交通列车运行 控制系统的国产化率必须达到7 0 9 6 n 。在这样的背景下，国内的很多高校和企业已 经开始具有自主知识产权的c b t c 系统的研发，并取得了一定的成果。北京交通 大学轨道交通控制与安全国家重点实验室自主研发的基于无线通信的列车运行控 制( c b t c ) 系统就是其中之一。 c b t c 系统的关键技术有两个，一个是“车地通信 ，它是c b t c 的基础；另 一个是“列车定位 ，只有确定了列车的准确位置，才能计算出列车间的相对距离， 才能保证根据线路条件，对列车进行限速或者与地面设备发生联锁。车地通信和 列车定位共同构成了c b t c 系统的两大支柱【3 1 。北京交通大学自主研发的c b t c 系统已经攻克了这两个关键技术，并且成功地进行的现场试验，下面将以该c b t c 系统为例具体介绍c b t c 系统的原理。自主研发的c b t c 系统的基本结构如下图： 图2c b t c 系统的基本结构 f i g u r e2c b t cs y s t e ms t r u c t u r e 图2 为自主研发的c b t c 系统的基本结构，包括：列车自动监控系统( a u t o m a t i c t r a i ns u p e r v i s i o n ，a t s ) 、数据库存储单元( d a t a b a s es t o r a g eu n i t ，d s u ) 、区域控 制器( z o n ec o n t r o l l e r ，z c ) 、计算机联锁( c o m p u t e ri n t e r l o c k i n g ，c i ) 、轨旁设备 ( w a y s i d ee q u i p m e n t ，w e ) 、车载控制器( v e h i c l e o nb o a r dc o n t r o l l e r ，v o b c ) 和数据通信系统( d a t ac o m m u n i c a t i o ns y s t e m ，d c s ：包括骨干网、网络交换机、 无线接入点及车载移动无线设备) 。 该c b t c 系统采用的是无线通信的通信方式。具体地说，无线c b t c 系统是 指通过无线通信手段( 而不是轨道电路) 来确定列车位置，从而实现列车控制的 信号系统。列车上的车载控制器v o b c 通过探测安装在轨道上的应答器，查找它 们在数据库中的位置，然后决定列车所在位置，并且还测量自前一个探测到的应 4 答器起已行驶的距离。列车车载控制器v o b c 通过使用列车到轨旁的双向无线通 信向轨旁c b t c 设备报告本列车的位置。 c b t c 轨旁区域控制器z c 根据各列车的当前位置、速度及运行方向等因素， 同时考虑列车进路、道岔状态、线路限速以及其它障碍物的条件，向列车发送“移 动授权( m o v e m e n t a u t h o r i t y ，m a ) 信息，即列车可以走多远、多快，从而保证 列车间的安全间隔。 c b t c 系统的通信方式，使得列车定位不再依赖轨道电路，而是依据列车本身 实现列车定位。这种方式大大缩短了列车运行间隔，提高了运输效率。但是，列 车密度的大大提高也使得列车自动调整的难度进一步加大。因此，根据c b t c 下 城市轨道交通的特点进行列车自动调整相关问题的研究是十分重要的。 1 3 c b t c 系统中的列车自动调整 1 3 1列车自动监控系统概述 从图2 可以看到，列车自动监控( a u t o m a t i ct r a i ns u p e r v i s i o n ，a t s ) 系统是自 主开发c b t c 系统的一个重要组成部分，同时，它也是c b t c 中实现列车自动调 整功能的载体。 具体地说，a t s 系统是城市轨道交通列车运行控佑l j ( a u t o m a t i ct r a i nc o n t r o l ， a t c ) 系统的一个重要组成部分。a t c 是城市轨道交通运输控制自动化系统的核心， 是基于联锁设备之上的上层建筑。它从联锁设备采集信息并显示信息供决策者进 行决策，同时能够接收决策者的命令信息并执行，其某些智能单元也能根据自身 采集的信息进行实时响应，保证故障危险的及时报警和排除，从而保证列车的安 全、快速、正点运行p j 。 列车运行自动控制系统包括三个子系统【5 1 ：列车自动监控系统a t s 、列车自动 保护系统a t p ( a u t o m a t i ct r a i np r o t e c t i o n ) 、列车自动运行系统a t o ( a u t o m a t i c t r a i n o p e r a t i o n ) 。列车自动运行系统( a t o ) 主要用于实现“地对车控制”，即用地恧信息 实现对列车的驱动、制动的控制，它能模拟有经验的司机完成驾驶列车的任务， 使列车经常处于最佳运行状态，提高乘客舒适度，提高列车准点率。列车自动防 护系统( a t p ) 主要用于对列车驾驶进行防护，对于安全有关的设备或系统实行监 控，实现列车间隔保护、超速防护等功能。 列车自动监控( a t s ) 子系统是在a t p 、a t o 子系统地支持下完成对列车运 行的自动监控的远程遥控系统。其主要功能有六项，分别为：集中显示功能、集 中控制功能、列车运行时刻表管理功能、运行数据记录与统计功能、仿真功能和 检测与报警功锹引。 1 ) 集中控制功能：通常，在a t s 子系统中设置中央及车站两级控制权限。在正 常运营时，运行控制权属于中心；在必要时( 例如，控制中心设备故障) ，经 过权限转移，可将控制权转移至一个或多个联锁车站，控制权转移后，车站控 制设备临时代替中央控制中心，负责全线的运营调度； 2 ) 集中显示功能：在控制中心内通过大型显示屏，以图形的方式集中显示出全线 的状态，包括列车的运行位置及运行状态，相应的车次号等等； 3 ) 列车运行时刻表编辑管理功能：除了要编辑时刻表、负责加载当时时刻表， 打印时刻表外的一个很重要的功能就是要对比计划时刻表和实际时刻表的偏 差，根据偏差进行列车运行调整( 包括列车自动调整和调度员人工调整) ； 4 ) 运行数据记录与统计功能：要记录大量与运行相关的数据，例如，列车运行里 程数，实际列车运行图、列车运行与计划时间的偏差、重大运行事件、系统故 障情况等等。除了记录外，a t s 子系统还要可以将所记录的事件进行回放；还 要能够提供统计报表； 5 ) 系统仿真功能：系统仿真是通过仿真手段，离线模拟列车的在线运行。用于系 统调试，演示以及人员培训； 6 1 监测与报警功能：a t s 子系统能够及时记录被监测对象的状态，除了状态显示 功能外，还要有一定的预测、诊断和故障定位功能。 典型的a t s 系统的基本结构如下图所示： 删帆b 禽凰白，羼，。用 ” “ m 。鏖国自i 汐 “”2 车辆段( 予留) j 薪；?著?j需 车站 铲圈i 回国 辩园圜 图3a t s 系统的基本结构 f i g u r e3a t ss y s t e ms t r u c t u r e 6 二霹凰 囵 幕禽 国 禽 囱 鱼一 国 刁鞠班掰i商 图 霾m 作为自主研发c b t c 系统的一个重要组成部分，轨道交通控制与安全国家重 点实验室也进行a t s 子系统的自主研发，而城市轨道交通的列车自动调整功能是 a t s 系统功能的一个重要组成部分。 1 3 2a t s 中列车自动调整原理 列车自动调整的任务是调整列车运行，确保列车运行遵照时刻表。在列车自 动调整的实现过程中，比较列车实际运行时分与计划时刻表的计划运行时分，调 整计算后的结果发送到相应的功能接口，具体的列车自动调整原理框图如下： 匡囤i i f r 算机联钡糸缓； i i 本地前端处理器； i f 一型堕一f 图4 列车自动调整原理图 f i g u r e4 a u t o m a t i ct r a i nr e g u l a t i o ns c h e m a t i cd i a g r a m 列车自动调整的原理：过程连接将所有的从微机联锁和a t c 系统等报告的信 息送到信息处理单元( 7 ) 。信息处理单元将所有关于轨道占用和列车状态的指示， 包括到站和离站事件报文( 来自a t c ) ，转发到列车监视和跟踪定位系统( 1 1 ) 。 列车监视和跟踪定位系统根据这些指示检测列车运行。如果列车运行是进站或离 站，列车监视和跟踪定位系统将会把此事件报告到时刻表比较单元( 1 2 ) 和乘客 信息显示系统( 1 4 ) 。时刻表比较单元计算时刻表的偏差并发送调整命令到列车自 动调整单元( 3 ) 。列车自动调整单元必须将调整结果转换成合适的列车调整命令 7 然后通过过程连接( 4 ) 转发到列车a t o 。停站时间也被发送到控制着停车时间指 示器( 6 ) 的特定本地前端处理器，且离站时间被报告到进路自动排列单元( 2 ) 。 每列列车的预计到站时间得到计算，并被发送到乘客信息显示系统( 5 ) ，由乘客信 息显示系统进行存储和管理。 1 4 国内外的研究现状 由于铁路在国民经济发展中的重要作用，列车运行调整问题多年来一直吸引 着广大学者的注意力。而随着铁路信号领域技术的不断进步，研究的逐步深化， 现已形成多种针对不同应用环境，侧重解决不同问题的列车运行调整的数学模型 和调整算法，同时也有不少学者总结列车运行调整问题的研究历程【6 】1 7 】。 近2 0 年来，学者们多是以干线铁路的情况为背景进行的研究和试验。然而近 几年城市轨道交通迅猛发展，以城市轨道交通为背景的列车运行调整的算法研究 却相对较少，针对城市轨道交通的列车运行调整的研究现状的总结更是少之又少。 学者们对列车运行调整问题的分析研究往往都会针对某一个特定环境下的某 一个或某些情况而言，运用一种算法或几种算法的融合来解决所遇到的运行调整 问题。总的来说，目前有代表性的主要有以下几种方法： ( 1 ) 仿真模拟的方法 所谓仿真模拟就是基于对现实环境及现实系统充分了解，进行的一种尽可能 全面的模拟，构建出一个对于研究者或使用者非常透明而清晰的模型，并且能够 对不同的情况，不同的系统进行分析、对比以及预测。 由于列车运行调整问题动态性，实时性，复杂性的特点，模拟仿真的方法就 常常被应用于列车运行调型8 h 9 1 ，主要用以辅助人们进行决策。例如，西门子开发 的运营模拟工具t r a n s i t ( t r a i n a n a l y s i sa n ds i m u l a t i o nt 0 0 1 ) 【9 】，已经有简单的 自动调整功能。随着d e d s ( 离散事件动态系统) 理论的发展，运行调整仿真技术 的研究有了更大的进步，但是该理论还处于研究的起步阶段，缺乏统一的理论基 础，模型也不够直观，难以充分验证其完整性，正确性。 就仿真模拟的方法本身来说，它的本质可以说是一项实验技术，其结果的好 坏取决于所采用的模型和数据以及模拟次数的多少。因此这种方法的依赖性很大。 ( 2 ) 运筹学( o p e r a t i o n sr e s e a r c h ，o r ) 的方法 运筹学最早成功应用于车间调度问题上，于是很多学者开始尝试用运筹学来 解决运行调整的问题。运筹学方法一般是能产生一个精确最优解的方法，其求解 的特点是首先构建一个数学模型，然后利用优化理论进行求解。典型的运筹学方 法有分枝定界法( b & b ) 和整数规划法( i p ) 。 在实际应用方面，c u 1o 】等为s a 0p a u l o 地铁公司开发了一套时刻表白动生成 系统，能够在约束和环境不是很复杂的情况下通过拉格朗日松弛技术进行分层求 解。尽管运筹学的方法在一定程度对运行调整算法进行了探索，但是由于运行调 整问题的复杂性和不确定性，其结果往往并不令人满意。比如，己经证明分枝定 界法的计算复杂性是指数型的。并且这类方法的搜索空间范围非常大，很容易产 生组合爆炸问题。 ( 3 ) 人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 的方法 2 0 世纪8 0 年代人工智能技术的逐步兴起，并吸引了大量的专家学者将其应用 于解决调度问题。人工智能适合于解决有很大搜索空间、专家希望很快找到可行 解的那类问题。用以解决运行调整问题的这类方法的代表有模糊决策的方法、专 家系统的方法以及模糊专家系统的方法【l l 】【1 4 1 。 在实际应用方面，西南交通大学的肖膊1 2 】，北京交通大学刘炯【1 3 1 都先后将专 家系统应用与城市轨道交通的列车运行调整。我国学者蔡伯根用计算及模拟的方 法构建了具有三级控制结构的动态多级产生式专家调整系统【l4 1 。 但是专家知识的获取一直是专家系统技术的瓶颈问题，为解决该问题而建立 的一些知识获取工具和机器学习算法尚未达到实用的程度。另外随着解决问题规 模的增大，知识库也会很大，势必降低推理效率。这两个瓶颈一直制约着专家系 统在列车运行调整领域的应用。 ( 4 ) 优先调度规贝j j ( p f i o r i t yd i s p a t c hr u l e s ，p d r ) 的方法 优先调度的方法是一种模拟调度员手工调整，按顺序铺画列车运行线的方法， 它将列车运行调整问题转化为列车的排序问题，这样实现起来非常容易，计算的 复杂度也比较低。这种方法给每个参加调度运算的列车都计算一个独立的优先权， 按优先权的次序按从高到低的顺序对待调整列车计算分配时刻表。所有列车计算 分配完成后，也就形成了一个可行的列车运行调整方案。 很多学者基于该方法做了大量的努力【1 5 】- 【1 7 1 ，例如：周学松，朱钰【1 7 】提出的列 车运行状态推导图方法，也是在确定列车出发顺序的前提下解决单个列车运行线 的推算问题，提出了一种人工智能类的基于列车运行状态推导图的列车运行调整 算法。 这种方法的优点是模型相对简单，复杂性低，但是正是由于这一点，使其在 大多数情况下都忽略了列车运行调整中一些特殊优化情况，而且这种模型的调整 方式对于城市轨道交通列车运行调整的实时性要求来说是不合适的。 ( 5 ) 智能计算的方法 智能计算又称为软计算，于1 9 9 4 年由l a z a d e n 1 8 1 首先提出。综合利用了近 2 0 年来研究十分活跃的优化求解方法，如神经元网络算法( n e u r a ln e t w o r k ，n n ) 、 9 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、模拟退火( s i m u l a t e d a n n e a l i n g ，s a ) 、学习 推理，模糊逻辑等等【1 9 1 。智能计算的特点是可以容忍不精确因素的影响，得出可 行的，鲁棒性好，并且低成本的求解方案。它更多的依赖于数值，而不是依赖于 知识，能够使机器智商( m a c h i n ei n t e l l i g e n c eq u o t i e n t , m i q ) 成为可能【1 9 1 。 在智能技术的应用中，求解运行调整问题使用较多的是遗传算法，它是一种 多点同时搜索逐渐逼近最优解的方法。遗传算法的主要特点是群体搜索策略和群 体中个体间的信息交换，搜索不依赖梯度等高阶信息，尤其适用于处理传统搜索 方法难于解决的复杂和非线性问题。 除了遗传算法本身的优点以外，遗传算法也符合列车运行人工调整的过程【硼， 人工调整的过程，实质上是调度员在一定规则限制下，根据一定的经验进行枚举 或搜索试凑，最终寻求一个可以接受的调整方案的过程。而遗传算法既能体现一 定的规则和经验( 采用约束条件、加权值) ，又能进行随机搜索( 样本的选择、再生、 交叉、变异等操作) 和试凑( 适应度计算) 。二者有很强的相似性，也就是说后者可 以很好地模拟前者。而且遗传算法提供了一种以有限的代价来解决搜索和优化大 规模问题的通用方法。 已经有一些学者在这方面进行了一定的探索，比如：学者v i v i a ns a l i m 2 1 】使用 遗传算法求解单线铁路的最佳会让、越行地点问题；学者周伟【2 2 】研究了使用遗传 算法解决以列车总晚点时分最小为优化目标的列车运行调整问题，结合我国高速 铁路的特点，建立了行车调整的事件驱动的状态空间模型。针对状态转移方程的 表达及在冲突确认和疏解上的缺陷，结合算法的求解特点和列车运行的实际可能 性，提出了改进方法。 尽管遗传算法针对干线铁路已经进行了一定的研究应用，但是还没有学者将 它应用于城市轨道交通的列车自动调整之中。因此，本文以现在列车运行控制系 统的前沿方向( c b t c 系统) 为依托利用遗传算法对列车自动调整模型进行了优化 求解的算法分析。 除了以上这五大类方法外，还有研究各种其它情形下列车运行调整问题的方 法。比如p e t r i 网列车运行调整算法研究【2 3 1 ，a g e n t 列车运行调整算法研究【2 4 】，等其 中一些解决思路和方法也非常值得借鉴。 1 5 本文的主要研究内容及各章的安排 本文的研究内容主要包括：阐述了课题的背景和意义：根据c b t c 系统对列 车自动调整的需求，提出一个改进的列车自动调整的模型；并利用遗传算法对模 型的进行求解分析；最后，以较为繁忙的北京城铁八通线为背景，以本文提出的 1 0 遗传算法为依据进行了仿真模拟验证，证明了基于g a 的列车自动调整算法的可 用性和有效性。这对于c b t c 系统中a t s 子系统的列车自动调整功能的课题攻关 具有实际意义。 本文各章的结构安排如下： 第一章，对本文的研究背景、意义以及研究现状进行介绍。具体内容包括自 主开发的c b t c 系统特点、结构以及基本原理、a t s 子系统的简要介绍以及a t s 中列车自动调整功能的基本原理的介绍。并且对现有运行调整研究方法进行了总 结和比较，给出运用遗传算法进行列车运行调整的可行性。最后对全文的主要工 作和结构安排进行概述。 第二章，对列车运行调整的问题进行了分析和建模。具体内容包括总结城市 轨道交通的特点，移动闭塞下列车运行的特点并分别说明了两者对于列车自动调 整模型建立所产生的影响。细致分析了城市轨道交通的列车运行图，以复线铁路 为例，提出了车次计划和表计划的概念；然后，建立了一个改进的更加适用与c b t c 系统的列车自动调整模型，并对模型进行了细致的求解分析。 第三章，应用遗传算法对上一章中建立的列车自动调整模型进行了求解分析。 具体内容包括简述了遗传算法的基本原理、方法及其优势特点；详细阐述了应用 遗传算法进行列车自动调整模型求解分析的步骤和方法，为后面的仿真研究提供 了理论依据。 第四章，进行了算法的仿真验证以及结果分析。具体内容包括仿真的总体环 境的介绍，仿真工具的介绍，仿真系统的结构设计，控制流程设计以及仿真结果 的综合分析。这一章充分证明了本文提出的模型、算法的可用性和有效性。 最后，第五章对整篇论文进行了总结和展望。 1 6 本章小结 本章简述了本文研究的背景和意义，包括自主开发的c b t c 系统特点、结构 以及基本原理、c b t c 系统中a t s 子系统的简要介绍、a t s 系统中列车自动调整 原理的介绍；还就现有列车运行调整的研究方法进行了总结及比较，给出运用遗 传算法进行列车运行调整模型求解分析的可行性。最后对全文的主要工作和结构 安排进行概述。 2 列车运行调整问题分析及模型建立 2 1 列车运行调整问题的分析 2 1 1城市轨道交通的特点 城市轨道交通是一个复杂而技术密集的公共交通系统，其各个工作环节紧密 相连，协同工作的程度高，要求控制高度集中，统一指挥调度等。与其他城市交 通方式比较，归纳起来其特点可表现为【l 】： 1 ) 速度快。 一般线路最高运行速度为8 0 k m h ，旅行速度( 包括启动、减速制动及停车在 内的从起点开车到终点停车的平均速度) 为3 0 - 4 0 k m h 。快速线路运行速度为1 0 0 - 1 2 0 k m h ，旅行速度可达6 0 k m h 左右。因此适于输送市内中长途客流。 2 ) 运量大。 地铁的单向小时断面流量( 一条线的上行或下行线路在高峰时间一个小时内 最高区