铁路货运站树枝形专用线取送作业计划自动编制研究

Automatic Preparation of Pick-Up and Delivery Operation Schedule for Tree-Shaped Special Railway Line of Freight Station

摘要

在铁路货运站日常工作中，合理安排专用线取送车是确保装卸作业高效进行的关键。传统的取送作业计划依赖人工经验，效率较低，难以应对复杂需求。研究针对树枝形专用线布局的单调机取送顺序优化问题，考虑作业时间窗约束以满足货物时效要求。通过对日计划进行批次划分，构建带时间窗的取送作业优化模型，并采用改进的遗传算法进行求解，优化了算法的选择、交叉和变异操作，提高了求解效率和精度。实验结果表明，该模型有效优化了取送顺序，减少了作业时间和成本，提升了运营效率。实例分析验证了模型和算法的可行性和优越性，为铁路货运站的自动化调度提供理论支持和应用价值。

Abstract

Reasonable arrangements for pick-up and delivery vehicles of special lines are the key to ensuring efficient loading and unloading operations in the daily work of railway freight stations. The traditional pick-up and delivery operation schedule relies on manual experience, which is inefficient and fails to cope with complex requirements. To optimize the sequence of single locomotive pick-up and delivery for tree-shaped special lines, the constraints of operation time window were considered to ensure freight timeliness in this study. By dividing the daily schedule into batches, constructing an optimization model for pick-up and delivery operations with time windows, and utilizing an improved genetic algorithm to solve the model, the selection, crossover, and mutation operations of the algorithm were optimized, and the efficiency and accuracy of the solution were improved. The experimental results show that the model effectively optimizes the pick-up and delivery sequence, reduces operation time and costs, and improves operation efficiency. By verifying the feasibility and superiority of the model and algorithm, the case analysis provides theoretical support and application value for the automatic scheduling of railway freight stations.

Graphical abstract

关键词

货运站 / 铁路运输 / 调车作业计划 / 专用线取送顺序

Key words

Freight Station / Railway Transport / Shunting Operation Schedule / Pick-Up and Delivery Sequence of Special Line

0　引言

铁路货运站调度员通常是将日计划分割为阶段计划，接着确认各阶段计划内的取送车批次，再确认各批次的取送车顺序，从而根据专用线的取送车顺序编制站内解编作业计划。货运站接轨的铁路专用线分布形式大多呈树枝形，和放射性专用线不同的是，调机在专用线往返取送时，一般是将一批次内所有需要取送的专用线作业点访问后再回车站。

目前对于取送作业优化问题研究较多。李冰等^[1]研究了多调机环境下铁路专用线取送车的优化问题，提出基于聚类方法的策略，并利用遗传算法和人工鱼群算法优化调机顺序。吴宇超^[2]基于包钢铁路专用线的实际情况，建立了取送车问题的模型，并利用多种算法优化机车取送和车辆总时长。郭垂江^[3]研究了树枝形货物作业点的取送车调度问题，建立了以最小化调车机车走行时间为目标的模型，并通过改进的禁忌搜索算法优化取送车顺序和调度时间。张鹿宁^[4]研究了冶金煤矿企业的取送作业，提出了一个最小化货车延期占用时间的模型，该模型分为列车编组、取送和进路优化3个部分，并改进了遗传算法进行测试验证。唐春林等^[5]研究了树枝形专用线的取送车作业，建立了以最小化走行和等待时间为目标的模型，并采用融合蚁群算法和模拟退火算法进行求解。李冰等^[6]构建了一个以最小化调机等待和惩罚成本及运营成本为目标的模型，采用HH-GAP&AIP策略生成初始取送方案，并通过异步循环启发式算法和调整方法进行优化。雷友诚等^[7]针对铁路专用线提出智能优化方法，采用两级优化策略和融合遗传算法与蚁群算法的GAASelite进行求解。杨新春^[8]为树枝形专用线取送顺序设计了蚁群算法，并与动态规划算法进行比较分析。李明向^[9]建立了一个以最小化停留费用和调机成本为目标的模型，并用HH-IBA&GA策略解决树枝形铁路专用线取送问题。Gyorgyi等^[10]研究了一种动态随机货物取送问题。学者们通过分析不同客户间货物取送作业发生的概率，提出了一种基于概率分析的启发式求解算法进行求解。Betinelli等^[11]提出了迭代局部搜索和分支-价格算法来解决多车辆拆分负载和多台调车机车的列车编组问题。针对实际问题不同研究人员的模型、算法不尽相同，但是多数研究都是致力于取送车作业优化。在此，通过借鉴学者们的模型和优化策略并实地调研后，结合铁路货运站专用线取送车作业的实际情况，建立数学模型，设计算法求解策略，求解专用线取送作业顺序。

