山东科技大学本科毕业设计（论文）

为了充分发挥该铁路线的货运能力，需要排定一张最优的货车运行时刻表，即要求每天发出最多的货运列车且不干扰已排定的客运列车。 4.1.2 问题分析

求解这个问题较为复杂，但可将其转化为网络最大流问题。 （1）设A、B两市及其间的车站共P个。每个车站有nk条岔道（k=1,2,3…P）,可停放nk列列车。从第k站到第k+1站的行车时间货车为tk个小时，客车为tk' 个小时。

设?k为火车到达第k站并从第k站开出的时刻 设?k为客车到达第k站并从第k站开出的时刻 设?k?1为货车到达第k+1站并从第k+1站开出的时刻 设?k?1为客车到达第k+1站并从第k+1站开出的时刻 于是显然有?k?1??k?tk ?k'?1??k'?tk'

（2）若??k,?k?1?与?',?'k?1有公共部分，则称??k,?k?1?与?',?'k?1是相交的，否则成为不相交的。显然有当只??k,?k?1?与?',?'k?1相交情况下客车才有可能（并非必然）在第k站与地k+1站间追上货车。

''（3）在??k,?k?1?与?',?'k?1相交情况下，?k，?k?1，?k，?k?1间的相交关系

''????????可由图4.1.1所示：

20

山东科技大学本科毕业设计（论文）

图4.11

情况Ⅵ为途中货车追上了客车故不符合题意。情况Ⅰ与情况Ⅱ中在第k站与第k+1站间不发生在途中追上货车。而在情况Ⅲ中必发生在第k站与第k+1

21

山东科技大学本科毕业设计（论文）

站间客车在途中追上货车。 于是有下列结论：

若??'k,?'k?1?在??k,?k?1?内，即?'k??k及?'k?1??k?1，则在第k站与第k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。 （4）绘制网络图

用（k，?k）表示第k站处于时刻?k的状态，如在?k=2.3在（k，2.6），（k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）及（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。

22

山东科技大学本科毕业设计（论文）

图4.1.2

上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。 4.1.3 问题求解

以货运列车的运行时间为基础绘制网络图。

（1）令?A,?B,?C,?D为火车从某站开出或到达某站的时刻。依题意，若不受客车干扰则：

23

山东科技大学本科毕业设计（论文）

?A=0:00,2:00,4:00…… ?B=5:00,7:00,9:00…… ?C=9:00,11:00,13:00……

?D=16:00,18:00,20:00……

于是货车在相邻两站的运行时间为（若不受客车干扰）：

??A,?B?:?0,5?,?2,7?,?4,9?,?6,11?,?8,13?,?10,15?,?12,17?,?14,19?,?16,21?,?18,23?,?20,15?,?22,27???(25点即翌日1点，余类推)

??B,?C?:?5,9?,?7,11?,?9,13?,?11,15?,?13,17?,?15,19?,?17,21?,?19,23?,?21,25?,?23,27?,?25,29?,?27,31??

??C,?D?:?9,6?,?11,18?,?13,20?,?15,22?,?17,24?,?19,26?,?21,28?,?23,30?,?25,32?,?27,34?,?29,36?,?3??(2)令?A,?B,?C,?D为客车从某站开出或到达某站的时刻，依题意：

''''?A'=2:00,7:00,12:00,17:00,22:00 ?B'=5:00,10:00,15:00,20:00,25:00(即1:00) ?C'=7:00,12:00,17:00,22:00,27:00（即3:00）

?D'=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）

于是客车在相邻两站之间的运行时间为：

??

'A,?B:?2:00,5:00?,?7:00,10:00?,?12:00,15:00?,?17:00,20:00?,?22:00,25:00?'???

'B,?C:?5:00,7:00?,?10:00,12:00?,?15:00,17:00?,?20:00,22:00?,?25:00,27:00??24