铁路客运站到发线运用方案是客运站作业计划的重要内容之一，其目的在于最大限度地满足不同类型的列车按照运行计划在客运站进行到发的作业需求.合理的到发线运用计划不仅是列车在站安全地完成行车作业的基本保障，而且可以实现方便旅客乘降、提高客运站作业效率以及保证客运站设备均衡使用等.但是，当恶劣天气、线路故障等原因导致列车大量晚点到达，导致客运站到发线能力紧张时，原有的到发线运用方案已不能适应变化了的列车作业要求，必须对客运站到发线运用方案进行调整，以保证列车运行安全和尽快恢复列车正点运行.

车站到发线运用方案编制问题是近年来国内外学者研究的热点问题.国内学者一般使用线性0-1规划模型^[1-2]、非线性0-1规划模型^[3-4]混合整数规划模型^[5]对车站到发线运用方案编制问题进行描述，模型的优化目标主要为最小化到发线使用成本^[1-3]、均衡使用到发线^[4]及最小化列车停站时间^[7]等，求解模型所采用的算法也以模拟退火算法^[1-2]、蚁群算法^[3]、遗传算法^[4]、拉格朗日松弛算法^[5]等启发式算法为主，这是由于车站到发线运用方案编制问题本质上是NP难题(non-deterministic polynomial, NP-Hard)问题^[5].国外与车站到发线运用方案编制问题相关的研究可参考文献[6].国外学者主要将车站到发线运用方案编制问题抽象为节点紧模型(node packing model, NPP)^[7]、集合紧模型(set packing model, SPP)^[8]及图着色问题^[9]等经典问题求解，也有国外学者直接使用线性0-1规划模型^[10]或二次0-1规划模型^[11]对车站到发线运用方案编制问题进行描述，同时还有国外学者^[12]设计了模拟现场调度员思路的启发式方法来解决车站到发线运用方案编制问题.国外学者的研究主要包括最小化到发线使用成本^{[8, 11]}、最大化车站通过能力^[7]及最小化列车到达和出发晚点时间^[12]等，所采用的算法以特殊设计的分枝定价算法^[7-8]及分枝定界定价算法^[11]为主.

国内外学者除对如何合理、高效地编制车站计划到发线运用方案进行了大量研究工作，也有一部分学者对到发线运用方案调整问题进行了研究.王栋^[13]阐述了到发线运用计划调整的可行措施，包括改变列车停靠到发线、列车到达和出发时间及列车到发线占用时间等，并建立了对应于4种优化指标下的实时调整模型.乔瑞军^[14]以列车对到发线使用偏好为首要目标、以列车实际到发时间与理想到发时间的偏离程度为次要目标，建立了列车延误情况下的铁路客运站到发线运用方案调整优化模型，并设计了先考虑到发线运用、后考虑列车到发时间的分步求解算法.朱昌锋^[15]分析了到发线运用方案实时调整对于辅助列车调度员工作的必要性，并提出了基于滚动时域的到发线运用方案动态调整策略.

与前人的研究工作相比，本文主要有以下3个方面的贡献.首先，考虑了在列车大量晚点到达的情况下，如何在短时间内对列车的到达和出发时间以及列车所分配到发线进行综合优化调整，以保证列车运行安全和尽快恢复列车的正常运行秩序; 其次，采用0-1变量描述列车占用离散的铁路到发线时空资源的冲突关系，从而避免了大M法中复杂的列车占用到发线先后顺序变量; 最后，基于铁路到发线时空资源占用冲突分步求解的思路，设计了高效的遗传模拟退火算法以快速得到问题的满意解，并通过实例验证了模型和算法的有效性.

本文首先分析了铁路到发线资源的离散化时空描述方法，在此基础上以列车加权总晚点时间与到发线使用费用之和最小为优化目标，以保证列车运行安全和满足列车在站到发作业要求为约束条件，建立了求解客运站到发线运用方案调整问题的线性0-1规划模型，并设计了遗传模拟退火算法对模型进行求解，从而解决了客运站到发线运用方案调整问题.

