1. 引言
1.1. 背景介绍
相比于公路运输和航空运输,铁路运输由于受气候和自然环境影响较小,且运输成本较低,在国内大宗货物,如钢铁、煤炭、矿石、粮食等的运输市场中占据优势地位。货物列车编组计划是车流组织计划的具体体现,它规定了路网上将车流组织成列流的方式与办法,在铁路货运组织过程中处于核心位置。在我国铁路系统中超过一半以上的货运量由铁路货运通道承载,而当前主要依赖人工编组的办法受个人能力限制使得货运通道上经常出现运能不足、货物滞留等事件,从而影响整个铁路系统的运输效率。因此,研究铁路货运通道上的列车编组计划优化方法对于提升铁路货运运能,降低社会交通成本具有重要意义。
1.2. 相关工作
车流组织是铁路运输组织的重要内容,是将车流由发生地送到目的地的办法。其中,车流径路确定的是货车从始发站送到终点站所途径的线路。高旭敏等 [1] 以路网总的运营费用最低作为目标函数,同时考虑了线路、车站的能力约束,构建了车流径路的优化模型。苏顺虎等 [2] 分析目前铁路网车流径路存在的问题,提出路网车流径路综合最优的含义,分别以运输时间最少,运输距离最短,运输成本最低为目标建立了多目标0-1规划模型。空车调配问题也是铁路运输调整的重要组成部分,目的是在保证车流组织要求的前提下使得运送空车的费用最小。宋晓东等 [3] 通过综合考虑空车调配问题的多方面因素,构建了考虑车种代用的空车调配多目标优化模型,并在此基础上提出了考虑线路能力约束的空车调配多目标优化模型,使空车调配优化模型更加符合铁路运输实际。梁栋等 [4] 基于我国铁路网络规模大,列车组织形式多样化以及按图行车的特点,设计了与物理时空网络有所区别的服务时空网络。时空网络是研究铁路动态车流组织的一种有效方法。借助于服务时空网,构建了我国铁路运输动态车流组织的策略优化模型。Li等 [5] 首先解释了对货运列车编组计划编制的复杂性,然后通过将车流路线与编组方案联合优化,将货运列车编组计划问题转化为编组网络图的计算问题,建立数学模型使得铁路网内车流总成本最小。Newton等 [6] 将编组计划问题转化为服务网络设计问题,建立了编组去向网络。Kwona等 [7] 基于时空网络建立了动态多商品流模型来模拟货运车辆的路径和调度问题,对已有的编组去向和列车编组方案进行了改进。
国内外学者对于单组列车编组计划进行了大量研究。曹学明等 [8] 研究了直达列车的一种特殊情形即装车地直达列车问题,通过分析影响装车地直达列车开行的因素,建立了装车地直达列车开行的非线性规划模型。赵慧等 [9] 在我国铁路系统上,技术站间计划车流量、集结参数、技术站无改编节省、车流运行径路等已知的条件下进行了技术站间单组列车编组计划的优化研究。Ahuja等 [10] 提出货运编组问题是为了网络中所有调车场的所有装运确定分类计划,以最小化总装运成本,创建编组计划,使用超大规模领域搜索实现解决方案所需的各种约束。单组列车的开行对日均车流量有一定的要求,每个车组中集结的货车数量要达到列车的编成辆数才能安排开行,集结时间较长,而且单组列车的发车间隔较长,货物的运输时间成本较高。因此,近年来学者们开始关注分组列车编组计划的研究。
对于分组列车编组计划的研究一般将分组列车所包含车组数量限定为不超过三组,且规定途中只进行一次换挂作业。王志美等 [11] 在单组列车编组计划方案的基础上,建立了减轴分组列车编组计划优化模型,以车流组织成本最小作为目标函数。陈崇双等 [12] [13] [14] 对分组列车的车流组织特征进行了较为系统的研究,分析了其在编成站、换挂站以及终到站的技术作业特点,并与相应的单组列车形式进行了对比。此外还优化了分组列车编组计划所涉及的相关参数,同时提出了分组列车编组计划优化模型。该模型以车小时消耗最小为目标函数,考虑了铁路网络每一条路线中可以改编的最大车流量、每个技术站可以处理的车辆数,以及每个技术站的调车线数量作为模型的约束条件。田怀秀等 [15] 通过分析技术站每个编组去向的车流结构,建立了单组列车与分组列车联合优化的列车编组计划模型。在实验中说明了此模型的有效性与可行性,同时证明了列车编组计划的优化可以降低货物运输的成本。肖杰等 [16] 按照分阶段优化理论将分组列车组织过程分为车流路径、单组列车编组计划、分组列车编组划三个优化问题,并将车流路径与单组列车编组计划中所建立的编组去向及其吸收的车流强度作为已知条件,建立分组列车编组计划优化模型。肖杰等 [17] 以最大限度地降低技术站总车小时消耗为目标,引入阶跃函数设置开行分组列车的条件,建立包括单组列车和分组列车的编组计划综合优化模型,并采用遍历算法求解技术站编组计划综合优化模型,得到总车小时消耗更少的技术站列车编组计划。
Martinelli等 [18] 考虑到铁路行业竞争激烈的运营环境,缩短决策间隔变得十分必要,提出了一种神经网络模型及其求解方法能在短时间内获得列车编组问题的良好解。Bertanzi等 [19] 研究了给定运输频率时,多产品物流网络的库存和运输成本之和最小的问题,并为此提出了基于序列分解或通过动态规划技术解决简单问题的启发式算法。Michael等 [20] 研究了美国一条主要货运铁路的联合列车调度和需求流问题,提出了一种禁忌増强型遗传搜索算法。Chen等 [21] 采用定性分析的方法结合定量测量和理论推导,并结合仿真实验系统探讨了列车编组方案优化的问题。Xiao等 [22] 提出了同时考虑一节编组列车和两节编组列车的编组计划综合优化模型,并提出了一种基于蚁群系统的启发式优化方法来求解该模型。
综上,我们可以看出,相较于单组列车,分组列车由多个车组组成,每个车组集结的货车数量不需要达到列车的平均编成辆数,能够有效缩短发车间隔,加速货物周转。另外,远程车流通过分组列车的运输可以免除通过多个短程单组列车运输时的改编作业,降低技术站的调车作业负担。因此,有必要研究分组列车编组计划优化问题。已有的研究对分组列车编组计划采用分阶段优化的方法,这样会造成传统分组列车编组计划模型在单组列车编组计划模型的求解结果上进行优化时每个子问题的中间解只具有局部最优性,最终解的全局最优性较差。为此本文提出了分组列车与单组列车编组计划一体化总体优化模型,并设计了相应的遗传算法来求解。
1.3. 本文贡献
本文对铁路货运通道上的分组列车编组计划优化问题展开研究,主要工作包括:
1) 针对已有研究基于单组列车编组计划优化模型的分组列车编组计划分阶段优化方法优化效果欠佳的问题,以货物运输过程中的车小时消耗为优化目标建立了货运通道上的分组列车与单组列车编组计划一体化总体优化模型。
2) 设计了关于上述优化模型的遗传算法,数值实验表明我们所设计的算法能够快速有效地求解上述模型,得到面向需求的铁路货运通道上的分组列车编组计划优化方案,从而表明本文所提出的列车编组计划优化模型可以应用于实际的列车编组计划制定工作中。
本文主要内容安排如下:第二节建立了货运通道上的分组列车与单组列车编组计划模型;第三节针对上述模型设计了遗传算法并给出了相关算法的数值实验;第四节总结了本文的研究内容并指出了进一步的研究方向。
2. 模型
2.1. 问题描述
我国的铁路网是为了客货运输需求而建设的相互联结的铁路干线、支线以及车站和枢纽所构成的网状结构的铁路系统。其中技术站设有比较完善的调车设备和机务、车辆等设备,为邻近的铁路区段供应机车和办理货物列车的解体、编组等作业。铁路编组站是铁路枢纽的核心,是车流集散和列车解编的基地,根据各车场配置数量和方式的不同,编组站也分为不同级别。连接区域经济中心和重要口岸,通过大中小城市,同时与多条铁路货物运输线路和枢纽相联结的铁路线路称之为铁路货运通道。铁路货运通道是整个铁路运输网络的主骨架,因为其强大的运输能力以及连接众多铁路线路的优势,铁路货运通道运输需求旺盛,运输能力强大,设备利用率高效,但由于我国现在依然主要采用人工编组的方式,难以解决整个路网层面上的车流组织工作。
我国铁路大部分线路采用的是客货共线形式,由于客运列车和货运列车的速度级别不同会导致相互等待,而且客运列车优先级要高于货运列车,不利于分组列车的组织秩序。现在实行客货分线运输,既能保证货运铁路的运能,也能保证客运铁路的速度,其中铁路货运通道就属于货运专线的一种。铁路货运列车的种类也按照其编组地点和运行距离、运输性质、编组方式和车组数量等划分为不同的类别。比如常用的一些列车种类有:i) 始发直达列车。只由一个车站所装的车组构成,通过一个及以上编组站,不进行改编作业;ii) 技术直达列车。在技术站编组,通过一个及以上编组站,不进行改编作业;iii) 区段列车。在技术站编组,不通过技术站且在区段内不进行摘挂作业;iv) 摘挂列车。在技术站编组,在区段内各中间站进行摘挂作业;v) 单组列车。仅包含一个车组,列车在沿途技术站不进行任何改编作业;vi) 分组列车。由两个及其以上到达站的车辆组成,且按到达站选编成组,在沿途有关技术站进行车组换挂作业。除此以外,针对当前对送达时间更为敏感的白货(如鲜活货物、饮食品、药品等)货运量大幅增长,国家提出了班列和快运列车。“定点、定线、定车次、定时、定价”为特征的五定班列。新型运输模式的发展一方面大大提升了运输效率,缩短了运输时间,另一方面,将发车和到达的时间固定,也满足了客户准确掌握货物运输过程的需求。
随着我国经济的快速发展和生活水平的不断提高,铁路货物运输需求不断增长,对现有的铁路货运车流组织方式提出了更高的要求。我国铁路货物运输工作组织的基本任务之一就是合理编制铁路货物运输组织模式,改进货物运输路径和编挂方式,不断提高铁路的运输效率。目前我国铁路货物列车编组计划属于中长期规划问题,按照各铁路局下发的列车编组计划表来执行,但由于过长的更新间隔使得列车编组计划不能及时适应车流的变化,因此优化研究列车编组计划对于提升铁路货运的经济效益是非常有必要的。
关于铁路货运分组列车编组计划的优化问题,目前的研究是基于单组列车编组计划的求解结果编组去向的,同时分组列车的组织条件相对苛刻,对编组站的设备条件要求较高,因此这一方面的研究还不够广泛。尽管如此,相比单组列车来说分组列车由多个车组组成,需求来源更为广泛,能够较为快速的集结车辆,减少货车的集结时间,也更容易达到满轴。同时分组列车也可以沿途吸收一部分车流,缩短发车间隔,加速货物周转,从而降低成本。当需求条件一定时,开行分组列车可以减少一部分单组列车的开行,而且分组列车的开行使得整列车的编组作业转化为补轴车辆在中转站的摘挂作业,比单纯地开行单组列车能够节省更多的车小时消耗。但已有的研究中大多分组列车是基于单组列车的求解结果并且只研究了最优单组列车编组方案下的分组列车编组方案,未能考虑所有单组列车编组方案情况下的分组列车编组方案,而且单组列车编组计划的优化模型求得的是近似最优,无法保证得到的列车编组去向使得列车的车小时消耗达到最少,造成分组列车编组计划模型的计算结果达不到最优。本文对分组列车编组计划的研究独立于单组列车编组计划的研究成果,提出了单组列车与分组列车整合优化的模型。其中分组列车编组计划优化模型的求解过程通过单独优化,不依赖于单组列车编组计划模型的求解结果,能够减少已有结果对现有模型的影响,缩短货物运输时间,降低货物在运输过程中对铁路设施资源的占用成本。
分组列车编组计划建模问题的难点在于:在一般情形下,经济成本最小化与时间成本最小化是相互矛盾的。为了降低经济成本会要求列车满轴开行,使得列车的集结时间增加,导致货物在站内的停留时间延长。反之,为了降低时间成本会要求列车定点开行,这样会产生列车欠轴现象,进而导致经济成本上升。此外,与单组列车编组计划相比,分组列车编组计划模型面对的解空间规模较大,可以开行的列车与车流的摘挂方案比单组列车编组计划模型更加复杂,容易造成分组列车欠轴量较大。本文提出了铁路货运通道上的分组列车编组计划优化模型可以缩小铁路网络规模,提高分组列车编组计划的求解速度,在车流量较大的货运通道路网上,分组列车的欠轴运行问题可以得到解决。
在铁路货运分组列车编组计划的优化中,类似于单组列年,并不是所有的分组列车都要开行,对于所有的车流需求,需要选择技术效益更高的分组列车编组方案。因此无论是对单组列车还是分组列车都必须建立符合实际情况并且可以优化编组计划问题的数学模型。铁路货运通道上的分组列车编组计划优化问题主要解决的是确定在货运通道路网上可以开行哪些分组列车,并且每一支需求车流挂在哪些分组列车上时可以使得列车消耗的车小时达到最小。分组列车编组计划决策过程中需要考虑到流平衡问题、每一支需求只能选择一条运输路径,一旦运输路径被选择,相对应的列车必须开行,并且每一列车的欠轴量不能超过某一常数,将其作为模型的约束条件。在分组列车的始发站,由于分组列车是由多个车组构成的,各车组集结完成的时间不一定相同,编组作业较单组列车更为复杂,车小时消耗更多。在分组列车的换挂站,要进行各车组的卸车,装车改编作业,消耗的车小时较多。因此本文提出的铁路货运通道上的分组列车编组计划优化模型将列车的集结成本与在换挂站的中转成本之和的最小值作为模型的优化目标,寻找一个经济成本最小的运输方案。
2.2. 数学模型
定义有向图G表示铁路货运通道示意图,顶点集V表示为货运通道路网上各技术站的集合,
泛指任意一个技术站,集合S表示全部需求,s泛指任意一个需求。
主要使用的参数有:
c:分组列车在技术站的集结参数;
:单组列车在技术站的集结参数;
:在技术站z的平均中转时间;
:需求s的车流强度;
:分组列车的平均编成辆数;
:单组列车的平均编成辆数;
:需求s的起点;
:需求s的终点。
设置如下决策变量:
模型中考虑如下约束条件:
(1)
(2)
(3)
约束(1) (2) (3)使得任意的需求从起点流出最终流入终点,在中间经过车站的流入等于流出。
(4)
(5)
约束(4) (5)表示决策变量
与
之间的关系,保证了所有被需求选择过的列车都会开行。
(6)
其中参数
用来控制分组列车在不同区间上所吸收车流量的差异。约束(6)的作用是保证分组列车的欠轴程度不会超过参数
规定的范围。
下面我们继续讨论模型的优化目标部分。
在本文中,我们以规划周期内所有需求通过货运通道时在站内停留的车小时消耗为优化目标,主要包括两个部分:第一部分为列车集结产生的车小时消耗。
(7)
列车集结所产生的车小时消耗主要与列车长度以及技术站集结参数有关。在公式(7)中,我们将分组列车与单组列车集结所产生的车小时消耗分别计算,原因在于分组列车的编组作业比较复杂,因此分组列车的集结时间成本比单组列车的集结时间成本高。
第二部分车小时消耗主要由需求在中转站中转所产生。
(8)
这一部分车小时消耗主要与技术站的平均中转时间有关,且与中转的车流量成正比。为了便于计算,在公式(8)中,我们将所有需求的起点亦看作中转站来处理,这样做对于优化方案的决策不会产生任何影响。我们的最终优化目标是尽可能降低上述两个部分车小时消耗的总和。即:
(9)
3. 算法
3.1. 算法设计
针对上述数学模型,我们设计了遗传算法进行求解。算法设计主要特点如下:
1) 编码
分组列车编组计划模型中决策变量包括开行哪些列车
或
,具体的车流编组方案
、
、
。当
、
、
的值确定后按照公式(4),(5)就可以确定变量
和
的值,因此决策变量
、
、
的不同组合即为模型的优化解空间。将所有的编组方案按照公式(7),(8)分别计算当前编组方案中列车集结所产生的车小时消耗和需求在中转站中转所产生的车小时消耗,最后按公式(9)计算模型的目标函数值。
2) 初始种群
初始种群指随机生成一定数量的个体形成一个初始群体,作为进化的基础。通过随机设置取值范围内的数来得到,每个个体代表问题的一个解。本文采用的是二进制编码,每一个基因随机取0或者1的值,组成一个个体,在已知编码方法的基础上随机生成0-1矩阵作为遗传算法的初始种群。
3) 适应度函数
适应度函数是根据目标函数确定的用于区分群体中个体好坏的标准,一般以目标函数或者改造目标函数作为适应度函数,个体的好坏通过算法的适应度函数来评判。鉴于我们的优化目标是尽可能降低两个部分车小时消耗的总和,因此本文算法中每个个体的适应度函数取模型的目标函数值的负值,当目标函数值越大说明此编组方案的车小时消耗越少。
4) 选择、交叉、变异
新个体的选取采用轮盘赌输的机制。首先采用计算编组方案目标值的方法对每一个个体进行排序,规定前
个个体直接进入下一代新种群,然后在剩余的个体中利用概率的方案随机选择个体。新种群的任意个体按照设置的交叉概率与变异概率进行配对交叉或者某个个体的任意基因位进行变异。
5) 终止条件
将最大迭代次数作为程序终止条件,停止算法。
3.2. 数值实验
根据已知需求集合,各技术站的参数以及车流路径,建立最优编组方案。铁路货运通道路网规模为10个站点,图中每个圆圈表示一个技术站,两个技术站之间的铁路弧段是有向的,见图1,两两之间的车流需求见表1,每个站点的参数见表2。
![](//html.hanspub.org/file/11-2621394x50_hanspub.png)
Figure 1. Road network diagram of freight transportation corridor
图1. 货运通道路网图
![](Images/Table_Tmp.jpg)
Table 1. Traffic flow transportation demand in road network
表1. 路网中车流运输需求
![](Images/Table_Tmp.jpg)
Table 2. Parameters of each technical station
表2. 各技术站参数
本文进行的数值实验中列车的平均编成辆数取55 (
),技术站的集结参数(
)和平均周转时间
取表1,
取10。采用遗传算法对模型进行求解,其中一个种群包含30个个体,将交叉概率取值设为0.6,变异概率取值设为0.01,取最大迭代次数为500次。经过计算得到列车开行方案见表3、需求路径规划见表4,上述两表共同构成分组列车编组计划:
![](Images/Table_Tmp.jpg)
Table 4. Traffic flow path for each demand
表4. 各需求的车流路径
使用上述遗传算法求解所得的关于需求的车小时消耗为10,486车小时,即在规划周期内所有需求通过货运通道时在站内停留的车小时总量。通过数值实验表明该遗传算法收敛速度较快。根据表1画出图2,技术站1开行4趟分组列车;技术站2开行1趟单组列车,4趟分组列车;技术站3开行1趟单组列车,5趟分组列车;技术站4开行2趟分组列车;技术站5开行2趟分组列车看出每个技术站上开行的列车数量较为平均,说明各个技术站负担均衡。所有开行的列车中,分组列车占比89.47%说明相比于单组列车,分组列车在节约铁路运输过程中的车小时消耗方面具有更大的优势。
![](//html.hanspub.org/file/11-2621394x57_hanspub.png)
Figure 2. The optimal formation plan of the multi-block train
图2. 分组列车最优编组方案图
4. 结论与展望
本文针对分组列车编组计划模型在单组列车编组计划模型求解结果基础上分阶段优化效果欠佳的问题,综合考虑了铁路货运通道上货物运输过程中集结车小时消耗和中转车小时消耗,建立了货运通道上的分组列车与单组列车编组计划一体化总体优化模型,并设计了遗传算法对模型进行求解。数值实验表明遗传算法可以较快地给出分组列车的优化编组方案,且我们提出的分组列车编组计划优化模型也说明相比于纯单组列车,单组列车与分组列车联合的编组方案使得货物运输的车小时消耗更少。
目前国内主要依靠人工来制定列车编组计划的做法已不适应当前的铁路货运发展的需求,随着信息技术与数据科学的发展,关于列车编组计划的研究正朝着自动化,智能化的方向发展。本文以规划周期内所有需求通过货运通道时在站内停留的车小时消耗为优化目标,综合考虑分组列车欠轴约束,利用混合整数规划建立了铁路货运通道上的分组列车编组计划一体化优化模型,为解决分组列车编组计划优化问题提供了新思路。
NOTES
*通讯作者。