计算机编制列车运行图的理论与方法课件.ppt

1、主讲：彭其渊主讲：彭其渊 教授教授/博导博导E-mail:qiyuan- 第一部分 列车运行图的理论与方法第一节第一节 列车运行图的作用列车运行图的作用 列车运行图列车运行图是是运用坐标原理表示列车运行的一种图解方运用坐标原理表示列车运行的一种图解方式。列车在任一时间的运行位置都有唯一的点与之相对应。式。列车在任一时间的运行位置都有唯一的点与之相对应。列车运行图是列车运行的工作计划，它决定着列车占用各区列车运行图是列车运行的工作计划，它决定着列车占用各区间的顺序、列车在车站到达和出发（或通过）的时刻，列车间的顺序、列车在车站到达和出发（或通过）的时刻，列车在各区间的运行时分，列车在车站的停车时

2、分等。通过列车在各区间的运行时分，列车在车站的停车时分等。通过列车运行图，可以把整个铁路网的活动联系成一个统一的整体，运行图，可以把整个铁路网的活动联系成一个统一的整体，把车、机、工、电、辆等所有与行车有关的单位组织起来，把车、机、工、电、辆等所有与行车有关的单位组织起来，严格地按照一定程序，有条不紊地进行工作。因此，列车运严格地按照一定程序，有条不紊地进行工作。因此，列车运行图是铁路运输工作的一个行图是铁路运输工作的一个综合性计划综合性计划。 第二节第二节 传统手工编图存在的主要问题传统手工编图存在的主要问题 编图问题涉及面广、制约因素复杂、技术难度大，因此编图问题涉及面广、制约因素复杂、技

3、术难度大，因此在人工编图的方式下，编图理论和先进技术手段的应用受到在人工编图的方式下，编图理论和先进技术手段的应用受到了极大的限制，编图的速度和质量得不到科学的保证。现有了极大的限制，编图的速度和质量得不到科学的保证。现有的人工编图所呈现的主要问题如下：的人工编图所呈现的主要问题如下：（1 1） 由于手工编制列车运行图周期长、不能作多方案比选由于手工编制列车运行图周期长、不能作多方案比选和评价，运行图质量缺乏科学的保证，编图机动性和评价，运行图质量缺乏科学的保证，编图机动性差，差，难以适应市场竞争的需要难以适应市场竞争的需要；（2 2） 手工编图在从资料收集、准备，到编调图工作的完成手工编图在

4、从资料收集、准备，到编调图工作的完成以及指标的计算、时刻表的打印和运行图绘制的全过以及指标的计算、时刻表的打印和运行图绘制的全过程中，重复劳动量大、牵涉的人员和部门多、程中，重复劳动量大、牵涉的人员和部门多、组织工组织工作复杂、效率低、出错率较高作复杂、效率低、出错率较高；（3 3） 手工方式的运行图调整工作手工方式的运行图调整工作只能在小范围内进行只能在小范围内进行，难，难以从全局出发保证运行图综合效益，也难以适应特殊以从全局出发保证运行图综合效益，也难以适应特殊的运行需要和环境的要求。的运行需要和环境的要求。第三节第三节 计算机编制列车运行图的特点计算机编制列车运行图的特点 利用计算机编制

5、列车运行图具有以下特点：利用计算机编制列车运行图具有以下特点： （1 1）提供了）提供了高效的数据处理手段高效的数据处理手段，减轻了列车运行图编制，减轻了列车运行图编制和数据资料处理中的劳动强度，提高了处理的速度和精确度，和数据资料处理中的劳动强度，提高了处理的速度和精确度，降低了出错率；降低了出错率； （2 2）保障了列车运行图编制的科学性，提供了多方案辅助）保障了列车运行图编制的科学性，提供了多方案辅助决策的信息，有利于方案的评价和选择；在此基础上，吸取决策的信息，有利于方案的评价和选择；在此基础上，吸取人工编图的先进经验，使列车运行图成为智能化的产物，从人工编图的先进经验，使列车运行图成

6、为智能化的产物，从而而保证了列车运行图的质量保证了列车运行图的质量；（3 3） 实现了实现了系统资源共享系统资源共享，保证了编图信息的存储、传输，保证了编图信息的存储、传输及处理，改善了数据信息的管理和交流，实现了编图及处理，改善了数据信息的管理和交流，实现了编图业务的整体化，提高了编图效率，业务的整体化，提高了编图效率，为实现铁路运营管为实现铁路运营管理现代化打下了基础理现代化打下了基础；（4 4） 缩短了列车运行图编制全过程的时间缩短了列车运行图编制全过程的时间，提高了铁路适，提高了铁路适应市场和特殊需要的应变能力，改善了铁路运输服务应市场和特殊需要的应变能力，改善了铁路运输服务水平，提高