1 问题分析 1.1 铁路到发线资源的时空描述

铁路客运站到发线资源是具有时间和空间双重属性的二维资源.对于到发线运用问题，客运站拥有的空间资源集合为其到发线集合，时间资源为问题所研究的时间段.令以时间间隔Δτ为单位对所研究时段$ \mathscr{T}$离散化后，共有|T|个时间间隔，|T|=[$ \mathscr{T}$/Δτ]，到发线数量为|I|，则客运站的到发线资源可描述为二维资源矩阵X.

$ \mathit{\boldsymbol{X}} = \left[ {{x_{i,t}}} \right] = \left[ {\begin{array}{*{20}{c}} {{x_{1,1}}}&{{x_{1,2}}}& \cdots &{{x_{1,\left| T \right|}}}\\ {{x_{2,1}}}&{{x_{2,2}}}& \cdots &{{x_{2,\left| T \right|}}}\\ \cdots & \cdots & \cdots & \cdots \\ {{x_{\left| I \right|,1}}}&{{x_{\left| I \right|,2}}}& \cdots &{{x_{\left| I \right|,\left| T \right|}}} \end{array}} \right] $

式中:x_{i, t}表示到发线资源(i, t)的状态.

$ {x_{i,t}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 到发线资源\;i,t\;被使用\\ 到发线资源\;i,t\;未被使用 \end{array} \end{array}} \right. $

将到发线资源离散化后，可以对列车占用和腾空到发线的过程进行更加准确、直观的描述.对于如图 1a所示包含4条到发线、2条正线的铁路客运站A，有5列列车在1h内在客运站进行作业，列车对到发线资源的占用包括列车在被分配到发线上从接车开始到作业完毕再到出清到发线的时间段，其运行如图 1b和图 1c所示.以5 min为时间间隔为例对到发线时空资源进行离散化，则该客运站在该运行图下资源使用情况可描述如图 2a，其到发线资源矩阵X_A可描述如图 2b.

根据以上定义，列车在站作业过程对到发线资源占用有如下特征：

(1) 列车使用的唯一性特征.列车一次作业只能使用唯一的一条到发线;

(2) 到发线资源一次性使用特征.同一到发线资源元素最多只能被一次作业使用，即x_{i, t}≤1;

(3) 连续使用特征.列车在使用到发线时将至少使用1个到发线资源，当使用多个时，到发线资源总是在时间上被连续使用，如某列车从时间t开始使用到发线i，且总使用时间间隔数为Δt时，x_{i, t}=x_{i, t+1}=x_{i, t+2}=…=x_{i, t+Δt}.

1.2 铁路到发线运用问题分析

铁路客运站一般通过编制到发线运用方案来合理使用到发线资源，方便旅客乘降.但当发生列车大量晚点时，原有的到发线运用方案已不能适应列车的到发作业要求，导致客运站到发线能力紧张，从而必须将列车运行计划与客运站到发线运用方案综合起来进行优化调整.因此，本文研究在固定数量到发线的客运站中，多列不同等级的列车由于不可抗拒原因晚点到达客运站时，如何合理调整客运站到发线运用方案和列车运行计划，以保证列车运行安全和尽快恢复列车正点运行.

根据列车占用到发线时空资源的特征，在调整到发线运用方案时，要考虑列车占用到发线的唯一性和连续性.此外，为满足旅客的出行方便和乘降作业要求，一般情况下被调整列车的实际到达和出发时间应分别不早于其计划到达和出发时间，并保证被调整列车的运行安全.在满足以上条件的基础上，考虑不同列车等级和列车对到发线的使用要求，实现在保证列车运行安全的同时，充分利用客运站通过能力，最小化晚点发生后列车加权总晚点时间与到发线使用费用之和.

2 模型构建 2.1 参数及变量说明 2.1.1 参数说明

参数汇总见表 1.如非特别提及，所有与时间相关的参数和变量的取值均为时间间隔Δτ的整倍数.

2.1.2 变量说明

对任意列车l、k (l, k∈L)、任意一条到发线i (i∈I)和任意时刻t (1≤t≤M_T)，模型定义如下：

