火车站股道列检问题

2007年第四届苏北数学建模联赛题目

我国第六次铁路大提速已经于2007年4月18日正式展开。第六次铁路大提速在京哈、京沪、京广、京九、陇海、浙赣、兰新、广深、胶济等干线展开，列车运行最高时速达200公里，其中京哈、京广、京沪、胶济线部分区段时速将达到250公里。这次提速受到了大家的广泛关注，也为人们的出行带来了更大的方便。随着列车速度的提高，如何保证列车的安全运行也成了一个比较重大的问题。

徐州火车站（以下简称徐州站）作为一个非常重要的铁路枢纽，面临着更多的工作。徐州站共有5个站台，10个股道。下图是徐州站的站台和股道（即列车所走的轨道）的分布图。

图1 徐州火车站站台和股道分布示意图

列车提速后，徐州站的旅客列车的到发情况见附表一。其中，“到”表示列车到达徐州站的时间，“发”表示列车离开徐州站的时间，“股道”表示列车在站内所经过的股道，“停站时分”表示列车在徐州站停留的时间（单位：分钟）。

利用上面的信息，我们对以下两个问题进行研究。一般来讲，火车站是分白班和晚班进行工作的。为了简化问题，我们只对上午八点以后（包含八点）和晚上七点以前到达徐州站的列车进行分析。

问题一、股道的合理安排

1、研究各股道繁忙程度。

2、除了股道6（股道6主要是直通车通过，且该股道上的列车没有旅客上下车、列检等需求）外，如果要使各股道的繁忙程度大致相同，而且空闲时间尽量均衡，如何调整各车次停留的股道。注意，由于股道6与站台没有直接相连，对于有旅客上下车的列车是不能停留在第6股道的。

问题二、旅客列车的列检问题

徐州站的客列检是一项十分重要的工作，对于保证列车的正常运行和旅客安全等有着极其重要的作用。徐州站的客列检工作量大，对参加列检的工作人员要求高。

为了保证客列检工作的正常进行，对客列检进行合理的分工，对保障列检作业过程的安全和工作人员的积极性有一定的作用。

现对徐州站客列检工作简介如下：

I、列车的简要分类

根据列检工作的要求，我们对列车作如下分类：始发车，就是以徐州站为始发站的列车；终到车，就是以徐州站为终点站的车；其余的为通过车。

II、需要列检的车满足的条件

根据客列检技术检查作业标准：终到车不需要列检；始发车一般在开出徐州站前15分钟进行列检。

对于通过车，在站时间小于6分钟的不需要列检；在站时间为6～20分钟的，列车在站期间，全部需要列检；在站时间大于20分钟的，列车进站后10分钟和列车出站前10分钟进行列检。

在对列车进行列检时，必须在列车上悬挂号志（一般为旗子），来表示列车正在进行列检。

III、列检工作人员的相关作业要求

①一般来说，列检人员需要在列车进站前3分钟到达相应的股道等待列车的到达；列检人员需要在列车完全离开车站后离开作业股道。

②当某个列检作业队需要列检的下一列车30分钟后才会到达时，作业队可以回到股道两端的休息室等待，此时，作业队对下一列车进行作业时不需要胯股道。

③列检工作按作业队进行，每列需要列检的列车由一个作业队负责，每个作业队在对某一列车进行列检完成后，才能对另外的列车进行列检。

对于徐州站的列检工作，我们考虑安排5个作业队进行。

1、由于作业队在进行跨股道作业时，会有危险存在，故请你考虑，如何给5个作业队进行分工，才能使得每个作业队跨股道数目尽量地少。

2、如何对5个作业队进行分工，才能使得每个作业队跨股道数目尽量地少，且各个作业队的工作量（即列检的列车的数目）基本一致。

3、（1）在满足2中的条件的前提下，如何使得各个作业队的繁忙程度基本相同（即不会出现某作业队在某时间段内没有进行任何工作，而其他作业队进行了很多列车的列检工作）；

