基于货运服务网络的铁路局车辆排空优化模型研究

Research on Optimization Model of Empty Car Distribution among Regional Railways Based on Freight Service Network

摘要: 本文研究铁路空车调配过程中的车辆局外排空问题。针对已有研究对于铁路局之间的车辆排空问题缺乏有效模型与优化算法的问题，本文构建了综合考虑车辆排空成本与排空速度的整数规划优化模型，该模型能够依据空车分布情况动态选择车辆集结地、规划车辆集结路径。本文设计了针对上述模型的混合遗传算法，利用最小费用最大流算法计算种群中个体的适应度值，从而得到具有高精确性的解。通过数值实验表明，在货运服务费用已知的前提下，本文所采用的方法平均节约空车集结成本35%以上。

Abstract: This paper studies the problem of empty car distribution among regional railways. We have not seen any work on effective models and optimization algorithms for this problem. We construct an integer programming optimization model that considers the trade-off between the cost and distributing speed. The model dynamically selects assembly stations and plans car assembly paths according to the distribution of empty car. In this paper, a hybrid genetic algorithm for the above model is designed, and the minimum cost maximum flow algorithm is used to calculate the fitness value of individuals in the population, thus obtaining the high-accuracy solution. Numerical experiments show that under the premise of known freight service cost, the method adopted in this paper can save over 35% of the assembly cost on average.

1. 引言

货运列车由提供动力的机车与装载货物的车辆组成。一方面，车辆的种类众多，如棚车、敞车、罐车等等；另一方面，任意类型车辆的使用循环周期是一致的：空车–送达装车地装车–重车–送达目的地卸车–空车。当车辆在货物目的地卸空之后，将空车由卸车地运送至装车地进行重新装车的过程被称为空车调配。为空车指定装车地的决策过程是空车调配的核心问题。按照装车地归属的铁路局进行划分，空车调配可分为局内排空与局外排空两部分。本文主要研究空车调配中的局外排空问题，即空车所在地与装车地分属不同铁路局的情况。我国铁路部门将整个铁路网络(不包含城市轨道部分)进行划分，由18个铁路局分别管辖。每一个铁路局都可以被看作是一个独立运营的铁路公司。空车在进行局内排空时调度较为灵活，既可以与重车混编，也可以编开整列空车直达列车，而进行局外排空时一般只能通过编开空车直达列车送达外局。目前铁路局对于向局外排空的通行做法是，指定若干车站作为集结地，依据集结地的选择对全路局的货运站进行划分，使得每个货运站均属于某个集结地的集结范围。当该货运站产生需要排空的车辆时，将这些车辆运送到对应的集结地，同时在集结地将到达的车辆编入空车直达列车向局外排空。这样做的不足之处在于没有考虑实际空车分布情况，一方面车辆运送成本较高，另一方面如果属于某集结地的集结范围内空车较少，则这些空车的排空速度将会明显降低。因此，我们面临的挑战是：铁路局应当如何高效且低成本地向局外排空。这个问题被称之为铁路局车辆排空问题。

本文将构建关于铁路局车辆排空问题的整数规划模型。这里引入服务网络：货运服务网络指为货物提供服务的网络，每个服务有对应的服务起点和终点，以及使用该服务的花费。空车从产生地经由货运服务网络运送至集结地。在该问题中铁路局管辖界内铁路网络是已知的。这个网络可以被一个有向赋权图来表示，图中的顶点表示货运站，边表示运输服务，边上的权重表示运输成本。例如，图中存在一条由顶点u指向v的有向边 $\left(u,v\right)$，其权重为 $w_{uv}$，则意味着铁路提供从u出发到达v的运输服务，该服务运送一辆车辆从u抵达v的成本为 $w_{uv}$。显然，这个图是强连通的，即从任意顶点出发的车辆可以通过一串连续的首尾相接的运输服务抵达任意终点。我们设每个顶点上现有的需要向局外排空的空车数量亦为

已知量。铁路局车辆排空问题的主要决策内容包含两点：1) 选择哪些车站作为车辆集结地？2) 任意车站上的空车应当选择哪条服务路径到达集结地？在解决铁路局车辆排空问题时，我们希望以最小代价且最迅速地完成车辆排空。但是，成本最小与速度最快通常是矛盾的：快速通常意味着较高的代价，反之，低成本则无法保证速度。因此，我们在解决这个问题时需要寻求二者之间的平衡。车辆排空的成本主要产生于将车辆送至集结地的过程中。这里我们以车辆在集结过程中的运输成本最小化作为铁路局车辆排空优化模型的优化目标。车辆排空过程的快慢主要由集结到同一集结地的车辆数决定。集结到某一集结地的车辆越多，则编成空车直达列车所需的时间越短，意味着排空速度越快；反之则排空速度越慢。为了保证车辆排空速度，我们设置一个集结参数作为解的约束条件，使得求得的所有集结地所集结的车辆数都不低于这个集结参数。明显地，当集结参数取值为零时将会得到集结成本最小的解。集结参数取值越大，每个集结地所集结的车辆将越多，相应的车辆排空速度就越快，同时会造成集结成本升高。综上所述，我们可以通过调整集结参数来控制车辆排空成本与排空速度之间的平衡。

