列车运行调整问题研究综述

陈 东，李永辉，张仪彬

（1.西南交通大学峨眉校区 交通运输系，四川 峨眉 614202；2.西南交通大学峨眉校区计算机与通信工程系，四川 峨眉 614202）

列车运行调整问题研究综述

陈 东1，李永辉2，张仪彬1

（1.西南交通大学峨眉校区 交通运输系，四川 峨眉 614202；2.西南交通大学峨眉校区计算机与通信工程系，四川 峨眉 614202）

列车运行调整是铁路行车组织研究的重点，在研究方法和内容上都有较为丰硕的成果。在分析诸多列车运行调整研究内容的基础上，归纳阐述了列车运行调整目标、调整措施和调整研究对象，通过分类比较各种列车运行调整研究方法，从研究手段的选择、计算机仿真的应用和今后的研究方向等方面进行研究展望，提出加强研究手段、拓展研究内容，探索新的优化算法，并将技术站车流接续作为运行调整的约束和目标等是值得研究的方向。

铁路；列车运行调整；车流组织；专家系统

列车在运行过程中会受到诸如不良天气、接触网故障、旅客上车延误、技术站始发晚点等因素的影响，使其偏离图定列车运行线。列车运行调整是在遇到上述情况时，通过运用合理的调整策略，使列车进入新的有序状态的过程。列车运行调整问题是实现列车调度指挥系统智能化、自动化的核心和基础。由于列车运行调整需考虑的因素众多、各种组合方案的规模庞大，求解算法的实现难度和求解效率等，决定了这类研究成果的实用化程度。

1 列车运行调整研究概述

1973年，B•Szpigel 首次提出“最优列车调度”问题[1]，开始了列车运行调整问题的研究。Sauder 于 1983年提出了一个优化的列车调度模型，并开发出用于单线铁路的全局优化方法。欧美、日本铁路多采用规划型的运输组织模式，对列车运行的准点性要求更高，在列车运行调整方面有丰富的研究成果。其成果在注重算法优化的同时，更重视专家系统、仿真等研究手段的运用。日本新干线列车运行管理系统(COSMOS)、欧洲铁路运输管理系统(ERTMS)和北美高级列车控制系统(ATCS)等是这一领域较为优秀的研究成果，为列车运行管理和调整提供了良好的平台与手段，也推动了该领域研究的进一步深化。

《日本新干线上的列车运行调整》(谢文炳，1979)系统地介绍了日本新干线铁路的运行调整方法及效果，对国内列车运行调整的研究起到了良好的促进作用。《用计算机编制列车运行调整计划的研究》(程宇，1988)对列车运行调整进行了比较系统的研究。进入 20 世纪 90年代，列车运行调整的研究受到诸多学者的重视。由于在基础理论和研究手段方面，列车运行调整和运行图的计算机编制存在很多共同点，很多研究手段、算法和研究成果都是通用的，因此这一时期的研究成果极为丰富，研究手段呈现多样化，数学规划、离散事件动态建模、人工智能等在这些成果中得到了很好的应用。近年来，随着城市轨道交通、高速铁路等轨道运输方式的快速发展，研究对象也进一步扩展。理论研究促进了实作系统的开发，其成果已初步应用于铁路运输调度指挥系统，极大地提高了我国铁路调度指挥生产效率。

2 列车运行调整研究

2.1 列车运行调整目标

列车运行调整用于纠正因各种原因使列车偏离运行计划的行为，因此列车运行调整的总目标是恢复列车预定运行计划。基于这一原则，运行调整目标可以表述为总晚点列车数最少、总晚点时间最少、加权总晚点时间最少等。尤其是基于不同的运行调整对象，有的研究提出了分类调整目标。例如，结合城市轨道交通客运服务的特点，吴洋提出城际列车的运行调整目标是尽快恢复列车运行计划或均衡列车的发车间隔，而不是简单地恢复运行计划[2]，这一目标有利于客运站的工作组织，相关研究成果对于城市轨道交通的列车调度调整有一定的借鉴意义。

2.2 列车运行调整措施