1　阶段计划内取送作业批次划分

1.1　初始批次方案构造

对于一个阶段计划内的取送作业，在求解取送作业顺序之前，先需要划分取送作业的批次，在此采用合并的方式对一个阶段内的取送作业进行批次划分。

将24 h转化为1 440 min，将一天内所有专用线的计划取送车时间t转化到[0，1 440]中的数，并将一天内计划取送车时间t从小到大排序，并且要满足送车先于取车。首先将所有的取送作业划分为一个单独批次，并且如果同一专用线作业点需要连取带送时，将送车批次排在取车批次之前。初始化取送批次方案如图1所示，其中v_i表示专用线和货运站，v_{\mathrm{0}}表示货运站，{v_i}_{,i\ne \mathrm{0}}表示专用线，初始取送批次方案为每个取送任务之间都插入货运站，图中方案表示由货运站依次前往2号、6号、3号、6号、1号专用线取送且每次取送过程都返回货运站。该方案为一个包含5个取送作业的初始方案。

1.2　取送批次合并

在初始批次方案的基础上，对批次进行合并优化。

步骤1：将初始批次记为time=1。

步骤2：将下一个取送批次合并，并且判断当前批次内专用线待送车数和待取车数是否满足机车牵引定数，若不满足，转步骤4，跳出循环。否则判断批次time和批次(time+1)中的专用线是否满足专用线最大存车数约束，如果不满足，将不满足最大存车数的专用线的取车批次移动到该专用线送车批次之后，即该专用线作业点在这一批次送车时取送结合(取车批次移动至送车批次之后如图2所示)，如果此时专用线车辆还未装卸完成，将该送车批次移动到下次取车批次之前，即该专用线下一次取车时取送结合(未装卸完毕的装卸点送车批次移动至下次取车批次之前如图3所示)，并更新前面的批次，如果访问到带时间窗的批次，需保证不超过规定的时间窗范围。更新所有的批次编号并重复进行步骤2，将所有满足专用线最大存车数的批次合并后转步骤3。

步骤3：将批次time和time+1合并后，如果这个批次内包含重复的送车点或者取车点，将其合并，再转到后续提出的遗传算法求解该批次内的最优取送顺序即取送时机，剩下的批次转步骤2，继续计算后续取送批次。

步骤4：优化结束。

通过上述步骤即可得到满足牵引能力约束、专用线最大存车数、时间窗约束的取送批次方案。取送批次合并方案如图4所示。合并重复的取送批次如图5所示。

2　带时间窗的树枝形专用线取送车作业顺序模型构建

实际生产过程中取送车作业组织形式较多，有单一送车、单一取车、送取结合、送兼调移、取兼调移、送取兼调移。专用线厂矿单位内部配有调机可自行调移，因此不用考虑专用线内的车辆调移。

从实际问题出发，对于重点专用线优先送的约束将其转化为时间窗约束，如果调机在这一批次的取送过程中违反了时间窗约束，就会出现取送不及时的情况，从而影响车辆及时出入专用线，造成经济损失，将其视为违反了时间窗约束导致的时间成本。

以函数的形式来表达时间效应成本，称之为惩罚成本函数，惩罚函数的系数是专用线和铁路货运站签订的，取送作业时间偏离时间窗约束越大，其成本就越高。惩罚函数y{u}_i(t_i)如下。