7、了铁路运输经济效益；水平，提高了铁路运输经济效益；（5 5） 促进了全路技术设施合理配置和设备能力的协调促进了全路技术设施合理配置和设备能力的协调，有，有利于设备应用效率的综合发挥，有利于促进员工素质利于设备应用效率的综合发挥，有利于促进员工素质及服务水平的提高，形成人员设备及应用间的良性循及服务水平的提高，形成人员设备及应用间的良性循环，提高了铁路参与市场竞争制胜的能力。环，提高了铁路参与市场竞争制胜的能力。第四节第四节 国内外研究现状综述国内外研究现状综述一、国外计算机编制列车运行图研究发展概况一、国外计算机编制列车运行图研究发展概况 国外对计算机编制列车运行图的研究，一般开始于五十国外对

8、计算机编制列车运行图的研究，一般开始于五十年代后期年代后期 。 日本日本从从19601960年开始研究利用计算机编制列车运行时刻表。年开始研究利用计算机编制列车运行时刻表。19641964年在列车作业计划中利用计算机编制了具有实用价值的年在列车作业计划中利用计算机编制了具有实用价值的运行时刻表，并进行了以尽可能减少编制时刻表所需劳动和运行时刻表，并进行了以尽可能减少编制时刻表所需劳动和时间为目标的研究。时间为目标的研究。 19731973年日本应用计算机编制了东北、高年日本应用计算机编制了东北、高倚、上越、倍越、东海道、山阳等六条线路中部分区段的列倚、上越、倍越、东海道、山阳等六条线路中部分区

9、段的列车运行图，效果显著，节省了约车运行图，效果显著，节省了约2/32/3的编图时间。的编图时间。 日本日本应用计算机编制列车运行图主要采取人机对话的形应用计算机编制列车运行图主要采取人机对话的形式，编图人员使用光笔进行列车运行图的编制和调整，大大式，编图人员使用光笔进行列车运行图的编制和调整，大大的减少了编图的工作量。近几年，日本在研究的减少了编图的工作量。近几年，日本在研究“人工智能人工智能”的基础上进行列车运行图编制专家系统的开发，采用搜索树的基础上进行列车运行图编制专家系统的开发，采用搜索树原理和经验制约作为知识规则进行驱动，利用启发式手段原理和经验制约作为知识规则进行驱动，利用启发式

10、手段（HEURISTICHEURISTIC），进行局部自动调整，从而把人的判断能力），进行局部自动调整，从而把人的判断能力和计算机的高速运行能力结合起来，开发了列车运行图编制和计算机的高速运行能力结合起来，开发了列车运行图编制系统（系统（DIADSDIADS），并在），并在19911991年后的实际工作中得到了应用。年后的实际工作中得到了应用。 原苏联原苏联从五十年代后期开始，对列车运行图的计算机从五十年代后期开始，对列车运行图的计算机编制进行了大量的研究工作，对模型及模式进行了多种试编制进行了大量的研究工作，对模型及模式进行了多种试验、改进和完善。验、改进和完善。采用的基础算法主要为模拟人工

11、方法，采用的基础算法主要为模拟人工方法，不追求运行图最优，而是着眼于实用，采用人机对话方式，不追求运行图最优，而是着眼于实用，采用人机对话方式，应用计算机代替人工烦琐的运算工作，在计算机给定方案应用计算机代替人工烦琐的运算工作，在计算机给定方案的基础上进行人机对话方式的修改调整，直至满意为止，的基础上进行人机对话方式的修改调整，直至满意为止，从而减少了运行图编制时间，但优化效果甚微。从而减少了运行图编制时间，但优化效果甚微。 美国美国从五十年代后期以来一直开展从五十年代后期以来一直开展 “ “应用计算机编制列应用计算机编制列车运行图车运行图”的研究工作，其采用的主要技术路线是计算机模的研究工作

12、，其采用的主要技术路线是计算机模拟方法和逻辑判别方法。拟方法和逻辑判别方法。19581958年，美国年，美国GRSGRS公司开发了模拟列公司开发了模拟列车运行程序。该程序由两部分组成：第一部分为牵引计算程车运行程序。该程序由两部分组成：第一部分为牵引计算程序，确定任意的列车运行位置及行车速度；第二部分为逻辑序，确定任意的列车运行位置及行车速度；第二部分为逻辑进路程序，用于确定某一列车在站停车或通过，列车的会让进路程序，用于确定某一列车在站停车或通过，列车的会让方案，根据列车的等级、到达会车地点的时间以及该方向区方案，根据列车的等级、到达会车地点的时间以及该方向区间是否空闲等条件确定。间是否空闲

13、等条件确定。 过模拟列车的运行过程，确定最佳的信号配置方案及闭过模拟列车的运行过程，确定最佳的信号配置方案及闭塞分区长度，进行人员的培训和调度员、车站值班员的能力塞分区长度，进行人员的培训和调度员、车站值班员的能力测试，对运营中的各种影响因素进行研究分析，提出改进措测试，对运营中的各种影响因素进行研究分析，提出改进措施等。施等。 英国英国也采用计算机模拟方法进行编图研究。也采用计算机模拟方法进行编图研究。19651965年英国借助计算机，首先在较短的区段上进行列车运年英国借助计算机，首先在较短的区段上进行列车运行模拟，后来发展到在包括行模拟，后来发展到在包括3030个车站、个车站、300300

