铁路技术站作业计划综合编制的优化模型研究

赵 军，张煜婷，张思宇

铁路技术站作业计划综合编制的优化模型研究

赵 军，张煜婷，张思宇

（1. 西南交通大学，交通运输与物流学院，成都 611756；2. 综合交通运输智能化国家地方联合工程实验室，成都 611756）

本文探讨铁路技术站作业计划中三个重要子计划，即车流推算、调机运用和调车线运用计划的综合编制问题。首先，以给定的时间精度将计划时段离散化为有限个时刻，并采用累积流思想刻画车辆占用调车线的情况。进而，以车辆在站总停留时间和对调车线占用总惩罚最小为目标，将该综合问题建立为整数非线性规划模型。根据模型特点，利用既有线性化技术，将该模型转换为整数线性规划模型。最后，计算分析结果表明，所提出的线性模型可正确刻画技术站作业计划综合编制的特点和要求，采用合理的时间精度设置，该模型可在合理时间内找到高质量的解。

铁路运输；作业计划；数学优化；技术站；综合编制

0 引 言

技术站是铁路货物列车的生产场所，其工作组织的质量对铁路货物运输组织的各个环节产生影响。在现场，技术站的日常工作通过编制各种类型的作业计划来组织。阶段计划是技术站重要的作业计划之一，主要解决3~4 h计划时段内的车流推算、调机运用、到发线运用和调车线运用等子问题，其中前两个子问题常合称为配流问题。各子问题相互联系和影响，共同决定技术站阶段计划的可行性。研究作业计划综合编制的优化方法，同时解决多个关联的子问题，对于提高技术站作业计划编制质量、保证技术站工作组织效率具有重要意义。

国外对技术站作业计划编制开展了一定研究。早期的研究主要关注作业计划中各子问题的优化。例如，对于车流推算问题，Bektas[1]引入时间窗，建立了空车流重配的0-1线性规划模型。Boysen[2]研究了基本车流推算问题，提出三种车流分配策略，并设计定向搜索算法求解。针对调车线运用问题，Bohlin[3]以二次解体车辆数最少为目标，分别建立了基于生成列和弧索引的整数线性规划模型。Gestrelius[4]进一步约束出发列车按站顺编组，提出了基于生成列的整数规划模型。近来，国外对技术站作业计划的集成编制进行了探讨。Gestrelius[5]对技术站车流推算与调车线运用进行综合优化，以最小化二次编组车数和股道占用成本为目标，建立了整数规划模型。Haahr[6]提出了启发式求解框架，综合优化技术站解体排序、编组排序和调车线运用三个子问题。对于相同问题，Raut[7]建立了混合整数线性规划模型，并提出了滚动时域求解算法。

国内针对技术站作业计划编制中的各子问题开展了许多工作。对于配流问题，薛锋[8]设计了GAAA算法，首先生成解体方案的集合，其次以蚁群算法对以上解集进行检验，得到配流成功车数最多的配流方案。黎浩东[9]考虑不同满轴约束条件，以阶段内配流代价最小为目标，建立混合整数线性规划模型，并设计和声搜索算法进行求解。赵军[10]以车流在站总停留时间最小为目标，构造多解多编运营条件下的混合整数线性规划模型，并设计基于随机键编码的有偏遗传算法求解。马亮[11]将问题分为初步和二次配流两部分，首先采用混合算法获取初步配流方案，然后设计贪婪算法对配流方案进行优化。对于调车线运用问题，黎浩东[12]以最小化整理线数量和出发列车总连挂钩数为目标，构建0-1线性规划模型。马亮[13]定义股道活用原则，基于此建立了使调车场股道混乱度最小和占用优先级最大的整数优化模型，并设计启发式回溯算法求解。同时，国内对技术站作业计划综合编制也开展了一定工作。薛锋[14]建立综合考虑配流、到发线运用和取送车作业的混合整数非线性规划模型，并采用ECGACO算法求解。Shi[15]对配流和调车线运用综合问题，提出了以最小化车辆在站停留时间为目标函数的混合整数规划模型，并设计启发式算法确定解体顺序。

