数学建模论列车调度的最大流与分解协调模型20

1、列车调度的最大流与分解协调模型胡晶王凤娟廖建华指导教师：张清华【摘要】本文以济南至徐州段作为研究对象，采用规划模型确定最大货车插入量、列车时刻表及运行图等。在确定货车插入量时，建立最小最大值模型，在一定的约束条件下，利用网络系统的最大流问题解决两个相邻站点最多可插货车量，再取各相邻区间段可插货车最小值作为该段的可行插车数，通过Excel求解，最后得出下行线可插货车数为50辆，上行线可插货车数为18辆，并通过 Matlab编程绘制了列车运行图。在制定临时客车时刻表时，采用“提高正点率”来刻画增开临时客车对货车所造成的影响程度，使调整后的各次列车充分贴近预定时刻，尽快恢复列车的正点运行， 建立相应

2、的线性规划模型，并得出了相应的列车时刻表和列车运行图。当列车晚点时需要进行列车调度，提高列车平均运行速度和提高列车运行正点率是本文使用的两个优化目标。【关键词】列车调度线性规划 多目标优化Matlab1问题分析本题以济南至徐州区间段为研究对象，主要研究以下三方面的问题：最大货车插入量，临时列车时刻表及运行图，因故晚点时所进行的调度策略。求最大货车插入量时， 要求相邻列车必须满足一定的时间间隔和空间间隔条件，即两相邻列车在区间运行时的时刻差与空间距离必须满足一定的约束条件，这是典型的在约束条件下的规划问题；制定临时客车时刻表时，要求不改变现行列车时刻表及尽量减少对货车的影响，此处关键是用一个指标

3、来刻画临时客车对列车的影响，把不影响现行列车和对货车的影响最小作为目标来安排临时客车时刻 表；当客车因故晚点进行调整时，要使得造成的影响最小， 关键也是用一些指标来表示对列车造成的影响。2基本假设（1）客车运行的让路原则是慢车让快车（2）列车在两个站点间是匀速运行的（3）忽略列车的长度，将其视为一质点，不影响运行路程（4）各站点可容纳停留的列车数量无限大，即在站点可以超车（5）同相行驶的列车间至少相隔7分钟才可以正常运行3模型建立与求解1.最大插车量及列车运行图的确定1.1模型建立列车有序运行：列车运行必须满足一定的时间间隔和空间间隔要求，即两列列车在区间运行的时刻差与空间距离必须满足一定的约

4、束条件。由于不同类型列车具有不同的速度，通过所给数据总共有五种类型的列车，分别为直达（Z）、特快（T）、快速（K）、管道高速（N）、普快（数字）。根据所给数据，利用不同类型的列车所经过的总路程与其所花的总时间的比值得出不同类型列车的平均速度：nx SjW 二罟其中匸1、2、3、4、5 （1）送Tjjj H各类型列车的平均运行速度为:vi = 120km/h,V2 =110km/h,V3 = 80km/h,V4 = 75km/h,V5 = 70km/h一般情况下，货车的运行速度小于客车运行速度，故设定货车的平均运行速度为v6= 70km/h列车运行调整问题是多目标优化问题，为研究其数学性质， 下

5、面以复线调度区段为研究对象首先建立最大网络流模型。假设某线路途经n个车站，设为第1个站点和第n个站点分别为始发站和终点站，其余各站称为中转站点。对于任意两相邻站点之间均存在最多安排的货车数目= maxMj（i =1,2, n） （ 2）则此条铁路上最多可安排的货车数目为M 二minM1',M2', ,Mn' （3）此时问题转化为求解各区间段的最大可插货车数目M的最小值，建立优化模型M 二minM1,M2, ,Mn' M=maxMj（i =1,2, n）即 M 二 mi n YmaxMmax M2, maxMj （ 5）约束条件：1.相继两列列车在两个相邻站点运行

6、期间的时间间隔不得少于7分钟；2.货车与客车的运行总量比大约为 5:7 ；下面给出约束条件的数学表达式（以济南至天津为考虑范围），考虑沿下行方向的第i个车站的插车情况，一个运行周期内共开出 p辆列车，第i个车站与第1个车站间距离为 Si，设插车时间为Tk，从第i个车站开出的时间按从小到大进行排序有11 , t 2，当两个时间段可插车时，首先要满足ti Tk 王 7 （ 6）从第i 1个车站开入的时间按从小到大进行排序有t1 ', t2 '，当两个时间段可插车时，应满足t；-Tk'_7 （ 7）其中Tk=Tk，Si_ （ 8）/ V6设定在两个相邻站点间已经运行的客车数量

