编组站车辆调度问题研究

2011-05-09刘红英娄正良

铁路通信信号工程技术 2011年4期

刘红英娄正良

（北京全路通信信号研究设计院有限公司，北京 100073）

编组站的车辆调度问题可以描述为对于一系列到达列车，组织合格的出发列车，在满足一定的约束条件下（比如线路资源，调机资源，编挂条件等），力争实现一定的目标（如实现编组站最大的吞吐量，调机线路等资源占用最少等），为了和通常的车辆调度问题(VSP)[1]相区别，在这里称之为铁路车辆调度问题(RVSP)。

1 RVSP数学模型

1.1 RVSP目标

编组站比较重要的指标是中时和停时，通常编组站的主要任务是车辆的中转，而装卸车辆只是比较辅助的业务。因此比较注重中时，在本文的RVSP模型中，将只考虑中时。

假设采样区间的开始时间是t0，结束时间是tE。

以一个二元组来描述车辆

公式(1)中得V表示车辆，ts表示该车辆的到达时间，te表示该车辆的离去时间。定义下列集合：

公式(2)中S1采样区间的开始时刻t0车站内有m辆站存车。S2表示采样区间[t0，tE]在内陆续到达的车辆n辆。S3表示在采样区间[t0，tE]陆续发出l辆车。

很显然这个集合满足公式(3)的关系

则目前需要上报的班中时ΔT′按下式计算，采样区间为一个班。

公式(4)中的ΔT′主要是根据出发车辆计算的中时。该指标不适合作为RVSP问题的优化目标。因为ΔT′采用较长时间的采样区间长度（至少一个班）是有意义的，基本上也能反映整个编组站的车辆中转时间。但可微的性能比较差，当取样长度不是一个班，而是在逐渐缩小或者取样区间移动时，该值波动比较大。比如某个取样长度内没有发车，则该取样长度的中时为零。

采用下式来计算该采样区间的中时

采用公式(5)可以比较准确反映各个采用区间的中时。同时也可以在动态过程中计算中时。

在上面的公式中，每辆车的ts是已知的。采样区间[t0，tE]是设定的，也可以认为是已知的。但是出发车的辆数l和每辆车的te是未知的。

1.2 RVSP资源约束

在RVSP中重点考虑两类资源，一类是线路资源，另一类是机车资源。一辆车从到达到出发，需要经历接车、到达作业、解体、集结、编组、发车等诸多环节，有的车辆还需要重复解体，有些还需要交流，有些还需要特殊调车处理（比如有些车辆不能过峰）。还有些车辆不需要解体集结编组，直接发车。一辆车从到达，到发车，需要一系列的作业，这些作业可以用一系列的时间点来刻画。因此将上述的二元组表达车辆用下式来表示。

根据公式(6)的车辆表达定义可以用如下集合来表示每一辆车的各个作业的时间区间。

车辆的这些时间区间肯定都需要占用线路资源，但有些区间不需要占用调机资源的，比如车辆在集结时。

因此定义集合

在占用线路或使用调车资源时，是以整个车组为单位占用的。定义车组集合

很显然，该车组是和车辆的时间片有关系的。因为车辆在不同的时间，属于不同的车组。不同的车辆，如果在某个时间片属于同一个车组，则其时间片相同。如下式所示：假设Sam表示时间片（ta，ta+1）的某个车组

上式中的时间片没有涉及线路、调机，是因为车辆的某一个时间片肯定只属于一个调机或线路。因此该车组所表示的时间片也只能和一条线路或调机相关。

每一条线路可以用车组占用的时间片来表示

对于线路存在如下约束，就是一条线路不可以同时被两个车组使用。即满足下面的两个约束

公式(12)中第一个公式表示线路在某个时间片中只能被一个车组占用。比如一条线路有一个车组时，不能再接车或作为机车转移使用。公式(12)第二个公式表示线路最多是满占用时间，比如在某个采样区间中，一条线路上的车组都在占用。则第二个公式取等号。

同样对于调机也可以用车组占用的时间片来表示

同样上面的公式表示机车在某个时间片中只能被一个车组占用。比如机车不可能同时解体两列车。

根据以上定义用下列的等式将线路资源和车辆作业联系起来。

LNUM表示编组站的所有线路资源的数量。上式表明所有的车辆在任何状态下都需要占用线路资源，包括车辆在机车上，也需要占用线路资源。