14、架信号机的架信号机的单线自动闭塞区段上进行列车运行模拟。从单线自动闭塞区段上进行列车运行模拟。从19711971年开年开始，英国用计算机直接指挥编组站的作业过程，广泛始，英国用计算机直接指挥编组站的作业过程，广泛采用列车运行图自动描绘系统。采用列车运行图自动描绘系统。 此外，德国、比利时、罗马尼亚、加拿大等国家此外，德国、比利时、罗马尼亚、加拿大等国家也先后进行了计算机编图的研究与试验，在不同程度也先后进行了计算机编图的研究与试验，在不同程度上取得了一些成果。上取得了一些成果。 德国、法国、日本等国相继建立了高速铁路列车实时调德国、法国、日本等国相继建立了高速铁路列车实时调度指挥系统，用以控制

15、指挥高速列车运行。度指挥系统，用以控制指挥高速列车运行。 总之总之，国外利用计算机采用模拟方法编制列车运行图已，国外利用计算机采用模拟方法编制列车运行图已趋于成熟，得到了普遍的应用和推广。由于计算机及其辅助趋于成熟，得到了普遍的应用和推广。由于计算机及其辅助装置的不断更新，编图周期也日渐缩短，从而可编制较多的装置的不断更新，编图周期也日渐缩短，从而可编制较多的方案运行图以供选择，或通过便利的人机交互手段提高编图方案运行图以供选择，或通过便利的人机交互手段提高编图质量。质量。 与此同时，国外也持续开展了建立数学模型、开发相应与此同时，国外也持续开展了建立数学模型、开发相应算法、实现计算机局部编图

16、乃至整体优化的研究，曾先后提算法、实现计算机局部编图乃至整体优化的研究，曾先后提出了以数学规划类模型为主的各种不同形式的数学模型。但出了以数学规划类模型为主的各种不同形式的数学模型。但由于列车运行图的庞大规模及复杂内涵，往往不是由于模型由于列车运行图的庞大规模及复杂内涵，往往不是由于模型本身存在病态无法计算，就是算法的复杂性无法收敛，迄今本身存在病态无法计算，就是算法的复杂性无法收敛，迄今仍未见有实用性进展的公开报道。仍未见有实用性进展的公开报道。 二、国内研究概况二、国内研究概况 我国铁路对利用电子计算机编制列车运行图的研我国铁路对利用电子计算机编制列车运行图的研究始于六十年代初期。三十多年

17、来，许多铁路高校和究始于六十年代初期。三十多年来，许多铁路高校和科研单位采用不同的方法对不同的问题作了深入细致科研单位采用不同的方法对不同的问题作了深入细致的研究，无论在理论上还是实用开发方面均取得了许的研究，无论在理论上还是实用开发方面均取得了许多成果。多成果。 6060年代年代铁科院运输所铁科院运输所率先在我国研究利用计算机铺画率先在我国研究利用计算机铺画单线非平行运行图。经过多年的研究，铁科院于单线非平行运行图。经过多年的研究，铁科院于19851985年开年开发了发了“人机对话方式铺画全路直通客车方案人机对话方式铺画全路直通客车方案”软件，先后软件，先后在在PDP-11PDP-11和和V

18、AXVAX系列计算机上运算，软件实现了许多功能，系列计算机上运算，软件实现了许多功能，但由于当时计算机运算速度和技术水平的限制，系统仍不但由于当时计算机运算速度和技术水平的限制，系统仍不能直接应用。能直接应用。 近十年来，经过近十年来，经过铁科院运输所铁科院运输所坚持不懈的努力，对该坚持不懈的努力，对该软件进行了大量的修改和完善，目前已应用于实际编制全软件进行了大量的修改和完善，目前已应用于实际编制全路客车直通方案。该软件系统采用人机对话方式，实现了路客车直通方案。该软件系统采用人机对话方式，实现了运行时分累计，运行轮廓方案，兑现方案和检调方案的铺运行时分累计，运行轮廓方案，兑现方案和检调方案

19、的铺画，对主要枢纽客运站进行行车间隔检查、车站到发线检画，对主要枢纽客运站进行行车间隔检查、车站到发线检查和库线检查以及打印方案指标等功能。查和库线检查以及打印方案指标等功能。 哈尔滨铁路局哈尔滨铁路局从七十年代开始研究计算机编制列车运行从七十年代开始研究计算机编制列车运行图工作，利用图工作，利用DJS-C4DJS-C4机研究模拟人工编图。机研究模拟人工编图。19871987年与铁科院年与铁科院一起承担了铁道部下达的一起承担了铁道部下达的“电子计算机编制列车运行图电子计算机编制列车运行图”的的科研项目，在哈尔滨至安达间单线货物列车运行图。其方法科研项目，在哈尔滨至安达间单线货物列车运行图。其方

