行车课件3-第三章--技术站列车编组计划的编制

第三章 技术站列车编组计划的编制,第一节 编制单组列车编组计划的基本原理 第二节 绝对计算法 第三节 表格计算法 第四节 整数规划模型和二次0-1规划模型简介 第五节 分组列车编组计划 第六节 区段管内列车编组计划,技术站汇集的车流： 装车地直达列车未吸收的车流； 到达技术站解体的装车地直达列车内的运程车流； 卸车地未能组织空车专列的零星空车；,第一节 编制单组列车编组计划的基本原理,第三章 技术站列车编组计划的编制,一、技术站车流组织的两个原则 同一支车流不拆散原则：技术站发出的车流有许多支，一般不可能每一支车流都单独形成一支列流，故有两支或多支车流合并在一起的情况，它们共同合成一支较短程的列流，开往较近的技术站。当车流合并时，不应当把同一支车流的车流量分离开来，分别与不同的车流合并，纳入几支不同的列流中。,第三章 技术站列车编组计划的编制,车流接续归并原则：在车流合并之后，流程较长的车流不得不“迁就”流程较短的车流，在某一技术站改编，然后继续前进。这时，长程车流便成为该技术站发出的车流的一部分，与该站相同到站的车流合并开行。,二、编组方案表示法 一支列流的形成，不外乎两种可能： 或者是一支车流单独形成一支列流简称“单开” 或者是两支或多支车流合成一支列流简称“合开” 如果把单支车流不与任何其它车流合并也视作一种车流组合方式的话，那么可以说，列流是由车流组合而形成的。因此，一个编组方案，实质上就是方向上所有车流的一种组合方式。同一技术站发出的车流相互组合形成该技术站的编组方案，方向上各技术站的编组方案配合起来构成方向上的编组方案。,第三章 技术站列车编组计划的编制,技术站的编组方案用阿拉伯数字、加号“+”和逗号“，”所组成的式子表示。 阿拉伯数字代表车流的到达站 “+”表示车流合并开行 “，”表示车流不合并 把方向上各技术站的编组方案写在一起，中间用分号“；”隔开，便可以表示方向上的编组方案,第三章 技术站列车编组计划的编制,以下图（左）中的A4站为例，如果N40， N41， N42， N43都单开，则编组方案为“0,1,2,3”；如果N40与N41合并形成列流， N42与N43合并形成列流 ，则编组方案为“0+1,2+3”。,若N40， N41， N42合开， N43单开， N30， N31合开， N32单开， N20， N21单开，N10单开，则方向上的编组方案为“0+1+2，3；0+1，2；0，1；0”，此编组方案的列流图如下图（右）所示 。,第三章 技术站列车编组计划的编制,三、单组列车编组方案数 对有n个技术站的线路方向，除A0站外，任一Ak站恰好发出k支车流。记Ak站的编组方案数为f(k)，这也就是k支车流的组合方案数。显然，f(1)=1。为了推导公式的方便，规定f(0)=1 。 按照单组列车的含义，列车中车流的到站不应近于列车的到站，所以在Ak站发出的k支车流中，最短的那支车流(k,k-1)必须纳入最短的列流中，否则不为任何列流所吸收。这意味着，在Ak站的单组列车编组方案中，总存在一支列流。 除车流外， Ak站还有支车流，从中任意选出i支车流与车流(k,k-1)合开，有 种选法，每一种选法都可以与剩下的k-1-i支车流的组合方式匹配形成编组方案，而k-1-i支车流的组合方式数也就是Ak-1-i站的编组方案数f(k-1-i)。,第三章 技术站列车编组计划的编制,Ak站的单组列车编组方案数为 有n个技术站的线路方向上全部编组方案数q(n)为 排除不相邻车流合并这种情况，有n个技术站的方向上总的编组方案数q(n)为,第三章 技术站列车编组计划的编制,随着n的增大，方案数目爆炸式地增长。如何解决这种“组合爆炸”问题，是车流组织面临的一大难题。 现在通常采用的方法是分阶段计算法，即根据车流集散规律把全路划分成多个地区或方向，使每个地区或方向包含少数几个主要编组站通称“支点站”. 第一步，计算支点站的列车编组计划 第二步，分别计算各相邻支点站之间的编组计划。,第三章 技术站列车编组计划的编制,支点站的选择应注意： （1）是大量车流产生或消失的地点； （2）具有先进的技术设备和强大的改编能力； （3）是变更列车重量（或换长）标准的地点； （4）是地理上的自然分界点，如国际联运的口岸站，水陆联运的交接站，铁路方向的起讫点等； （5）处于几条铁路线的交汇地点。,第三章 技术站列车编组计划的编制,四、总体思路 关于编组方案优化算法，国内外专家学者进行了长期的研究和探索，提出了各种各样的优化方法。按其性质，可以归纳成三大类： 第一类是穷举法，习惯上称为绝对计算法，就是对所有的编组方案逐一计算其车小时总消耗，其中总消耗最小的方案即为最优方案。 第二类可称为筛选法，其要点是通过一定的判别条件来删除或排除部分不利的方案，精简方案数，缩小搜索范围，而对未删除的方案进行分析比较，逐步选出经济有利的方案。 第三类数学规划法，就是把车流组织问题化为一类数学规划问题来建模求解。,第三章 技术站列车编组计划的编制,第二节 绝对计算法,一、目标函数 以F耗记方向上总的车小时消耗，绝对计算法的目标函数为： 其中： 因此,第三章 技术站列车编组计划的编制,二、计算方法,各支点站改编车数,各支点站改编车小时消耗,编发的直达列流支数,该编组方案的方案值,编组方案表达式,行：直达车流 列：沿途支点站,第三章 技术站列车编组计划的编制,产生显然不利方案的情况有两种： （1）当远程车流与短程车流合并时，额外增加改编作业次数； （2）当远程车流与短程车流合并时，虽改编次数不变，但在t节值较大的支点站改编。,第三章 技术站列车编组计划的编制,分析左图的10个方案，有： 方案是显然不利方案（与方案相比，在A2站徒然增加一次改编作业） 方案与方案比较，如果 ，则方案是显然不利方案，因为 反之，方案是显然不利方案。,第三节 表格计算法,一、算法原理 假定存在一个方向上每支车流在途中每个支点站都改编的编组方案（即一支直达列流也没有的方案）。这样，任何一个编组方案与它比较，只要有某支车流（设车流量为N通）在某支点站无改编通过，相对于这个假想的方案就有车小时节省N通t节。把方案中有无改编通过车流的支点站集合记作W，设 ，在w站无改编通过的车流量为 ，w站的t节为 ，则直达车流无改编通过途中支点站的车小时总节省F通为,第三章 技术站列车编组计划的编制,以F节表示编组方案总的车小时节省，则 目标函数为： 就算法思想而言，表格计算法并不对全部编组方案计算方案值，而是利用几个判别条件，把肯定有利的列流（如果存在的话）首先确定下来，把不合理的列流排除在外，对可能有利的列流，按不同的车流合并方式计算车小时节省，然后加以比较选择。这些判别条件包括绝对条件、必要条件和充分条件。,第三章 技术站列车编组计划的编制,1.绝对条件 该支车流在沿途任一支点站无改编通过的车小时节省都不小于该车流编开直达列流在列车始发站的集结车小时消耗。 其中,K为直达车流（i, j）的途中支点站集合 例题,由绝对条件可以得到一个推论：若 则车流(i，j)不应在站k改编。此时，称车流(i，j)在支点站k满足了绝对条件。,第三章 技术站列车编组计划的编制,【例2-3-2】下图表示出5个支点站方向的6支直达车流量、各支点站的T集和t节。,因为：,所以，车流（4，1）和（2，0）满足了绝对条件，应当开行直达列流和，并归入最优编组方案中。,第三章 技术站列车编组计划的编制,2.必要条件 该支车流无改编通过沿途支点站所获得的车小时总节省不小于该车流编开直达列流在列车始发站的集结车小时消耗，即 若干支直达车流（设其中最短的车流为（i,j），总车流量为 ）合开的必要条件是： 这些车流合并之后无改编通过沿途支点站所获得的车小时总节省不小于它们合开直达列流在列车始发站的集结车小时消耗，即,第三章 技术站列车编组计划的编制,3.充分条件 一支（或几支合并的）长程车流不与某支（或几支相互衔接的）短程车流合并的充分条件是：长程车流在其超行区段无改编通过支点站的车小时总节省不小于该车流编开直达列流在始发站的集结车小时消耗。这里所谓“超行区段”，是指长程车流比短程车流多运行的那部分区段。,第三章 技术站列车编组计划的编制,二、算法步骤 画出表格及算法的计算表格如下所示,各支直达车流量N通与途中支点站的t节的乘积 N通t节,改编车数,改编能力,第三章 技术站列车编组计划的编制,在表格的上半部分填记完毕之后，选择最佳方案的工作可按下面的步骤进行。 第1步 确定初始方案 1.对满足绝对条件的单支车流，在其各格内画上“”记号，表示列流确定开行；若某支车流在支点站满足了绝对条件，亦在相应格内画上“”记号，表示该车流不在站改编。 2.对满足必要条件（2-3-13）的单支车流，在其各格内画上“”记号，表示暂定为单开。 3.对其余车流，考虑相互合并，若满足必要条件（2-3-14），在格内画“”记号；若不满足，则考虑与已画“”或“”记号的车流合并，合并后也在相应格内画“”记号。 至此，初始方案确定完毕。,第三章 技术站列车编组计划的编制,第2步 调整初始方案，逐步寻求最优方案 调整的实质是利用必要条件和充分条件，寻找更为有利的车流组合方式。调整的方法一般是从流程较长的车流入手，改变它（们）与其他较短车流的合并方式由与这一支（或几支）车流合并变为与那一支（或几支）车流合并，由合开变为单开，由单开变为合开等等。 直观地看，对长程车流可采取两种办法： 1.压缩。压缩长程车流的到站，或发站，或发、到站同时压，使之与短程车流合并。 2.切割。把一支长程车流分割成两部分或更多部分，分别与两支或多支短程车流合并。,第三章 技术站列车编组计划的编制,调整将会引起车小时得失的变化。其变化表现在这样几个方面： (1) 直达列流支数的变化。列流支数增加，就有的损失（即多消耗），列流支数减少，就有的节省； (2) 直达列流始发站的变更。若始发站由变为，则集结车小时消耗由变为； (3) 直达车流无改编通过途中支点站的变化。只要在某支点站通过，便在对应的格子内画“”，只要在某站改编，便在对应的格子内取消“”。由无“”变为有“”，表示有车小时节省，由有“”变为无“”，表示有车小时损失。这种变化容易在计算表上直接观察出来。 经过简单的计算，可以得出调整后车小时的变化值。只要车小时总节省在增加，换言之，只要调整带来的节省，大于调整引起的损失，就应当进行调整。每次调整完毕后都得到一个过渡方案，又可以此为基础进行新的调整，如此逐步逼近最优解。,第三章 技术站列车编组计划的编制,第3步 检查最优方案，确定最佳方案 方案调整到最后，找不到节省车小时更多的方案，即得到最优方案，接着可填写计算表的下半部分。若有的支点站改编车数大于其改编能力，则应进行方案的改选。这时，可以退回到某过渡方案重新调整，也可在最优方案基础上，对能力不足的支点站组织部分车流无改编通过，以减少改编车数。何者为佳，仍需比较确定。 最佳方案确定之后，用式（2-3-10）计算其方案值，并画出对应的列流图。,第三章 技术站列车编组计划的编制,【例2-3-3】已知资料及计算表格如图2-3-6所示。 第1步 确定初始方案,初始方案的方案值为,第三章 技术站列车编组计划的编制,第2步 调整初始方案 1.对长程车流N40压缩到站，由与N42和N20合并，变为与N41合并，得过渡方案。 这样调整引起的车小时变化有： 600+180-120-450=210（车小时）,第三章 技术站列车编组计划的编制,2.在上面的基础上，对长程车流压缩到站，即由单开变为与合并，得过渡方案，结果见下图。因这一调整节省300车小时，损失260车小时，净节省40车小时。,第三章 技术站列车编组计划的编制,3.在上面的基础上，对长程车流由压缩到站变为压缩发站，即不与合并，而与合并，结果右图所示