(1) 到发线选择变量

$ {w_{l,i}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 列车\;l\;选择了到发线\;i\\ 列车\;l\;未选择到发线\;i \end{array} \end{array}} \right. $

$ {z_{l,k}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 列车\;l\;与列车\;k\;选择了同一条到发线\\ 列车\;l\;与列车\;k\;未选择同一条到发线 \end{array} \end{array}} \right. $

(2) 列车占用到发线状态变量x_{l, i, t}

$ {x_{l,i,t}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 时间\;t\;时,列车\;l\;正在占用到发线\;i\\ 时间\;t\;时,列车\;l\;未占用到发线\;i \end{array} \end{array}} \right. $

(3) 为描述列车的到达、出发过程，定义了到发线使用状态变量u_{l, i, t}和到发线腾空状态变量v_{l, i, t}，分别表示列车l接车到达和发车离开所导致的到发线状态.

$ {u_{l,i,t}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 时间\;t\;时,列车\;l\;尚未到达到发线\;i\\ 时间\;t\;时,列车\;l\;已经到达到发线\;i \end{array} \end{array}} \right. $

$ {v_{l,i,t}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 时间\;t\;时,列车\;l\;已经腾空到发线\;i\\ 时间\;t\;时,列车\;l\;尚未腾空到发线\;i \end{array} \end{array}} \right. $

由x_{l, i, t}、u_{l, i, t}和v_{l, i, t}的定义可知，这三者存在关系如下：

$ x_{l, i, t}=1-\left(u_{l, i, t}+v_{l, i, t}\right) $

(1)

例如对于图 1示例客运站A，当列车l在时刻5占用下行到发线5并在时刻20离开，上述3个变量u_{l, i, t}、v_{l, i, t}和x_{l, i, t}对于该过程描述的取值分别如图 3所示.

(4) 列车到达和出发先后顺序变量

$ {\lambda _{l,k}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 列车\;l\;在列车\;k\;之前到达客运站\\ 列车\;l\;在列车\;k\;之后到达客运站 \end{array} \end{array}} \right. $

$ {\mu _{l,k}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} 列车\;l\;在列车\;k\;之前从车站出发\\ 列车\;l\;在列车\;k\;之后从车站出发 \end{array} \end{array}} \right. $

(5) 列车实际到达时间y_{l, a}和列车实际出发时间y_{l, d}

$ y_{l, \mathrm{a}}=M_{\mathrm{T}}-\sum\limits_{i \in I} \sum\limits_{t=1}^{M_{\mathrm{T}}}\left(1-u_{l, i, t}\right) $

(2)

$ y_{l, \mathrm{d}}=M_{\mathrm{T}}-\sum\limits_{i \in I} \sum\limits_{t=1}^{M_{\mathrm{T}}} v_{l, i, t} $

(3)

为保证在同一条到发线上进行到发作业的前后两列车之间满足必要的安全间隔时间，模型假设列车在出发之后仍然占用到发线一段时间，这段时间即为到发线作业安全间隔时间D，因此模型中的列车实际出发时间y_{l, d}为列车腾空到发线的时间y′_{l, d}与到发线安全作业间隔时间D之和.同样地，本文采用的时间范围是M_T，即研究时段$\mathscr{T} $与到发线作业安全间隔时间D之和.

2.2 目标函数

当因部分列车晚点到达客运站而需对到发线运用方案进行调整时，首先应尽量不改变列车的到达和出发时间; 其次，要尽量满足列车对到发线的使用要求，本文所设计目标函数如式(4)所示.式(4)由两项之和构成，第1项为列车加权总晚点时间，其中，列车等级越高则P_l取值越大，且α为第1项的加权系数; 第2项为到发线使用费用.

$ \begin{array}{*{20}{c}} {\min z = \alpha \sum\limits_{l \in L} {{P_l}} \left[ {\left( {{y_{l,{\rm{a}}}} - {t_{l,{\rm{a}}}}} \right) + } \right.}\\ {\left( {{y_{l,{\rm{d}}}} - {t_{l,{\rm{d}}}} - D} \right)] + \sum\limits_{l \in L} {\sum\limits_{i \in {I_l}} {{w_{l,i}}} } {c_{l,i}}} \end{array} $