列车运行调整措施是指当列车运行发生偏差后，为恢复列车运行计划所采取的措施。其主要包括变更列车到发时刻、变更列车到发顺序、改变列车车站行车方式、变更列车标准运行时间、增开列车、取消列车、压缩车站作业时间、组织高速列车利用渡线在区间越行中速列车等。这些措施在既有普速铁路的列车运行调整中应用非常广泛。对于高速铁路和城市轨道交通，列车运行调整的措施还有运用备用动车组、运用其他站空闲动车组、变更列车接续时间，以及中速列车下线运行、变更动车组交路和反向行车等[3]。不同的措施实施难度差别很大，对后续列车运行的影响也各不相同。

2.3 列车运行调整研究对象

根据研究对象的不同，可将列车运行调整分为既有普速铁路、高速铁路(客运专线)和城市轨道交通线路 3 类。基于各类轨道交通的不同运输特点对研究对象进行分类，提高了研究的针对性，降低了研究难度，这一分类方法也被多数研究者采纳。

既有普速铁路分为单线和双线，采用客货共线的运输组织模式。由于货物列车与旅客列车的等级差别明显，在列车运行调整时可以赋予这两类列车不同的权限，通过牺牲货物列车的运行效率而获得旅客列车运行计划的优先恢复，这是日常调度指挥中经常采用的组织措施。单线和双线铁路在调整目标、调整措施等方面基本相同。不同的是，单线铁路因某一时间范围内只能有一列车占用某一闭塞区间，对向列车间的交会和同向列车的越行等作业只能在车站进行，列车运行调整问题需要考虑因素更多、约束条件更复杂，具有很强的优化必要性，是近年来研究的热点[4-8]。

高速铁路(客运专线)在闭塞方式、列车种类、天窗设置、运行调整目标及调整措施等方面与既有普速铁路存在较大的不同，研究的重点也不同。随着我国高速铁路的快速发展，与高速列车运行调整相关的研究，包括调度系统的建设和运行图的计算机铺画，成为近年来的研究热点。

城市轨道交通在闭塞方式、列车种类、列车运行调整目标等方面不同于其他轨道交通。随着城市轨道交通的快速发展，以城市轨道交通为背景的研究近年来也十分丰富。

3 列车运行调整研究方法的分类比较

3.1 基于规划方法的列车运行调整研究

列车运行调整问题具有涉及变量多、组合数量大等特点，是完全的NP 问题。数学规划方法因其表达清晰、模型成熟，被众多研究者所青睐。例如，建立描述网络线路列车运行图的通用化模型，并提出时空局域滚动算法完成列车运行图的求解[9-11]；建立运行调整问题的数学规划模型，利用专业知识对模型进一步简化，并在此基础上提出遗传算法、协调优化算法、分枝定界等方法对模型进行求解[4-7，12]。从这些研究成果可知，由于解的空间巨大，常规解法很难得到全局最优解，运用专业知识对模型进行合理简化，缩小解的空间及寻找可行的求解算法成为这类研究方法的重点。经过多年的研究，所建立的模型已经相对成熟。目前，各类研究更倾向于寻找更为高效、合理的算法[7，12-13]，计算复杂度和实时性成为衡量这类研究方法的一个重要指标。

3.2 基于专家系统的列车运行调整研究

专家系统具有直观、能较好地利用经验性知识等特点，也是经常采用的研究手段。日本新干线列车运行管理系统(COSMOS)、欧洲铁路运输管理系统(ERTMS)和北美高级列车控制系统(ATCS)等专家系统的建立，为列车运行管理和调整提供了良好的平台与手段。随着研究的进一步深入，相关成果也不断涌现[14-17]。在我国，程宇等提出了用于编制双线自动闭塞区段列车运行调整计划的专家系统[18-19]，张莉艳等提出了基于移动闭塞条件下的列车运行调整专家系统[20]。但该类系统的知识库、方法库、模型库在建立时缺乏统一性描述，其算法的优劣取决于算法设计者的计算机表达水平。基于不同平台的专家系统通用性差，难以借鉴、拓展，成为制约其发展的瓶颈。

3.3 基于离散事件动态建模的列车运行调整研究

