铁路大提速下的京沪线列车调度(含有源程序)

  • 格式:doc
  • 大小:2.17 MB
  • 文档页数:20

铁路大提速下的京沪线列车调度摘要本文针对目前京沪铁路运行现状,对京沪铁路上添加列车其运行图的铺画问题进行了研究,并探索了晚点列车调度的问题。

在添加货车时,本文选取徐州——蚌埠区间作为研究对象,采用运筹学中的网络最大流理论,根据列车实际运行要求提出了一系列约束条件,在此基础上对此区间内的车站和图定列车画出了网络图,并建立了相应算法求取网络最大流量即此区年内可铺画的最大货车数目。

通过对已求得网络图中增广链的分析,我们编排了货车运行时刻表,并铺画出了新的列车运行图。

在考虑临客问题时,将此模型进行了改造与推广,使之适用于解决临客的铺画问题。

通过依次向运行图中添加临客,我们得出一系列可行的方案。

对这些方案进行总耗时和对货车影响的比较后,最终得到了一个优化的临客运行方案。

最后,采用“满意理论”的思想,建立了一个在多约束条件下求得目标函数最优解的满意优化模型,并采用遗传算法对其进行求解。

关键字运行图网路最大流遗传算法列车运行调度一、问题重述与问题分析1.背景京沪线是我国最繁忙的铁路线之一,直接贯通我国两大枢纽城市北京上海,目前全线采用上行线和下行线独立双向运行方式,均承担着多趟客车。

我国铁路大都采用客货混运的机制,目前主要干线铁路客车最高时速可达160公里/小时,货车最高时速为80公里/小时。

怎样在繁忙的客运线上尽可能多的安排火车以提高运量成为社会各界关心的话题。

2.任务1)从京沪全线选择一个区间段,根据现行的列车时刻表最多能安排多少趟货车,并制订出具体的“列车运行图”。

2)对现行的列车时刻表进行分析,若要在客流增加时在北京至上海、北京至南京、天津至上海、北京至合肥、北京至青岛间各增开一对临时客车,在不改变现行列车时刻表及尽量减少对货车影响的条件下,安排京沪线区间临时客车的时刻表及“列车运行图”。

3)如果在即将实行的第6次大提速时将京沪线上的客车的最高时速提高到200公里/小时,货车的最高时速提高到120公里/小时,制订出相应的客车时刻表和“列车运行图”。

按照第1题选择的区间段进行估计,与提速前相比货车可以提高多少运力?4)针对预计到2010年投入运行的京沪高速铁路客运专线,如果高速列车时速达到300公里/小时,普通列车提速到200公里/小时。

在安全行车规程的要求之下,并考虑各经过城市的客运需求量,给出现有客车相应的时刻表,同时还能至少增加多少客车,运行时刻表如何?5)如果某一列客车因故晚点,就会影响到后续列车的正常运行,给出可行的实时调整相关列车的运行策略,使得造成的影响最小,并就某一列客车进行分析检验。

3.分析.对于第一问,在京沪全线中选取了徐州——蚌埠的这一段铁路进行分析。

为了尽可能多的安排货车,我们决定采用网络最大流的算法对此问进行分析,并结合考虑列车在运行过程中的多种约束条件,得出添加的货车数目并可相应的画出运行图。

对于第二问,虽然添加临客与添加货车的情况有所不同,但我们仍可利用上问的模型,将其进行适当的改进,得出最优解,排出临客运行时间表。

对于第五问,针对客车晚点这一现实意义极强的情况,我们决定建立满意优化模型,并使用遗传算法对其求解,以徐蚌区间为例,进行实况分析。

二、基本假设1.客车进站、出站的时间都不予考虑。