国内外学者对于空车调配问题做出了大量研究。Gorman [1] 综述了铁路空车调配问题。很多学者针对客户需求，研究以客户满意度为主要优化目标的空车调配问题。Heydari等人 [2] 建立了基于客户的多时段需求的空车调配模型，并且利用拉格朗日启发式算法与分枝定界算法求解该模型。温鑫 [3] 针对客户实际需求，建立了综合考虑车种代用与需求时间窗要素的铁路空车调配优化模型，并利用遗传算法求解模型。程学庆 [4] 综合考虑铁路经济效益最大化、货主满意度最大化和空重车调配路径最合理化目标，构建了铁路空车调配多目标优化模型。另一类研究则主要考虑了铁路运输能力对于空车调配的约束。程学庆等人 [5] 建立了基于时间窗和区段空车运输能力约束的空车调配优化模型。Spieckermann等 [6] 将空车调配问题看作一个调度问题，以最小化空车走行费用建模，并设计求解模型的贪婪算法。林柏梁等人 [7] 综合考虑空车供需平衡与路段通过能力约束，建立了空车调配优化模型。朱海狍 [8] 考虑了列车开行频次所产生的影响，提出了一种最短路径未知且路段通过能力有限的空车调配优化模型。Holmberg等人 [9] 考虑列车的到站和发站时间，建立了关于空车调配问题的带列车运力约束的多商品流优化模型。进一步的，Holmberg等人 [10] 研究了具有路径成本固定的多商品流问题，并提出了一种基于拉格朗日启发式算法的混合算法，该算法采用了对偶次梯度搜索和原始启发式算法，计算结果表明该方法能较好地估计最优目标函数值的下界。亦有学者通过将时间变量划分为较短的时间段，研究多阶段动态空车调配问题。梁栋等人 [11] 采用动态规划方法提出了铁路局管内空车调配的多阶段策略优化模型。苏婕 [12] 利用时空网络图将空车调配问题转化为的运输问题(Transportation Problem)，通过依次计算每个时段内的运输问题最终得到原问题的解。目前已知的关于空车调配的研究几乎全部基于空车可以与重车混合编组的前提条件。通过前文对于铁路局车辆排空的流程描述可知，这些研究均不适用于铁路局之间的车辆排空问题。因此，本文的研究拓展了关于空车调配问题的研究领域，同时对于提升铁路车辆使用效率、降低运输成本具有实际意义。

本文的主要贡献有以下两点：

1. 通过对铁路局车辆排空流程与优化需求的分析，综合考虑排空成本与排空速度二者之间的平衡，本文建立了关于铁路局车辆排空问题的优化模型，该模型根据实际的空车分布情况动态选择车辆集结地、规划车辆集结方式；

2. 针对模型设计了以遗传算法为元启发式算法，以最小费用最大流算法计算种群中个体适应度的混合遗传算法，该算法对于铁路局车辆排空优化模型具有较高精确度。

本文主要内容安排如下：第二节主要描述关于铁路局车辆排空问题的整数规划优化模型；第三节主要叙述关于上述模型的算法设计；第四节主要描述数值实验设计与计算结果；第五节是关于本文研究的结论总结以及对于未来研究方向的展望。

2. 模型

2.1. 问题分析

排空问题主要需要决策集结站点如何选取以及空车的集结方式，针对这样的需求，已知的是货运服务网络和空车的分布。由于成本主要产生于集结过程，因此将集结成本作为优化目标，这里的成本是空车在运送至集结地过程中使用的服务网络成本。同时考虑到排空速度，本文引入集结参数，将每个集结地保有一定数量的空车作为约束条件。若该参数越大，则编成列车发出的速度越快，但相应地会增加成本。集结成本与排空速度两个因素相互制约，本文通过建立车辆排空模型得到平衡两者的优化结果。

2.2. 符号说明

G：货运服务网络；

V：图中顶点集，表示车站集合；

E：图中边集，表示运输服务；

W：边上权重，表示货运服务费用；

a：顶点上权重，表示各车站上的空车数量；