综上，国内外主要关注技术站作业计划编制中的个别子问题，对作业计划综合编制的探讨不多。在既有的作业计划综合优化研究中，国外采用的优化方案不适用我国实际，国内的相关工作通常把调车线运用规则进行简化处理。然而，实际技术站工作中，各技术作业间存在强的时空因果关系，忽略这种关系将会给模型在现场的运用带来影响。Shi[15]建立的配流与调车线运用综合模型对本文有所启发，但仍有可提升的空间。文中规定各去向的车流只能严格按照固定的方案使用调车线，不允许调车线灵活运用。固定调车线运用方案固然可减轻模型的建模难度并便于现场实施，但与此同时可能丢掉调车线运用的灵活性，影响作业计划的质量，还有可能因调车线能力紧张，使得作业计划不可行。

结合技术站作业计划编制的特点和要求，本文以车辆作为车流推算的最小单元，对文献[10]中的配流模型进行拓展；考虑调车线固用与活用相结合，根据文献[7]提出的累积流思想刻画车辆占用调车线情况；进而以车辆在站总停留时间和对调车线占用惩罚最小为目标函数，提出技术站车流推算、调机运用和调车线运用综合问题的整数非线性规划模型，并借助既有线性化技术将该模型转换为线性模型；最后设计算例对模型的正确性进行验证。

1 问题描述

本文对具有一套改编系统的技术站在给定计划时间内的作业计划综合编制问题进行研究。车辆在站按到达场—驼峰—调车场—出发场的顺序依次流动，列车到达车站后根据安排好的接车进路进入到达场指定股道等待后续技术检查。列检完毕的到达列车由空闲解体调机推上驼峰进行解体，在解体溜放过程中，脱钩的车辆溜入指定调车线，与后续进入线路的车辆集结成列。待完成集结作业后，空闲编组调机按一定顺序连挂调车线上集结完成的车辆以编成出发列车，再转至出发场指定线路，等待进行出发技术检查作业及发车作业。

在现场，技术站通过编制作业计划来指导日常运输生产，需解决几个优化决策问题。其中，车流推算确定到发列车间的车流接续方案，调机运用解决调车机车的解体、编组等调车作业计划，到发线运用确定到发列车对到发线的占用方案，调车线运用解决车辆对调车线的占用方案。由车辆在站技术作业过程可知，车流推算和调机运用决策在很大程度上决定了技术站对车辆的中转效率和作业计划的质量。同时，到发线运用和调车线运用决策又限制了车流推算和调机运用决策的可行性，相比于到发线，调车线是供车辆在解体完成后和编组开始前可能长时间停留的场所，其运用决策对车流推算和调机运用决策的影响更为显著。因此，本文具体研究技术站含车流推算、调机运用和调车线运用综合问题的优化方法。

综上，本文解决的技术站作业计划综合编制问题可描述为：给定到达列车、到达车辆、出发列车、解体调机、编组调机和调车线等信息，以车辆在站总停留时间和对调车线占用总惩罚最小为目标，确定到发列车车流推算方案、列车解编方案和车辆-调车线占用方案，并满足所有的运营和安全规则。

2 模型构建

2.1 符号说明

本节模型使用的集合和参数见表1，变量见表2。

表1 集合、参数定义

表2 变量定义

Tab.2 Definitions of variables

续表2

符 号含 义 当出发列车满长时取1，否则取0 当出发列车在时间上可接续车辆时为1，否则为0 当出发列车经调机kk在时刻开始编组作业时取1，否则取0 当时，若出发列车先于出发列车编组结束取1，否则取0 出发列车的编组开始时刻 当车辆占用调车线时取1，否则取0 从计划时段初至时刻，累积占用调车线的车辆的总长度 从计划时段初至时刻，累积释放调车线的车辆的总长度

2.2 目标函数

由问题描述，本文考虑车辆在站总停留时间和调车线占用总惩罚最小的目标。一方面，技术站的运营目的是快速中转车辆，给定计划时段内，站内改编设备及能力有限，为加快车辆周转速度，首要目标应最小化车辆在站总停留时间。另一方面，现场一般按固用与活用相结合的原则为车辆安排调车线，在能力允许的情况下，优先为车辆安排固用的调车线，若能力不足，也应对固定使用方案做最小调整。为反映现场的调车线运用特点，引入车辆-调车线占用惩罚，并以车辆对调车线占用总惩罚最小作为次要目标。基于此，目标函数表达如下：

需说明的是，在目标函数（1）中，第二项次要目标的值远小于第一项主要目标的值，式（1）将这两项目标直接加在一起形成一项目标，正好可反映两个目标的相对重要性，即在先优化第一项目标的前提下再优化第二项目标，也可避免求解多目标优化问题的困难。

2.3 约束条件

2.3.1 到达列车解体约束

到达列车解体约束如下：