2.不考虑机车交路3.不考虑货车避让线4.不考虑维修天窗三、符号约定与名词解释1.名词解释接算站 指连接两条或两条以上线路、办理接算业务的车站 到发线 指车站内可供避让的股道数目 闭塞 指对相继运行的列车间距的约束增广链运筹学网络流理论的术语,这里借用来表征一个可行的列车调度2.符号约定 G 目标运行图矩阵 T调整后的运行图矩阵12(,)G G ρ 距离函数,表征两张运行图的接近程度 12(,)w G G ρ加权后的距离函数 j Sj 车站到发线数目四、利用网络最大流模型求解区间货车数目1.背景讨论首先选择研究的区间。

本文重点在于理论模型的探讨,因此选取的区间既要有代表性、有现实价值,又不希望带来不必要的复杂度。

因此我们选取区间,遵循以下原则:a.区间两端为接算站b.区间内无接算站京沪铁路从北至南大概分为京山线京津段,津浦线津德段、德济段、济徐段、徐蚌段、蚌宁段和沪宁线。

我们权衡后,选择了津浦线徐蚌段作为研究对象。

徐蚌段上起徐州,下至蚌埠,历经徐州、符离集、宿州、芦岭、固镇与蚌埠六个三等以上车站,全程165公里,图定共有51对列车经过。

据此,画出区间运行图如下:图1 徐蚌段图定客车列车运行图下面向区间内铺画货车。

为了简化模型,我们做以下约定:1.铺画的货车运行区段为全区间2.假定货车在区间内匀速运行,并不考虑启动与制动时间3.不考虑闭塞区间4.不考虑接续时间5.上下行分开,单独考虑6.货车以一定间距从第一站均匀发出7.不考虑通勤、路用、运转等非图定列车。

8.不考虑晚点、机破等突发事件在此约定下,铺画的货车就成为了图中的平行斜线,其斜率为货车的平均速度。

此时,铺画货车只受到两个约束1.货车不能对现有客车运行图有任何影响2.待避列车数目受到所在车站到发线数目约束定理1:铺画货车运行图,遵循的唯一原则是,货车不能在区间内被客车超越。

我们不妨设相邻的两站为k站和1k站,在两站之间铺画一趟客车一趟货车,设货车发车时间为t k,客车发车时间为t k’,货车到站时间为t k+1,客车到站时间为t k+1’,则运行图可能出现以下四种情况:图2 相邻两站客货车冲突示意可以看到,情况I与情况II不会发生冲突;情况III由于客车速度慢于货车,是不可能发生的。

因此,发生冲突的只可能是情况IV。

此时,货车发车时间早于客车,而到站时间晚于客车。

换句话说,此时[t k’,t k+1’]含于[t k, t k+1]。

因此得到结论:若[t k’,t k+1’]含于[t k, t k+1],则k站到k+1站之间会发生客车追上货车的情况,从而产生冲突,使得这种调度成为错误的调度。

2.绘制网络图货车运行中,有在两站之间运行与在某站待避两种情况。

列车运行时,其时间与空间一起发生改变;而待避时,只有时间发生改变,而空间保持不动。

因此,我们可以自然的想到,利用图论网络的思想解决此问题。

某车站在某时刻的状态,表示为图中的结点。

例如,蚌埠站在2:00的状态,就表示为结点(蚌埠, 2:00)。

而结点内的值,就是在此时刻时,此站内待避的列车数目。

下面,把这些结点组成网络。

把表示同一车站不同时刻状态的结点纵向排成一列;这样,6个车站,就有了6列结点。

6列拼合,就组成了一个网络。

这个网络中,纵向相邻的两个节点为同一车站相邻时间的状态,其时间间距为货车的发车间隔;而横向相邻的两个结点位相临界点相继时间的状态,其时间间距为货车在两站之间的平均运行时间。

然后,在网络的节点之间添加弧。

a.纵向相邻的结点之间都添加上弧,弧的容量为车站的到发线数目。

这样,一个流量从上面的结点流到下面的节点,就表示实际中,一趟列车待避了间距时间;弧的容量限制就表征了到发线数目的约束。

b.横向的相邻结点之间,只有调度可行才添加弧。

所谓调度可行,就是对于横向相邻结点(k, t1)和(k+1, t2),k站和k+1站之间的所有客车的运行时间,都不得含于[t1, t2]。