B：给定常数，集结参数，表示集结站点上要求的空车数量下限；

C：V的子集，表示集结站点集合；

S：表示除集结车站的其余车站集合；

i：表示除集结车站外的其余车站；

j：表示集结站点；

$x_{ij}$ ：决策变量；表示S中i点送往C中j点的空车数量；

N：表示正整数集。

2.3. 符号说明

根据空车分布不同，动态选取空车集结站点，以集结过程中运送空车成本之和最小为目标，并保证每个集结站点空车数量大于给定下限。模型输入为：货运服务网络G (假设任意两点之间空车均选择最短路径到达，因此货运服务网络为实际路网抽象成的完全图)，各站空车数量a，集结参数B。输出为：最优集结站点集合C，空车集结方案。构建铁路局车辆排空问题的整数规划优化模型如下：

$\min {\displaystyle {\sum }_i{\displaystyle {\sum }_j{w}_{ij}\cdot x_{ij}}}$ (1)

$\text{s}\text{.t}\text{.}{\displaystyle {\sum }_i{x}_{ij}}+a_j\ge B,\forall j\in C,$ (2)

${\displaystyle {\sum }_j{x}_{ij}}=a_i,\forall i\in S,$ (3)

$x_{ij}\in N.$ (4)

模型中：式(1)为目标函数，为所有从车站i到车站j的空车数量乘以i到j的单位运送成本表示运送空车成本最小；式(2)为从所有不同车站i发出到达j的空车数加上j站上的空车数之和大于B，表示各集结站点上空车数量的下限约束；式(3)为S中任意一个车站i，送往j站的所有空车数之和等于该车站上的空车数量。式(4)为决策变量约束。

3. 算法

3.1. 最小费用最大流算法

最小费用最大流算法 [13] 是一类应用在网络中的组合优化算法，网络的每条边上都有容量和费用两个属性，如何选择流向和相应的流量，得到最小费用下的可行流是最小费用最大流算法主要解决的问题。具体为：在初始网络W上，取初始流为零流，构造增广费用网络图，求出网络中从起点到终点的最短路，如果不存在，输出最小费用最大流；如果存在，通过在原网络中得到相应的增广路，对可行流进行调整，调整后得到新的可行流，重复以上过程直到找到网络中的最小费用最大流。

3.2. 遗传算法

遗传算法 [14] 是美国J. Holland教授于1975年提出的一种借鉴于生物进化规律而来的随机搜索算法，它模拟了生物的进化过程，通过选择、交叉以及变异等操作，种群经过若干代进化后，可以达到最优(或近最优)的状态。已广泛用于生产调度问题 [15]、函数优化 [16]、自适应控制 [17] 等方面。算法首先编码产生初始种群，通过计算种群中个体的适应度值选择出适应度高的个体。利用交叉和变异操作产生新的种群，重新对新的种群进行评价，直到满足停止条件，得出优化结果。

3.3. 最小费用最大流–遗传混合算法

(1) 编码

本文选择二进制编码。每个解是由0和1组成的符号串，简单易行。在车辆排空问题中1代表选择该点作为集结站点，0代表不被选为集结站点。将所有车站编号，例如，解(0 1 0 1 0 0)代表一共有6个车站，其中第2个车站和第4个车站被选为空车的集结站点。

(2) 初始化种群

初始种群指随机生成一定数量的个体形成一个初始群体，以作为进化的基础。每个个体代表一个解。问题中假设所有站上待分配的车辆总数为Q，要求分配后每个集结站上最少达到的空车数量为B，因此最终选取的空车集结站点数最多为 $\lceil Q/B\rceil$，即集结站点数量有上限。为了缩小算法的搜索空间，在生成初始种群时，控制每个个体中基因为1的数量不超过 $\lceil Q/B\rceil$，直接生成符合条件的种群可以减少搜索无用个体，加快进化效率。

根据车站数m，建立一个 $m\times px$ 的0~1 (初始种群)矩阵：

(3) 适应度值计算

适应度函数是评价个体好坏的标准，一般以目标函数或者改造目标函数作为适应度函数。本文研究问题的目标是选取集结站点后空车集结过程的花费最小，因此可以根据空车集结过程花费规定个体的适应度值计算方法。

根据实际背景，服务网络可以看作是由集结车站和其余车站组成的完全二部图，集结过程可以看作是其余车站向集结车站运送空车，使得成本最小并且满足集结站点对空车数量的需求。这一过程可以利用图论中最小费用最大流的思想。因此本文采用最小费用最大流算法实现其余站点到集结站点的分配过程。适应度值的确定如下：