同样可以用下列等式说明车辆作业和调机资源的关系。

MNUM表示编组站的所有机车资源的数量。调机和线路不同，车辆只有需要移动时，才需要调机资源。而这些活动需要机车资源可以作为已知量输入。

实际上机车和线路自身会有一些时间片用于自身的活动。比如线路停用，那么该条线路在停用期间，是和车辆的时间片没有直接关系。机车也会有一些机车作业，如机车上油等作业。在RVSP模型中，也可以加上这些活动约束。在本文的数学建模中，忽略这些作业。但在实现时，没有忽略。

1.3 RVSP出发列车对车辆要求的约束

从编组站发出的列车首先要符合下达的阶段计划要求，另外还要符合编挂条件约束。这一点反映车辆的时间片序列上，有的车辆多，有的车辆少。另外，也是产生所有钩计划的约束条件。

在前面描述RVSP目标时，定义列车是一系列车辆的集合。但实际上车辆在列车上是有次序的。需要增加一个关系R来表达这种车辆在列车上的前后次序。

假定在给定的采样区间内发出w辆车。

所有出发列车的关系集合：

假定Ri表示附加在第i辆出发列车上的关系，第i辆车的编挂要求是Ψi，则Ri必须符合给定的编挂要求Ψi，即

每一列出发列车的编挂要求是已知的。而到达列车的关系是已知的。如何从已知的关系中进行拆分、组合成新的关系，并且新的关系满足编挂条件的约束。这是编组站所有活动的依据和根本目标。

目前没有将该目标作为RVSP的目标。因为该目标首先必须满足，其次它的弹性仅仅表现在满足编挂要求的前提下，选择一个比较好的关系。实际上是编组高质列车，减轻后继的车站作业负担，但这种弹性通常会和车站本身的中时相矛盾。因此在本文中不将它列为RVSP的目标。

1.4 数学模型

根据前面对目标和约束的讨论，RVSP的数学模型可以描述如下：假定给定的采样区间是[t0，tE]。

公式(20)中字符的含义参见前文。

实际上编组站的资源还包括一大类资源，即人力资源。在该模型中假设这类资源无穷大，不予考虑。

站形分布、车辆占线规则、调机使用规则、本务机接续、调度命令等也可以算作约束。该模型为了简化起见，也没有包含这些规则约束。

2 算法与实现

如果以车辆为单位，基本上一辆车进站后经过接车、到达作业、解体、集结、编组、发车这些作业。但不是每一辆车都是这样，有些需要重复解体，而有些可能需要站修。因此有些车辆可能会经历重复解体，交流等作业。

图1简单地表达接4辆车，发四辆车的经过。圆圈表示列车的作业节点(到、解、集、编、发)，黑色线条表示车辆流动的方向，虚线条表示机车使用接续，即因为使用机车资源而使这些节点发生次序关系。浅黑色线条表示峰位或正线使用接续。这些连接线中还不包括停车线，走行线等关系。

中间的黑色粗黑线表示到达列车和出发列车的车辆对应关系。实际上到达列车和出发列车的车辆是多对多的关系，一辆到达列车的车辆需要解体到多列出发列车中去，而一辆出发列车则是由多个到达列车解体形成的。如果忽略虚线、浅黑色线条，可以将上图看成是一个二部图。

实际上编组站不断有到达列车和出发列车。并且作业节点也远比图1所示的多。因此，所有的节点构成的图是比图1复杂得多的无始无终的图。RVSP的问题复杂性大，没有好的多项式算法。目前现状是在这个大问题下有很多子问题的算法。比如车辆选编算法，调机任务分配算法等。

2.1 技术作业图表铺画法

众所周知，运输问题的作业图表法是一种有效的标准算法。目前所有的手工编制计划的方式都是通过作业图表的铺画完成。

各种作业以图形的方式反映在图表上，比较直观。图2是成都北技术作业图表。各个站会因为站形和具体业务的差异而有所不同。图中横坐标是时间轴。纵向是机车和线路资源。在这张图表上比较直接地反映各项作业对线路和机车的占用。也可以间接地反映车辆流动方向。沿着技术作业图表铺画，可以自然地保证机车，线路分时复用，不重叠，即满足公式(15)和公式(16)。