基于图染色的铁路调车场调车问题研究

Research on Railway Shunting Problem Based on Graph Coloring

摘要: 本文主要研究铁路调车场调车问题。与已有研究相比，本文同时考虑了调车场的股道数量限制与股道容量限制，更加符合实际情况。首先，我们将带股道数量限制与股道容量限制的调车场调车问题转化为一种特殊的图染色问题。接着，为该问题设计了一种贪婪算法，并通过数值实验说明该算法适合于实际应用。

Abstract: This paper mainly studies the shunting problem of railway shunting yard. Compared with the existing research, this paper considers both the number limit and the capacity limit of the shearing yard, which is more in line with the actual situation. Firstly, we transform the shunting problem of the shunting yard with the limitation of the number of channels and the limitation of the capacity of channels into a special pattern dyeing problem. Then, a greedy algorithm is designed for this problem, and the numerical experiment shows that the algorithm is suitable for practical application.

1. 引言

1.1. 背景介绍

调车场在铁路网络系统中处于核心地位，其主要作用是解体进站列车以及将在站车辆按照编组计划重新编组成出发列车。目前我国铁路车站依靠人工经验编制的调度计划已不能完全保证车辆调度和编组的效率，当列车不均衡、密集到达、车辆目的地车站远多于车站股道数量时，很容易导致车辆滞留在车站，从而影响整个铁路系统的运输效率。因此，研究铁路车站多线股道车辆调度优化方法对于提升铁路货运运能，提高铁路经济效益具有重要意义。如何通过优化调度提升调车场车辆调度效率获得了广泛关注。

1.2. 相关工作

铁路股道车辆的调度仍是铁路货运的最大挑战之一，也是国内外学者研究的热点问题。铁路货物运输也是运筹学的经典应用领域，Nemani等 [1] 研究了铁路货物运输过程中的运输堵塞问题，该问题研究了最小成本铁路货运计划的形成。但在这个问题中，铁路股道车辆调度是在宏观层面上考虑的，即没有考虑车站内的车辆股道调度操作。运筹学方法应用在微观层面上的铁路股道车辆调度规划，其中实际的车辆移动和调度操作被考虑。文献 [2] [3] [4] 研究调车场股道的固定使用，一般用来作为实际车辆股道调度的基本准则。在以往铁路股道车辆调度的研究 [5] [6] [7] [8] 中很少考虑调车场股道的灵活使用对车辆调度的影响，但是如果调车场股道得不到灵活使用，车辆不能进行合理调度，可能会影响到发站车流的接续关系和车辆编组计划的按时实施。薛峰等 [9] 研究了配流和调车场股道调整使用的协同优化，但是模型中将目的地车站不同的车辆尽量溜放到不同的股道，这样可能会增加列车解体时车辆调度以及出站编组时的调度次数；同时，没有考虑车辆编组时在列车中的顺位等因素。马亮等 [10] 在动态分流的基础上，综合考虑调车场在站车辆状态、调车场股道容量和解编作业时序限制等，建立了阶段时间内调车场股道整数优化模型，并设计了启发式回溯算法。Boysen等 [11] 系统地研究了将进站货运列车的车辆分配给出站货运列车，使所选择的车辆截割的优先级值最大，并观察给定的列车能力，其中一个基本的决策任务是列车编组问题，优化目标是将调度运输利润最大化。

Futhner [12] 的方法是最古老的排序方法之一，该方法在不考虑车辆进站顺序的情况下，为出站的车辆序列构造分类表。随着时间的推移，类似的基于规则的重新安排车辆的方法被开发出来并应用于实践。德国Schweizer Bundesbahnen的运兵学研究组 [13] [14] 将基于规则的重新安排车辆的方法开发出来并应用于实践，其中最著名的是同步三角形，或几何图形。基于规则的启发式方法的优点是简单和透明，在不考虑车辆进站顺序的条件下，经验丰富的工作人员在通常情况下可以进行有效调度。Cicerone等 [14] 首先考虑了分流的概念。将研究重点放在分流场classifification problems (CP) (通常称为分类碗)中对列车编组和列车分类进行建模的分类问题，即研究将进站车辆分配给出站列车的方案。讨论CP的离线变体，其中所有相关信息都是已知的，并且不允车辆同时到达。在任何变体中，对于进站的车辆存在三种移动过程：从分类碗中的入站股道移动到分拣股道(i-t-move)；从分拣股道移动到出站股道(t-o-move)；从分拣股道移动到另一个分拣股道(t-t-moves)。如果车辆不允许t-t-move的调度，则为单级变体，否则为多阶段的变化。在此基础上，对不限制股道数量或容量的分类碗进行了研究。