步骤1 对于每个种群中的每个个体 $x_{uv}$，利用最小费用最大流算法，计算每个个体在网络流中的费用，即对应的集结站点选取方式下空车的集结成本 $w_{uv}$。其中最小费用最大流算法的实现参数如下：

$N=\left(V,E,C,W\right)$ 是以V为顶点集，E为弧集，C为弧上的容量，W为弧上货运服务费用的网络。增加一个源点s和汇点t，源点和所有的供点相连，容量为点上的空车数 $a_i$，费用为0，汇点和所有集结站对应的点相连，容量为 $B-a_i$，费用为0，供点和集结站点之间的容量设为 $\infty$，费用为对应服务的运输成本，即经过此条服务运送一辆空车的成本。根据上述参数设置，这里最小费用最大流算法计算出的是满足集结站点上最低空车数对应的费用和空车分配方案，如果车站上还有未集结空车，将其按照成本最小的原则分配到相应的集结车站。整个过程的成本由单位运送费用乘以运送空车数。

步骤2 计算种群中最大成本值 $w_{\max }$，每个个体的适应度值为：

${w^{\prime }}_{uv}=w_{\max }-w_{uv}$

(4) 遗传算子的确定

遗传算子包括选择、交叉和变异。本文选择轮盘赌输法进行选择，并且加入精英保留策略。每个个体进入下一代的概率等于其适应度值与整个种群中个体适应度值和的比例，每一代中最好的个体不参与交叉和变异，直接保留到下一代。使得最优个体不会被破坏。

交叉是通过两个个体进行部分基因的互换，从而产生新的个体。本文选择单点交叉。由于个体中1的个数即集结站点的个数有上限，通过交叉操作时可能会破坏这样的特点，因此在交叉时对此进行调整。如果经过交叉操作后产生的个体中基因为1的数量超过上限，则需要做以下的边界吸收操作：检查个体中1的数目，如果超过上限，则产生一个随机数，作为重新调整为0的个数，并通过随机产生调整的位置将该位置上的1变为0。

变异是指在一定概率下，个体发生基因突变的情况。本文采取单点变异的方式，随机指定个体中某个基因发生变异。和交叉类似，在此过程中也要进行边界吸收操作。

(5) 停止条件

本文将最大迭代次数作为停止条件。

4. 数值实验

本节的数值实验均使用MATLAB语言实现，其中遗传算法参数设置为：种群规模为30，交叉概率为0.6，变异概率为0.01，迭代次数为300次。

4.1. 数值实验1

在4个服务网络上利用本文提出的算法进行数值实验，并与枚举法进行对比。服务费用矩阵见附录(表A1)，计算结果见表1。

Table 1. Results of genetic algorithm and enumeration

表1. 遗传算法和枚举法结果

由表1可以看出，本文使用最小费用最大流–遗传算法计算得出的最优近似解和枚举法得出的精确值相同，遗传算法作为一种随机搜索算法，本文通过引入最小费用最大流算法，提高了计算结果的精度。

4.2. 数值实验2

本节以沈阳铁路局为例，利用区段中心优化法 [18] 对简化后51个车站(见附录：图A1)的排空问题进行计算。货运服务费用与距离、车站级别等有关，我们综合这些影响因素确定各服务上的费用。随机生成20组空车分布(各站上的空车数量)见附录(表A2)，分别使用本文提出的排空方法和现有的固定空车集结站点的排空方式对以上20组数据计算并作对比，结果见表2。

Table 2. Comparison of experimental results

表2. 实验结果对比

由表2可以看出，利用本文设计的算法优化出了合理的空车集结站点。经过分配，每个集结站点上的空车数量达到设定的下限，可以满足集结站点上空车快速编成列车发出的需求；相比于现有的固定集结站点的集结方式，降低了空车的集结成本，改变了空车数量分布差别较大的情况。

5. 结论与展望

本文主要研究铁路空车调配过程中的车辆局外排空问题。在已知货运服务网络的基础上，本文构建了综合考虑车辆排空成本与速度的整数规划优化模型，并设计了针对上述模型的混合最小费用最大流算法的遗传算法，通过数值实验说明运用该算法能够得到具有高精确性的解。进一步的，本文通过数值实验表明与固定空车集结点的做法相比本文所采用的方法平均节约空车集结成本35%以上。在研究车辆排空问题的同时考虑空、重车流的配合与路网运能资源合理运用是本领域的重要研究方向。

附录

Table A1. A service cost matrix

表A1. 服务费用矩阵

Figure A1. Network map of Shenyang railway bureau

图A1. 沈阳铁路局路网图

Table A2. Empty train distribution at each station

表A2. 各站空车分布

NOTES

^*通讯作者。