20、法是建立数学模型和车站越行判别条件及区间占用判别条件的是建立数学模型和车站越行判别条件及区间占用判别条件的数学公式，利用模拟人工算法对模型进行求解。但由于数学数学公式，利用模拟人工算法对模型进行求解。但由于数学模型复杂且不够全面，软件功能不够完善，计算结果离实际模型复杂且不够全面，软件功能不够完善，计算结果离实际应用仍有一定距离。但作为用数学模型描述并采用一定算法应用仍有一定距离。但作为用数学模型描述并采用一定算法求解的计算机编图模式，取得了许多可借鉴的经验。求解的计算机编图模式，取得了许多可借鉴的经验。 北方交通大学北方交通大学从七十年代初开始就应用计算机对有关从七十年代初开始就应用计算机对

21、有关列车运行图问题进行了多方面的研究。首先，他们通过大列车运行图问题进行了多方面的研究。首先，他们通过大量模拟试验铺划满表列车运行图，取得了双线自动闭塞区量模拟试验铺划满表列车运行图，取得了双线自动闭塞区段旅客列车扣除系数方面的一些重要数据和结论，并开展段旅客列车扣除系数方面的一些重要数据和结论，并开展了编制具有较合理弹性及均衡性双线列车运行图的研究。了编制具有较合理弹性及均衡性双线列车运行图的研究。此外，还配合铁路重载运输和组合列车的试验开行，用计此外，还配合铁路重载运输和组合列车的试验开行，用计算机进行了相应的模拟计算和研究。近年来，又开展了列算机进行了相应的模拟计算和研究。近年来，又开展

22、了列车运行实时调整的研究。车运行实时调整的研究。 兰州铁道学院兰州铁道学院在在8080年代研究了单线非追踪列车运行图年代研究了单线非追踪列车运行图的数学模型，并用启发式算法编制程序在的数学模型，并用启发式算法编制程序在IBM-370IBM-370机上编制机上编制了了6 6个区间、个区间、1212对货物列车的实验运行图。近年来，长沙铁对货物列车的实验运行图。近年来，长沙铁道学院也开展了列车运行图的优化及计算机编制问题的研道学院也开展了列车运行图的优化及计算机编制问题的研究。他们根据列车运行图的组合特点，用优化理论方法建究。他们根据列车运行图的组合特点，用优化理论方法建立了单、复线区段列车运行图优

23、化的初步数学模型，建立立了单、复线区段列车运行图优化的初步数学模型，建立了单线区段列车运行图优化的理论和方法，采用优化计算了单线区段列车运行图优化的理论和方法，采用优化计算与人机对话相结合的方法，编制了衡阳冷水滩单线区段与人机对话相结合的方法，编制了衡阳冷水滩单线区段试验货物列车运行图。试验货物列车运行图。 从八十年代初开始了计算机编制列车运从八十年代初开始了计算机编制列车运行图的研究，采取理论研究与实际应用开发并举，着重于行图的研究，采取理论研究与实际应用开发并举，着重于实际应用的研究路线，实际应用的研究路线，19871987年底在年底在VAX-750VAX-750机上试编出了三机上试编出了

24、三个区段的单线货物列车运行图。个区段的单线货物列车运行图。19901990年年19931993年，与成都年，与成都铁路局合作研制开发了单线区段实用列车运行图编制系统，铁路局合作研制开发了单线区段实用列车运行图编制系统，铺划了广元马角坝区段单线列车运行图。该系统采用铺划了广元马角坝区段单线列车运行图。该系统采用“窗口窗口”滚动技术，即首先在运行图中的某一时间段的某滚动技术，即首先在运行图中的某一时间段的某些区间内开一个些区间内开一个“窗口窗口”，然后再在该，然后再在该“窗口窗口”内进行列内进行列车会让和越行的局部优化，并通过车会让和越行的局部优化，并通过“窗口窗口”的滚动寻求满的滚动寻求满意解。

25、意解。 在复线列车运行图研究方面，在复线列车运行图研究方面，19891989年实现了计算机编年实现了计算机编制符离集徐州北区段列车运行图。并在此基础上采用模制符离集徐州北区段列车运行图。并在此基础上采用模型控制为主，人机交互为辅，开发了型控制为主，人机交互为辅，开发了“复线列车运行图计复线列车运行图计算机系统算机系统”，并于，并于19931993年年1111月月1 1日投入实际运用，编制了济日投入实际运用，编制了济南徐州两个相连区段的实用列车运行图。经过三年的深南徐州两个相连区段的实用列车运行图。经过三年的深入研究和不断完善，该系统在入研究和不断完善，该系统在19971997年初全路列车运行图