随着人们对调度领域研究的持续深入，以及领域之间研究的相互联系交流，越来越多的数学理论被应用到不同的领域解决调度问题，其中的图染色算法就是代表之一。马建峰 [15] 给出了图上顶点染色，边染色的算法。其中边染色算法是一个非多项式时间的精确算法，顶点染色算法是一个多项式时间的近似算法，该算法的时间复杂性为O(n~3logn)，空间复杂性为O(n~3)的近似算法，它是由贪婪策略得到的。对于任意的图，该算法所用的期望颜色数为⌈log (n+1)⌋。元野等 [16] 研究针对零担物流货物配装调度优化环节，创建带冲突关系货物装箱问题的数学规划模型，将其转换成为顶点着色模型进行表示；针对上述问题模型，设计并实现基于贪心着色操作的两阶段启发式算法。王浩 [17] 研究核心是整车物流仓储中心中的道位优化调度问题，阐明了图着色模型以及其在调度优化方面存在的优势，把调度过程中的问题转换成为基于权重的图着色算法道位优化调度模型，并且通过实例数据计算结果的分析与比较，证明了该模型及思路是切实可行的。

通过对近年来国内外铁路股道车辆调度问题研究的总结可见，关于铁路股道车辆调度问题的模型一般以经济成本，或者股道数量作为优化目标。以经济成本和股道数量为优化目标的主要问题在于实现车辆在股道的调度和编组过程中，没有考虑车辆在车站股道内或股道间因调度次数所产生的费用，以及车辆在站停留等待调度编组所产生的费用。并且现有的方法一般不考虑车辆的进站顺序、不允车辆同时到达，所有的相关信息都是已知的，没有同时考虑车辆编组作业中车辆在列车中的顺序以及股道容量等因素，这与实际中的铁路股道车辆调度过程是有所差别的，同时结合图染色算法在调度领域的应用，为此本文以减少车辆在股道上的调度次数和车辆在站滞留时间作为优化目标，并设计了相应的基于图染色的贪婪算法来求解。

1.3. 本文贡献

本文对铁路调车场调车问题展开研究，主要工作包括：

1) 将带有股道数量与股道容量约束条件的调车场调车问题转化为二部图上的边染色问题。已有研究将调车场调车问题转化为图染色问题进行研究时，会假设可使用的股道数量是无限的，主要优化目标为使用尽可能少的股道数。而我们所考虑的问题中股道的数量与容量都有限制，更加符合实际情况。

2) 设计了关于上述图染色问题模型的贪婪算法，数值实验表明我们所设计的算法能够快速有效地求解上述模型，得到面向需求的铁路股道车辆调度优化方案，从而表明本文所提出的铁路股道车辆调度方法可以应用于实际的铁路股道车辆调度工作中。

本文主要内容安排如下：第二节建立了铁路股道车辆调度模型；第三节针对上述模型设计了基于图染色的贪婪算法并给出了相关算法的数值实验；第四节总结了本文的研究内容并指出了进一步的研究方向。

2. 模型

2.1. 问题背景

如图1所示，所有进站列车在到达场解体，解体后形成的车辆序列在股道的驼峰部分通过重力作用从峰顶溜放到调车场的股道上。之后车辆再在调车场股道上根据车辆编组计划进行编组操作，最后用调机牵引车组安装动力车头，操作结束后列车开行出站。铁路股道车辆调度的流程大致相同的，但是在不同铁路车站的调车场内存在不同的股道车辆调度基础操作模式。如果铁路股道一端是死角，则当车站内进行车辆调度时只能从股道的一侧进行车辆停入或取出的调度操作，这样的铁路股道调度操作模式称为堆栈。在这种调度操作模式下任何停在同一堆上的两辆车辆，如果没有进行额外的重新安排或调度操作，将会改变车辆在解体进站所生成的车辆序列中的顺序。如果停放在股道上的任何两辆车辆都保持着在解体进站所生成的车辆序列中的顺序，这是一个单向铁路股道，即列车解体后车辆在股道的一端进行溜放停入调度操作，在另一端进行编组取出调度操作，这样的铁路股道调度操作模式称为队列。在上述两种车辆股道调度操作下，车站股道对于车辆的停入和取出调度操作均只在股道的一侧进行，这样的铁路股道调度操作模式称为单进单出车辆调度模式，如图2所示。

