小议列车调度的最大流与分解协调模型

导语：小议列车调度的最大流与分解协调模型一文来源于网友上传，不代表本站观点，若需要原创文章可咨询客服老师，欢迎参考。

【摘要】本文以济南至徐州段作为研究对象，采用规划模型确定最大货车插入量、列车时刻表及运行图等。在确定货车插入量时，建立最小最大值模型，在一定的约束条件下，利用网络系统的最大流问题解决两个相邻站点最多可插货车量，再取各相邻区间段可插货车最小值作为该段的可行插车数，通过Excel求解，最后得出下行线可插货车数为50辆，上行线可插货车数为18辆，并通过Matlab编程绘制了列车运行图。

在制定临时客车时刻表时，采用“提高正点率”来刻画增开临时客车对货车所造成的影响程度，使调整后的各次列车充分贴近预定时刻，尽快恢复列车的正点运行，建立相应的线性规划模型，并得出了相应的列车时刻表和列车运行图。

当列车晚点时需要进行列车调度，提高列车平均运行速度和提高列车运行正点率是本文使用的两个优化目标。

【关键词】列车调度线性规划多目标优化Matlab

1问题分析

本题以济南至徐州区间段为研究对象，主要研究以下三方面的问题：最大货车插入量，临时列车时刻表及运行图，因故晚点时所进行的调度策略。求最大货车插入量时，要求相邻列车必须满足一定的时间间隔和空间间隔条件，即两相邻列车在区间运行时的时刻差与空间距离必须满足一定的约束条件，这是典型的在约束条件下的规划问题；制定临时客车时刻表时，要求不改变现行列车时刻表及尽量减少对货车的影响，此处关键是用一个指标来刻画临时客车对列车的影响，把不影响现行列车和对货车的影响最小作为目标来安排临时客车时刻表；当客车因故晚点进行调整时，要使得造成的影响最小，关键也是用一些指标来表示对列车造成的影响。

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:560

2042/204301:4301:5002:5202:5901:094

2130/213102:0402:1103:0403:1101:009

K371/K37403:1603:1304:1204:1901:065

K10703:4603:5304:4204:4900:560

K10105:0105:0806:1306:2301:126

4921/492405:4005:4706:3606:4300:560

K5105:5306:0006:5006:5700:570

1227/123006:0706:1407:0307:1000:560

K187/K19006:1706:2407:1307:2000:560

4941/494406:2106:2807:2107:2801:006

1345/134806:5607:0307:5308:0000:590

K55/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、作出之间可插货车运行T－S图；

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：10

22：03天津22：102：10济南02：2301：42济南02：00

01：42济南02：0003：34泰山03：4504：16兖州04：30

04：16兖州04：3004：43兖州04：5105：50南京06：12

05：50南京06：1205：34蚌埠008：42上海0

08：42上海0

北京――南京：（下行）北京――青岛：（下行）

到站

时刻始发站发车

时刻到站

时刻始发站发车

时刻

0北京19：500北京20：12

22：12天津22：2022：15天津22：27

01：52济南02：1223：18沧州23：26

03：25泰山03：3301：13德州01：20

04：25兖州04：4002：25济南0

06：11南京0

3.列车晚点时调度策略的制定

当某一列客车因故晚点，它必然会影响这一区间段后面很多列车的正常运行，列车调度员就要调整后续列车的运行状态，制订出新的列车时刻表，设调整起始时间为，调整时间长度为，在内在共有列待调整列车，记为分别表示在的到达和出发时刻，若在站始发，则记，若列车在站终到，则记；为在的停车标识变量，停车时值为1，通过时值为0；表示时刻占用到发线的标识变量，占用时为1，否则为0。对于，称进入调度区段的车站为其发站，记为，离开调度区段的车站称为其到站，记为。

列车运行调整问题含有很多优化目标，而提高列车平均旅行速度和提高列车运行正点率是实际指挥中经常被使用的两个优化目标。提高列车运行平均旅行速度也就是减少列车通过本调度区段的时间，此优化目标可用在发站的到达时刻与到站的出发时刻来计算，具体为（17）

在上式中，如果为始发列车，则在发站取出发时刻计算；如果为终到列车，则在到站取到达时刻计算。

列车运行正点在运输统计中有明确规定，在此定义变量为在到站运行正点的标识变量，正点时值为1，否则值为0。是列车种类、发站与到站的到发时刻的函数。提高列车运行正点率也就是减少晚点列车数，此优化目标可以表示为（18）

计算步骤：

求解多目标优化列车运行调整问题的分解协调计算模型的计算过程如下所示：

第1步：确定调整起始时间和时间跨度。

第2步：搜索调整时间范围内的列车，确定待调整列车集。

第3步：复制待调整列车集内的列车时刻表，将复制后的数据作为备份。

第4步：协调分组计算，调用列车分组函数，将待调整列车集分为优先级从高至低的个层次，也就是子调整列车集，记为。

第5步：目标设定计算，根据每组列车的运行特性和运行要求，指定每组列车的优化目标，构成个子调整问题，分别记为。

第6步：优化计算，按优先级从高至低顺序依次求解子问题，求解时首先判断子调整问题的类型，然后选择相应的求解方法，每次计算完毕后都记录本组列车对各种资源的占用。

第7步：结果还原，依次从占用链表中取出列车时刻，形成统一的列车时刻表，整合为原问题的解!分解协调优化计算结束。

4模型评价及推广

模型评价

1、此模型将多目标规划转化为单目标规划，使得模型简洁易懂。

2、对于列车的调度问题的研究，我们考虑到两个目标：提高正点率和总旅行时间节省。这与实际生活很相近。

3、第一问中我们计算出的货车数与当前客车数之比符合的关系，由此可知我们所建模型具有一定的实际应用效果。

4、因为题中涉及到的列车时刻表很多，数据整理量相对困难，我们所建模型难免会缺少精确性。

模型推广

该模型利用插值法进行分析与求解，计算结果与实际列车运行结果吻合的很好，适用于一般的列车调度问题。可将此模型推广到各条线路，同样适用于其它线路。本模型只是针对京沪线路进行分析，对其它线路的研究方法也可用此模型。