26、大年初全路列车运行图大调整的过程中，编制了京沪线天津上海、京广线安阳调整的过程中，编制了京沪线天津上海、京广线安阳浦圻和京九线临清梁堤头等区段的实用列车运行图，在浦圻和京九线临清梁堤头等区段的实用列车运行图，在我国第一次实现了计算机编制枢纽列车运行图和复线干线我国第一次实现了计算机编制枢纽列车运行图和复线干线上的方向列车运行图。上的方向列车运行图。 开发的此系统在开发的此系统在19971997年年4 4月通过了铁道部鉴定，主要月通过了铁道部鉴定，主要解决了枢纽衔接各方向列车到发的协调配合、枢纽大小运解决了枢纽衔接各方向列车到发的协调配合、枢纽大小运转列车工作组织、技术站直通列车接续以及敌对进路

27、的交转列车工作组织、技术站直通列车接续以及敌对进路的交叉干扰等问题。叉干扰等问题。 此外，济南局、北京局、成都局、上海局、兰州局、此外，济南局、北京局、成都局、上海局、兰州局、柳州局、郑州局、上海铁道大学、广州铁路职工大学等单柳州局、郑州局、上海铁道大学、广州铁路职工大学等单位也都先后在这方面进行了研究，取得了一些成绩。位也都先后在这方面进行了研究，取得了一些成绩。三、国内外计算机编图的方法综述三、国内外计算机编图的方法综述 综观国内外对计算机编图研究的历史和现阶段的情况，综观国内外对计算机编图研究的历史和现阶段的情况，所采用的方法主要有以下几种：所采用的方法主要有以下几种： （1 1）模拟方

28、法）模拟方法 有模拟列车运行、模拟人工铺划等方法。该方法主要有模拟列车运行、模拟人工铺划等方法。该方法主要以人工编图的原则和经验为条件，生成计算机编图的判别以人工编图的原则和经验为条件，生成计算机编图的判别准则和执行程序，实现人工编图的全过程。采用该方法编准则和执行程序，实现人工编图的全过程。采用该方法编图，其质量和效果在很大程度上取决于判别准则和执行过图，其质量和效果在很大程度上取决于判别准则和执行过程程序设计的合理与全面性。程程序设计的合理与全面性。 （2 2）移动列车始发点）移动列车始发点 该方法一般在双线区段采用。编图时按某一时间间隔该方法一般在双线区段采用。编图时按某一时间间隔给定列

29、车始发点，实现一条运行线的行车间隔检查及处理给定列车始发点，实现一条运行线的行车间隔检查及处理的递推铺划，当发现不满足间隔时间时，移动列车始发点，的递推铺划，当发现不满足间隔时间时，移动列车始发点，重新进行该条运行线的铺划，如此重复进行，直到处理完重新进行该条运行线的铺划，如此重复进行，直到处理完毕。毕。（3 3）逐区间递推铺划）逐区间递推铺划 该方法主要用于单线区段。从该区段的某一端开始，该方法主要用于单线区段。从该区段的某一端开始，依区间出现的先后顺序进行检查铺划。对相对的两个方向依区间出现的先后顺序进行检查铺划。对相对的两个方向而言，其中一列顺列车运行方向铺划，另一列则反方向铺而言，其中

30、一列顺列车运行方向铺划，另一列则反方向铺划；依要求也可以从限制区间开始向区段两端延伸铺划。划；依要求也可以从限制区间开始向区段两端延伸铺划。（4 4）数学模型方法）数学模型方法 利用逻辑代数、线性规划、图论及动态规划方法建立利用逻辑代数、线性规划、图论及动态规划方法建立描述列车运行图的数学模型，通过编程实现计算机求解。描述列车运行图的数学模型，通过编程实现计算机求解。从目前的研究结果看，由于列车运行图涉及面广、影响因从目前的研究结果看，由于列车运行图涉及面广、影响因素繁杂，难以用一个模型进行描述，有些因素还难以用数素繁杂，难以用一个模型进行描述，有些因素还难以用数学表达式表达，甚至本身之间就是

31、相互矛盾和制约的。对学表达式表达，甚至本身之间就是相互矛盾和制约的。对于这样一个于这样一个NPNP完全问题，鉴于现阶段计算机速度、容量以完全问题，鉴于现阶段计算机速度、容量以及算法上的局限，还难以通过数学模型和相应的求解算法及算法上的局限，还难以通过数学模型和相应的求解算法得出满意且符合实用的列车运行图。得出满意且符合实用的列车运行图。（5 5）人工智能专家系统方法）人工智能专家系统方法 利用智能化语言编程，把列车运行图的物理条件和人利用智能化语言编程，把列车运行图的物理条件和人工经验作为知识规则，生成编图专家系统，并按照列车的工经验作为知识规则，生成编图专家系统，并按照列车的走行顺序进行组合