y{u}_i(t_i)=otr\cdot \mathrm{m}\mathrm{a}\mathrm{x}(e_i-t_i,\mathrm{0})+utr\cdot \mathrm{m}\mathrm{a}\mathrm{x}(t_i-x_i,\mathrm{0})⑴

式中：otr表示送车到取送点的机会成本；utr表示晚于时间窗的惩罚值；e_i表示取车时间；x_i表示最晚送车时间；t_i表示调机到达时间。

如果调机在时间窗e_i前到达取送点i，会产生机会损失成本otr\times \mathrm{m}\mathrm{a}\mathrm{x}(e_i-t_i,\mathrm{0})；如果在最晚送达时间之后到达，会产生延误成本。时间窗内到达则成本为0。当软时间成本的2个系数都取最大值M时，软时间成本函数可以等同于硬时间成本函数。其中，软时间成本表示可以违反时间窗口，如果违反不会导致任务失败，但会产生额外的成本；硬时间成本表示取送取送任务必须在规定的时间窗口内完成，否则导致任务失败。

2.1　模型假设

模型假设如下。

（1）一批次取送作业只由1台调机作业。

（2）调机的运行速度不会被连挂车辆的数量影响。

（3）车组到达车站的时间已知。

（4）调机编组完成出发时刻已知。

（5）专用线内装卸作业完成时间已知。

（6）机车牵引定数已知，且不会被环境因素影响。

（7）送进专用线内的全部是空车，从专用线拉出的全部是重车，机车牵引定数不受地形的影响。

2.2　参量与变量描述

为构建模型，引入以下参量与变量。