(4)

2.3 约束条件

由到发线时空资源特征和列车在站作业过程特征，客运站到发线运用方案调整问题需服从到发线占用唯一性、到发线持续作业、到发线冲突、车站追踪间隔时间、列车在站作业时间和列车到发时间等6类主要约束条件以保证列车运行安全和满足列车对到发线的使用要求.

(1) 到发线占用唯一性约束

$ \sum\limits_{i \in I_{l}} w_{l, i}=1, \quad \forall l \in L $

(5)

$ w_{l, i}=0, \quad \forall l \in L, i \in\left(I-I_{l}\right) $

(6)

式(5)和式(6)保证列车l只在可选的到发线集合中选择唯一一条的到发线进行作业.

(2) 到发线冲突约束

$ \sum\limits_{l \in L} x_{l, i, t} \leqslant 1, \quad \forall i \in I, \quad \forall 1 \leqslant t \leqslant M_{\mathrm{T}} $

(7)

式(7)保证任意一条到发线在任一时刻均最多只有一列车占用.

(3) 到发线持续作业约束

$ \begin{array}{*{20}{c}} {{u_{l,i,t}} \ge {u_{l,i,t + 1}} + {w_{l,i}} - 1,\quad \forall l \in L,}\\ {\forall i \in I,\forall 1 \le t < {M_{\rm{T}}}} \end{array} $

(8)

$ \begin{array}{*{20}{c}} {{v_{l,i,t}} \le {v_{l,i,t + 1}} - {w_{l,i}} + 1,\quad \forall l \in L,}\\ {\forall i \in I,\forall 1 \le t < {M_{\rm{T}}}} \end{array} $

(9)

$ \begin{array}{*{20}{c}} {{u_{l,i,t}} \le {u_{l,i,t + 1}} + {w_{l,i}},\quad \forall l \in L,}\\ {\forall i \in I,\forall 1 \le t < {M_{\rm{T}}}} \end{array} $

(10)

式(8)~式(10)通过保证u_{l, i, t}和v_{l, i, t}取值的连续性来实现列车在某一条到发线上的持续作业.

(4) 车站追踪间隔时间约束

$ \begin{array}{l} {y_{l,{\rm{a}}}} - {y_{k,a}} \ge \left( {1 - {z_{l,k}}} \right){h_a} + {z_{l,k}}D - {\lambda _{l,k}}M,\\ \forall l,k \in L:l \ne k,{\pi _l} = {\pi _k} \end{array} $

(11)

$ \begin{array}{l} {y_{l,{\rm{d}}}} - {y_{k,d}} \ge \left( {1 - {z_{l,k}}} \right){h_d} + {z_{l,k}}D - {\mu _{l,k}}M,\\ \forall l,k \in L:l \ne k,{\pi _l} = {\pi _k} \end{array} $

(12)

$ \begin{array}{l} {z_{l,k}} \ge {w_{l,i}} + {w_{k,i}} - 1,\\ \forall l,k \in L,\forall i \in {I_l} \cap {I_k}:k > l,{\pi _l} = {\pi _k} \end{array} $

(13)

$ z_{l, k}=z_{k, l}, \quad \forall l, k \in L : k>l, \pi_{l}=\pi_{k} $

(14)

$ {\lambda _{l,k}} + {\lambda _{k,l}} = 1,\quad \forall l,k \in L:k > l,{\pi _l} = {\pi _k} $

(15)

$ \mu_{l, k}+\mu_{k, l}=1, \quad \forall l, k \in L_{ :} k>l, \pi_{l}=\pi_{k} $

(16)

式(11)和式(12)保证同方向到达与出发的任意两列车间满足车站到达和出发追踪间隔时间要求公式(13)通过w_{l, i}和w_{k, i}的取值来确定列车l和列车k是否使用同一条到发线.式(14)~式(16)根据列车l和列车k之间的先后关系，分别对z_{l, k}、λ_{l, k}和μ_{l, k}的取值进行了限制.