32、的运行实验。这种方法首先起源于日本，走行顺序进行组合的运行实验。这种方法首先起源于日本，是在对是在对“人工智能人工智能”的研究及运用日趋活跃的背景下发展的研究及运用日趋活跃的背景下发展起来的。起来的。（6 6）范围约束搜索树法）范围约束搜索树法 该方法把运行图看作各区间列车运行顺序的一个组该方法把运行图看作各区间列车运行顺序的一个组合，以运行时间带代替运行线铺画列车，把运行图编制合，以运行时间带代替运行线铺画列车，把运行图编制作为一个搜索问题来解决。采用作为一个搜索问题来解决。采用以时间带代替运行线以时间带代替运行线铺铺画列车运行图，各列车的运行时间带在各区间单独考虑画列车运行图，各列车的运行

33、时间带在各区间单独考虑时，幅度比较宽，但如果把相邻区间合并起来考虑，由时，幅度比较宽，但如果把相邻区间合并起来考虑，由于列车运行的连续性，各列车就会因自身或与其他列车于列车运行的连续性，各列车就会因自身或与其他列车之间相互制约可能的到发时刻，在时刻上的传播约束条之间相互制约可能的到发时刻，在时刻上的传播约束条件，使时间带的宽度变窄。随着被考虑区间的增多，各件，使时间带的宽度变窄。随着被考虑区间的增多，各列车运行时间带的宽度也越来越窄，甚至接近于列车运列车运行时间带的宽度也越来越窄，甚至接近于列车运行线。行线。 虚拟节点虚拟节点 第一区间第一区间 运行顺序运行顺序 第二区间第二区间运行顺序运行顺

34、序 最后区间最后区间运行顺序运行顺序 图图 1.1 确定列车运行顺序的搜索树确定列车运行顺序的搜索树 第第三三区间区间运行顺序运行顺序 （7 7）人机对话方式）人机对话方式 列车运行图的编制，具有影响因素多，组织规模大，列车运行图的编制，具有影响因素多，组织规模大，信息量大，变化快的特点。从决策问题的特征分析，运行信息量大，变化快的特点。从决策问题的特征分析，运行图编制可分为方案图（草图）编制、基本图（详图）编制图编制可分为方案图（草图）编制、基本图（详图）编制和实绩列车运行图编制。在上述三类运行图编图层处理的和实绩列车运行图编制。在上述三类运行图编图层处理的决策问题中，结构化决策问题和非结构

35、化决策问题的比例决策问题中，结构化决策问题和非结构化决策问题的比例可用图可用图1.21.2表示。表示。 非结构化 结构化 编制列车运行图方案图 编制列车运行图基本图 编制实绩列车运行图 图 1.2 问题结构化程度示意图 利用计算机编制列车运行图是一个要求理论与实际相利用计算机编制列车运行图是一个要求理论与实际相结合、技术难度非常大的工作，国内外学者为此做了大量结合、技术难度非常大的工作，国内外学者为此做了大量的研究工作，尝试过许多解决方法，但是他们在取得一定的研究工作，尝试过许多解决方法，但是他们在取得一定的成果的同时，又存在着各种问题，而产生这些问题的根的成果的同时，又存在着各种问题，而产生

36、这些问题的根本原因就在于他们所采用的方法都是把列车运行图的编制本原因就在于他们所采用的方法都是把列车运行图的编制问题作为结构化决策问题全部交由计算机来处理。问题作为结构化决策问题全部交由计算机来处理。 编制列车运行图的过程是在有限的铁路运输设备和人编制列车运行图的过程是在有限的铁路运输设备和人力的条件下，把由战略计划层制定的列车运行方案变为具力的条件下，把由战略计划层制定的列车运行方案变为具体的能够实施的列车运行计划的过程。在这个过程中，既体的能够实施的列车运行计划的过程。在这个过程中，既有结构化决策问题，又有非结构化决策问题，处理时不能有结构化决策问题，又有非结构化决策问题，处理时不能一概而

37、论。一概而论。 因此结合我国实际情况，提出了采用人机对话方式编因此结合我国实际情况，提出了采用人机对话方式编制客货列车运行图的方法。制客货列车运行图的方法。 在编制列车运行图过程中，编图者的在编制列车运行图过程中，编图者的业务知识业务知识可分为可分为三个部分：三个部分： 1 1编制列车运行图的技能；编制列车运行图的技能； 2 2编图区段内与行车有关的铁路设施、设备编图区段内与行车有关的铁路设施、设备 情况以及与编图有关的数据；情况以及与编图有关的数据； 3 3编图区段列车运行方案、运输需求和客流编图区段列车运行方案、运输需求和客流 情况等信息。情况等信息。 列车运行图 输出 阅读列车运行图知识

