数学建模竞赛——列车调度的最大流与分解协调模型.doc

列车调度的最大流与分解协调模型胡晶 王凤娟 廖建华 指导教师：张清华【摘要】本文以济南至徐州段作为研究对象，采用规划模型确定最大货车插入量、列车时刻表及运行图等。在确定货车插入量时，建立最小最大值模型，在一定的约束条件下，利用网络系统的最大流问题解决两个相邻站点最多可插货车量，再取各相邻区间段可插货车最小值作为该段的可行插车数，通过Excel求解，最后得出下行线可插货车数为50辆，上行线可插货车数为18辆，并通过Matlab编程绘制了列车运行图。在制定临时客车时刻表时，采用“提高正点率”来刻画增开临时客车对货车所造成的影响程度，使调整后的各次列车充分贴近预定时刻，尽快恢复列车的正点运行，建立相应的线性规划模型，并得出了相应的列车时刻表和列车运行图。当列车晚点时需要进行列车调度，提高列车平均运行速度和提高列车运行正点率是本文使用的两个优化目标。【关键词】列车调度 线性规划 多目标优化 Matlab1 问题分析本题以济南至徐州区间段为研究对象，主要研究以下三方面的问题：最大货车插入量，临时列车时刻表及运行图，因故晚点时所进行的调度策略。求最大货车插入量时，要求相邻列车必须满足一定的时间间隔和空间间隔条件，即两相邻列车在区间运行时的时刻差与空间距离必须满足一定的约束条件，这是典型的在约束条件下的规划问题；制定临时客车时刻表时，要求不改变现行列车时刻表及尽量减少对货车的影响，此处关键是用一个指标来刻画临时客车对列车的影响，把不影响现行列车和对货车的影响最小作为目标来安排临时客车时刻表；当客车因故晚点进行调整时，要使得造成的影响最小，关键也是用一些指标来表示对列车造成的影响。2 基本假设（1）客车运行的让路原则是慢车让快车（2）列车在两个站点间是匀速运行的（3）忽略列车的长度，将其视为一质点，不影响运行路程（4）各站点可容纳停留的列车数量无限大，即在站点可以超车（5）同相行驶的列车间至少相隔7分钟才可以正常运行3 模型建立与求解1.最大插车量及列车运行图的确定1.1模型建立 列车有序运行：列车运行必须满足一定的时间间隔和空间间隔要求，即两列列车在区间运行的时刻差与空间距离必须满足一定的约束条件。由于不同类型列车具有不同的速度，通过所给数据总共有五种类型的列车，分别为直达（Z）、特快（T）、快速（K）、管道高速（N）、普快（数字）。根据所给数据，利用不同类型的列车所经过的总路程与其所花的总时间的比值得出不同类型列车的平均速度： （1）各类型列车的平均运行速度为： 一般情况下，货车的运行速度小于客车运行速度，故设定货车的平均运行速度为 列车运行调整问题是多目标优化问题，为研究其数学性质，下面以复线调度区段为研究对象首先建立最大网络流模型。假设某线路途经个车站，设为第1个站点和第个站点分别为始发站和终点站，其余各站称为中转站点。对于任意两相邻站点之间均存在最多安排的货车数目 （2）则此条铁路上最多可安排的货车数目为 （3）此时问题转化为求解各区间段的最大可插货车数目的最小值，建立优化模型 （4） 即 （5）约束条件：1.相继两列列车在两个相邻站点运行期间的时间间隔不得少于7分钟；2.货车与客车的运行总量比大约为；下面给出约束条件的数学表达式（以济南至天津为考虑范围），考虑沿下行方向的第个车站的插车情况，一个运行周期内共开出辆列车，第个车站与第个车站间距离为，设插车时间为，从第个车站开出的时间按从小到大进行排序有，当两个时间段可插车时，首先要满足 （6）从第个车站开入的时间按从小到大进行排序有，当两个时间段可插车时，应满足 （7）其中 （8）设定在两个相邻站点间已经运行的客车数量为，则相邻站点可插入货车数量满足 （9）故整理得出数学模型为 (10) (11)1.2 模型求解1.2.1数据整理通过下载“列车运行时刻软件”查找途径济南至徐州线路上站点的列车运行时刻下行方向以济南到泰山的列车运行情况为例：表1 济南到泰山插车情况 济南到泰山距离为71公里，若插入货车，则历时71/70约为60分钟车次 济南发时插车的最小时间 泰山发时插车到站的最小时间插车运行时间可插货车数（辆）K67/K700:0700:1401:0301:1000: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:5604941/494406:2106:2807:2107:2801:0061345/134806:5607:0307:5308:0000:590K55/K5807:3007:2708:2608:3301:0612 1469/147211:3911:4612:3512:4200:560 N461/N46412:5112:5813:5113:5801:033 108513:1013:1714:0714:1400:570 T159/T16213:2913:3614:1714:2400:480 1033/103613:3813:4514:3314:4000:550 K172/K173A13:5013:5714:5014:5701:003 K172/K173B13:5013:5714:5014:5701:0012 K75/K7814:0914:1615:0515:1200:560 K4515:5716:0416:5216:5900:550 2581/258416:4316:5017:3917:4600:560 1341/134417:2717:3418:2318:3000:560 2555/255819:4419:5120:5020:5701:063 147720:0620:1321:0221:0900:560 K293/K29620:2820:3521:2921:3601:0110 146121:3221:3922:2922:3600:570 2032/203321:4321:5022:5423:0101:115 142522:1522:2223:1223:1900:570将24小时可插货车数相加，则得济南至泰山两站点之间可插货车为78辆。上行方向以徐州到枣州列车运行情况为例：表2 徐州到枣州插车情况徐州到枣州的距离为67公里，若插入货车，则历时约为57分钟车次 徐州发时插车的最小时间 枣州发时插车到枣州站的最小时刻插车运行时间可插货车数（辆）146201:5001:5703:1103:1801:1818 2129/213202:5303:0003:4003:4700:470 T17803:3603:4304:1804:2500:420 1342/134305:2205:2906:0806:1500:460 2582/258306:5307:0007:3907:4600:460 1470/147109:3009:3710:1710:2300:460 K171/K174A11:2511:3212:1112:1800:460 K171/K174B11:2511:3212:1112:1800:460 1228/122911:3511:4212:2212:2900:470 1034/103512:3312:4013:1913:2600:460 490813:0613:1313:5314:0000:470 K1618:2818:3519:1419:2100:460 4942/494318:3818:4519:2519:3200:470 108619:0119:0819:4819:5500:470 K10819:4219:4920:2820:3500:460 K206/K20720:0120:0820:4720:5400:460 147820:0920:1620:5521:0200:460 K256/K25720:5921:0621:4521:5200:460 2556/255721:3121:3822:1922:2600:480 将24小时可插货车数相加，则得徐州到枣州两站点之间可插货车为18辆。1.2.2 求解利用Excel电子表格，解出各个期间段的可插货车最大量分别为：表3 下行方向各相邻站点可插入货车数济南至泰山泰山至磁窑磁窑至兖州兖州至邹城邹城至腾州腾州至枣庄西枣庄西至徐州78辆72辆74辆84辆56辆50辆57辆表4 上行方向各相邻站点可插入货车数徐州至枣庄西枣庄西至腾州腾州至邹城邹城至兖州兖州至磁窑磁窑至泰山泰山至济南18辆23辆27辆39辆26辆35辆37辆则由最优化模型解得：下行线可插货车最多为50辆，上行线可插货车最多为18辆，则共可插入68辆货车。1.3 列车运行图利用Matlab作出列车运行图Step1、将时间、距离进行转换，时间以分钟计算、距离以公里计算；Step2、作出之间可插货车运行TS图；Step3、当时，转到第二步；Step4、济南至徐州站点遍历完全后，停止。图一 济南至徐州列车运行图2. 临时客车时刻表及运行图的制定要增开的临时客车要满足以下三个条件：（1）增开的临时客车与原有的客车之间没有相互追及的问题（2）增开的临时客车之间不能有相互追及的问题（3）要尽量使得新增的临时客车对已有的货车影响最小对临时客车和货车而言，我们采用“提高正点率”来刻画增开临时客车所造成的影响程度。提高正点率为目标，使调整后的各次列车充分贴近预定时刻，尽快恢复列车的正点运行，这是列车运行调整过程中通常追求的目标。由，该函数可描述为 (12)考虑到列车运行晚点才需调整，即：、比、的值要大，且、对于某一条线路上的调度来说是常数，所以上述目标可转化为 (13)对一定类别的列车而言，其区间运行时分是常数，故可推导出上式的等价表达式 (14)为了增开临时列车，则必须避免由此产生的区间、站线以及最小间隔时间的冲突，但是由题意可知，客车运行时间不能进行调整，因此只能对货车做出调整，同时做出如下的假设：待调列车在每一车站都可能停车避免各种冲突。在上述假设下，各种最小间隔时间都需要添加一个起停车附加时分起停。这样，一方面保证了列车运行绝对满足间隔时间要求；另一方面起停车附加时分起停的数值较小，对临时列车以及货车的调整给予了方便。综上所述，为了得到待调列车的相互关系和相互位置，可用如下模型描述 （15） （16）对于客流增加时要增开的5对临时客车：北京上海，北京南京，天津上海，北京合肥（有效区间为北京蚌埠），北京青岛（有效区间为北京济南），进行分析。发现其中有3对临时客车经过北京天津；5对经过天津济南；4对经过济南蚌埠；3对经过蚌埠南京；2对经过南京上海。根据上述模型，首先要去掉不能安排临时客车的区间，通过编程计算，分别求出了各段可以增开的临时客车的数量。表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上海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.列车晚点时调度策略的制定当某一列客车因故晚点，它必然会影响这一区间段后面很多列车的正常运行，列车调度员就要调整后续列车的运行状态，制订出新的列车时刻表，设调整起始时间为，调整时间长度为，在内在共有列待调整列车，记为分别表示在的到达和出发时刻，若在站始发，则记，若列车在站终到，则记；为在的停车标识变量，停车时值为1，通过时值为0；表示时刻占用到发线的标识变量，占用时为1，否则为0。对于，称进入调度区段的车站为其发站，记为，离开调度区段的车站称为其到站，记为。列车运行调整问题含有很多优化目标，而提高列车平均旅行速度和提高列车运行正点率是实际指挥中经常被使用的两个优化目标。提高列车运行平均旅行速度也就是减少列车通过本调度区段的时间，此优化目标可用在发站的到达时刻与到站的出发时刻来计算，具体为 （17）在上式中，如果为始发列车，则在发站取出发时刻计算；如果为终到列车，则在到站取到达时刻计算。列车运行正点在运输统计中有明确规定，在此定义变量为在到站运行正点的标识变量，正点时值为1，否则值为0。是列车种类、发站与到站的到发时刻的函数。提高列车运行正点率也就是减少晚点列车数，此优化目标可以表示为 （18）计算步骤：求解多目标优化列车运行调整问题的分解协调计算模型的计算过程如下所示