(5) 列车在站作业时间约束

$ \sum\limits_{t=1}^{M_{\mathrm{T}}} x_{l, i, t} \geqslant w_{l, i} \times\left(\Delta_{l}+D\right), \quad \forall l \in L, \forall i \in I $

(17)

如果列车l占用到发线i，则列车在到发线i上的停留时间必须不小于列车计划停站时间与到发线作业安全间隔时间之和.

(6) 列车到达和出发时间约束

$ {y_{l,{\rm{a}}}} \ge {t_{l,{\rm{a}}}},\quad \forall l \in L $

(18)

$ {y_{l,{\rm{d}}}} \ge {t_{l,{\rm{d}}}} + D,\quad \forall l \in L $

(19)

$ {y_{l,{\rm{d}}}} \ge {y_{l,{\rm{a}}}} + {\Delta _l} + D,\quad \forall l \in L $

(20)

式(18)保证列车实际到达时间不小于列车计划到达时间; 式(19)保证列车实际出发时间不小于列车计划出发时间与到发线安全作业间隔时间之和; 式(20)保证列车实际停站时间不小于计划停站时间与到发线作业安全间隔时间之和.

第(1)(3)组约束分别对应了到发线时空资源三特征，第(4)(6)组约束为列车在站作业过程约束.除此之外，模型还需满足如下基本条件.

(1) 初始条件.在模型开始的初始时刻，式(21)初始化u_{l, i, t}值均为1，式(22)初始化v_{l, i, t}值均为0，即在初始时刻既没有列车到达客运站也没有列车从客运站出发.式(23)~式(25)分别固定在列车晚点发生之前到达客运站的部分列车的占用到发线、到达客运站时间以及客运站出发时间.式(26)和式(27)分别更新列车在开始晚点后预计到达客运站及从客运站出发的时间.

$ u_{l, i, 1}=1, \quad \forall l \in L, \forall i \in I $

(21)

$ v_{l, i, 1}=0, \quad \forall l \in L, \forall i \in I $

(22)

$ {w_{l,i}} = {q_{l,i}},\quad \forall l \in L,\forall i \in I:{t_{l,{\rm{a}}}} < S $

(23)

$ y_{l, \mathrm{a}}=t_{l, \mathrm{a}}, \quad \forall l \in L : t_{l, \mathrm{a}}<\mathrm{S} $

(24)

$ y_{l, \mathrm{d}}=t_{l, \mathrm{d}}, \quad \forall l \in L : t_{l, \mathrm{a}}<S $

(25)

$ t_{l, \mathrm{a}}=t_{l, \mathrm{a}}^{1}, \quad \forall l \in L_{1} $

(26)

$ t_{l, \mathrm{d}}=t_{l, \mathrm{d}}^{1}, \quad \forall l \in L_{1} $

(27)

(2) 变量取值

$ w_{l, i}=\{0,1\}, \quad \forall l \in L, \forall i \in I $

(28)

$ \begin{array}{l} {u_{l,i,t}},\;\;\;{v_{l,i,t}} = \{ 0,1\} ,\quad \forall l \in L,\forall i \in I,\\ \forall 1 \le t \le {M_{\rm{T}}} \end{array} $

(29)

$ \begin{array}{l} {z_{l,k}},{\lambda _{l,k}},{\mu _{l,k}} = \left\{ {0,1} \right\},\;\;\;\;\forall l,k \in L:l \ne k,\\ \;\;\;\;{\pi _l} = {\pi _k} \end{array} $

(30)

式中：x_{l, i, t}、y_{l, a}和y_{l, d}是为便于表示模型而引入的中间变量，其值均可由u_{l, i, t}和v_{l, i, t}的取值推导得到.

2.4 有效不等式

有效不等式是暗含在前文模型约束条件中的约束关系，为提高模型求解速度，在模型中引入如下有效不等式.

$ u_{l, i, t} \geqslant 1-w_{l, i}, \quad \forall l \in L, \forall i \in I, \forall 1 \leqslant t \leqslant M_{\mathrm{T}} $