若调度可行,弧的容量则限制为1;一个流量从左边的节点流到右面的节点,就表示实际中,一趟列车从左边的站点运行到了右面的站点。

由以上的讨论可见,一趟图定的货车,表示在网络中,就是一个从最左边一列流到最右边一列的一个增广链。

而可以铺画的货车的最多数目,就是此网络的最大流量。

由此可见,按照上面的规则得到网络图后,只要求出其最大流量,此流量即为所求。

一般来说,求取最大流采用Ford-Fukerson标号法为多。

但是标号法不易用程序实现,因此,结合问题实际,我们采用这样一种算法:1.从第一列第一个结点开始,引出一个流量。

2.若目前节点有弧引向右边的相邻结点,且此弧容量未满,则将此流量沿弧流向右边。

3.若向右无弧,或者流量已满,则沿向下的弧流向下边。

4.若向右、向下的弧流量皆满或已无弧可前进,则此流量取消。

5.若某流量到达了最右边一列,则停止前进。

同时回到第一列,从此列的下一个结点开始,重复此算法把第一列所有的结点都引过流量后,达到最右边一列的节点的流量之和,即为此条件下最大可铺画货车数目;而此流量流经的结点历程,就是此趟货车的运行图。

实现算法,利用Matlab实际求解徐蚌区间。

按列铁路技规,相继车次的最短发车间隔为7min。

本题目中,为留有一定的裕度,并考虑到安全闭塞因素,设定每15min发出一趟货车,其平均时速为50kph。

则,此区间内上行可最多铺画48趟货车,下行可最多铺画39趟货车。