列车运行调整的实质是处理列车与车站、列车与区间，以及列车之间的关系，规定列车占有区间和站线的合理时机。如果将列车占用区间与车站看成事件，那么由列车、区间、车站、信联闭设备，以及区段内各种技术设备组成的列车运行系统是一个离散事件动态系统[21]。周磊山建立了离散事件动态系统驱动的状态空间调整模型，提出了网络分层并行算法(NHPA)[22]。该模型算法和求解思路都有较强的优势，兼顾了事件顺序设定法和列车顺序设定法的优点，并以此为思路建立了“计算机编制列车运行图系统”运用于哈尔滨铁路局。周磊山教授及其研究团队运用该研究方法在运行图铺画、列车运行调整、运行图与动车组运用一体优化方面取得了一系列的研究成果。章优仕在后续文献中运用离散事件的拓扑图模型对单线列车的运行调整进行研究，建立了单线列车运行图的离散事件拓扑图模型，并在此基础上提出了单线列车运行调整的迭代修复算法[8，13]。该算法具有良好的实时性，较好地拓展了离散事件动态系统的研究手段。

3.4 其他智能研究方法

除上述规划方法、专家系统、离散事件动态建模等方法外，粗糙集、智能体(Agent)、计算机仿真等方法在列车运行调整中的研究也相当活跃。

粗糙集理论(Rough Set)作为智能信息处理技术的新成果，是由波兰科学家 Z.Pawlak 教授提出来的对不完整数据进行分析、推理、学习、发现的新方法，在许多科学领域和工程领域得到成功应用。黄康和陈东等提出了采用粗糙集方法构造列车运行调整系统，给出了模型结构和知识获取规则、自学习的粗糙规则提取算法和列车运行调整算法[23-24]。该研究手段能通过对以往调度规则的分析，通过知识约简，得到列车运行在不同情况下的调整策略，供调度人员参考。该研究手段强调调度人员的知识及其行之有效的经验性策略在列车运行调整中的作用，并具有很好的实时性。

Agent 是一个具有控制问题求解机理的计算单元，其特点是具有自治性、交互性、反应性和预动性。利用这一特性，实现列车运行调整方案的自动生成及调整，改变以往以人为主体的调度指挥方式，实现智能调度系统和人员共同工作的人机互控模式。多智能体系统(Multi-Agent System，MAS)是由多个可互相交互的称为Agent的计算单元组成的系统，具有很强的分布式特性，可用于构建列车运行调度指挥系统。贾传峻等结合已有技术，提出了依托列车调度指挥系统建立多智能体调度集中系统的方案[25]。路飞建立了基于多Agent的地铁列车运行调整系统[26]。 王宏刚建立了基于Agent的客运专线综合运营管理调度系统[27]。这些研究对于Agent 在铁路运输中的应用进行了有效的尝试，并取得了一定的研究成果。Agent 中对于调度指挥规则的简洁、正确的描述和知识表达的通用性，成为Agent 应用中的关键。Agent在分析复杂的社会经济活动中取得了很丰富的研究成果，对列车运行调整这一复杂的组合优化问题，也有良好的应用前景。

严格地说，计算机仿真不能单独列为一类研究方法，因为上述的离散事件动态建模、MAS 等研究手段也涉及计算机仿真，其研究成果相当丰富。Pascal Rebreyend 介绍了一个专门用于列车调度和调整的软件 DisTrain，能较快地校验各种调整方法的调整效果，具有较强的实用性[28]。有关研究也介绍了仿真方法在运行调整中的应用[8，15，20-21]。列车运行过程随机性特点明显，采用仿真的方法推演其运行及调整过程，并基于其研究成果建立实用系统，是一个非常有发展潜力的研究手段。

4 研究展望

经过多年的研究，在众多学者的努力下，列车运行调整研究取得了丰硕的成果。随着铁路网规模的扩大，随着普速铁路、高速铁路、城市轨道交通等的快速发展，列车运行调整目标、约束条件也在不断发展。同时，随着计算机软硬件技术的提高、新的优化算法的提出，使得局限于计算能力的一些问题的解决成为可能。可以认为，今后列车运行调整仍然是研究的热点。