(31)

$ v_{l, i, t} \leqslant w_{l, i}, \quad \forall l \in L, \forall i \in I, \forall 1 \leqslant t \leqslant M_{\mathrm{T}} $

(32)

$ x_{l, i, t} \leqslant w_{l, i}, \quad \forall l \in L, \forall i \in I, \forall 1 \leqslant t \leqslant M_{\mathrm{T}} $

(33)

$ \begin{array}{l} {x_{l,i,t}} = 0,\;\;\;\;\forall l \in L,\forall i \in I,\forall t < {t_{l,{\rm{a}}}}\;或\\ \;\;\;\;\;\;t > {t_{l,{\rm{d}}}} + {\Delta _{\max }} + D \end{array} $

(34)

式(31)~式(33)的原理类似，结合图 3能对这三个公式有更加直观的理解.以式(31)为例说明，当列车l占用到发线i时，则式(31)为u_{l, i, t}≥0，为无效约束; 当列车l不占用到发线i时，则式(31)为u_{l, i, t}≥1，即u_{l, i, t}=1.式(34)考虑到当客运站能力紧张，需要将计划或预计占用到发线时间互相重叠的两列车安排到同一条到发线时，其中一列等级相对较低列车的到发时间将被推迟一段时间，这段时间的最大值即为Δ_max+D，而且列车的到发时间只能被推迟，因此可用式(34)限制变量x_{l, i, t}在t < t_{l, a}或t>t_{l, d}+Δ_max+D范围内的取值为0.

式(1)~式(34)即构成了客运站到发线运用与列车运行调整协同优化问题的线性0-1规划模型，采用商业优化软件CPLEX对模型进行求解，以验证模型的正确性.同时，为提高问题求解效率，设计了遗传模拟退火算法^[16].

3 遗传模拟退火算法 3.1 染色体编码

染色体编码采用一维实数编码的形式，每个染色体的长度为列车数量|L|，染色体的基因按照列车计划或预计到达时间由小到大的顺序进行编号，每个基因值的取值范围均为[1, |I|].每个染色体都对应一个到发线分配方案，如图 4所示.

3.2 生成初始种群

采用如下的初始种群个体生成策略：

(1) 固定在列车晚点发生之前到达客运站的列车所使用的到发线，所分配到发线为初始到发线运用方案中这部分列车所使用的到发线;

(2) 对于下行到发线，将剩余未固定到发线的下行列车随机地平均分配到下行到发线上; 对于上行到发线，执行类似操作;

(3) 重复(1)和(2)，直至所有初始种群个体生成完毕.

3.3 生成可行解

设计的染色体只确定每列列车所要占用的到发线空间资源，而未考虑由于不满足到发线作业安全间隔时间、车站到达追踪间隔时间和车站出发追踪间隔时间等安全作业要求，而引起的3类时间资源冲突.在调整列车的到达和出发时间来消解时间资源冲突时，若冲突是由于不满足到发线作业安全间隔时间和车站到达追踪间隔时间要求而引起的，则需要将列车的到达时间和出发时间调整相同的值; 否则，若冲突是由于不满足车站出发追踪间隔时间而引起，则只需要调整列车的出发时间来消解冲突.

下面对消解由于不满足到发线安全作业间隔时间要求而引起的时间资源冲突的启发式规则进行介绍，消解另外两类时间资源冲突的规则与此类似.

(1) 将所有列车按照计划或预计到达时间由小到大的顺序进行排序，并从1到|L|进行编号;

(2) 根据给定的列车顺序和表 2中的算法疏解列车占用到发线时间资源冲突;

(3) 计算所有列车实际到达和实际出发时间分别相对于计划或预计到达和出发时间的总调整量，该值即为染色体的目标函数值.

3.4 确定适应度函数

适应度函数参考文献[16]中的遗传模拟退火算法部分的适应度函数如下：

$ {f_i}\left( {{t_k}} \right) = \exp \left\{ { - \frac{{f\left( i \right) - {f_{\min }}}}{{{t_k}}}} \right\} $