根据实际中铁路车站股道的车辆调度操作流程和车辆在股道的调度模式，从中提取出本文所要解决的铁路股道车辆调度问题模型：在同时限制车站股道数量和股道容量的条件下，以队列的铁路股道车辆调度操作模式，根据车辆编组决定进站解体后的车辆溜放到哪一个股道，以减少车辆在股道间调度的次数为优化目标，实现车辆在股道上完成编组操作作业。

Figure 1. Schematic diagram of railway station track infrastructure

图1. 铁路车站股道基础设施简图

Figure 2. Diagram of single in single out scheduling mode

图2. 单进单出调度模式示意图

2.2. 调车场调车问题

模型主要参数如下所示：

T：铁路车站内股道的数量，且按照顺序依次代表股道的编号；

R：车站内股道的容量，每条股道的容量均相同；

c：列车上搭载车辆的数量 $0<c\le C$，所有列车搭载车辆的数量均为c；

d：到站车辆的目的地车站种类数量， $d\in N^{*}$ 且 $d>m$ ；

D：目的地车站集合 $D=\left\{1,2,\cdots ,d\right\}$，每个车辆有且只有一个目的地车站；

$d_j$ ：表示车辆j的目的地车站， $d_j\in D$ ；

V：车辆编组计划

模型的已知条件：

1) 车辆目的地集合 $D=\left\{1,2,\cdots ,d\right\}$，每个车辆有且只有一个目的地车站。目的地车站的数量d远大于股道数量T。

2) 车辆编组计划 $V=\left\{V_1,V_2,\cdots ,V_k\right\}$。 $V_i=d_1{d}_2\cdots d_j$， $\forall d_j\in D\left(j=1,2,3,\cdots ,c\right)$ 是一个长度为n的数组，数组中的元素都属于目的地集合D。表示对于输入的n个车辆编组成新列车的计划。

模型的输入与输出：

输入：长度为 $n\left(n=s\cdot c\right)$ 的数列 $I=d_1{d}_2{d}_3\cdots d_n$， $\forall d_j\in D$ 表示n个已知目的地车站的输入车辆。任意车辆的属性主要有两个： $d_j\in D$ 表示它的目的地，下角标j表示它在输入数列中的位置。

输出：长度为n的数列O： $d_{11}{d}_{12}\cdots d_{1c},d_{21}{d}_{22}\cdots d_{2c},d_{31}\cdots$。注意：I和O中的数量是相等的。

模型中的约束条件：

1、股道数量约束，同一时间可使用的股道数不超过T；

2、股道容量约束，任意时刻一条股道上停放的车辆数不超过R；

3、不容许车辆在股道之间进行移动。

模型的优化目标：

由于增加了股道数量与容量的约束条件，对于一对输入I与输出O，有可能不存在可行解，即不存在一种符合约束条件的调车方案使得由输入I可以得到编组结果O。此时需要调整输入数组I中元素的顺序，使得调整后的输入数组存在可行的调车方案能够得到规定的输出O。这里的调整意味着车辆的重新溜放，因此一个调整动作应当是将某个位置上的数删掉，同时将该数添加至队尾。在这里，我们的优化目标是使用尽可能少的调整得到可顺利编组的输入。

综上所述，我们所研究的问题描述为

调车场调车问题：已知长度为n的输入数组I表示输入车辆的顺序，输出数组O表示关于这些车辆的编组计划。已知参数T，R属于正整数，分别表示股道数量与容量上限。不允许车辆在股道之间调度。目标是找到一个属于I的包含最少元素的子列S，从I中将S所对应的元素全部删除，同时将S添至队尾所构成新的输入I’，使得I'存在一个可行的调度方案可以得到输出O。

