彭其渊， 张永祥， 鲁工圆， 李文新， 石 铁

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

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

车站到发线运用方案编制问题是近年来国内外学者研究的热点问题.国内学者一般使用线性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 铁路到发线资源的时空描述

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

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

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

a 示例车站A布置示意

b A站某时段下行列车运行c A站某时段上行列车运行

图1 客运站A布置及列车运行

Fig.1Layout and train diagrams of passengerstation A

a 到发线资源使用情况

b 到发线资源矩阵

Fig.2 Arrival and departure track resource usage and its time-space resource matrix

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

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

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

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

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

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

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

2 模型构建

2.1 参数及变量说明

2.1.1参数说明

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

表1 参数说明

2.1.2变量说明

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

(1) 到发线选择变量

(2) 列车占用到发线状态变量xl,i,t

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

由xl,i,t、ul,i,t和vl,i,t的定义可知，这三者存在关系如下：

xl,i,t=1-(ul,i,t+vl,i,t)

(1)

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

a ul,i,t

b vl,i,t

c xl,i,t=1-(ul,i,t+vl,i,t)

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

(5) 列车实际到达时间yl,a和列车实际出发时间yl,d

(2)

(3)

2.2 目标函数

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

(4)

2.3 约束条件

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

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

(5)

wl,i=0, ∀l∈L,i∈(I-Il)

(6)

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

(2) 到发线冲突约束

(7)

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

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

ul,i,t≥ul,i,t+1+wl,i-1, ∀l∈L,

∀i∈I,∀1≤t

(8)

vl,i,t≤vl,i,t+1-wl,i+1, ∀l∈L,

∀i∈I,∀1≤t

(9)

ul,i,t≤ul,i,t+1+wl,i, ∀l∈L,

∀i∈I,∀1≤t

(10)

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

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

yl,a-yk,a≥(1-zl,k)ha+zl,kD-λl,kM,

∀l,k∈L:l≠k,πl=πk

(11)

yl,d-yk,d≥(1-zl,k)hd+zl,kD-μl,kM,

∀l,k∈L:l≠k,πl=πk

(12)

zl,k≥wl,i+wk,i-1,

∀l,k∈L,∀i∈Il∩Ik:k>l,πl=πk

(13)

zl,k=zk,l, ∀l,k∈L:k>l,πl=πk

(14)

λl,k+λk,l=1, ∀l,k∈L:k>l,πl=πk

(15)

μl,k+μk,l=1, ∀l,k∈L:k>l,πl=πk

(16)

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

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

(17)

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

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

yl,a≥tl,a, ∀l∈L

(18)

yl,d≥tl,d+D, ∀l∈L

(19)

yl,d≥yl,a+Δl+D, ∀l∈L

(20)

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

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

ul,i,1=1, ∀l∈L,∀i∈I

(21)

vl,i,1=0, ∀l∈L,∀i∈I

(22)

wl,i=ql,i, ∀l∈L,∀i∈I:tl,a

(23)

yl,a=tl,a, ∀l∈L:tl,a

(24)

yl,d=tl,d, ∀l∈L:tl,a

(25)

(26)

(27)

(2) 变量取值

wl,i={0,1}, ∀l∈L,∀i∈I

(28)

ul,i,t,vl,i,t={0,1}, ∀l∈L,∀i∈I,

∀1≤t≤MT

(29)

zl,k,λl,k,μl,k={0,1}, ∀l,k∈L:l≠k,

πl=πk

(30)

式中：xl,i,t、yl,a和yl,d是为便于表示模型而引入的中间变量，其值均可由ul,i,t和vl,i,t的取值推导得到.

2.4 有效不等式

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

ul,i,t≥1-wl,i, ∀l∈L,∀i∈I,∀1≤t≤MT

(31)

vl,i,t≤wl,i, ∀l∈L,∀i∈I,∀1≤t≤MT

(32)

xl,i,t≤wl,i, ∀l∈L,∀i∈I,∀1≤t≤MT

(33)

xl,i,t=0, ∀l∈L,∀i∈I,∀t

t>tl,d+Δmax+D

(34)

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

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

3 遗传模拟退火算法

3.1 染色体编码

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

图4 染色体编码示意图

3.2 生成初始种群

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

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

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

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

3.3 生成可行解

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

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

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

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

表2 列车占用到发线时间资源冲突疏解算法

Tab.2 Conflicts resolving algorithm for the occupancy of arrival and departure track time resources

每列车i(1≤i≤|L|) 每列车j(1≤j

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

3.4 确定适应度函数

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

(35)

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

3.5 确定温度下降函数

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

tk=Tαk

(36)

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

3.6 遗传操作

3.6.1邻域搜索

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

(37)

若Pij(tk)大于[0,1)区间的随机数r1，则将染色体j替换染色体i.

3.6.2选择

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

(38)

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

3.6.3交叉

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

3.6.4变异

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

4 算例分析

图5 客运站拓扑结构

Fig.5 Layout of the passenger stations

Fig.6 Arrival and departure track utilization scheme between 16:00 and 22:00

假设该客运站从18：38时刻得知有6列下行列车和4列上行列车将晚点到达，已知这些列车晚点后预计到达客运站的时间，由此可以推算出这些列车的到达晚点量、预计到达和出发时间如表6所示.由表2可知，到发线计划作业时间的最大值Δmax为43 min，研究时段长度T为360 min，取到发线作业安全间隔时间D为6 min，因此MT为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可以看出，同一条到发线上相邻两列车的间隔时间均不小于到发线作业安全间隔时间，且不同到发线上的同向列车间均满足车站追踪间隔时间约束.

表3 16:0022:00时段到发列车

表4 16:0022:00时段计划到发线使用情况

表5 不同方向、不同等级列车使用客运站到发线费用

表6 晚点列车的预计到达和出发时间

表7 被推迟列车的到达时间和出发时间推迟量

表8 调整后16:0022:00时段到发线使用情况

表9 不同目标函数加权系数α取值下CPLEX与遗传模拟退火算法求解结果

Tab.9 Solving results of CPLEX and the Genetic Algorithm-Simulated Annealing Hybrid Algorithm with different objective function weighting coefficients

目标函数加权系数αCPLEX遗传模拟退火算法目标函数值求解时间/s目标函数值求解时间/s与CPLEX相差百分比/%403 9397404 140285.10807 2195897 507283.9912010 49976410 914283.9516013 78344714 233283.2620017 05967917 612273.2424020 33938820 951273.0128023 61936024 342273.0632026 89959627 681282.9136030 17932931 069282.9540033 45934034 402292.8244036 73941237 808282.91

5 结论

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

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

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

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

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

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