编组站车辆调度问题研究

刘红英 娄正良

（北京全路通信信号研究设计院有限公司，北京 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)。

2.2 MAS在管理系统设计与实现中的应用[2]

RVSP问题涉及面宽，关系错综复杂。很难用算法来一次性解决所有问题。在本文中，首先尝试将问题分解成一个个的个体。通过分层，分批地解决个体问题，进而解决全局的问题。

对编组站业务的分析，以仿真的方式，采用多A gen t[3]系统[4]仿真来组织和实现编组站计划的自动编排、铺画和动态调整。

系统通过各个A gen t模拟编组站现场执行情况，迭代调整各项作业优先次序和使用资源，不断优化目标值，最后生成的任务执行次序和资源使用状况可以通过技术作业图表显示和调整。

3 实践和结论

目前基于M A S仿真的启发式算法解决的RVSP问题的系统在成都北编组站正式运行，运行效果良好。系统通过单个智能A gen t的相对简单的决策和调整，从整体上实现整个RVSP问题的解决。具有以下特点。

1）动态性

由于在建模的过程中充分考虑了采样区间的微分和移动的性能。因此，系统能够根据车站作业实时执行的过程和用户参与实时调整采样区间[t0，tE]，并且在新的采样区间上重新优化，迭代调整。从而使系统动态地根据实际作业进度和用户参与调整后继的作业次序和资源分配。

2）实时性

由于成都北C IPS系统中有计划直接指挥下层的控制系统，因此需要有很强的实时性。由于前述的动态性，使得实时性具有可能。

因为采用A gen t迭代循环仿真车站作业，因此无法保证能够实时地给出最优解。因此设计的Agent会保证每一个解都是可行解，可以执行的解。在时间允许的情况下，再用后继的较优解来替代前面的解。

3）可控性

系统通过多种方式自动求解，将结果反映给客户，视觉上的有技术作业图表、列车表、毛玻璃、钩计划和站场表示等，听觉上语音提示和语音报警等。用户很容易得到系统后面的任务进展情况。

用户也可以很容易操纵后继的任务，系统会根据用户的参与动态地重新计算、优化。

4）优化性

系统在设计的时候充分考虑到系统的可扩展性和可优化型。

可以通过增加、变换A gen t模具的启发学习的算法来实现业务的变迁和增添新业务。比如在编组选择尾部调机时，目前采用非均衡的尾部调机算法。可以根据需要采用均衡的尾部调机算法来替代当前算法而实现车站的特殊要求。

随着系统运行时间的增长，积累历史数据。通过对历史数据的挖掘和分析来优化系统运行的参数矩阵，提高系统的优化速度和性能，从而实现系统的离线自学习功能。

[1]教材编写组．运筹学[M]．3版．北京：清华大学出版社，2005.

[2]娄正良．编组站CIPS系统的调度计划管理[J]．铁路通信信号工程技术，2006（4）：8-9

[3]陈森发．复杂系统建模理论和方法[M]．南京：东南大学出版社，2005.

[4]冯珊，唐超，闵君，等．用于复杂系统建模与仿真的面向智能体技术[J]．管理科学学报，1999，2（2）：71-76.