式（2）为解体完成时刻唯一性约束，即各到达列车必须经某台解体调机在最早解体开始时刻后的某时刻完成解体作业。式（3）为占用调机不冲突约束，表示各解体调机在计划时段内各时刻至多只能完成一列到达列车的解体作业。式（4）定义了到达列车的解体完成时刻。式（5）和式（6）为占用溜放线不冲突约束，即相继进行解体技术作业的到达列车，其解体结束时刻至少间隔一个溜放时间。式（7）和式（8）为变量定义域约束。

2.3.2 车流推算约束

车流推算约束如下：

式（9）为车流推算唯一性约束，表示车辆只能编入一列出发列车。式（10）~（12）为出发列车满轴约束，即未满足满轴要求的出发列车无法开行。式（13）~（14）为车流接续的时间约束，表示仅当出发列车编组开始时刻不早于车辆的解体完成时刻时，允许车辆编入该出发列车。式（15）为车流接续的去向约束，即当出发列车可吸收去向包含车辆的去向时，车辆编入出发列车为可行方案；式（16）~（18）为变量定义域约束。

2.3.3 出发列车编组约束

出发列车编组约束如下：

式（19）为编组开始时刻唯一性约束，即出发列车必须经某台编组调机在最晚编组开始时刻前的某时刻开始编组作业。式（20）为占用调机不冲突约束，表示一台编组调机在计划时段内各时刻至多只能完成一列出发列车的编组作业。式（21）定义了出发列车的编组开始时刻。式（22）和式（23）为占用峰尾牵出线不冲突约束，即相继进行编组技术作业的出发列车，其编组结束时刻至少间隔一个转场时间。式（24）~（26）为变量定义域约束。

2.3.4 调车线运用约束

调车线运用约束如下：

2.4 优化模型

综上，铁路技术站作业计划综合编制问题可构建为以下优化模型M：

目标函数：式（1）

s.t. 式（2）~（36）

不难看出，约束（28）~（32）中存在几个非线性项，使得模型M是1个非线性模型，显著增加了求解难度。下节依次对这些非线性约束进行线性化，进而提出技术站作业计划综合编制的线性模型。

3 模型线性化

3.1 约束（28）~（30）的线性化

由此，式（28）~（30）可转换为以下线性约束：

3.2 约束（31）的线性化

基于此，式（31）可转换为：

3.3 约束（32）的线性化

3.4 线性模型

综上，模型M可转换为以下线性模型M′：

目标函数：式（1）

可见，模型M′是1个整数线性规划模型，其规模随着到达列车、到达车辆、出发列车、解体调机、编组调机、调车线和离散化时刻的数量呈多项式增长。为求解该模型，对于小规模例子，可采用商业优化软件（例如CPLEX、GUROBI等）直接求解；对于大规模例子，模型规模将变大，商业软件可能不再有效，此时还需要研究另外的求解算法。本文致力于构建技术站作业计划综合编制问题的整数线性规划模型，通过模型显示技术站的车流推算、调机运用和调车线运用综合问题可在统一的1个线性模型下进行综合优化。因此，接下来的算例分析中，直接采用商业优化软件求解模型M′。

4 算例分析

4.1 算例描述与参数取值

以1个技术站0：00~3：00的阶段计划为例，验证所提出模型的可行性。该技术站有车流去向10个，在考虑阶段内，有到达列车4列，编号为A0~A3，其中A0表示计划初调车场现在车，到达列车信息见表3。到达车辆185辆，设定各到达列车中车辆按去向分组且按去向的编号递增排列，假设各辆车总重80 t，换长1.1，简便起见，省略具体到达车辆信息。有候选出发列车4列，编号为D1~D4，各列车的牵引定数4240 t（可向下波动80 t），总换长88（可向下波动1.1），出发列车信息见表4，D1、D2和D4为小运转列车，允许欠轴开行。解体和编组调机各1台，列车溜放和转场时间均为0 min。有调车线10条，信息见表5。

表3 到达列车信息

Tab.3 Information of inbound trains

表4 出发列车信息

Tab.4 Information of outbound trains

表5 调车线信息

Tab.5 Information of classification tracks

以Intel（R）Core（TM）i7-7700 3.6 GHz CPU和16 GB RAM的个人电脑为计算平台，采用MATLAB 9.0编程所提出的优化方法，并调用软件CPLEX 12.8对线性模型M′同前进行求解。

4.2 计算结果及分析

