薛 锋，陈崇双，户佐安

1.西南交通大学 交通运输与物流学院，成都610031

2.北京交通大学 轨道交通控制与安全国家重点实验室，北京100044

1 引言

铁路编组站的调度指挥工作是通过编制与执行阶段计划来完成的。阶段计划（3～4 小时）是班计划（12 小时）分阶段的具体安排，主要解决本阶段内所有列车的出发计划、调机运用计划和到发线运用计划三个决策问题，其中第一个子问题确定出发列车的编组内容和车流来源（即配流），第二个子问题确定每台调机的调车工作内容和时段，第三个子问题安排到发列车占用到发线计划。只有合理运用调机，正确地组织解编作业，才能加速调车场的车流集结过程，缩短车辆在站停留时间，实现列车的出发计划，因而调机运用与列车配流密不可分，而第三个问题则相对独立[1]。如何合理地运用调机全面完成配流计划，是值得研究的问题。在技术站中，由于区段站调机设备少，往往使接续时间合理的车流因调机的繁忙而难于实现，一些专家学者在研究区段站的配流问题时都紧密结合调机来建模和求解[2-3]。编组站虽然调机配备较多，且解体和编组作业由不同的调机担当，但仍需以配流计划为核心，合理决策，使列车配流与调机运用相协调。本文根据编组站的实际作业特点，构造了配流与调机运用的协调优化模型，以期实现编组站车流资源的合理分配。

2 参数定义

设T0为阶段计划开始时刻，在阶段计划时间内的出发列车的车流来源包括[4]：

（1）T0时刻已解入调车场集结等待编组的现车，可视作1 列到达列车。

（2）T0时刻到达场内待解列车车流。

（3）阶段时间内预计将要到达列车车流。

（4）交换场等待转场分解的车组，每转场一次视作1 列到达列车。

（5）货场、专用线、车辆段取回待分解的本站作业车、修竣车，每取回一次视作到达一列。