(35)

式中：t_k表示种群进化到第k代时的温度; f(i)表示第i个染色体的目标函数值; f_min为第k代种群中最小的目标函数值; f_i(t_k)则表示第i个染色体在温度为t_k时的适应度值.

3.5 确定温度下降函数

在确定初始温度T后，采用如式(36)所示温度下降函数进行降温，即

$ {t_k} = T{\alpha ^k} $

(36)

式中：t_k为种群进化到第k代时的温度; α为温度下降速率.在本文所设计的遗传模拟退火算法中，若全局最优个体目标函数值连续n代不发生改变，则将温度提升至T/2.

3.6 遗传操作 3.6.1 邻域搜索

对种群中的每一个染色体进行邻域搜索操作，即随机改变染色体i的任意一个位置的基因值，以产生新的染色体j，计算染色体j的目标函数值f(j)，根据模拟退火算法的Metropolis准则接受或拒绝染色体j^[16].

$ {P_{ij}}\left( {{t_k}} \right) = \min \left\{ {1,\exp \left( { - \frac{{f\left( j \right) - f\left( i \right)}}{{{t_k}}}} \right)} \right\} $

(37)

若P_ij(t_k)大于[0, 1)区间的随机数r₁，则将染色体j替换染色体i.

3.6.2 选择

采用轮盘赌的方法选择父代个体，根据个体适应度值计算累积概率如下：

$ C_{i}=\sum\limits_{k=1}^{i} f_{k} / \sum\limits_{k=1}^{N} f_{k} $

(38)

式中，N为种群规模.产生[0, 1)区间的随机数r₂，若r₂∈(C_i, C_j)，则个体j被选择作为父代.本文采用精英保留策略，即种群中适应度值最高的个体不经过交叉、变异操作而直接保留至子代，因此，在选择操作中也不能选择该个体.同时，为避免算法过早收敛于局部最优解，在选择操作中限制个体连续被选中作为父代.

3.6.3 交叉

每次随机选择两个父代个体，并产生[0, 1)区间的随机数r₃，若r₃大于或等于交叉率，则不进行交叉操作，将两个父代个体直接保留至子代; 否则，采用两点交叉算子进行交叉.

3.6.4 变异

对于染色体的每一个基因，若该基因所对应的列车不是在列车晚点发生之前到达客运站，则产生[0, 1)区间的随机数r₄.若r₄大于或等于变异率，则不进行变异操作; 否则，随机为该基因分配一条不同的到发线.

4 算例分析

图 5所示客运站中有5条下行到发线及下行正线用于接发下行列车，有4条上行到发线及上行正线用于接发上行列车.取时间间隔Δτ为1 min，在16:00-22:00时段内有70列上行和下行列车计划在该客运站内进行到发作业，将列车的计划到达t_{l, a}和出发时间t_{l, d}转化为以分钟为单位且从时刻1开始的时间，根据t_{l, a}和t_{l, d}来推算列车到发线计划作业时间Δ_l，并用数值1-3对列车等级P_l进行赋值，如表 3所示.客运站计划到发线使用情况如表 4所示，相应的计划到发线运用方案如图 6所示.不同方向、不同等级的列车使用客运站不同到发线的费用如表 5所示，“—”表示到发线不能被该方向的列车使用.

假设该客运站从18：38时刻得知有6列下行列车和4列上行列车将晚点到达，已知这些列车晚点后预计到达客运站的时间，由此可以推算出这些列车的到达晚点量、预计到达和出发时间如表 6所示.由表 2可知，到发线计划作业时间的最大值Δ_max为43 min，研究时段长度T为360 min，取到发线作业安全间隔时间D为6 min，因此M_T为366 min，取车站到达追踪间隔时间和车站出发追踪间隔时间均为5 min.同时，设置目标函数第一项的加权系数α为200.