38、 2.线路设备 有关知识 (数据库) 1.编制列车 运行图技能 (模型） 与本职工作 有关的知识 图 1.3 人机对话编制列车运行图示意图 3.列车运行图 方案等 命令 计计算算机机 人人 其其它它铁铁路路计计划划制制定定者者 进行计算机编制列车运行图时，将第进行计算机编制列车运行图时，将第1 1、2 2部分知识赋予计算机，部分知识赋予计算机，使编图者只需根据自己所掌握的第使编图者只需根据自己所掌握的第3 3部分，采用人机对话方式，由计部分，采用人机对话方式，由计算机编制列车运行图。算机编制列车运行图。 采用以模型优化计算机控制为主，人机对话调整为辅，采用以模型优化计算机控制为主，人机对话调整

39、为辅，人机结合互补的方式编制列车运行图，其人机结合互补的方式编制列车运行图，其特点特点是：是：（1 1）能充分发挥计算机的高速计算能力和人的主观能动性，）能充分发挥计算机的高速计算能力和人的主观能动性，避免了采用单一方式所带来的不足。避免了采用单一方式所带来的不足。（2 2）结合了我国编图的实际情况，能有效的解决客货列车）结合了我国编图的实际情况，能有效的解决客货列车运行图综合编制、复线方向直通列车在技术站接续、枢纽运行图综合编制、复线方向直通列车在技术站接续、枢纽各衔接方向列车的均衡到达、各局间分界口列车合理衔接、各衔接方向列车的均衡到达、各局间分界口列车合理衔接、枢纽内大小运转列车的协调配

40、合以及机车交路勾画等问题。枢纽内大小运转列车的协调配合以及机车交路勾画等问题。第一节第一节 铁路网描述铁路网描述 铁路是一个复杂的网络，旅客列车和货物列车在列车铁路是一个复杂的网络，旅客列车和货物列车在列车运行图的指导下有序地在铁路网上运行。构成铁路网络的运行图的指导下有序地在铁路网上运行。构成铁路网络的主要因素是分界点（指车站和线路所）和线路。为了讨论主要因素是分界点（指车站和线路所）和线路。为了讨论的方便，在构造简化的铁路网络图时，只保留与列车运行的方便，在构造简化的铁路网络图时，只保留与列车运行直接相关的网络干支线和枢纽联络线等。同时，把车站看直接相关的网络干支线和枢纽联络线等。同时，把

41、车站看成一个点，车站到发线因素以及与车站相关的进路因素在成一个点，车站到发线因素以及与车站相关的进路因素在构建模型时作为约束条件构建模型时作为约束条件 。 简化的铁路网络图由节点和弧（连接节点的线路）组简化的铁路网络图由节点和弧（连接节点的线路）组成。对应于单线铁路和双线铁路的弧，给出如下定义：成。对应于单线铁路和双线铁路的弧，给出如下定义： 定义定义1 1 在构造的网络图中，如果在构造的网络图中，如果a a、b b为弧为弧j j的两端节的两端节点，则节点点，则节点a a和节点和节点b b是相邻的；当是相邻的；当a a为弧为弧j j的起点，的起点，b b为弧为弧j j的终点，则弧的终点，则弧j

42、 j是从节点是从节点a a出发并到达节点出发并到达节点b b。同样，当两条。同样，当两条弧弧i i和和j j有相同节点有相同节点a a时，则弧时，则弧i i与弧与弧j j是相邻的。是相邻的。 定义定义2 2 单向弧单向弧：在一个网络图：在一个网络图G G中，有两个相邻节中，有两个相邻节点和，由至存在线路，如图点和，由至存在线路，如图2.1.12.1.1所示，经过此线路只所示，经过此线路只能由节点到达，反之则不能。对应于这样线路的弧称为能由节点到达，反之则不能。对应于这样线路的弧称为单向弧。单向弧。jajb j图图2.1.1 2.1.1 单向弧示意图单向弧示意图 组成复线铁路的上、下行线路在网络

43、图中用单向弧组成复线铁路的上、下行线路在网络图中用单向弧表示，其集合为表示，其集合为SCSC。 定义定义3 3 双向弧双向弧：在一个网络图：在一个网络图G G中，有两个相邻节点中，有两个相邻节点和，连接和的线路存在如下特性：既可经由此线路从节点和，连接和的线路存在如下特性：既可经由此线路从节点到达节点，也可沿此线路从节点到达节点，对应于这样线到达节点，也可沿此线路从节点到达节点，对应于这样线路的弧称为双向弧。如图路的弧称为双向弧。如图2.1.22.1.2所示，双向弧的集合为所示，双向弧的集合为DCDC。在网络构造时，单线铁路对应的弧为双向弧。在网络构造时，单线铁路对应的弧为双向弧。图图2.1.

44、2 2.1.2 双向弧示意图双向弧示意图jajb j 实际上，网络图构造中，单线铁路对应的实际上，网络图构造中，单线铁路对应的双向弧，也可看成由两条单向弧组成，只不过双向弧，也可看成由两条单向弧组成，只不过由由j ja a至至j jb b这一事件与由这一事件与由j jb b至至j ja a的事件互为敌对，的事件互为敌对，不能同时发生。不能同时发生。 定义定义4 4 如图如图2.1.42.1.4所示，弧所示，弧d d与弧与弧a a、b b、c c具有包含关具有包含关系，记为系，记为( (a a、b b、c c) )d d，称弧，称弧d d为为包含弧包含弧，弧，弧a a、b b、c c为为被包被包

45、含弧含弧，且弧，且弧a a称为称为被包含起始弧被包含起始弧，弧，弧c c称为称为被包含终止弧被包含终止弧。 包含弧与被包含弧在物理上是同一径路，因此在模型包含弧与被包含弧在物理上是同一径路，因此在模型构造时应视为相同弧进行约束。构造时应视为相同弧进行约束。 包含弧与被包含弧经常在铁路枢纽内出现。包含弧与被包含弧经常在铁路枢纽内出现。 定义定义5 5 如图如图2.1.52.1.5所示，在列车实际运行径路中，若所示，在列车实际运行径路中，若弧弧i i被一列车占用，则另一弧被一列车占用，则另一弧j j必不能被另一列车同时占用。必不能被另一列车同时占用。反之亦然反之亦然。称弧称弧i i与弧与弧j j存

46、在敌对进路关系，记为存在敌对进路关系，记为ijij。bcadij图图2.1.3 敌对进路示意图敌对进路示意图 这样，对于构造的简化铁路网络图，可以用改进的邻这样，对于构造的简化铁路网络图，可以用改进的邻接目录表示，即用弧的编号与其对应节点顺序排列表示。接目录表示，即用弧的编号与其对应节点顺序排列表示。如图如图2.1.42.1.4所示的网络图，可以写出其所有节点的到达邻接所示的网络图，可以写出其所有节点的到达邻接目录和出发邻接目录。目录和出发邻接目录。 kijhlabdc图图2.1.4 2.1.4 简化铁路网络示意图简化铁路网络示意图 出发邻接目录出发邻接目录 到达邻接目录到达邻接目录 A(a)

47、=i,c,j,b A(aA(a)=i,c,j,b A(a)=)= A(b)=k,c,l,d A(b)=j,a A(b)=k,c,l,d A(b)=j,a A(c)=h,d A(c)=i,a,k,b A(c)=h,d A(c)=i,a,k,b A(d A(d)= )= A(d)=l,b,h,c A(d)=l,b,h,c 第二节第二节 模型构造模型构造一、约束条件一、约束条件 这里，引入这里，引入dtimedtime表示一天的时间，表示一天的时间，dtimedtime为一常数，为一常数，当用小时、半小时、分、半分、当用小时、半小时、分、半分、1/41/4分为单位表示时间时，分为单位表示时间时，分别

48、为：分别为：2424、4848、14401440、28802880、57605760。同时，引入符号于。同时，引入符号于模型中，其意义为：模型中，其意义为：x yxyxyxdtimeyxy 当时当时 令令L L表示区间线路对应联弧集，表示区间线路对应联弧集，L LB B表示半自动闭塞区间表示半自动闭塞区间线路对应弧集，线路对应弧集，L LZ Z表示自动闭塞区间线路对应弧集，表示自动闭塞区间线路对应弧集，DCDC为为网络双向弧集，网络双向弧集，SCSC为网络对应单向弧集，为网络对应单向弧集，N N表示网络节点集，表示网络节点集，T T表示在构造网络上运行的列车集合，表示在构造网络上运行的列车集合

49、，T Tj j表示在双向弧表示在双向弧j j上上由一端至另一端的列车集合，由一端至另一端的列车集合，T Tj j表示在双向弧表示在双向弧j j上与上与T Tj j+ +集集合中列车运行方向相反的列车集合，合中列车运行方向相反的列车集合， 并有：并有： LLLBZDCjSCDCL 1 1 区间列车运行时间约束区间列车运行时间约束k1k2jXFik1XDik2QXtqQXtttyikijikijij12图图2.2.1 2.2.1 列车区间运行时分约束示意图列车区间运行时分约束示意图XDXFQXtqQXtttyiT jL kkNkjkjikikikijikijijBLEL21121212(,)、且

50、(2.2.1)(2.2.1)2 2 列车停站时分约束列车停站时分约束 若令表示列车若令表示列车i i在节点在节点k k对应车站的停站时分，则列车对应车站的停站时分，则列车i i在节点在节点k k的停站时间应满足如下条件。的停站时间应满足如下条件。XDikXFikktsik图图2.2.2 2.2.2 列车停站时分约束示意图列车停站时分约束示意图XFXDtsiT kNikikik(,)(2.2.2)(2.2.2)3 3 列车间隔时间约束列车间隔时间约束 （1 1） 列车追踪间隔时间约束列车追踪间隔时间约束 当列车在弧当列车在弧j j( )( )上运行时，同向列车间应按追踪间隔上运行时，同向列车间应