根据文献 [18] 可知：

定理1：调车场调车问题是NP完全问题。

2.3. 车辆编组染色问题

将车辆在股道上的编组问题转化为二部图上的边染色问题。

本文中所使用的二部图定义如下：

定义1：设正整数集合 $D=\left\{1,2,3,\cdots ,d\right\}$ 表示所有车辆可能的目的地车站集合。二部图 $G=\left(U+V,E\right)$ 的顶点集由U和V两部分组成， $\left|U\right|=\left|V\right|=n$。其中 $u_i\in U$ 表示第i个进入车站调车场的车辆， $v_j\in V$ 表示第j个出站的车辆。设函数

$dest=U+V\to D$

表示一个车辆的目的地车站。图G的任意一对顶点 $u_i\in U$ 和 $v_j\in V$ 之间存在一条边，当且仅当 $dest\left(u_i\right)=dest\left(v_j\right)$。

在这个定义的二部图的基础上定义其边染色：

定义2：设二部图G如定义1所定义。正整数集 $C=\left\{1,2,\cdots \right\}$ 表示可选择的染色集，设符号“NUL”表示特殊染色，令

$\bar{C}=C\cup \left\{\text{NUL}\right\}$

则称定义在边集上的函数color： $E\to \bar{C}$ 是二部图G上的一种染色。

染色的本质是对图中边集的一种分类，而关于分类问题，我们首先关心的是类别的数量：

定义3：已知二部图G，函数color是G的一个染色。设 $S_k$， $k=1,2,\cdots$ 表示染色为k的边所构成的集合， $S_{\text{NUL}}$ 表示染色为“NUL”的边组成的集合。设函数

$\phi \left(S_k\right)=\{\begin{array}{l}1,\text{if}{S}_k\ne \phi \\ 0,\text{else}\end{array},\forall k=1,2,\cdots$

则称函数

$\text{color}\left(G\right)={\displaystyle {\sum }_{k=1}^{\infty }\phi (\; S\; k\; )}$

为染色color在G上的染色数。

为使得溜放到同一条股道内的车辆排列顺序与车辆的输入顺序不产生矛盾，即在任一股道上的两个车辆排列的先后顺序应与它们在输入队列中的先后顺序一致，因此我们定义图染色的无冲突性质。

定义4：已知二部图G，以及G上的一个染色color如上所定义，边集 $S_k$， $k=1,2,\cdots$ 如定义3所定义。对任意 $S_k\ne \phi$，设 $\left(u_i,v_j\right),\left(u_i,v_j\right)\in S_k$，

如果

${u^{\prime }}_i<u_i$

成立，当且仅当

${v^{\prime }}_j<v_j$

成立。则称染色color是无冲突的。

由于我们所考虑的问题不仅需要考虑股道数量约束，还需要考虑股道容量约束，所以不同于一般染色问题，继续进行定义：

定义5：设图G，染色color如定义1，2所示，集合 $S_k$， $k=1,2,\cdots$ 如定义3所定义。设函数

$\delta \left(\left({u^{\prime }}_i,{v^{\prime }}_j\right),\left(u_i,v_j\right)\right)=\{\begin{array}{l}1,\text{if}{i}^{\prime }<i\text{and}{j}^{\prime }<j\\ 0,\text{else}\end{array}$

其中 $\left(u_i,v_j\right),\left({u^{\prime }}_i,{v^{\prime }}_j\right)$ 为图G的两条边。

当染色边集 $S_k$， $k\in C$ 与图G的边满足

$\text{color}\left(\left(u_i,v_j\right)\right)\ne \text{NUL}$ 且 $\text{color}\left(\left(u_i,v_j\right)\right)\ne k$

时，定义函数

$\text{reside}\left(S_k,\left(u_i,v_j\right)\right)=\underset{\left({u^{\prime }}_i,{v^{\prime }}_j\right)\in S_k}{{\displaystyle \sum }}\delta \left(\left(u_i,v_j\right),\left({u^{\prime }}_i,{v^{\prime }}_j\right)\right)$

函数

$\text{reside}\left(S_k\right)=\underset{\begin{array}{c}\text{color}\left(\left(u_i,v_j\right)\right)\ne \text{NUL}\\ \text{color}\left(\left(u_i,v_j\right)\right)\ne k\end{array}}{\max }\left\{\text{reside}\left(S_k,\left(u_i,v_j\right)\right)\right\}$

根据以上定义，我们接下来描述车辆一个可行的车辆调度方案所对应的特殊染色问题：

定义6：已知二部图G以及G上的一个染色color。设正整数T，R是两个常数。如果染色color满足：

1) 染色color是无冲突的；

2) 边集 ${\displaystyle {\sum }_{k=1}^{\infty }{S}_k}$ 是二部图G的一个完美匹配；