车流推算方案见表6，其中，第2列为出发列车的编组内容，由各到达列车中车辆组成，编组调机在编组过程中需将车流推算方案中指定车辆连挂成列。以出发列车D1为例，编入D1的车辆来自于到达列车A0、A1和A2，车辆编号分别是1~5、18~51和75~77。根据表6可得，所有出发列车均配流成功，其中出发列车D3满轴出发，其余小运转列车欠轴出发。

到达列车解体方案见表7，其中，各到达列车的待解时间为其解体实际开始时刻减去其最早开始时刻。可见，到达列车解体顺序与到达顺序一致，即先到先解；相继进行解体作业的列车间，前序列车的解体结束时刻与后续列车的解体开始时刻相同，解体调机连续不间断进行作业，工作效率高；各到达列车待解时间较小，列车完成技检后快速进行解体。

表6 车流推算方案

Tab.6 Wagon-flow allocation plan

表7 到达列车解体方案

Tab.7 Classification plan of inbound trains

出发列车编组方案见表8，其中，各出发列车的待发时间等于其编组最晚结束时刻减去其实际结束时刻。从表8可看出，出发列车按出发顺序先后进行编组，事实上，由于最后一列到达列车A3已于1：20结束解体，D2、D3和D4采取其他编组顺序（例如2、4和3或者3、4和2）也可获得相同的计算结果；相继进行编组作业的列车间，前序列车的编组结束时刻与后续列车的编组开始时刻一致，编组调机连续不间断进行作业，工作效率高。

表8 出发列车编组方案

Tab.8 Assembly plan of outbound trains

调车线运用方案如图1所示，图中，峰尾在右端，纵轴表示调车线，横轴表示车辆，对于各条调车线，以车辆在线路上停靠位置离右端的距离表示其占用该调车线的先后顺序。图1表明，车辆均按固定使用方案占用调车线，不存在占用惩罚。例如，D2同时吸收了去向8的车辆65~74和108~117、及去向9的车辆15~17、118~130和182~185，这两个去向的车辆分别在在其固用调车线S9和S10上集结，便于后续编组作业。此外，由于计划时段内不存在优先在调车线S1、S3、S4和S5上集结的车辆，这些线路上无车辆占用。

图1 调车线运用方案

统计结果见表9，其中第三行和第四行分别为目标函数（1）中第一项和第二项的值，即车辆在站总停留时间和对调车线占用总惩罚，第五行为获得解的计算误差。由表9可知，使用模型M′找到了算例的最优解，由于车辆均可在其固用调车线上集结，无调车线占用惩罚，目标函数值等于其第一项的总停留时间。对于计算时间，模型M′耗费不到2 min将算例求解到最优。综上，本文所提出的线性模型可正确描述技术站作业计划综合编制问题，并在限制时间内同时得到了可行的车流推算、调机运用和调车线运用方案。该模型可避免分步求解可能存在的不可行问题，体现了对技术站作业计划进行综合编制是必要且可行的。

表9 统计结果

Tab.9 Statistics results

4.3 时间精度对结果的影响

不难看出，时间精度∆对模型M′的规模和求解性能具有影响。分别取时间精度为1、5和10 min，在每个时间精度下，限定模型计算时间为3 min或求到最优。计算结果见表10，其中，“解的质量”指获得解与最好解的相对误差，该值越小，计算结果越好。

表10 时间精度的影响

Tab.10 Effect of time granularity

根据表10可知，随着时间精度的降低，解的质量变差，时间精度取10 min时最优解的质量相对于取1和5 min时的解变差1.5%。同时，时间精度越低，模型越容易求解，当时间精度取1 min时，在180 s内找不到可行解，此时需花810 s才能找到最优解；当时间精度取5和10 min时，都能在120 s以内收敛。由此可知，时间精度同时影响模型的解质量和计算时间，在实际实施时，应合理设置时间精度的取值，在满足决策时间要求的同时保证解质量。

5 结束语

本文提出了技术站集车流推算、调机运用和调车线运用计划综合编制的优化模型，以车辆在站总停留时间和调车线占用总惩罚最小为目标，构建了该综合问题的整数非线性规划模型，再进一步将其转换为整数线性规划模型。根据算例分析结果，所提出的优化模型可准确描述技术站作业计划综合编制的特点，通过合理的时间精度设置，能够在合理时间内返回高质量的计算结果。为完整刻画原问题的要求，文中所提出的综合优化模型含许多时空和资源约束，使得该模型对于大规模的问题可能存在求解困难。因此，在以后的研究中需要分析该模型的特点，设计更有效的求解算法，以在解的质量和计算时间上取得更好的折中效果。

