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

计算机编制列车运行图的理论与方法,主讲：彭其渊教授/博导E-mail:qiyuan-peng,第一部分列车运行图的理论与方法,计算机编制列车运行图,第一章概述第一节列车运行图的作用第二节传统手工编图存在的主要问题第三节计算机编制列车运行图的特点第四节国内外研究现状综述,计算机编制列车运行图,计算机编制列车运行图,第一节列车运行图的作用列车运行图是运用坐标原理表示列车运行的一种图解方式。列车在任一时间的运行位置都有唯一的点与之相对应。列车运行图是列车运行的工作计划，它决定着列车占用各区间的顺序、列车在车站到达和出发（或通过）的时刻，列车在各区间的运行时分，列车在车站的停车时分等。通过列车运行图，可以把整个铁路网的活动联系成一个统一的整体，把车、机、工、电、辆等所有与行车有关的单位组织起来，严格地按照一定程序，有条不紊地进行工作。因此，列车运行图是铁路运输工作的一个综合性计划。,计算机编制列车运行图,第二节传统手工编图存在的主要问题编图问题涉及面广、制约因素复杂、技术难度大，因此在人工编图的方式下，编图理论和先进技术手段的应用受到了极大的限制，编图的速度和质量得不到科学的保证。现有的人工编图所呈现的主要问题如下：（1）由于手工编制列车运行图周期长、不能作多方案比选和评价，运行图质量缺乏科学的保证，编图机动性差，难以适应市场竞争的需要；,计算机编制列车运行图,（2）手工编图在从资料收集、准备，到编调图工作的完成以及指标的计算、时刻表的打印和运行图绘制的全过程中，重复劳动量大、牵涉的人员和部门多、组织工作复杂、效率低、出错率较高；（3）手工方式的运行图调整工作只能在小范围内进行，难以从全局出发保证运行图综合效益，也难以适应特殊的运行需要和环境的要求。,计算机编制列车运行图,第三节计算机编制列车运行图的特点利用计算机编制列车运行图具有以下特点：（1）提供了高效的数据处理手段，减轻了列车运行图编制和数据资料处理中的劳动强度，提高了处理的速度和精确度，降低了出错率；（2）保障了列车运行图编制的科学性，提供了多方案辅助决策的信息，有利于方案的评价和选择；在此基础上，吸取人工编图的先进经验，使列车运行图成为智能化的产物，从而保证了列车运行图的质量；,计算机编制列车运行图,（3）实现了系统资源共享，保证了编图信息的存储、传输及处理，改善了数据信息的管理和交流，实现了编图业务的整体化，提高了编图效率，为实现铁路运营管理现代化打下了基础；（4）缩短了列车运行图编制全过程的时间，提高了铁路适应市场和特殊需要的应变能力，改善了铁路运输服务水平，提高了铁路运输经济效益；（5）促进了全路技术设施合理配置和设备能力的协调，有利于设备应用效率的综合发挥，有利于促进员工素质及服务水平的提高，形成人员设备及应用间的良性循环，提高了铁路参与市场竞争制胜的能力。,计算机编制列车运行图,第四节国内外研究现状综述一、国外计算机编制列车运行图研究发展概况国外对计算机编制列车运行图的研究，一般开始于五十年代后期。日本从1960年开始研究利用计算机编制列车运行时刻表。1964年在列车作业计划中利用计算机编制了具有实用价值的运行时刻表，并进行了以尽可能减少编制时刻表所需劳动和时间为目标的研究。1973年日本应用计算机编制了东北、高倚、上越、倍越、东海道、山阳等六条线路中部分区段的列车运行图，效果显著，节省了约2/3的编图时间。,计算机编制列车运行图,日本应用计算机编制列车运行图主要采取人机对话的形式，编图人员使用光笔进行列车运行图的编制和调整，大大的减少了编图的工作量。近几年，日本在研究“人工智能”的基础上进行列车运行图编制专家系统的开发，采用搜索树原理和经验制约作为知识规则进行驱动，利用启发式手段（HEURISTIC），进行局部自动调整，从而把人的判断能力和计算机的高速运行能力结合起来，开发了列车运行图编制系统（DIADS），并在1991年后的实际工作中得到了应用。,计算机编制列车运行图,原苏联从五十年代后期开始，对列车运行图的计算机编制进行了大量的研究工作，对模型及模式进行了多种试验、改进和完善。采用的基础算法主要为模拟人工方法，不追求运行图最优，而是着眼于实用，采用人机对话方式，应用计算机代替人工烦琐的运算工作，在计算机给定方案的基础上进行人机对话方式的修改调整，直至满意为止，从而减少了运行图编制时间，但优化效果甚微。,计算机编制列车运行图,美国从五十年代后期以来一直开展“应用计算机编制列车运行图”的研究工作，其采用的主要技术路线是计算机模拟方法和逻辑判别方法。1958年，美国GRS公司开发了模拟列车运行程序。该程序由两部分组成：第一部分为牵引计算程序，确定任意的列车运行位置及行车速度；第二部分为逻辑进路程序，用于确定某一列车在站停车或通过，列车的会让方案，根据列车的等级、到达会车地点的时间以及该方向区间是否空闲等条件确定。过模拟列车的运行过程，确定最佳的信号配置方案及闭塞分区长度，进行人员的培训和调度员、车站值班员的能力测试，对运营中的各种影响因素进行研究分析，提出改进措施等。,计算机编制列车运行图,英国也采用计算机模拟方法进行编图研究。1965年英国借助计算机，首先在较短的区段上进行列车运行模拟，后来发展到在包括30个车站、300架信号机的单线自动闭塞区段上进行列车运行模拟。从1971年开始，英国用计算机直接指挥编组站的作业过程，广泛采用列车运行图自动描绘系统。此外，德国、比利时、罗马尼亚、加拿大等国家也先后进行了计算机编图的研究与试验，在不同程度上取得了一些成果。,计算机编制列车运行图,德国、法国、日本等国相继建立了高速铁路列车实时调度指挥系统，用以控制指挥高速列车运行。总之，国外利用计算机采用模拟方法编制列车运行图已趋于成熟，得到了普遍的应用和推广。由于计算机及其辅助装置的不断更新，编图周期也日渐缩短，从而可编制较多的方案运行图以供选择，或通过便利的人机交互手段提高编图质量。,计算机编制列车运行图,与此同时，国外也持续开展了建立数学模型、开发相应算法、实现计算机局部编图乃至整体优化的研究，曾先后提出了以数学规划类模型为主的各种不同形式的数学模型。但由于列车运行图的庞大规模及复杂内涵，往往不是由于模型本身存在病态无法计算，就是算法的复杂性无法收敛，迄今仍未见有实用性进展的公开报道。,计算机编制列车运行图,二、国内研究概况我国铁路对利用电子计算机编制列车运行图的研究始于六十年代初期。三十多年来，许多铁路高校和科研单位采用不同的方法对不同的问题作了深入细致的研究，无论在理论上还是实用开发方面均取得了许多成果。,计算机编制列车运行图,60年代铁科院运输所率先在我国研究利用计算机铺画单线非平行运行图。经过多年的研究，铁科院于1985年开发了“人机对话方式铺画全路直通客车方案”软件，先后在PDP-11和VAX系列计算机上运算，软件实现了许多功能，但由于当时计算机运算速度和技术水平的限制，系统仍不能直接应用。近十年来，经过铁科院运输所坚持不懈的努力，对该软件进行了大量的修改和完善，目前已应用于实际编制全路客车直通方案。该软件系统采用人机对话方式，实现了运行时分累计，运行轮廓方案，兑现方案和检调方案的铺画，对主要枢纽客运站进行行车间隔检查、车站到发线检查和库线检查以及打印方案指标等功能。,计算机编制列车运行图,哈尔滨铁路局从七十年代开始研究计算机编制列车运行图工作，利用DJS-C4机研究模拟人工编图。1987年与铁科院一起承担了铁道部下达的“电子计算机编制列车运行图”的科研项目，在哈尔滨至安达间单线货物列车运行图。其方法是建立数学模型和车站越行判别条件及区间占用判别条件的数学公式，利用模拟人工算法对模型进行求解。但由于数学模型复杂且不够全面，软件功能不够完善，计算结果离实际应用仍有一定距离。但作为用数学模型描述并采用一定算法求解的计算机编图模式，取得了许多可借鉴的经验。,计算机编制列车运行图,北方交通大学从七十年代初开始就应用计算机对有关列车运行图问题进行了多方面的研究。首先，他们通过大量模拟试验铺划满表列车运行图，取得了双线自动闭塞区段旅客列车扣除系数方面的一些重要数据和结论，并开展了编制具有较合理弹性及均衡性双线列车运行图的研究。此外，还配合铁路重载运输和组合列车的试验开行，用计算机进行了相应的模拟计算和研究。近年来，又开展了列车运行实时调整的研究。,计算机编制列车运行图,兰州铁道学院在80年代研究了单线非追踪列车运行图的数学模型，并用启发式算法编制程序在IBM-370机上编制了6个区间、12对货物列车的实验运行图。近年来，长沙铁道学院也开展了列车运行图的优化及计算机编制问题的研究。他们根据列车运行图的组合特点，用优化理论方法建立了单、复线区段列车运行图优化的初步数学模型，建立了单线区段列车运行图优化的理论和方法，采用优化计算与人机对话相结合的方法，编制了衡阳冷水滩单线区段试验货物列车运行图。,计算机编制列车运行图,西南交通大学从八十年代初开始了计算机编制列车运行图的研究，采取理论研究与实际应用开发并举，着重于实际应用的研究路线，1987年底在VAX-750机上试编出了三个区段的单线货物列车运行图。1990年1993年，与成都铁路局合作研制开发了单线区段实用列车运行图编制系统，铺划了广元马角坝区段单线列车运行图。该系统采用“窗口”滚动技术，即首先在运行图中的某一时间段的某些区间内开一个“窗口”，然后再在该“窗口”内进行列车会让和越行的局部优化，并通过“窗口”的滚动寻求满意解。,计算机编制列车运行图,在复线列车运行图研究方面，1989年实现了计算机编制符离集徐州北区段列车运行图。并在此基础上采用模型控制为主，人机交互为辅，开发了“复线列车运行图计算机系统”，并于1993年11月1日投入实际运用，编制了济南徐州两个相连区段的实用列车运行图。经过三年的深入研究和不断完善，该系统在1997年初全路列车运行图大调整的过程中，编制了京沪线天津上海、京广线安阳浦圻和京九线临清梁堤头等区段的实用列车运行图，在我国第一次实现了计算机编制枢纽列车运行图和复线干线上的方向列车运行图。,计算机编制列车运行图,开发的此系统在1997年4月通过了铁道部鉴定，主要解决了枢纽衔接各方向列车到发的协调配合、枢纽大小运转列车工作组织、技术站直通列车接续以及敌对进路的交叉干扰等问题。此外，济南局、北京局、成都局、上海局、兰州局、柳州局、郑州局、上海铁道大学、广州铁路职工大学等单位也都先后在这方面进行了研究，取得了一些成绩。,计算机编制列车运行图,三、国内外计算机编图的方法综述综观国内外对计算机编图研究的历史和现阶段的情况，所采用的方法主要有以下几种：（1）模拟方法有模拟列车运行、模拟人工铺划等方法。该方法主要以人工编图的原则和经验为条件，生成计算机编图的判别准则和执行程序，实现人工编图的全过程。采用该方法编图，其质量和效果在很大程度上取决于判别准则和执行过程程序设计的合理与全面性。,计算机编制列车运行图,（2）移动列车始发点该方法一般在双线区段采用。编图时按某一时间间隔给定列车始发点，实现一条运行线的行车间隔检查及处理的递推铺划，当发现不满足间隔时间时，移动列车始发点，重新进行该条运行线的铺划，如此重复进行，直到处理完毕。,计算机编制列车运行图,（3）逐区间递推铺划该方法主要用于单线区段。从该区段的某一端开始，依区间出现的先后顺序进行检查铺划。对相对的两个方向而言，其中一列顺列车运行方向铺划，另一列则反方向铺划；依要求也可以从限制区间开始向区段两端延伸铺划。,计算机编制列车运行图,（4）数学模型方法利用逻辑代数、线性规划、图论及动态规划方法建立描述列车运行图的数学模型，通过编程实现计算机求解。从目前的研究结果看，由于列车运行图涉及面广、影响因素繁杂，难以用一个模型进行描述，有些因素还难以用数学表达式表达，甚至本身之间就是相互矛盾和制约的。对于这样一个NP完全问题，鉴于现阶段计算机速度、容量以及算法上的局限，还难以通过数学模型和相应的求解算法得出满意且符合实用的列车运行图。,计算机编制列车运行图,（5）人工智能专家系统方法利用智能化语言编程，把列车运行图的物理条件和人工经验作为知识规则，生成编图专家系统，并按照列车的走行顺序进行组合的运行实验。这种方法首先起源于日本，是在对“人工智能”的研究及运用日趋活跃的背景下发展起来的。,计算机编制列车运行图,（6）范围约束搜索树法该方法把运行图看作各区间列车运行顺序的一个组合，以运行时间带代替运行线铺画列车，把运行图编制作为一个搜索问题来解决。采用以时间带代替运行线铺画列车运行图，各列车的运行时间带在各区间单独考虑时，幅度比较宽，但如果把相邻区间合并起来考虑，由于列车运行的连续性，各列车就会因自身或与其他列车之间相互制约可能的到发时刻，在时刻上的传播约束条件，使时间带的宽度变窄。随着被考虑区间的增多，各列车运行时间带的宽度也越来越窄，甚至接近于列车运行线。,计算机编制列车运行图,计算机编制列车运行图,（7）人机对话方式列车运行图的编制，具有影响因素多，组织规模大，信息量大，变化快的特点。从决策问题的特征分析，运行图编制可分为方案图（草图）编制、基本图（详图）编制和实绩列车运行图编制。在上述三类运行图编图层处理的决策问题中，结构化决策问题和非结构化决策问题的比例可用图1.2表示。,计算机编制列车运行图,计算机编制列车运行图,利用计算机编制列车运行图是一个要求理论与实际相结合、技术难度非常大的工作，国内外学者为此做了大量的研究工作，尝试过许多解决方法，但是他们在取得一定的成果的同时，又存在着各种问题，而产生这些问题的根本原因就在于他们所采用的方法都是把列车运行图的编制问题作为结构化决策问题全部交由计算机来处理。,计算机编制列车运行图,编制列车运行图的过程是在有限的铁路运输设备和人力的条件下，把由战略计划层制定的列车运行方案变为具体的能够实施的列车运行计划的过程。在这个过程中，既有结构化决策问题，又有非结构化决策问题，处理时不能一概而论。因此结合我国实际情况，提出了采用人机对话方式编制客货列车运行图的方法。,计算机编制列车运行图,在编制列车运行图过程中，编图者的业务知识可分为三个部分：1编制列车运行图的技能；2编图区段内与行车有关的铁路设施、设备情况以及与编图有关的数据；3编图区段列车运行方案、运输需求和客流情况等信息。,计算机编制列车运行图,进行计算机编制列车运行图时，将第1、2部分知识赋予计算机，使编图者只需根据自己所掌握的第3部分，采用人机对话方式，由计算机编制列车运行图。,计算机编制列车运行图,采用以模型优化计算机控制为主，人机对话调整为辅，人机结合互补的方式编制列车运行图，其特点是：（1）能充分发挥计算机的高速计算能力和人的主观能动性，避免了采用单一方式所带来的不足。（2）结合了我国编图的实际情况，能有效的解决客货列车运行图综合编制、复线方向直通列车在技术站接续、枢纽各衔接方向列车的均衡到达、各局间分界口列车合理衔接、枢纽内大小运转列车的协调配合以及机车交路勾画等问题。,第一节铁路网描述第二节模型构造第三节关于模型的进一步讨论,计算机编制列车运行图,第二章网络列车运行图数学模型的研究,计算机编制列车运行图,第一节铁路网描述铁路是一个复杂的网络，旅客列车和货物列车在列车运行图的指导下有序地在铁路网上运行。构成铁路网络的主要因素是分界点（指车站和线路所）和线路。为了讨论的方便，在构造简化的铁路网络图时，只保留与列车运行直接相关的网络干支线和枢纽联络线等。同时，把车站看成一个点，车站到发线因素以及与车站相关的进路因素在构建模型时作为约束条件。,计算机编制列车运行图,简化的铁路网络图由节点和弧（连接节点的线路）组成。对应于单线铁路和双线铁路的弧，给出如下定义：定义1在构造的网络图中，如果a、b为弧j的两端节点，则节点a和节点b是相邻的；当a为弧j的起点，b为弧j的终点，则弧j是从节点a出发并到达节点b。同样，当两条弧i和j有相同节点a时，则弧i与弧j是相邻的。,计算机编制列车运行图,定义2单向弧：在一个网络图G中，有两个相邻节点和，由至存在线路，如图2.1.1所示，经过此线路只能由节点到达，反之则不能。对应于这样线路的弧称为单向弧。,图2.1.1单向弧示意图,组成复线铁路的上、下行线路在网络图中用单向弧表示，其集合为SC。,计算机编制列车运行图,定义3双向弧：在一个网络图G中，有两个相邻节点和，连接和的线路存在如下特性：既可经由此线路从节点到达节点，也可沿此线路从节点到达节点，对应于这样线路的弧称为双向弧。如图2.1.2所示，双向弧的集合为DC。在网络构造时，单线铁路对应的弧为双向弧。,图2.1.2双向弧示意图,计算机编制列车运行图,实际上，网络图构造中，单线铁路对应的双向弧，也可看成由两条单向弧组成，只不过由ja至jb这一事件与由jb至ja的事件互为敌对，不能同时发生。,计算机编制列车运行图,定义4如图2.1.4所示，弧d与弧a、b、c具有包含关系，记为(a、b、c)d，称弧d为包含弧，弧a、b、c为被包含弧，且弧a称为被包含起始弧，弧c称为被包含终止弧。包含弧与被包含弧在物理上是同一径路，因此在模型构造时应视为相同弧进行约束。包含弧与被包含弧经常在铁路枢纽内出现。,计算机编制列车运行图,定义5如图2.1.5所示，在列车实际运行径路中，若弧i被一列车占用，则另一弧j必不能被另一列车同时占用。反之亦然。称弧i与弧j存在敌对进路关系，记为ij。,图2.1.3敌对进路示意图,计算机编制列车运行图,这样，对于构造的简化铁路网络图，可以用改进的邻接目录表示，即用弧的编号与其对应节点顺序排列表示。如图2.1.4所示的网络图，可以写出其所有节点的到达邻接目录和出发邻接目录。,图2.1.4简化铁路网络示意图,计算机编制列车运行图,出发邻接目录到达邻接目录A(a)=i,c,j,bA(a)=A(b)=k,c,l,dA(b)=j,aA(c)=h,dA(c)=i,a,k,bA(d)=A(d)=l,b,h,c,计算机编制列车运行图,第二节模型构造一、约束条件这里，引入dtime表示一天的时间，dtime为一常数，当用小时、半小时、分、半分、1/4分为单位表示时间时，分别为：24、48、1440、2880、5760。同时，引入符号于模型中，其意义为：,计算机编制列车运行图,令L表示区间线路对应联弧集，LB表示半自动闭塞区间线路对应弧集，LZ表示自动闭塞区间线路对应弧集，DC为网络双向弧集，SC为网络对应单向弧集，N表示网络节点集，T表示在构造网络上运行的列车集合，Tj表示在双向弧j上由一端至另一端的列车集合，Tj表示在双向弧j上与Tj+集合中列车运行方向相反的列车集合，并有：,计算机编制列车运行图,1区间列车运行时间约束,图2.2.1列车区间运行时分约束示意图,(2.2.1),计算机编制列车运行图,2列车停站时分约束若令表示列车i在节点k对应车站的停站时分，则列车i在节点k的停站时间应满足如下条件。,图2.2.2列车停站时分约束示意图,(2.2.2),计算机编制列车运行图,3列车间隔时间约束（1）列车追踪间隔时间约束当列车在弧j()上运行时，同向列车间应按追踪间隔运行。,图2.2.3自动闭塞区间列车间隔约束示意图,计算机编制列车运行图,(2.2.3),(2.2.4),计算机编制列车运行图,（2）列车连发间隔时间约束当列车在弧j()上运行时，同向列车应按连发条件运行。如图所示，列车连发间隔时间应满足如下约束条件：,图2.2.4半自动闭塞区间列车间隔约束示意图,计算机编制列车运行图,4同向列车越行条件约束,由于列车等级不同，牵引列车的机车也可能不一样，不同等级的列车在同一弧j对应的区间线路上运行时分也不一样。,图2.2.5列车越行示意图,计算机编制列车运行图,计算机编制列车运行图,越行后的列车出发间隔需满足：,其中,计算机编制列车运行图,5车站间隔时间约束为了保证行车安全和最佳地利用区间通过能力，列车到达、出发或通过车站均需满足一定的时间间隔约束。（1）不同时到达间隔时间约束,图2.2.6不同时到达和会车间隔约束示意图,（2.2.9）,计算机编制列车运行图,（2）会车间隔时间约束,（2.2.10）,计算机编制列车运行图,（3）同方向列车不同时到发间隔时间约束,图2.2.7同方向列车不同时到发间隔约束示意图,（2.2.11）,计算机编制列车运行图,（4）同方向列车不同时发到间隔时间约束,图2.2.8同方向列车不同时发到间隔约束示意图,(2.2.12),计算机编制列车运行图,（5）不同时通过间隔时间约束,、，且,(2.2.13),图2.2.9不同时通过间隔时间约束示意图,计算机编制列车运行图,（6）列车单独占用联弧约束对于某些联弧，如单线区间线路联弧，在一定的时间范围内只允许一列车占用。,图2.2.10列车单独占用联弧约束示意图,计算机编制列车运行图,（）,(2.2.14),(2.2.15),计算机编制列车运行图,8敌对径路约束列车在实际运行过程中，由于设备条件和线路配置关系，存在如图所示的敌对径路。,图2.2.11敌对径路约束示意图,（i1、i2T，k1N,j1、j2L,L(i1,G1,i2,G2)=M1(M2),M1、M2DJKk1）,(2.2.16),计算机编制列车运行图,9机车乘务组工作时间约束,(2.2.17),计算机编制列车运行图,10天窗时间约束,2.2.12“天窗”约束示意图,iT,jL,k1N,k2N,且k1=jB|Lk2=jE|L,(2.2.18),计算机编制列车运行图,11列车到发时刻特殊要求约束,(2.2.19),计算机编制列车运行图,12车站到发线约束,其中二元函数,(2.2.20),计算机编制列车运行图,二、目标函数每一组满足以上各约束条件的解、(），就对应一给定范围的列车运行图。这里，希望寻找一组解使以下三个目标函数都达到或趋于最优的列车运行图。,计算机编制列车运行图,1总旅行时间最小令k1为列车i的始发站对应节点，k2为列车i的终到站对应节点且k1、k2LJi，则,(2.2.21),计算机编制列车运行图,2技术站列车接续时间最小设JS为技术站对应节点集合，且,则,(2.2.22),计算机编制列车运行图,3机车总消耗时间最小机车总消耗时间由两部分组成，一是牵引列车旅行消耗的时间，即列车的总旅行时间Z1,第二是在机务段和机务折返段所在站的停留时间ZL,则,(2.2.23),计算机编制列车运行图,综上所述，就构造了基于路网的预先给定列车路径的列车运行图模型，编制列车运行图就是求一组满足所有约束条件的解使三个目标函数达到或趋于最优。,计算机编制列车运行图,第三节关于模型的进一步讨论一、关于目标函数的优化处理使目标函数都达到最小值的运行图是理想的最优运行图。在实际工作中，由于这些目标既相互依赖又相互制约，一般不可能使所有的目标函数均达到最优。因此，处理该多目标规划问题时，可以从具体实际出发，视各目标在总问题上所占的地位，抓住主要因素，将问题简化为单目标规划问题求解。,计算机编制列车运行图,我们可以把追求列车旅行时间最小(2.2.21)作为优化目标，把(2.2.22)作为约束条件处理：,(2.3.1),计算机编制列车运行图,对于机车总消耗时间，它是牵引列车消耗的总旅行时间和不牵引列车时在段（机务段和折返段）所在站停留总时间组成，而第一部分时间即为列车的总旅行时间。因此，目标函数可以写成：minZ3=minZ1+minZL(2.3.2),计算机编制列车运行图,二、关于模型的适用性模型基于网状线路编写，适用于单线、复线、单复线、三线及多线情况，也适用于自动闭塞和半自动闭塞区段、直线方向、枢纽及路网情况。（1）当构造的路网图中只存在双向弧，去掉不同时通过间隔时间约束,模型退化为一个单线网络列车运行图模型；（2）当构造的网络图中只存在单向弧，则去掉不同时到达间隔时间约束、会车间隔时间约束、不同时通过间隔时间约束、列车单独占用联弧约束，模型退化成一个复线列车运行图模型；,计算机编制列车运行图,（3）当构造的网络图中所有的弧，则约束条件列车连发间隔时间约束和同向列车越行条件约束中的一部分可以删去；当所有的弧，可以不考虑列车追踪间隔时间约束；（4）当把模型用于区段和直线线路时，则模型自动退化为区段列车运行图和直线方向列车运行图模型。,计算机编制列车运行图,三、关于弧的统一简化根据单线铁路行车的特点，在构造的网络图中，把单线区间线路对应的双向弧看成具有敌对径路关系的两条单向弧，如图2.3.1所示。,图2.3.1双向弧敌对关系示意图,计算机编制列车运行图,由此，(2.2.9)和(2.2.13)式可改写为：,(2.3.3),计算机编制列车运行图,同理，式（2.2.10)、(2.2.11)可改写为：,式(2.2.12)改写为：,(2.3.4),(2.3.5),计算机编制列车运行图,因此,对于发生在两相邻弧和同一双相弧的不同列车运行事件,可归纳为约束条件(2.3.6)。,(2.3.6),模型得到进一步简化。,计算机编制列车运行图,四、关于接触网天窗的约束处理在编制列车运行图时,一般要考虑线路维修和接触网检修需要，即在编制的列车运行图中要预留施工“天窗”。对不同线路条件、不同类型的“天窗”，模型中对“天窗”约束的处理是有区别的。,计算机编制列车运行图,（1）接触网检修“天窗”，考虑电分相点的位置,图2.3.2电分相点位置示意图,图2.3.3电力牵引“天窗”设置示意图,计算机编制列车运行图,(2.3.7),如图所示，则对于弧j2的约束条件为：,计算机编制列车运行图,（2）复线线路开设“天窗”，封锁一条正线，另一条正线双向行车不失一般性，设在t1,t2时间范围内，上行正线封锁施工，下行正线改为双向行车。在计算时，只需在该时间范围内把下行正线区间线路对应弧j由单向弧变为双向弧，由式(2.2.9)、(2.2.10)、(2.2.13)、(2.2.14)约束；也可在该时间范围内把发生在该弧j的上下行列车运行事件看成互为敌对事件，由式(2.3.6)约束。,第三章列车运行图计算方法的研究,计算机编制列车运行图,一、基于网状线路列车运行图分解算法在模型的建立中，随着构造网络图中弧和节点数的增加，以及在线路上开行的列车数的增加，模型中的变量和约束条件的增加速度愈来愈快。在一条只有200个车站，开行100对列车的直线线路上，假如每一列车的平均行程为100个车站，则描述该线路列车运行图的模型变量数约为60000个，约束条件大约在100，000个以上。,计算机编制列车运行图,计算机编制列车运行图,在我国，由七万多公里线路和近五千个车站组成的路网上，每天都开行着上千对旅客列车和上万对货物列车，对于如此大规模的问题，目前的算法和计算速度都难以适应要求。因此采用了如下的分解算法使计算过程获得简化。,计算机编制列车运行图,对于如图所示的简化网络图，其原模型可写为：,图3.1简化网络示意图,计算机编制列车运行图,计算机编制列车运行图,现将其一条线路抽出，如只考虑AB，则可得子问题模型为,然后采用加边法，将线路BC加进模型考虑，形成两条线路组成的网络图，要编制这个网络图的列车运行图，可把设计的AB子问题的解中与节点B相关的解分量加入新问题中考虑得到新的问题模型。,计算机编制列车运行图,图3.2加入线路BC后的简化网络示意图,计算机编制列车运行图,运用加边法依次类推，可逐步得到新问题及其模型，最后完成整个网络图分解后的模型。计算得到的解也明显与原问题一致。同时考虑描述在不同线路上运行的列车在节点B和D以及与节点B、D相邻的弧的约束，写出新的连接方程。,图3.3加入线路BD后的简化网络示意图,计算机编制列车运行图,最后，原问题可以分解为如下五个子问题求解,计算机编制列车运行图,对于任意规模的路网，均可采用加边法求解子问题，逐步得到路网列车运行图的解。分解网状线路的关键就在于如何选择线路交会点，作为生成列车始发、终到方案的基点。在生成列车初始到发点方案的基础上，可采用上述方法分步建模，为相对的子线路求解。,计算机编制列车运行图,二、时空局域滚动计算方法在将问题分为若干个子问题进行求解的基础上，提出了基于每一子问题求解的时空局域滚动计算方法。其算法思想可描述为：在运行图上设置一个可以包含若干个弧和节点、若干个运行列车的运行图窗口，在此窗口范围内可能出现的方案进行计算和比较，得到局域解并将其计算出来的分量带入预先设定好的约束条件，若满足条件则将窗口右移，换出最左方列车，换入右方一列新的列车，再次求解，依次类推直至得到完整的运行图解。,计算机编制列车运行图,图3.4运行图“窗口”示意图,计算机编制列车运行图,对于窗口局域