7、为Gi，则相邻站点可插入货车数量满足Mi': G5: 7 （9）故整理得出数学模型为M =minmaxCMM2,，Mn 卩 （10）ti 5 一7ti' f 7s.t心呀/ V6M i' :G 5: 71.2模型求解(11)1.2.1数据整理通过下载“列车运行时刻软件”查找途径济南至徐州线路上站点的列车运行时刻下行方 向以济南到泰山的列车运行情况为例：表1济南到泰山插车情况济南到泰山距离为71公里，若插入货车，则历时71/70约为60分钟车次济南发时插车的最小时间泰山发时插车到站的最小时间插车运行时间可插货车数（辆）K67/K700:0700:1401:0301:100

8、0:5602042/204301:4301:5002:5202:5901:0942130/213102:0402:1103:0403:1101:009K371/K37403:1603:1304:1204:1901:065K10703:4603:5304:4204:4900:560K10105:0105:0806:1306:2301:1264921/492405:4005:4706:3606:4300:560K5105:5306:0006:5006:5700:5701227/123006:0706:1407:0307:1000:560K187/K19006:1706:2407:1307:2000

9、:5604941/494406:2106:2807:2107:2801:0061345/134806:5607:0307:5308:0000:590K55/K5807:3007:2708:2608:3301:06121469/147211:3911:4612:3512:4200:560N461/N46412:5112:5813:5113:5801:033108513:1013:1714:0714:1400:570T159/T16213:2913:3614:1714:2400:4801033/103613:3813:4514:3314:4000:550K172/K173A13:5013:5714

10、:5014:5701:003K172/K173B13:5013:5714:5014:5701:0012K75/K7814:0914:1615:0515:1200:560K4515:5716:0416:5216:5900:5502581/258416:4316:5017:3917:4600:5601341/134417:2717:3418:2318:3000:5602555/255819:4419:5120:5020:5701:063147720:0620:1321:0221:0900:560K293/K29620:2820:3521:2921:3601:0110146121:3221:3922

11、:2922:3600:5702032/203321:4321:5022:5423:0101:115142522:1522:2223:1223:1900:570将24小时可插货车数相加，则得济南至泰山两站点之间可插货车为78辆。上行方向以徐州到枣州列车运行情况为例：表2徐州到枣州插车情况徐州到枣州的距离为 67公里，若插入货车，则历时约为57分钟车次徐州发时插车的最小时间枣州发时插车到枣州站的最小时刻插车运行时间可插货车数（辆）146201:5001:5703:1103:1801:18182129/213202:5303:0003:4003:4700:470T17803:3603:4304:18

12、04:2500:4201342/134305:2205:2906:0806:1500:4602582/258306:5307:0007:3907:4600:4601470/147109:3009:3710:1710:2300:460K171/K174A11:2511:3212:1112:1800:460K171/K174B11:2511:3212:1112:1800:4601228/122911:3511:4212:2212:2900:4701034/103512:3312:4013:1913:2600:460490813:0613:1313:5314:0000:470K1618:2818:3

13、519:1419:2100:4604942/494318:3818:4519:2519:3200:470108619:0119:0819:4819:5500:470K10819:4219:4920:2820:3500:460K206/K20720:0120:0820:4720:5400:460147820:0920:1620:5521:0200:460K256/K25720:5921:0621:4521:5200:4602556/255721:3121:3822:1922:2600:480将24小时可插货车数相加，则得徐州到枣州两站点之间可插货车为18辆。1.2.2 求解利用Excel电子表格

14、，解出各个期间段的可插货车最大量M；分别为：表3下行方向各相邻站点可插入货车数济南至泰 山泰山至磁窑磁窑至兖州兖州至邹城邹城至腾州腾州至 枣庄西枣庄西 至徐州78辆72辆74辆84辆56辆50辆57辆表4上行方向各相邻站点可插入货车数徐州至枣枣庄西腾州至邹城至兖州至磁窑至泰山至庄西至腾州邹城兖州磁窑泰山济南18辆23辆27辆39辆26辆35辆37辆则由最优化模型解得：下行线可插货车最多为50辆，上行线可插货车最多为18辆，则共可插入68辆货车。1.3列车运行图利用Matlab作出列车运行图Step1、将时间、距离进行转换，时间以分钟计算、距离以公里计算；Step2、作出 第i站与第i 1站 之

15、间可插货车运行T S图；Step3、当i =i 1时，转到第二步；Step4、济南至徐州站点遍历完全后，停止。徐州到济南安排货车列车运行图图一济南至徐州列车运行图2临时客车时刻表及运行图的制定要增开的临时客车要满足以下三个条件：（1）增开的临时客车与原有的客车之间没有相互追及的问题（2 ）增开的临时客车之间不能有相互追及的问题（3 ）要尽量使得新增的临时客车对已有的货车影响最小对临时客车和货车而言，我们采用“提高正点率”来刻画增开临时客车所造成的影响程 度。提高正点率为目标，使调整后的各次列车充分贴近预定时刻， 尽快恢复列车的正点运行, 这是列车运行调整过程中通常追求的目标。由 参考文献，该函