[1] BEKTAŞ T, CRAINIC T G, MORENCY V. Improving the performance of rail yards through dynamic reassignments of empty cars[J]. Transportation Research Part C: Emerging Technologies, 2009, 17 (3): 259-273.

[2] BOYSEN N, EMDE S, FLIEDNER M. The basic train makeup problem in Shunting yards[J]. OR Spectrum, 2016, 38 (1): 207-233.

[3] BOHLIN M, GESTRELIUS S, DAHMS F, et al. Optimization methods for multistage freight train formation[J]. Transportation Science, 2016, 50 (3): 823-840.

[4] GESTRELIUS S, DAHMS F, BOHLIN M. Optimisation of simultaneous train formation and car sorting at marshalling yards[C]// RailCopenhagen.Copenhagen: Railcopenhagen Press, 2013: 1-17.

[5] GESTRELIUS S, ARONSSON M, JOBORN M, et al. Towards a comprehensive model for track allocation and roll-time scheduling at marshalling yards[J]. Journal of Rail Transport Planning & Management, 2017, 7 (3): 157-170.

[6] HAAHR J T, LUSBY R M. A matheuristic approach to integrate humping and pullout sequencing operations at railroad hump yards[J]. Networks, 2016, 67 (2): 126-138.

[7] RAUT S, SINHA S K, KHADILKAR H, et al. A rolling horizon optimisation model for consolidated hump yard operational planning[J]. Journal of Rail Transport Planning & Management, 2019, 9: 3-21.

[8] 薛锋, 王慈光, 张展杰. 编组站配流的协调优化算法[J]. 西南交通大学学报, 2010, 45 (6): 932-937.

[9] 黎浩东, 何世伟, 景云, 等. 考虑不同满轴约束的编组站阶段计划配流优化[J]. 铁道学报, 2012, 34 (7): 10-17.

[10] 赵军, 彭其渊. 单向编组站配流与调机运用综合问题[J]. 铁道学报, 2012, 34 (11): 1-9.

[11] 马亮, 郭进, 陈光伟. 铁路编组站动态配流分层模型[J]. 中国铁道科学, 2015, 36 (2): 87-95.

[12] 黎浩东, 宋瑞, 呼志刚. 铁路编组站分类线运用优化研究[J]. 铁道学报, 2015, 37 (12): 8-13.

[13] 马亮, 张晓霞, 郭进. 基于启发式回溯算法的铁路编组站调车场调车线活用研究[J]. 铁道学报, 2016, 38 (8): 16-22.

[14] 薛锋. 铁路编组站配流协同优化模型与算法[J]. 系统工程理论与实践, 2013, 33 (11): 2930-2936.

[15] SHI T, ZHOU X. A mixed integer programming model for optimizing multi-level operations process in railroad yards[J]. Transportation Research Part B: Methodological, 2015, 80: 19-39

Optimization Model for the Integrated Operation Plan at Railway Technical Stations

ZHAO Jun, ZHANG Yu-ting, ZHANG Si-yu

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 611756, China)

This paper investigated the integrated design of three important sub-plans including wagon-flow allocation, engine scheduling and car-to-track assignment in the operation plan of railway technical stations. First, the planning period was discretized into a limited number of time points using a given granularity of time. The cumulative flow-based idea was used to describe the occupation of railcars on classification tracks. Then, the integrated problem was formulated as an integer nonlinear programming model with the objective of minimizing the total dwell time at station and total occupation penalty on classification tracks of railcars. According to the characteristics of the model, it was easily transformed into an integer linear programming model using existing linearization techniques. Finally, computational results show that the proposed linear model can describe correctly the characteristics and requirements for the integrated design of operation plan at technical stations. The model can find high-quality solutions within reasonable time under a reasonable setting of the granularity of time.

railway transportation; operation plan; mathematical optimization; technical station; integrated design

1672-4747（2020）04-0011-12

U292.16

A

10.3969/j.issn.1672-4747.2020.04.002

2020-02-26

中国国家铁路集团有限公司科技研究开发计划课题（K2018X004）

赵军（1986—），男，四川宜宾人，博士，副教授，研究方向为铁路运输组织，E-mail：junzhao@swjtu.edu.cn

赵 军，张煜婷，张思宇. 铁路技术站作业计划综合编制的优化模型研究[J]. 交通运输工程与信息学报，2020, 18(4): 11-22

（责任编辑：李愈）