（1）集合。I表示该批次内所有专用线取送点集合，记为I=\{i|i=\mathrm{0,1},...,\tilde{i}\}，\tilde{i}表示装卸点总数，i=\mathrm{0}表示编组站，i\ne \mathrm{0}表示专用线装卸点，其中I\mathrm{\text{'}}表示送车专用线批次集合，I\mathrm{\text{'}}\mathrm{\text{'}}表示取车专用线批次集合；V表示取送作业批次集合，记为V=\{v_i|i=\mathrm{0,1},...,\tilde{i}\}，v_{\tilde{i}}表示作业批次总数；H表示取送作业性质集合，记为H=\{h|h=\mathrm{1,2}\}，h=\mathrm{1}表示送车，h=\mathrm{2}表示取车；K表示调机编号集合，记为K=\{k|i=\mathrm{1,2},\dots ,\tilde{k}\}，\tilde{k}表示调机总数。

（2）参数。Q表示调机的牵引定数；{L_{v_i}}_{,v_{i+\mathrm{1}}}表示调机从i前往i+\mathrm{1}的走行里程；{t_{v_i}}_{,v_{i+\mathrm{1}}}表示调机从i前往i+\mathrm{1}的走行时间；M_i表示专用线i的最大存车数；t_b表示站调规定的调机返回时刻。

（3）状态变量。{T_i}^{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{h}}表示调机在专用线作业点i完成作业的时间；{T_i}^{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}表示调机到达专用线作业点i的时间；q_{v_i}表示调机在第i专用线作业点摘掉的车辆数；p_{v_i}表示调机在第i专用线作业点连挂的车辆数；t_y表示调机作业完成返回车站时刻。

（4）决策变量。{{\sigma }_{i,i+\mathrm{1}}}^k表示调机k的取送路径判别变量；{{\sigma }_{i,i+\mathrm{1}}}^k=\mathrm{1}表示调机k在装卸点i完成作业后前往装卸点i+\mathrm{1}，否则{{\sigma }_{i,i+\mathrm{1}}}^k=\mathrm{0}；m_{uk}表示批次分派调机判别变量，m_{uk}=\mathrm{1}表示第u批次由调机k负责，否则m_{uk}=\mathrm{0}。

（5）取送顺序表述。F(V)表示取送位次集合，记为F(V)=\{f(v)|f(\mathrm{1}),f(\mathrm{2}),...,f(\tilde{v})\}，f(v)表示取送作业v的取送位次；X(V)表示取送顺序集合，根据取送位次F(V)的先后顺序重新排列作业V形成取送顺序集合，记为X(V)=\{v|v\in V\}。

2.3　目标函数

针对专用线取送车的特点，保证重点专用线重点车辆及时送车的基础上，以一批次取送作业总耗时最短和机车连挂车辆走行公里数最小为优化目标，先划分阶段计划内的取送批次，再求解取送车顺序。

（1）最小化取送作业总时间。在保证及时取送的前提下，取送作业的总时间最小意味着调机的占用时间短，取送作业效率高。其中，包括调机在各专用线专用线作业点间走行的时间和取车时货物作业车在专用线内等待时间。取送车作业总时间Z₁最小化目标表达式如下。

Z_{\mathrm{1}}={\displaystyle \sum _{k=\mathrm{1}}^{\tilde{k}}}{m}_{uk}{{\sigma }_{i,i+\mathrm{1}}}^k[{\displaystyle \sum _{v_i=\mathrm{0}}^{v_{\tilde{i}}}}{t}_{v_i,v_{i+\mathrm{1}}}+{\displaystyle \sum _{v_i\in I\text{'}\text{'}}^{v_{\tilde{i}}}}max\left(\right.{T_i}^{finish}-{T_i}^{arrive},\mathrm{0})]⑵

（2）最小化总走行公里数。机车连挂车辆取送作业时，总走行公里数即各专用线作业点之间的走行里程与连挂的车辆数乘积求和，不仅与走行距离相关还与连挂的车辆数有关，故在编制取送作业计划时，需综合考虑这2项要素。机车走行的距离越长，连挂的车辆越多，则需要消耗的能量越多，因此在安排取送作业顺序时先送车多的专用线，不但能减少机车的消耗，还能降低现场调车工作人员的工作难度。机车连挂车辆总走行公里数Z₂最小的目标表达式如下。

Z_{\mathrm{2}}={\displaystyle \sum _{k=\mathrm{1}}^{\tilde{k}}}{m}_{uk}{{\sigma }_{i,i+\mathrm{1}}}^{\mathrm{k}}({\displaystyle \sum _{v_i\in I\mathrm{\text{'}}}^{v_{\tilde{i}}}}{p}_{v_i}{l}_{v_i,v_{\mathrm{i}+\mathrm{1}}}+{\displaystyle \sum _{v_i=\mathrm{0}}^{v_{\tilde{i}}}}{q}_{v_{\tilde{i}}}{l}_{v_i,v_{i+\mathrm{1}}})⑶

将2个目标经加权的方式处理成相同量纲的总目标函数，{Z_{\mathrm{1}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}是目标1的优化上界，{Z_{\mathrm{2}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}是目标2的优化上界，C_{\mathrm{1}}表示取送作业时间目标的权值，C_{\mathrm{2}}表示走行公里目标的权值，其中C₁+C₂=1， C₁和C₂的取值根据取送作业的现场实际情况给出(站内调机富裕时调整C₁取值偏大，在保证专用线及时取送的前提下节省机车走行能耗，调机紧张时调整C₁取值偏小)，目标函数既要保证取送作业的效率，又要节省机车的消耗。目标函数集合如下。

\mathrm{m}\mathrm{i}\mathrm{n}Z=C_{\mathrm{1}}\frac{Z_{\mathrm{1}}}{{Z_{\mathrm{1}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}+C_{\mathrm{2}}\frac{Z_{\mathrm{2}}}{{Z_{\mathrm{2}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}⑷

2.4　约束条件

（1）调机牵引能力约束。调机在出发时刻及各专用线作业点取送作业的全过程中，连挂车辆数不能大于机车的牵引定数，约束表达式如下。

\begin{array}{l}{\displaystyle \sum _{v_i=\mathrm{0}}^{v_{\tilde{i}}}}{q}_{v_{\tilde{i}}}-q_{v_i}+p_{v_i}\le Q\\ \sum _{v_i\in I\mathrm{\text{'}}}{q}_{v_i}\le Q\end{array}⑸

（2）专用线最大存车数约束。送入专用线的车辆数不能大于专用线当前状态的最大存车数，专用线存车数约束公式如下。

q_{v_{\mathrm{i}}}-p_{v_{\mathrm{i}}}\le M_i⑹

（3）取送顺序约束。同一车组送车要先于取车，约束表达式如下。

f\left(v^{\mathrm{1}}\right)>f\left(v^{\mathrm{2}}\right)v\in V⑺

（4）重点专用线优先取送。将此约束转化为时间窗约束，见式⑴。

（5）调机最晚返回时间约束表达式如下。

t_y\le t_g⑻

3　遗传算法求解策略

遗传算法(GA)是一种基于自然选择和遗传学原理的优化方法，通过模拟生物的复制、交叉和变异过程，从初始种群中生成新个体，并评估其适应度。经过多代进化，算法逐步改进种群，寻找最优解。遗传算法流程图如图6所示。

3.1　编码方案设计

根据此模型的特点，定义染色体的表示方式和编码方式，可以用一个列表来表示染色体。染色体基因的排列顺序表示取送作业决策变量的具体执行顺序，每个任务由3位数字表示，第一位表示分配的调机号，第二位表示专用线编号，第三位表示取送车操作，1表示送车，0表示取车。

这样，染色体就被编码成一个整数列表，比如(110)，(121)，(140)，表示1号调机负责，在1号专用线取车、2号专用线送车、4号专用线取车，染色体的长度等于固定批次内取送作业的总数。编码结构如图7所示。

3.2　种群初始化

首先随机生成一个染色体，该条染色体表示这一批次内所有专用线的取送作业，每个元素作为一个元组，其中包含专用线序号、取送车序号。在生成初始可行解时，为满足送车先于取车的约束，就要对染色体上的序列进行修改。例如，一条染色体的一部分错误序列为(120)，(131)，(121)，表示1号调机先去2号专用线取车，再去3号送车，接着再去2号送车，这样就违反了2号专用线先送后取的约束，那么就将这类序列排列方式的染色体取送顺序互换，从而生成新的染色体序列，最后将出发和返回编组站(100)和(101)分别插入到染色体的首位和末位，染色体的长度由此批次取送作业任务数决定，反复上述过程产生N条染色体构成初始种群。

3.3　约束处理与适应度函数

约束处理的常见方法有3种。第一种是将约束在染色体生成的过程中就加进去，该方法比较繁琐，设计染色体和算子的过程较困难。第二种是编码过程先不考虑约束，而是在遗传算法求解过程中针对染色体对应的解进行检验，这种方法适用于较为简单的模型。第三种方法最为常见，通过引入惩罚函数处理约束，根据该模型，需要限制惩罚函数处理专用线最大存车数和机车牵引定数这2个约束，得到目标函数如下。

\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}Z=C_{\mathrm{1}}\frac{Z_{\mathrm{1}}}{{Z_{\mathrm{1}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}+C_{\mathrm{2}}\frac{Z_{\mathrm{2}}}{{Z_{\mathrm{2}}}^{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}+y{u}_i(t_i)+\\ {\displaystyle \sum _{k=\mathrm{1}}^{\tilde{k}}}{m}_{uk}{{\sigma }_{i,i+\mathrm{1}}}^k\{[M_{\mathrm{1}}\mathrm{m}\mathrm{a}\mathrm{x}{\displaystyle \sum _{v_i=\mathrm{0}}^{v_{\tilde{i}}}}(q_{v_{\tilde{i}}}-q_{v_i}+p_{v_i})-\\ Q,\mathrm{0}]+M_{\mathrm{2}}\mathrm{m}\mathrm{a}\mathrm{x}[{\displaystyle \sum _{v_i=\mathrm{0}}^{v_{\tilde{i}}}}(q_{v_i}-p_{v_i})-M_i,\mathrm{0}]\}\end{array}⑼

由于要满足专用线最大存车数及机车牵引定数这2个约束，将M₁和M₂设置成非常大的整数(M₁和M₂用来保证不满足约束的解让min Z取到无穷大，满足约束取0值)，这就使得不满足约束条件的目标函数也会取得非常大的值。适应度函数要求越大越好，因此取上述目标函数的倒数作为适应度函数，适应度函数为fit(i)=\mathrm{1}/z。

3.4　遗传操作

（1）选择复制。该模型采用常用的轮盘赌选择、保留父代最优染色体替代子代最差染色体的方式。步骤如下。

步骤1：计算当前种群中每条染色体的适应度fit(i)。

步骤2：计算种群中所有染色体适应度的总和sumfit。

步骤3：计算每条染色体的选择概率p(i)=fit(i)sumf。

步骤4：计算每条染色体的累积概率ps(i)。

随机产生一个[0,1]的实数r，从种群中按照染色体的累积概率ps(i)开始遍历，如果染色体i的累积概率大于随机数r，则选择染色体i。否则，继续向后遍历，直到找到累积概率满足的染色体i。

（2）交叉。由于每个专用线作业点至多访问2次，简单的染色体交叉方式可能会造成访问的重复或者空缺，为了满足每个专用线作业点都访问到，且至多访问2次，研究采用修正后的部分映射交叉对染色体进行交叉处理，这种方式可以有效地控制交叉产生的染色体，使其符合问题的约束条件。首先随机选择2个交叉点，交换2条父代染色体在交叉点之间的部分，紧接着固定交换部分不变，遍历每条染色体中未交换的部分，如果存在与交换部分重复的部分，则根据交换部分的一一对应关系将重复的基因换成相对的基因，如此往复直到每条染色体中都不包含重复的基因。染色体交叉方式如图8所示。

（3）变异。为保证变异产生的子代染色体的合法性，在父代染色体上随机选择3个位置作为变异点，对这3个位置进行互换，得到5条子染色体，对所有的情况计算适应度，适应度最高的一条染色体进入子代种群。染色体变异方式如图9所示，对违反约束的染色体也采用部分映射交叉的方式修正。最后计算变换后5条染色体的适应度，只保留其中适应度最大的一条t染色体进入子代种群。

4　阶段计划内取送作业实例验证

4.1　算例描述

以某车站为实例，该站共有14条专用线呈树枝形分布，v₀表示车站，{v_i}_{,i\ne \mathrm{0}}表示各专用线装卸专用线作业点。该车站在0:00—8:00阶段计划内专用线最大容车数如表1所示，0:00—8:00阶段计划取送车信息如表2所示。机车行驶速度设置为15 km/h，专用线内配有调机负责车辆调移，送车入线和取车出线的服务时间均记为5 min，机车牵引定数Q为4 000 t，其中空车20 t，重车90 t。

4.2　算例求解

将一天24 h转换为1 440 min，各专用线作业点的t_i值如表3所示，在表3中依次将表2内的时间按照各专用线的顺序转化为[0，1 440]中的数t_i。各专用线之间走行距离如表4所示。

将各专用线作业点的t_i 值按由小到大的顺序排列，可得到初始的批次方案，再对初始批次方案进行优化，最终该阶段被划分为3个固定批次，最后再对各批次内的取送作业顺序分别求解优化，得到最终专用线取送作业计划如表5所示。

第一批次取送作业由1号调机负责，其解为[(100),(130),(161),(151),(181),(190),(171),(130),(121),(101)]，专用线访问顺序为v_{\mathrm{0}}-v_{\mathrm{3}}-v_{\mathrm{6}}-v_{\mathrm{5}}-v_{\mathrm{8}}-v_{\mathrm{9}}-v_{\mathrm{7}}-v_{\mathrm{3}}-v_{\mathrm{2}}-v_{\mathrm{0}}，调机取送作业时间171 min，调机连挂车辆总走行公里数为988.56 km；第二批次作业由3号调机工作，其解为[(300),(311),(321),(3 141),(3 131),(3 110),(3 100),(370),(360),(310),(301)]，专用线访问顺序为v_{\mathrm{0}}-v_{\mathrm{1}}-v_{\mathrm{2}}-v_{\mathrm{14}}-v_{\mathrm{13}}-v_{\mathrm{11}}-v_{\mathrm{10}}-v_{\mathrm{7}}-v_{\mathrm{1}}-v_{\mathrm{0}}，调机取送作业时间179 min，调机连挂车辆总走行公里数为734.8 km；第三批次取送作业由1号调机负责，其解为[(100),(131),(171),(150),(140),(1 121),(101)]，专用线访问顺序为v_{\mathrm{0}}-v_{\mathrm{3}}-v_{\mathrm{7}}-v_{\mathrm{5}}-v_{\mathrm{4}}-v_{\mathrm{12}}-v_{\mathrm{0}}，调机取送作业时间176 min，调机连挂车辆总走行公里数为348.36 km。

研究采用Python编制算法程序对算例进行仿真，种群数量设为100，迭代次数设置为300次，交叉概率取0.9，变异概率取0.1，惩罚系数otr设置为20，utr设置为50，C₁和C₂均设为0.5。该阶段内机车取送作业总占用时间为526 min，连挂车辆总走行公里数为2 071.72 km，阶段计划内总的适应度函数值为0.999 9，程序运算时长1.24 s。算法迭代收敛曲线如图10所示。根据仿真结果可以看出，取送方案符合要求。

遗传算法影响取送方案精度除算法本身的随机性外，通过设置不同的迭代次数和种群数量、交叉、变异概率观察模型的适应度函数值进行实验。分别将迭代次数改为100次，种群数量设置为200；迭代次数200次，种群数量100；迭代次数600次，种群数量100。

迭代次数100次，种群数量为200时，适应度函数值为0.999 5，程序运行时间1.21 s；迭代次数200次，种群数量100时，适应度函数值为0.998 2，程序运行时间1.12 s；迭代次数600次，种群数量100时，适应度函数值为0.999 8，程序运行时间3.42 s。算法迭代曲线如图10b、图10c、图10d所示。参数设置得过小无法保证解的质量，设置得过高又会影响求解的速度，因此选择种群数量设为100、迭代次数设置为300次的参数设置作为结果。

5　取送作业顺序实例验证

5.1　算例描述

由于阶段计划算例本身的局限性，对于各批次内的取送作业，需连取带送的专用线较少，不能很好地体现算法的优越性，因此为验证遗传算法求解取送顺序及时机的能力，以某货运站某批次内的专用线取送作业为实例，求解其取送顺序。该站专用线呈典型的树枝形分布，专用线的分布形式图如图11所示。

该站某批次内的专用线取送作业点为v₀-v₃-v₇-v₇-v₁-v₁-v₄-v₄-v₂-v₂-v₅-v₅-v₆-v₀，变量值不变，机车行驶速度仍为15 km/h,送车入线和取车出线的服务时间均记为5 min，调机编组完成出发时刻为8:32，机车牵引定数Q为4 000 t，空车20 t，重车90 t，规定的调机最晚回站时刻为11:51，某站专用线取送作业信息如表6所示，各专用线、装卸点之间走行距离如表7所示。

5.2　算例求解

根据前文的经验，种群数量设为100，迭代次数设置为300次，交叉概率取0.9，变异概率取0.1，惩罚系数otr设置为20，utr设置为50，C₁和C₂均设为0.5。程序运行后，得到结果为[(100),(111),(121),(171),(170),(141),(160),(151),(150),(140),(131),(120),(110),(101)]，由1号调机负责，专用线访问顺序为v_{\mathrm{0}}-v_{\mathrm{1}}-v_{\mathrm{2}}-v_{\mathrm{7}}-v_{\mathrm{4}}-v_{\mathrm{6}}-v_{\mathrm{5}}-v_{\mathrm{4}}-v_{\mathrm{3}}-v_{\mathrm{2}}-v_{\mathrm{1}}-v_{\mathrm{0}}，适应度值为0.999 9，程序运行时间为1.11 s，迭代到80次左右即收敛。遗传算法收敛曲线如图12所示，取送作业计划表如表8所示。

调机运行时间为183 min，连挂车辆走行总公里数为765.53 km，且调机送车时间满足时间窗约束和最晚返回时刻，经验证算法可行。

6　结束语

为实现铁路专用线取送作业计划的自动编制，结合铁路货运站专用线的布局特点，先确定阶段计划内的专用线取送作业批次，再建立数学模型，设计遗传算法对各批次内的取送顺序进行求解，最后通过算例对其进行验证。由于阶段计划算例本身的局限性，通过引入第二个更为复杂的算例验证算法在求解取送顺序及时机上的优越性。研究提出的算法求解策略可以在较短时间内求解阶段计划的专用线取送车作业顺序和时机，对于铁路货运站提高车辆周转效率有一定的参考价值。

参考文献

[1] 李 冰，党佳俊，轩 华 ．多调机环境下的树枝形铁路专用线作业车同步取送优化[J]．中国管理科学，2022，30(4)：228-239．

[2] LI Bing， DANG Jiajun， XUAN Hua.Optimization of Simultaneous Placing-in and Taking-out Wagons with Multiple Engines on Branch-shaped Siding[J]. Chinese Journal of Management Science，2022，30(4)：228-239

[3] 吴宇超 ．包钢铁路专用线取送车作业优化[D]．兰州：兰州交通大学，2022．

[4] 郭垂江 ．基于阶段计划的取送车调车作业计划编制优化研究[J]．铁道学报，2019，41(10)：10-16．

[5] GUO Chuijiang. Research on Optimization of Formulation for Shunting Operation Plan of Placing-in and Taking-out Wagon Based on Phase Plan[J]. Journal of the China Railway Society，2019， 41 (10)：10-16

[6] 张鹿宁 ．冶金企业铁路运输取送车优化调度方法研究[D]．北京：北京交通大学，2014．

[7] 唐春林，汪逸民，王文宪，等 ．基于蚁群和模拟退火算法的专用线动态取送车研究[J]．铁道运输与经济，2015，37(2)：75-80．

[8] TANG Chunlin， WANG Yimin， WANG Wenxian，et al. Study on Dynamic Wagon Placing-in and Taking-out on Industrial Siding Based on ACA and SA[J]. Railway Transport and Economy，2015，37(2)：75-80

[9] 李 冰，张志宁，轩 华 ．基于树枝形铁路专用线网络的小运转货物作业系统优化[J]．系统管理学报，2021，30(2)：201-214．

[10] LI Bing， ZHANG Zhining， XUAN Hua. Optimization of Local Freight Train Transship System Based on Branch-Shaped Siding Network[J]. Journal of Systems & Management，2021，30(2)：2021-214

[11] 雷友诚，肖 媛，王雅琳，等 ．企业货运铁路取送车作业智能优化方法[J]．湖南大学学报(自然科学版)，2012，39(1)：81-86．

[12] LEI Youcheng， XIAO Yuan， WANG Yalin，et al. Train Placing-in and Taking-out Operation Intelligent Optimization for Enterprise Freight Transport Railway[J].Journal of Hunan University(Natural Sciences)，2012，39(1)：81-86.

[13] 杨新春 ．技术站货物作业车取送优化研究[D]．成都：西南交通大学，2012．

[14] 李明向 ．基于先送后取的树枝形专用线非直达车流取送作业优化研究[D]．郑州：郑州大学，2022．

[15] GYÖRGYI P， KIS T. A Probabilistic Approach to Pickup and Delivery Problems with Time Window Uncertainty[J]. European Journal of Operational Research， 2019， 274(3)： 909-923.

[16] BETTINELLI A， CACCHIANI V， CRAINIC T G， et al. A Branch-and-cut-and-price Algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities[J]. European Journal of Operational Research， 2019， 279(3)： 824-839.

基金资助

辽宁省自然科学基金计划项目(2023-MS-273)