16、数可描述为i-yo"0);y+E 丿 zj =mjkWS(X：-X：o)2+(Y；Yj：)2tJj(12)l l x k Yk考虑到列车运行晚点才需调整，即:X、 y：、Xjk、Yjk 比：、k '丛；Xo、y。、j0、 j0 的值要大,且x：0、y：0、Xjko、Yjk对于某一条线路上的调度来说是常数，所以上述目标可转化为min f =迟疋x：I X i =1 _(13)对一定类别的列车而言，其区间运行时分是常数，故可推导出上式的等价表达式m0(14)minf 八 ' dj 亠二二 D：I X i dk 3S j dm J为了增开临时列车，则必须避免由此产生的区间、

17、站线以及最小间隔时间的冲突，但是由题意可知，客车运行时间不能进行调整，因此只能对货车做出调整，同时做出如下的假设：待调列车在每一车站都可能停车避免各种冲突。在上述假设下，各种最小间隔时间都需要添加一个起停车附加时分t起停。这样，一方面保证了列车运行绝对满足间隔时间要求；另一方面起停车附加时分 t起停的数值较小， 对临时列车以及货车的调整给予了方便。综上所述，为了得到待调列车的相互关系和相互位置，可用如下模型描述m0(15)minf = ： d- < : D；LX i 4kWS j :mJ'（y： -x；j2 兰伍d+严）2 k,ix“z（y；-x）2严）2 k,iwx,iZ（y：

18、 -y：l）2 ni2 k,iX,iwzlk 2i 12st<（Y -XiJL） £（ld+t ） k,|ES,iZ （ 16）"XitrzS+tJ2 k,l EX,iEZlk 22（Y Yhl） >l k,|EX,iEZlk 2i 12（Xi 二-Xi" -（id t ） k,L X,i Z对于客流增加时要增开的5对临时客车：北京-上海，北京-南京，天津-上海，北京合肥（有效区间为北京蚌埠），北京青岛（有效区间为北京济南），进行分析。发现其中有3对临时客车经过北京-天津；5对经过天津-济南；4对经过济南-蚌埠；3对经过蚌埠南京；2对经过南京上海。根据

19、上述模型，首先要去掉不能安排临时客车的区间，通过编程计算，分别求出了各段可以增开的临时客车的数量。表5北京上海：（下行）北京合肥：（下行）天津上海：（下行）到站 时刻始发站发车 时刻0北京20: 00到站 时刻始发站发车 时刻0北京19: 4222: 24天津22: 280天津22: 1022: 03天津22: 102: 10济南02: 2301 : 42济南02: 0001: 42济南02: 0003: 34泰山03: 4504: 16兖州04: 3004: 16兖州04: 3004: 43兖州04: 5105: 50南京06: 1205: 50南京06: 1205: 34蚌埠008: 42

20、上海008: 42上海0北京南京：（下行）北京青岛：（下行）到站 时刻始发站发车 时刻到站 时刻始发站发车 时刻0北京19: 500北京20: 1222: 12天津22: 2022: 15天津22: 2701: 52济南02: 1223: 18沧州23: 2603: 25泰山03: 3301 : 13德州01 : 2004: 25兖州04: 4002: 25济南006: 11南京03.列车晚点时调度策略的制定当某一列客车因故晚点，它必然会影响这一区间段后面很多列车的正常运行，列车调度员就要调整后续列车的运行状态，制订出新的列车时刻表，设调整起始时间为ts,调整时间长度为td，在t,ts+td内

21、在共有n列待调整列车，记为t1,tn； xly1分别表示t1在S的到达和出发时刻，若在 s站始发，则记x、-1，若列车在Sj站终到，则记i.yi- -1 ；为t'在s的停车标识变量，停车时值为1，通过时值为0； bt'表示t时刻t'占用Si到发线的标识变量，占用时为1,否则为0。对于t1，称进入调度区段的车站为其发站，记为离开调度区段的车站称为其到站，记为列车运行调整问题含有很多优化目标，而提高列车平均旅行速度和提高列车运行正点率是实际指挥中经常被使用的两个优化目标。提高列车运行平均旅行速度也就是减少列车通过本调度区段的时间， 此优化目标可用t'在发站的到达时刻x,与到站的出发时刻 yd1来计算,具体为yd1 - xf'(17)在上式中，如果为t1始发列车,则在发站取出发时刻y,计算；如果t1为终到列车，则在到站取到达时刻xd1计算。列车运行正点在运输统计中有明确规定，在此定义变量d 1为t'在到站sd 1运行正点发站与到站的到发时刻的函数。的标识变量，正点时值为1，否则值为0。：冷1是列车种类、 提高列车运行正点率也就是减少晚点