以表 3~表 6中的数据及其他已知参数作为模型输入，在CPU为Intel(R) Core(TM) i7-5600U 2.6 GHZ、内存为12G的电脑上，采用C#编程语言调用商业优化软件IBM ILOG CPLEX 12.7.0求解算例模型，CPLEX的相关参数均为默认值.CPLEX在运行679 s后求得问题最优解，问题最优目标函数值为17 059.经调整后，11列车的到达时间或出发时间被推迟，以满足到发线冲突约束和车站追踪间隔时间约束，如表 7所示，且有13列车所使用的到发线发生改变.模型所求得的调整后的到发线使用情况如表 8所示，将调整后的到发线使用情况绘制成图后如图 7所示.由图 7可以看出，同一条到发线上相邻两列车的间隔时间均不小于到发线作业安全间隔时间，且不同到发线上的同向列车间均满足车站追踪间隔时间约束.

为提高模型的求解效率，采用所设计的遗传模拟算法对以上算例进行求解.算法的各项参数设置为：种群规模N为50个，种群进化代数为300代，交叉率为0.98，变异率为0.05，初始温度T为80 000 ℃，温度下降速率为0.9，当前世代最优目标函数值最多连续n=5代不发生变化后，重新设置温度为T=40 000 ℃.采用C++语言编程实现遗传模拟退火算法，程序共运行20次，平均运行时间为27 s，所求得的平均目标函数值为17 612，与最优目标函数值17 059相差的百分比为3.24%，可见算法能在较短的时间内得到较优的满意解.算法某次运行的收敛过程如图 8所示，由图 8可以看出，种群在进化到第70代时，目标函数值即接近最优目标函数值，可见算法有较好的收敛性.同时，为测试不同目标函数加权系数α取值对CPLEX和遗传模拟退火算法求解效果的影响，将α从40开始以40为步长逐渐增加至440，依次采用CPLEX和遗传模拟退火算法对问题模型进行求解，求解结果如表 9所示，其中遗传模拟退火算法参数设置不变，并且取20次求解结果的平均值.从表 9可以看出，CPLEX和遗传模拟退火算法求解得到的目标函数值均随着α增大而不断增大，并且CPLEX求解时间在329 s764 s内波动，而遗传模拟退火算法的求解时间稳定在27 s29 s范围内.此外，遗传模拟退火算法求得的平均目标函数值与CPLEX最优目标函数值相差的百分比仅在2.82%~5.10%内波动.从遗传模拟退火算法的求解时间和求解质量可以看出，本文设计的遗传模拟退火算法有较高的稳定性，适合应用于铁路实际调度指挥工作中.

5 结论

铁路客运站到发线运用方案调整对于保证列车运行安全、提高到发线运用效率和尽快恢复列车正点运行具有重要意义.客运站到发线运用方案调整问题从根本上来说是到发线时空资源的分配与调整问题，本文使用离散化的到发线时空资源变量针对问题建立了线性0-1规划模型并设计了遗传模拟退火算法进行求解，所提出方法具有如下特征：

(1) 离散化的到发线时空资源变量从微观上描述了到发线使用过程原理，基于此定义，问题模型约束精炼到了到发线时空资源使用约束和列车在站作业过程两大类;

(2) 模型综合考虑了列车运行计划和列车对到发线的使用要求，在此基础上对客运站到发线运用方案进行调整，以得到尽量不改变列车运行计划条件下的新的到发线运用方案，而若由于客运站到发线能力不足，导致列车运计划被改变，其改变量可以作为列车调度员随后进行列车运行调整的依据;

(3) 离散化变量的引入使得模型变量规模较大，引入的有效不等式通过对无效约束的消除等提高了模型效率，使其能使用主流优化软件进行求解;

(4) 通过实例验证表明，结合问题特点而设计的遗传模拟退火算法可以快速对问题进行求解，实现了客运站到发线运用方案的实时调整.

本文所设计的遗传模拟退火算法采用了到发线时间和空间资源占用分步求解的思路，未来将考虑到发线时间和空间资源同时分配的更加有效的启发式算法.此外，本文仅考虑了适用于客运站的到发线运用方案调整模型与算法，并未考虑包含复杂调车作业的技术站，在下一步研究中将进一步研究考虑调车作业的建模方法以及技术站到发线运用方案调整问题的模型与求解方法.