3) 函数color(G)如定义3所定义， $\text{color}\left(G\right)\le T$ ；

4) 函数如定义5所定义， $\text{reside}\left(S_k\right)\le R$， $k=1,2,\cdots$。

则称染色color满足T-R约束。

车辆编组问题中的车辆重新溜放操作实质上是改变图G中顶点集U中顶点的顺序，因此：

定义7：已知二部图 $G=\left(U+V,E\right)$ 如定义1所定义。则使用函数

$f_x\left(u_i\right)=\{\begin{array}{l}{u^{\prime }}_i,\text{if}1\le i<x,\\ {u^{\prime }}_n,\text{if}i=x,\\ {u^{\prime }}_{i-1},\text{if}x<i\le n\end{array}$ 其中 $1\le x<n$

$f_x\left(v_j\right)={v^{\prime }}_j$， $j=1,2,\cdots ,n.$

得到新的顶点集合 $U^{\prime }+V^{\prime }$。任意一对顶点 ${u^{\prime }}_i$ 和 ${v^{\prime }}_j$ 之间存在一条边，当且仅当在图G中，顶点 $f_x^{-1}\left({u^{\prime }}_i\right)$ 和 $f_x^{-1}\left({v^{\prime }}_j\right)$ 之间存在一条边。依上述规定构造得到的图记为 ${G^{\prime }}_x$。由图G构造 ${G^{\prime }}_x$ 的过程称为图G的一次(关于 $u_x$ 的)重排。

在定义了图G的重排之后，我们最终可以定义关于车辆编组问题的图染色优化问题：

定义8：已知集合 $D=\left\{1,2,3,\cdots ,d\right\}$ 表示所有车辆可能的目的地车站集合，一个长度为n定义在D上的数组I表示输入车辆，另一个长度为n定义在D上的数组O表述输入车辆的编组顺序。

根据集合D，数组I和数组O构造如定义1的二部图 $G=\left(U+V,E\right)$，其中 $u_i\in U$ 对应I中的第i个数， $v_j\in V$ 对应O中的第j个数，即

$dest\left(u_i\right)=I\left[i\right],i=1,2,\cdots ,n$

$dest\left(v_j\right)=O\left[j\right],j=1,2,\cdots ,n$

令常数T等于最多可使用的股道数量，常数R等于股道的容量。

我们的目标是：找到最小的非负整数Z，使得图G经过Z次重排得到的图G’上存在一个满足T-R约束的染色。

我们的主要目标是证明：

定理1：在输入为I，输出为O的车辆编组问题中，最少重新溜放次数为Z，当且仅当由定义8所构造的图染色优化问题的最优解的值为Z。

证明：设数组I表示包含n个车辆的输入，对于该输入要求按照输出O的顺序进行编组。根据I构造顶点集U，使得 $u_i\in U$ 对应I中第i个位置的车辆；同理，根据O构造顶点集V，使得 $v_j\in V$ 对应O中的第j个位置的车辆。将根据定义1中的方法构造出的二部图记为 $G=\left(U+V,E\right)$。设非负整数 $Z^{*}$ 为由定义8所定义的图染色优化问题的最优解，即图G在通过 $Z^{*}$ 次重排后形成了新的图 $G^{\prime }=\left(U^{\prime }+V^{\prime },E^{\prime }\right)$，在图G’上存在一个满足T-R约束的染色，不妨设为染色color，至此，只要我们能够证明：

命题1：存在一个调车方案使得输入I能够得到输出O，当且仅当对应的二部图G上存在一个满足T-R约束的染色。

为了证明命题1，我们需要先证明下面几个命题。

命题2：在不考虑股道数约束和股道容量约束的前提下，任意一个从输入I到输出O的可行的调度方案等价于图G上的一个无冲突的，正常染色的边集， ${\displaystyle {\sum }_{k=1}^{\infty }{S}_k}$ 是图G的完美匹配的染色。

将根据定义1中的方法构造出的二部图记为 $G=\left(U+V,E\right)$，二部图 $G=\left(U+V,E\right)$ 的顶点集由U和V两部分组成， $\left|U\right|=\left|V\right|=n$。其中 $u_i\in U$ 表示第i个进入车站调车场的车辆， $v_j\in V$ 表示第j个出站的车辆，在不考虑股道数量约束和股道容量约束的前提下，可以通过增加股道数量或容量，即增大k的数值使得溜放到同一条股道内的车辆排列顺序与车辆的输入顺序不产生矛盾，即在任一股道上的两个车辆排列的先后顺序应与它们在输入队列中的先后顺序一致，因此满足定义4所定义的图染色无冲突性质。根据定义1和定义5图G的任意一对顶点 $u_i\in U$ 和 $v_j\in V$ 之间存在一条边，当且仅当 $dest\left(u_i\right)=dest\left(v_j\right)$，所以任意一个从输入I到输出O的可行的调度方案等价于图G上的一个无冲突的，正常染色的边集。图G是一个二部图，且根据定义1以及定义8中对于输入数组I和输出数组O的定义，则图G中任意两条边都没有公共顶点，因此图G中的所有顶点都是匹配点，即 ${\displaystyle {\sum }_{k=1}^{\infty }{S}_k}$ 是图G的完美匹配的染色。

命题3：对于任意一个从输入I到输出O的可行的调度方案，所使用的股道数量恰等于染色的染色数。

对于任意一个从输入I到输出O的可行的调度方案，当出现染色冲突时，根据定义2和定义7依规定由图G构造 ${G^{\prime }}_x$ 来对进站车辆的顺序进行重排，直到其变为无冲突染色问题。根据命题a在不考虑股道数约束和股道容量约束的前提下，任意一个从输入I到输出O的可行的调度方案等价于图G上的一个无冲突的，正常染色的边集， ${\displaystyle {\sum }_{k=1}^{\infty }{S}_k}$ 是图G的完美匹配的染色，因此二部图 $G=\left(U+V,E\right)$ 的顶点集U和V，任意一对顶点 $u_i\in U$ 和 $v_j\in V$ 之间存在一条边，且只存在一条边，即所使用的股道数量恰等于染色数。

命题4：对于任意一个从输入I到输出O的可行调度方案，任意一条股道上驻留过的最大车辆数，恰等于该方案所对应的染色的reside函数的值。

同命题3证明过程，根据定义5以及reside函数的定义当出现任意一条股道上驻留过的最大车辆数不满足约束时，根据定义2和定义7依规定由图G构造 ${G^{\prime }}_x$ 来对进站车辆的顺序进行重排，直到其满足股道容量约束，即任意一条股道上驻留过的最大车辆数，恰等于该方案所对应的染色的reside函数的值。

综合命题2，3，4的结论可知，对于输入I与输出O，存在一个同时满足股道数量约束和股道容量约束的可行调度方案等价于对应的图G上可以找到一个满足T-R约束的染色，这样就证明了命题1，从而最终完成了定理的证明。

3. 算法

3.1. 算法设计

根据定理1可知，如果调车场调车问题存在精确算法将导致 $P=NP$。因此，我们将为这个问题设计一个基于贪婪策略的实用算法。

图染色算法是求解将给定的二部图G和m种不同的颜色，用这些颜色为图G的各个顶点着色，每个顶点着一种颜色，最终使得G中任意相邻的两个顶点着不同的颜色。在运用图染色算法求解铁路股道车辆调度问题时，根据列车进站解体后形成的车辆进站序列、以及车站内的股道数量为进行染色所需的最多颜色数量进行染色求解，且在染色的过程中必须保证每种颜色所对应的车辆数目不超过股道容量，从而使得满足车辆编组的车辆停入同一条股道。

贪婪策略在解决问题时，总是在遍历问题所有可能的解决方案后做出在当前看来是最优解的选择。在运用贪婪算法求解铁路股道车辆调度问题时，每次根据车辆编组计划遍历所有可能的车辆出站序列，从中选出使得整体车辆序列调度次数最少的贪婪策略方案。针对上述铁路股道车辆调度的数学模型，结合图染色算法以及贪婪策略算法的特点，我们设计了基于图染色的贪婪算法对数学模型进行求解，并且算法的时间复杂度为 $O\left(n^2\right)$。算法设计的主要步骤如下：

第一步输入铁路车站内股道的数量(T)，车站内股道的容量(R)，列车进站解体后形成的车辆序列，到站车辆的目的地车站集合(D)，车辆编组计划(V)。

第二步对输入的给定进站车辆序列根据车辆编组，车站股道数量和股道容量进行图染色算法，得到满足车辆编组要求的车站股道数量和股道容量。判断此时得出的车站股道数量以及股道容量是否满足输入的股道数量和股道容量约束条件，符合则输出完成整体车辆调度的最小调度次数，否则执行第三步。

第三步对股道数量的约束。将图染色中超出输入约束条件股道数量(即图染色使用的颜色数超过股道数量)上停放的车辆放到车辆序列的末端，重新进行车辆溜放，记录溜放次数和重新溜放的车辆，根据新的车辆序列重新进行染色操作。若新生成满足车辆编组计划要求的股道数量满足输入的约束条件，则执行第四步，否则继续执行第三步。

第四步对股道容量的约束。在进行图染色算法的过程中如果所染颜色对应的车辆数目超出输入的股道容量约束时，将车辆放到车辆序列的末端，重新溜放该车，记录溜放次数和重新溜放的车辆，并且中止当前染色，执行第五步，否则输出完成整体车辆调度的最小调度次数。

第五步对车辆序列重新进行染色操作。判断染色过程中使用颜色的数量是否违反输入的股道数量约束，没有违反，执行第四步；否则，执行第三步。

算法的伪代码：

3.2. 数值实验

为验证算法的有效性，用基于图染色的贪婪算法对于铁路股道车辆调度问题进行了数值实验。实验数据参数如下：车站内股道数量为3条，每条股道均能最多容纳40辆车辆，进站列车数量为6辆，每辆列车上搭载的车辆数目均为40辆，列车种类为6种。进站的每辆列车所搭载车辆的目的地车站、车辆编组计划的具体情况见附录图A1，车辆在每辆列车中的搭载顺序见附录图A2。本文共采用了20组数据进行实验，实验结果如表1所示。

Table 1. Experimental results

表1. 实验结果

由表1可以看出，在20组实验中，基于图染色的贪婪算法的实验结果证明了算法解决该问题的有效性，即实现车辆直接在股道编组成列车的同时，也保证了车辆调度的次数。

4. 结论与展望

本文针对铁路车站内股道车辆调度受到铁路车站股道数量、股道容量等条件的限制，导致算例资源消耗较大且优化欠佳的问题，综合考虑了铁路股道车辆调度时的股道数量和股道容量约束，建立了铁路股道车辆调度优化模型，并设计了基于图染色的贪婪算法对模型进行求解。数值实验表明基于图染色的贪婪算法可以较快地根据车辆编组要求以及车站内股道车辆停放情况给出进站列车解体后车辆的优化调度方案，且我们提出的使用基于图染色的贪婪算法求解铁路股道车辆调度模型更符合实际的铁路股道车辆调度操作，可以有效减少车辆在股道间调度的次数和在站滞留的时间。

目前国内主要依靠人工定制车辆股道调度计划的做法已不适应当前的铁路货运发展需求，随着信息技术与数据科学的发展，关于铁路股道车辆调度的研究正朝着自动化，智能化的方向发展。本文以减少车辆在车站股道间调度的次数和在站滞留的时间成本为优化目标，综合考虑车站股道数量以及容量约束，利用基于图染色的贪婪算法求解了铁路股道车辆调度优化问题，为解决铁路股道车辆调度优化问题提供了新思路。

附录：

表A1. 车辆编组计划

表A2. 车辆搭载顺序