（2）在满足2中的条件的前提下，如何给各个作业队安排出时间吃午饭，且吃饭时间尽量与人们的正常吃午饭时间一致（如11：00－13：00，当然可以做适当的提前或延后）。要求各个作业队的吃饭时间不小于30分钟。请给出各个作业队的具体吃饭时间。

如果你认为5个作业队不能在满足相关作业要求的前提下，完成相关列车的列检，请给出充足的理由，并考虑安排更多的队进行列检工作，解决上面的几个问题；或者考虑通过对个别列车（主要是普客）的进站时间进行适当的延迟后（则出站时间需要作相应的延迟），5个作业队是否能完成相关列车的列检工作（可以认为对普客作出的进站时间延迟是由列车的晚点引起的）。

特别约定（为了简化问题，该约定根据实际情况进行了适量的简化）：

1、 始发车在出站前30分钟进入相应股道；终到车到站后，大概在股道停留20分钟后，离开相应股道。

2、 同一股道上不能同时有两列车停留。要求同一股道上停留的两列车之间最小时间间隔为10分钟（即若安排某列车进入某股道，必须保证该股道在列车进站前10分钟已经没有列车停留），当然时间间隔越大，越安全。

3、 若需要跨股道作业，跨股道需要的时间按以下方案处理：

i、在某站台两侧的股道，如股道2和股道3，在2站台的两侧，则作业队列检完股道2上的列车后，可以直接转身去等待股道3上列车的到来。可设从股道2到股道3需要1分钟。其他类似情况可作同样的处理。

ii、如果某股道上没有车（为了安全起见，要求在5分钟内该股道上不会有列车到达，否则，则不能跨越该股道）可以直接跨越，设跨越一个股道需要的时间为1分钟。

iii、若股道上有列车，且有号志（即在列检），列检人员可以从列车下面过去，直接跨越股道，认为跨越1个股道需要的时间为1分钟。

iv、若中间股道上有列车（没有号志）不可以跨越股道，则作业队必须先到站台两端再到达相应股道。可以设若两股道数之差小于3时，则需要6分钟到达相应的位置。若两股道数之间的差大于或等于3，则需要8分钟到达相应位置。

【摘要】：本文通过建立0-1整数规划模型、目标规划模型研究解决列车股道与列检工作的统筹安排任务。

第一问使用“各股道车次总数”及“各股道列车停留总时间”表示各股道繁忙程度，在模型Ⅰ(ⅰ)中给出具体表达式。

由于列车到站时间一定，股道安排属于NP类组合优化范畴，通过建立0-1非线性整数规划模型，以股道繁忙度尽量均衡且空闲时间尽量相同为目标，使用Lingo软件求解。NP类计算复杂度简化：本文通过分析各车次的进展时间关系，建立最小安全距集(见4.2.1)降低规划复杂度，并转化空闲时间到约束中求解，最终得到局部最优解见5.2.3。

列检队的安排方案本文通过目标规划模型表述，三层目标分别为各列检队跨股道数目尽量少，各列检队工作量基本一致，各列检队繁忙程度基本一致；在跨股道时间、条件限制与跨站点时间限制下利用计算机仿真求解（方案见6.4方案一），还考虑了交换目标层二、三的情况下给出了两种不同优势的安排方案（方案见6.4方案二），并对其二者可行性进行了分析。

在徐州站现行列车时刻方案下，安排人性化方案比较方便，本文通过建立启发式算法，给出列检安排变化程度较小的具体吃饭时间与列检调整方案。

五组列检队基本能够满足现工作量需求，但不能达到最优的列检空闲段非常均衡的目的，本文最后通过改变个别“普客”的到站与离站时间，给出了最终列检方案。

关键字： 目标规划 NP类组合优化 Matlab仿真

下载题目： 【Download】

下载原稿： 【Download】

作者保留一切权利，转帖请注明出处，不得用于商业用途。