设本阶段到达解体列车数为n，到达解体列车（含调车场现车）集合按到达时间先后记作DD={dd0,dd1,…,ddi,…,ddn}；将要编组出发的列车（不包括已编完的待发列车）数为m，编组出发列车集合按出发时间先后记作CF={cf1,cf2,…,cfj,…,cfm}；车站共有K个编组去向，构成编组去向集合QX={1,2,…,K}；车站共有D台调机，构成集合DJ={1,2,…,D}。对于到达解体列车ddi(i=1,2,…,n，其到达时刻为Tidd；开始解体时刻为Tijt；列车ddi中具有本站编组去向号k(1 ≤k≤K)的车数为ddik；对于出发列车cfj(j=1,2,…,m)，其出发时刻为；开始编组时刻为；已编组列车cfj中具有本站编组去向号k(1 ≤k≤K)的车数为cfjk。列车解体作业时间标准为tjt，编组作业时间标准为tbz，到达列车技术作业时间标准为tdd，出发列车技术作业时间标准为tcf；表示调机d的第s(1 ≤s≤Sd)项固定作业的开始时刻，其中Sd为调机d总的固定作业项数；表示调机d的第s项固定作业的作业时间；出发列车cfj的满轴车数为mj，配流时的方案值为Fj。

定义布尔变量：φid、φjd、λij、βj。若到达列车ddi(i=1,2,…,n)由调机d(1 ≤d≤D)解体，则φid取1，否则为0；若出发列车cfj(j=1,2,…,m) 由调机(1 ≤d≤D) 编组，则φjd取1，否则为0；若出发列车cfj能接续到达列车ddi，则λij取1，否则为0；若Fj≥0，则βj取1，否则为0。

定义决策变量：cfijk表示到达列车ddi(i=0,1,…,n)配入出发列车cfj(j=1,2,…,m)编组去向号k(1 ≤k≤K)的车数。

3 模型构造

3.1 配流约束

设M表示充分大的正数，则配流的约束条件为：

式（1）界定了出发列车中同一去向车流的配流上限；式（2）表示出发列车的基本去向组辆数约束；式（3）表示车流接续时间约束；式（4）表示列车编组辆数约束。

3.2 解体约束

式（5）表示任一列到达解体列车只能由一台调机解体；式（6）表示到达列车解体时须完成到达技术作业；式（7）表示若两列到达列车由同一台调机解体，在时间上不能冲突；式（8）表示双推单溜时，只有当前一列车解体完毕，另一列车才能开始解体；式（9）表示到达列车的解体作业与解体调机的固定作业不冲突。

3.3 编组约束

式（10）表示任一列出发列车只能由一台调机编组；式（11）表示出发列车的最晚编组时刻须满足技术作业时间要求，以保证正点发车；式（12）表示若两列出发列车由同一台调机编组，在时间上不能冲突；式（13）表示2 台调机编组时占用同一牵出线不冲突；式（14）表示出发列车的编组作业与编组调机的固定作业不冲突。

3.4 目标函数

编组站调机运用计划的安排是为列车合理配流服务的，而配流的最终目的是为了确保出发列车的满轴和正点。约束式（1）～式（14）的可行域保证了出发列车的正点，因此目标函数可设定为满轴列车数最多。

s.t. 式（1）～式（14）

式（15）表示尽可能使满轴的出发列车数最多，即欠轴列车数最少。至此，构造了基于列车配流和调机运用约束的协调决策优化模型。一般情况下，编组站解体和编组作业由不同的调机担当，二者在作业互不干扰，具有相对独立性，关键是列车的解体和编组方案决定了出发列车的配流方案，即只有在解体、编组方案确定的情况下，才能实现对配流问题的优化。由于调机的运用和配流方案密切相关，所以确定到达列车的解体顺序方案和出发列车的编组顺序方案需要考虑调机的数量和调机作业方式，解体和编组时刻的具体计算公式可参考文献[5]。

4 模型的遗传算法求解

列车配流和调机运用约束的协调决策优化模型，其复杂性为NP 难题，不可能得到求其最优解的多项式算法。编组站列车配流与调机运用的协调决策问题对算法收敛速度有着较强的实时性要求，需要根据问题的性质提出新的启发式算法。遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与种群内部染色体的随机信息交换机制相结合的优化搜索算法，它已经被成功地引入编组站作业优化领域用于解决大规模组合优化问题[6-8]。本文采用遗传算法，根据运输问题的资源分配特点进行求解[9]。编组站配流和调机运用协调决策问题有其特殊性，需设计有效的编码及适应函数。

4.1 编码及适应值函数

遗传算法编码方法灵活，且无规范的方法，在应用遗传算法求解车列解编排序问题时，由于问题所固有的特殊性，采用传统的二进制方式表示解空间，不仅复杂而且不便于处理不可行解的操作，最方便的编码方式是直接利用列车解编顺序作为基因。设J 为到达列车解体顺序方案，B 为出发列车编组顺序方案。设J 、B 对应的调机特征向量P={p1,p2,…,pu,…,pv}，pu表示解体（或编组）列车ddu（或cfu）的调机编号，v 为解体或编组列车数。

将调机特征向量P 对应的某个解体或编组顺序作为个体，即任一到达列车解体方案J={ddi,dd2,…,ddu,…,ddvJ}，任一出发列车编组顺序B={cfi,cf2,…,cfu,…,cfvB}。显然，J 、B 分别为到达列车或出发列车编号的一个排列。由于列车解编顺序的遗传编码并不能将约束条件表示出来，因此为了获得可行的解体顺序初始群体，可依据解体序号矩阵进行有效编码，限制不可行解的产生，具体的编码过程可参考文献[10]。

对任一解体方案J 和编组方案B 配流时，可根据式（15）计算配流方案中欠轴列车的列数，因此可将目标函数作为适应值函数。由此，适应函数可取：

4.2 算法思路

初始时，出发列车以先发先编的原则进行排序，到达解体列车根据解体序号矩阵随机产生若干个v 阶解体顺序排列作为初始群体，采用联赛选择规则对初始种群进行筛选，找出若干优化解。交叉规则采用非常规码常规交配法，变异规则采用交换变异算子，从解体序号矩阵限制的列车序号中随机选择两个变异点，按一定的概率进行变异，互相交换两个基因位置。对新个体重新按适应值进行排序，排在最后的染色体性能最差，将其用上一代最优染色体代替。在利用传统遗传算法时，交叉概率pc和变异概率pm在迭代过程中始终不变。在求解本模型时，可取pc和pm随着适应度动态变化，如此当种群各个体适应度趋于一致或趋于最优解时，pc和pm增大；当群体适应度比较分散时，pc和pm减小。由历史最优解体方案，对出发列车依次进行配流，并根据当前配流方案安排解编调机；若出发列车均满轴，则输出配流方案及调机安排，否则根据文献[11]的方法调整编组顺序，重新构造解体序号矩阵。最后以确定迭代代数作为停止准则。算法步骤如下：

步骤1初始化遗传算法相关参数。

步骤2以先发先编的原则进行的出发列车排序为初始条件，构造解体序号矩阵。

步骤3根据解体序号矩阵随机产生若干个v 阶解体顺序排列作为初始群体。

步骤4采用联赛选择规则对群体进行筛选，找出若干优化解。

步骤5根据优化群体对出发列车进行配流，分别计算适应度函数值，记录最优解体顺序，并安排解体调机。

步骤6若出发列车均满轴，则转步骤7，否则进行交叉和变异操作，重新计算适应度函数值，记录本次迭代最优解，将其与历史最优解做比较，若优于历史最优解，则用其替换历史最优解，否则转步骤4。

步骤7按照设定的条件，判断迭代是否终止，若终止，则输出历史最优解，否则转步骤5。

步骤8重新检查出发列车是否均满轴，若满轴，则安排编组调机，同时输出配流方案及解编调机安排，否则调整编组顺序，重新构造解体序号矩阵，转步骤3。

编组站的车流组织工作具有时变性的特征，虽然有很多算法可以得出模型的解，但是花费时间资源太多，这不符合动态调度的要求。动态调度要求优化解必须在一定时间内得到，即使所得解不一定最优，次优也可以接受。解体序号矩阵的构造方法从车流接续时间上保证了遗传算法以此产生的初始群体都为可行解，且变异操作也在解体序号矩阵限制的列车序号中选择，避免了不可行个体的产生。交叉和变异概率的动态变化，使个体产生的配流方案逐步接近全部满轴。因此，由解体序号矩阵产生的群体保证了算法的收敛性。

5 算例

5.1 时间标准及到发车流数据

某编组站列车解体、编组由不同的调机担当，解体、编组调机均为2 台。列车到达作业时间标准为35 min，出发作业时间标准为25 min，列车解体时间标准为25 min，编组作业时间标准为25 min。选取其中一个阶段的到发原始车流数据，见表1 和表2（其中10000 为调车场现车）。

表1 到达列车车流

表2 出发列车车流

5.2 算法结果分析

根据编组站配流问题的特点所改进的遗传算法，采用了增强型的初始种群生产策略，利用解体序号矩阵限制不可行解的产生，减少了遗传算法本身随机性带来的影响，并通过有限制的个体变异操作，避免了变异操作的盲目性，使变异后的种群能向高适应度方向进化，在每次变异后对母子染色体的适应度进行比较，只保留适应度高的个体，从而增强了种群适应度，使算法能够沿着出发列车全部满轴的方向前进，最终达到种群适应度高、运行代数和运行时间少的效果。

在求解配流方案时，在遗传算法中设定种群规模popsize=50，初始交叉率pc=0.8，变异率pm=0.08，最大进化代数根据实例不同设定为50～100 代不等。算法采用VC++6.0 语言编程，在LENOVO 酷睿TM2 计算机上，经过多次测算，结果表明采用遗传算法一般能在30 s 内收敛到最优解（或满意解），其中一次以配流方案中欠轴列车数最少为目标运行得到的配流方案和调机运用方案如表3、表4和表5 所示。将表2 和表3 对比可以看出，出发列车均已满轴。从表4 和表5 的解编调机安排分析可知，到达列车的平均待解时间为36.4 min，出发列车的平均待发时间为41.5 min，若在保证列车均满轴的前提下以待解和待发时间最小为目标，列车的配流方案还有进一步优化的空间。

表3 最终配流方案

表4 解体调机安排

表5 编组调机安排

6 结论

本文构建的基于列车配流和调机运用约束的协调决策优化模型，能够较好地描述编组站站配流和调机运用的协调问题。针对该问题，采用增强型的初始种群生产策略，利用解体序号矩阵限制不可行解的产生，并通过有限制的个体变异操作，使变异后的种群向高适应度方向进化。通过实例验算，表明采用遗传算法能够快速求解出满意的配流方案。在编组站实际工作中，列车预计的到达和出发时间与实际的到达、出发时间会有出入，需要通过人机对话动态调整，以保证系统运算结果的实用性。

[1] 王明慧，赵强.编组站智能调度系统阶段计划优化模型及算法研究[J].铁道学报，2005，27（6）：1-9.

[2] 李文权.铁路区段站日工作计划优化模型及其算法的研究[D].成都：西南交通大学，1997.

[3] 王正彬.区段站阶段计划调整模型与算法研究[D].成都：西南交通大学，2007.

[4] 王慈光.运输模型及优化[M].北京：中国铁道出版社，2004.

[5] 薛锋，罗建，陈崇双.编组站配流中解编时刻参数的计算[J].交通运输工程与信息学报，2010，8（4）：21-27.

[6] 牛惠民，胡安洲.双向编组站车流接续的综合优化[J].铁道学报，1998，20（6）：16-21.

[7] 崔炳谋，马钧培，张朴.编组站进路调度优化算法[J].中国铁道科学，2007，28（2）：100-103.

[8] 刘霆，何世伟，王保华，等.编组站调度计划随机机会约束规划模型及算法研究[J].铁道学报，2007，29（4）：12-17.

[9] 薛锋，罗建.基于遗传算法的动态MC2 运输问题求解[J].计算机工程与应用，2008，44（28）：236-238.

[10] 薛锋，王慈光，张展杰.编组站配流的协调优化算法[J].西南交通大学学报，2010，45（6）：932-937.

[11] 薛锋，王慈光.编组站列车编组顺序的调整方法[J].铁道学报，2007，29（4）：1-5.