（1）研究手段的选择。数学规划的方法虽然表达清晰，但求解困难，实时性较差，探索更加高效、优化的算法是这类研究手段的主要方向。专家系统和人工智能类算法因能充分借鉴专业知识，缩小解的空间，并能充分借鉴经验性知识，在这类问题的求解上有一定优势。这类方法在实际运用时仍存在一些缺点，如过程性知识表述困难、模型库和方法库的通用性差等，这些缺点的克服将促进这类研究方法的发展。

（2）计算机仿真的应用。计算机仿真能较直观地演示各种调整措施的执行情况，并对其实施效果进行评价，是一种非常好的研究手段。国外在交通运输领域非常重视仿真，并开发了很多实作或验证仿真平台，国内相关研究则有待进一步深入。

（3）今后的研究方向。对于列车运行调整，综合诸因素的一体优化是下一步的研究方向。铁路运输是一个大的联动系统，涉及专业和其他因素众多，仅列车运行调整就涉及机车(动车组)、车辆、供电、车流接续等众多因素。在现有研究中，已有针对机车(动车组)、车底和运行计划的一体优化。但是，针对列车运行调整和车流接续一体优化的研究则较少。由于铁路运输组织的复杂性，在实际运输生产中，为降低指挥难度，将联系紧密的车流组织和列车运行组织分割成两部分，大运转列车的车流组织工作交给技术站完成，调度所除调整路网列车运行之外，还管理区段内的摘挂车流在中间站的组织工作。列车的到发时间和编组内容是这两项工作的接口，这一分割有效地解决了铁路调度指挥系统智能化程度不高和计算能力不足条件下的列车运行调度指挥问题。纵观全局，车流组织虽然是车站的主要工作，但其生成的列流是组成运行线的源；反之，运行线如不能与车流组织很好的配合，则待发列车等待时间增大，车小时增加。因此，在列车运行调整中，将技术站的车流接续纳入其中进行考虑，兼顾点、线运输组织情况，将技术站的车流接续作为列车运行调整的约束和目标，达到满意的“中时、停时、旅速、周时”等运输指标，是值得研究的方向。

：

[1] B Szpigel. Optimal Train Scheduling on A Single Line Railway[J]. Operations Research，1973，7(2)：344-351.

[2] 吴 洋，罗 霞. 一种晚点地铁列车实施调整策略及其动态速控模式[J]. 中国铁道科学，2005，26(6)：113-118.

[3] 聂 磊，张星臣，赵 鹏，等. 高速铁路列车运行调整策略的研究[J]. 铁道学报，2001，23(4)：1-6.

[4] 曹家明. 单线铁路列车运行调整优化模型及算法[J]. 铁道学报，1994，16(3)：72-78.

[5] 赵 强. 单线铁路列车运行调整优化模型与算法研究[J]. 系统工程，1999，17(6)：12-18.

[6] 史 峰，黎新华，秦 进，等. 单线列车运行调整的最早冲突优化方法[J]. 中国铁道科学，2005，26(1)：107-113.

[7] 章优仕，金炜东. 基于遗传算法的单线列车运行调整体系[J]. 西南交通大学学报，2005，40(2)：147-152.

[8] 章优仕，金炜东. 单线列车运行调整的梯度搜索算法仿真研究[J]. 系统仿真学报，2010，22(11)：2496-2501.

[9] 彭其渊，杨明伦，聂勋煌. 单线区段实用货物列车运行图的优化模型及算法[J]. 铁道学报，1995，17(3)：15-20.

[10] 彭其渊，朱松年，王 培. 网络列车运行图的数学模型及算法研究[J]. 铁道学报，2001，23(1)：1-8.

[11] 彭其渊，王宝杰，周党瑞. 基于实用的一种网络列车运行图计算方法[J]. 西南交通大学学报，1999，34(5)：588-593.

[12] 罗 晴，金福才，胡思继. 列车运行调整问题的分解协调计算模型[J]. 北京交通大学学报，2004，28(6)：87-94.

[13] 章优仕，金炜东. 基于离散事件拓扑图模型的单线列车运行调整迭代修复算法[J]. 系统仿真学报，2009，21(21)：7003-7007.