针对每一条增广链,我们可以排出货车运行时刻表如下:50001 -0:45 -1:582:153:304:004:154:416:267:18-50003 -6:00 -7:13-7:30-8:00-8:269:18-50005 -6:30 -7:438:008:15-8:42-9:1110:03-50007 -7:15 -8:28-8:45-9:159:419:5610:48-50009 -7:30 -8:23-9:009:309:45-10:1111:03-50011 -7:45 -8:589:159:30-10:0010:2611:4112:33-50013 -11:30 -12:43-13:00-13:30-13:5614:48-50015 -11:45 -12:58-13:15-13:45-14:1115:03-50017 -12:00 -13:18-13:30-14:00-14:2615:18-50019 -12:15 -13:3313:4514:00-14:30-14:5615:48-13:15 14:28 4:45 15:15 15:41 -50023 -13 :30 -14 :43-15:00-15:30-15 :5616::48-50025 -13 :45 -14 :58-15 :15-15 :45-16 :1116 :43-50027 -14:00 -15 :13-15 :30-16:00 -16 :2616:58-50029 -14:15 -15 :13-15 :45-16:15-16:2616:58-50031 -14:30 -15:43-16:00-16:30-16:5617:48-50033 -14:48 -15:58-16:15-16:40-16:4318:03-50035 -15:00 -16:13-16:30-17:00-17:2618:18-50037 -15:15 -16:28-16:45-17:15-17:4118:31-50039 -15:30 -16:43-17:00-17:30-17:4618:48-50041 -15:45 -16:58-17:15-17:45-18:1118:34-50043 -16:00 -17:13-17:30-18:00-18:2619:18-50045 -16:15 -17:28-17:45-18:15-18:4119:33-50047 -16:30 -17:43-18:00-18:30-18:5619:48-50049 -16:45 -17:58-18:15-18:4519:1119:2620:18-50051 -17:00 -17:5318:3019:00-19:30-19:5620:48-50053 -18:00 -19:13-19:30-20:00-20:2621:18-50055 -16:15 -19:28-19:45-20:15-20:4121:33-50057 -18:45 -19:58-20:15-20:45-21:1122:03-50059 -19:00 -20:13-20:30-20:56-21:4822:18-50061 -22:00 -23:13-23:30-00:00-00:2601:18-22:15 23:28 23:45 00:15 00;41 -50065 -22:30 -23:43-00:00-00:30-00:5601:48-50067 -22:45 -23:58-00:15-00:45-01:1102:03-50069 -23:00 -00:13-00:30-01:00-01:2602:18-50071 -23:15 -00:28-00:45-01:15-01:4102:48-50073 -23:30 -00:43-01:00-01:30-01:5602:48-50075 -23:45 -00:58-01:15-01:45-02:1103:03-上行:车次蚌埠固镇芦岭宿州符离集徐州50002 -1:45-02:3603:0303:3304:0304:18-04:3405:48-50004 -3:30-4:21-4:48-5:18-5:346:48-50006 -4:45-5:36-6:03-6:33-6:498:03-50008 -5:00-5:51-6:18-6:48-7:047:18-50010 -5:15-5:06-6:33-7:03-7:198:33-50012 -5:45-5:21-6:48-7:18-7:348:38-50014 -5:45-6:36-7:03-7:33-7:499:03-50016 -6:00-6:51-7:18-7:48-8:049:18-50018 -6:15 7:06-7:33-8:03-8:199:33-50020 -6:30-7:21-7:48-8:18-8:349:48-50022 -6:45-7:36-8:03-8:33-8:4910:03-50024 -7:00-7:51-8:18-8:48-9:0410:18-50026 -8:00-8:51-9:18-9:48-10:0411:18-50028 -8:15-9:06-9:33-10:03-10:1911:33-50030 -8:30-9:21-9:48-10:18-10:3411:48-50032 -8:45-9:36-10:03-10:33-10:4912:03-50034 -9:00-9:51-10:18-10:48-11:0412:18-50036 -9:15-10:06-11:03-11:33-11:4913:03-50038 -9:30-10:21-10:48-11:18-11:3412:48-50040 -9:45-10:36-11:03-11:33-11:4913:03-50042 -10:00-10:51-11:18-11:48-12:0413:18-50044 -10:15-11:06-11:33-12:03-12:1913:33-50046 -10:30-11:21-11:48-12:18-12:3413:48-50048 -10:45-11:36-12:03-12:33-12:4914:03-50050 -11:00-11:41-12:18-12:48-13:0414:18-50052 -11:15-12:06-12:33-13:03-13:1914:33-50054 -11:30-12:21-12:48-13:18-13:3414:48-50056 -11:45-12:36-13:03-13:33-13:4915:03-50058 -12:00-12:51-13:18-13:48-14:0415:18-50060 -12:15-13:06-13:33-14:03-14:1915:33-50062 -12:30-13:21-13:48-14:18-14:3415:48-50064 -13:00-13:51-14:18-14:48-15:0416:18-50066 -13:15-14:06-14:43-15:03-15:1916:33-50068-14:00 -14:51-15:18-15:4816:0416:3417:48-50070 -14:15-15:06-15:3316:0316:1816:3416:4918:03-50072 -14:30-14:51-16:18-16:48-17:0418:18-50074 -14:45-15:36-17:03-17:0317:1917:3418:48-50076 -15:00-15:51-16:18-16:4817:1917:4919:03-50078 -15:15-16:06-16:33-17:0317:1918:0419:18-50080 -15:30-16:21-16:48-17:1818:3418:4919:43-50082 -16:00-16:51-17:18-17:4818:1918:4920:03-50084 -19:30-20:21-20:48-21:18-21:3422:48-50086 -20:30-21:21-21:48-22;18-22:3423:48-50088 -20:45-21:36-22:03-00:4800:0400:4902:03-50090 -21:00-21:51-22:18-00:0300:1901:0402:18-50092 -21:15-22:06-22:33-00:1800:3401:1902:33-50094 -21:30-22:21-22:48-00:3300:4901:3402:48-50096 -21:45-22:36-23:03-00:4801:0401:4903:03-画出区间内的列车运行图:图3 上行货车运行图图4 下行货车运行图五、临客运行图的铺画网络最大流的模型,其核心思想在于遍历所有的可能通路(即增广链)。