[14] C S Chang，B S Thia. Online Rescheduling of Mass Rapid Transit Systems：Fuzzy Expert System Approach[J]. Electric Power Applications，IEEE Proceedings，143(4)：307-316.

[15] Kiyotoshi Komaya. A New Simulation Method and Its Application to Knowledge-based Systems for Railway Scheduling[C]//Institute of Electrical and Electronics Engineers/American Society of Mechanical Engineers.Proceedings of 1991 IEEE/ASME Joint 1991 Railroad Conference. St Louis：Institute of Electrical and Electronics Engineers/American Society of Mechanical Engineers，1991：59-66.

[16] Hellstom P. An Evaluation of Algorithms and Systems for Computer Aided Train Dispatching[J]. Computer in Railway，1998，1998(7)：585-595.

[17] Lu Fei，Song Mumin，Tian Guohui，et al. The Integrated Intelligent Control Framework of Subway Train Based-on Multi-agent[C]//Proceedings of the 26th Chinese Control Conference. Zhangjiajie：Institute of Electrical and Electronics Engineers，2007：395-398.

[18] 程 宇. 列车运行调整专家系统的探讨[J]. 北方交通大学学报，1989，13(4)：115-123.

[19] 程 宇，秦作睿. 列车运行调整专家系统的研究[J]. 铁道学报，1992，14(2)：43-51.

[20] 张莉艳，李 平，贾利民，等. 在移动闭塞条件下列车运行调整的仿真研究[J]. 系统仿真学报，2004，16(10)：2257-2263.

[21] 王起龙，张宏勋. 对分层滚动列车运行调整算法的部分改进[J]. 铁道学报，1996，18(增)：42-45.

[22] 周磊山，秦作睿. 列车运行计划与调整的通用算法及其计算机实现[J]. 铁道学报，1994，16(3)：56-65.

[23] 黄 康. 基于粗糙集理论的行车指挥知识获取与决策的应用研究[D]. 北京：中国铁道科学研究院，2003.

[24] 陈 东，李永辉，张强锋，等. 基于粗糙集理论的列车运行调整方法研究[J]. 中国铁路，2009(7)：44-46.

[25] 贾传峻，胡思继，杨宇栋. 基于多智能体的铁路双线调度指挥系统[J]. 北京交通大学学报，2005，29(6)：13-17.

[26] 路 飞. 移动闭塞条件下的地铁列车的运行优化[D]. 济南：山东大学，2007.

[27] 王宏刚. 客运专线综合运营调度系统 Agent 结构和规则描述[J]. 交通运输工程学报，2008，8(6)：93-98.

[28] Pascal Rebreyend. DisTrain：A Simulation Tool for Train Dispatching[C]//Proceeding of The 8th International IEEE Conference on Intelligent Transportation Systems. Vienna：Institute of Electrical and Electronics Engineers，2005：801-806.

Study on Problems of Train Operation Adjustment

CHEN Dong1,LI Yong-hui2,ZHANG Yi-bin1

(1. Traffic and Transportation Department,Ermei School of Southwest Jiaotong University,Ermei 614202,Sichuan,China; 2. Computer and Communication Engineering Department,Ermei School of Southwest Jiaotong University,Ermei 614202,Sichuan,China)

Train operation adjustment is the key of railway running organization and has plentiful achievements on study method and content. Based on analyzing study contents of many train operation adjustment,this paper expounds the train operation adjustment target,adjustment measures and adjustment study object. Through classifying and comparing each study method of train operation adjustment,the paper makes prospection through aspects of selection of study approach,utilization of computer simulation and further study orientation,puts forward many valuable study orientations such as strengthening study approach,developing study content,exploring new optimization algorithm and taking vehicle flow connection in technical stations as restriction and target of operation adjustment.

Railway; Train Operation Adjustment; Vehicle Flow Organization; Expert System

1003-1421(2012)12-0026-05

U292.4

B

2012-09-20

中央高校科研业务专项经费创新基金(SWJTU 2011CX002EM)；教育部春晖计划(Z2011117)

王学智