运用学习规则求解编组站静态配流问题的研究

景 云，王慈光，王如义，唐建桥

（西南交通大学 交通运输学院，四川 成都 610031）

编组站配流问题研究如何合理地安排列车的解编方案和配流方案，使车流在车站停留时间最短，同时使编组站各项工作平稳、有序地进行，以保证整个路网的畅通[1]。配流问题分为动态配流和静态配流两个阶段。动态配流通过制定列车的解编方案，确定列车解编顺序，初步确定出发列车的车流来源；静态配流则通过确定出发列车具体的编组内容和车流来源得到最终配流方案。由于出发列车编组去向的多样性与交错性，即便列车的解编方案已经确定，车流的接续关系基本明朗，仍然存在多种配流方案，需要进行合理的优化选择[2]。本文将在文献[1]的基础上，设计一种新型网络算法求解静态配流问题。

1 静态配流模型

1.1 目标函数

编组站编制阶段计划的主要目的是为了保证编组站工作的稳定有序，在衔接线路能力足够的情况下尽可能向区间多发列车[3-6]。所以，配流问题的目标函数应为阶段内出发列车所配车辆总数最大，即：

式中：xij表示到达列车 di向出发列车 fj配入的车辆数。

按调度计划，出发列车分为可欠轴列车与不可欠轴列车。对不可欠轴列车，当列车发车时刻没有足够的车流令其满轴，该次列车将停运，线路能力将浪费；对可欠轴列车，在出发时刻应尽可能凑齐满轴[7]。这样配流问题就由较复杂的目标分解为两个较简单的目标，即在保证不可欠轴列车满轴的情况下，使可欠轴列车所配车数最多。

1.2 约束条件

通常情况下，一个阶段内总车流量供求是不平衡的。静态配流问题除了要考虑简单配流问题的约束条件外[2]，还需要考虑以下3个约束条件。

（1）接续时间约束。以D = {d0,d1,d2,…,dn}记为本阶段广义到达列车集合，包括调车场现车、到达场待解列车、本阶段陆续到达的列车、交换场等待转场分解的车组和从专用线取回待分解车组等；以F = { f1,f2,…,fm} 记为本阶段出发列车集合。只有符合接续时间要求的 di才能够提供给 fj所需的车辆。

（2）编组内容约束。到达列车 di中只有与出发列车 fj编组去向相符的车流才能成为 fj的车流来源。

（3）满轴约束。对可欠轴列车，其编成辆数可小于满轴车数；对不可欠轴列车其编成辆数应等于满轴车数。

将静态配流模型看作有时间约束、销量不确定的产销不平衡运输问题，可建立该问题的网络模型。

1.3 静态配流网络模型

由于接续时间约束条件的限制，到发列车之间并不一定能够建立一一对应的关系。将满足接续时间约束条件的到、发列车用弧连接起来，表示 di可以提供给 fj车流，弧的容量即为 di的车辆数，没有用弧连接的到、发列车表示不满足接续时间约束条件。

到达列车中的车流往往不止一个编组去向，将 di中每个组号作为一个中间节点，相当于一列单去向的到达列车，将其与去向相符的出发列车用弧连接起来，没有用弧连接的到、发列车表示不满足编组内容约束条件。

只将符合约束条件的到、发列车之间以弧相连，可以减小问题的规模，在求解的过程中暂不考虑运输费用。由于静态配流所要解决的关键问题是确定出发列车的编组内容(包括编组去向和各去向车数)，至于具体而精确的车流来源并无需明确，故利用文献[8]的化简方法进一步的化简，减小问题的规模，将经过整理后的到达列车重新排列得到 di'。

静态配流问题是产销不平衡的运输问题，为化为平衡运输问题，增加一个虚发点dn'+1。将该发点与可欠轴出发列车用弧连接；增加一个虚收点 fm+1，将该收点与所有到达列车用弧连接。除从 dn'+1吸收的车辆外，fm+1其实就是下一阶段的d0。由此，一个固定费用、产销平衡的运输网络模型就建成了。

2 算法的学习规则

由于大型编组站涉及的变量较多，使用传统的最大流算法较难在合理的时间内求得网络模型的最优解。学习规则是一种用来计算给定 dn'+1时配流方案的方法。通过在 dn'+1每次减小的过程中调用学习规则以判断配流方案的可行性，最终得到虚拟到达列车车辆数最小的配流方案，以求解静态配流问题的网络模型。

2.1 初始化权数

在运输问题的网络模型(图1)中，di'为输入层， fj为输出层，源 s 表示本阶段到达车辆总数，汇 t 表示出发车辆总数，层内元素无弧相连。

图1 静态配流网络模型示例图

联通系数 ρi'j表示输入层与输出层之间是否有弧相连，若有，则 ρi'j=1；若无，则ρi'j=0。权数wi'j表示将 di'分配到 fj的车辆占 di'总车辆的百分比，故如果输入层与输出层之间是联通的，应当满足：

2.2 误差函数

假设输入为(x0,x1,x2,…,xi',…,xn'+1)；期望输出为(r1,r2,…,rj,…,rm+1)，表示出发列车的满轴辆数；实际输出为(y1,y2,…,yj,…,ym+1)，则：

误差函数表示实际输出与期望输出之差，为：

函数值的大小表示出发列车所配车数与满轴车数的偏离程度，如果E(w)= 0，表示所有出发列车都满轴。虚拟出发列车 fm+1起调节车流的作用，吸收本阶段不能编入出发列车的车流，计算误差函数时不考虑 fm+1。

2.3 权值的计算

从一个随机选取的初始权值wi'j开始，在经过每次的学习过程中，沿E(w)下降最快的方向将权值移动一个很小的距离Δwi'j，最终确定权值w使误差函数值达到最小。若学习次数为t，每次学习后权值为wi'j(t)，则：

为实现梯度下降法，需要误差函数关于权重导数的显式表达，单层网络中，权值w为一系列线性方程组，梯度向量为：

导数的计算就网络图而言关于权重wi'j是局部的，基于导数的这一表示，权向量的移动距离为:

式中：η为学习速率参数，η∈( 0,1)。η的取值相当重要，因为η取得太小，则误差下降会非常缓慢，而η取得太大，则会导致发散振荡。

2.4 归一化处理

通过对权值的迭代，新产生的权值并不一定满足约束条件⑵，利用公式:

进行归一化处理，使式⑵成立。

2.5 学习步骤

步骤2：利用式⑶计算yi；利用式⑷计算E(wi'j( t ))。

步骤3：根据式⑺计算权值的改变量Δwi'j；根据式⑸更新权值wi'j( t + 1 )。

步骤4：根据式⑻对wi'j(t +1)进行归一化处理以满足式⑵。

步骤5：若误差函数E(wi'j( t + 1)) ≠ 0，转入步骤2；否则，停止学习，得出权值wi'j。

3 算法过程

在 dn'+1每次减小的过程中都调用学习规则得到一个配流方案，最终求得一个使虚拟到达列车车辆数最小，即出发列车所配车辆总数最大的配流方案，从而求解静态配流问题的网络模型。

3.1 虚拟到达列车初始值

在配流方案中，不可欠轴列车必须满轴，所以虚拟到达列车的车流不必提供给这些列车，dn'+1仅与可欠轴列车以弧相连。由于并非每一对到、发列车都能够建立对应关系，即便是到达列车总辆数大于出发列车总辆数，可欠轴出发列车依然可能欠轴。为使可欠轴出发列车能够满轴，虚拟列车的初始值应当等于可欠轴列车的最大配车数：式中：qj表示 fj能否欠轴，不可欠轴为1，可欠轴为 0。

3.2 配流方案的计算

调用学习规则计算后，若E(w) ≠ 0，表示有不可欠轴列车不满轴，无法得到可行的配流方案，需要回到动态配流阶段重新选择解编方案；若E(w) = 0，表示解编方案是可行解。对于一个可行的解编方案，不可欠轴列车的配车数是一定的，目标函数值的大小取决于可欠轴列车的配车数。在网络模型中，可欠轴列车也要等于满轴辆数，不足的车辆由虚拟到达列车提供，所以虚拟到达列车辆数越大，表示出发列车实际配车数越小。算法就是在调用学习规则保证所有列车都达到满轴的基础上，逐步寻找xn'+1的最小值。将经过第c次迭代后的 xn'+1记为：

式中： δ为迭代步长参数，δ∈( 0,1)。

若在第c次迭代时，误差函数 E(w) ≠ 0，表示 xn'+1下降的过多，有出发列车不满轴，应当增加 xn'+1。

当再次得到E(w) = 0，表示网络模型达到了平衡，所有出发列车都已满轴，且 dn'+1的车辆数最小，目标函数达到最优。此时，配流方案为：

最大配流辆数为：

3.3 算法步骤

步骤1：通过由动态配流得到的解编方案构建静态配流网络模型。

步骤2：建立虚发点与虚收点，对虚拟到达列车 xn'+1赋初值。

步骤3：调用学习规则，判断解编方案的可行性，若不可行则返回动态配流阶段重新寻找解编方案。

步骤4：若误差值E(w) = 0利用公式⑽计算虚拟到达列车辆数，若误差值E(w) ≠ 0利用公式⑾ 计算虚拟到达列车辆数。

步骤5：当重新满足E(w) = 0 时停止迭代，得出权值wi'j。

步骤6：利用式⑿计算列车配流方案，根据式⒀求出最多配流辆数。

4 算例

假设在某编组站一个阶段的配流问题中仅讨论4个去向: a,b,c,d，则到达列车 di与出发列车 fj共有4个组号l ={a,b,c,d}，记表示到达列车 d的l去向i的车组数量；为出发列车 fj的l去向的车组数量。表示第 i 列到达列车到达时刻；表示第 j 列出发列车出发时刻；T解表示解体时间；T编表示编组时间。按照先发先编的原则，经动态配流得到的解体方案为g ={11,32,23,44,55,76,87,68,99,109,1110}；除 f2, f6, f10为摘挂列车可欠轴外，其他列车均不得欠轴；到发列车的信息如表1、表2所示。

经简化后的静态配流网络模型如图2所示，输入层共有16列单去向到达列车和虚拟到达列车 d17，输入层内的字母和数字表示该列列车的编组去向和车辆数；输出层共有10列出发列车和虚拟出发列车f11。

表1 到达列车信息表

表2 出发列车信息表

图2 静态配流网络模型

当r = 40，η = 0.1，δ = 0.05 时，经计算得到的配流方案如下表所示。

表3 出发列车配流方案

该配流方案可使不可欠轴列车均满轴，可欠轴列车配车数最大，阶段内最大发车辆数为392辆，为最优方案。

5 结束语

本文提出的算法利用学习规则使配流方案满足满轴约束条件，通过设立虚拟到达列车将目标函数转化为求虚拟到达列车车辆数最小，以简化网络模型，从而避免利用最大流的方法求解大规模网络模型。算法能够快速、有效地解决大型编组站多列到发列车的静态配流问题，制定配流方案，对带有时间约束、销量不确定的产销不平衡运输问题也是有益的探索。

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

[2] 王慈光. 用表上作业法求解编组站配流问题的研究[J]. 铁道学报，2002，24 (4)：1-5.

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

[4] 何世伟，宋 瑞，朱松年. 编组站阶段计划解编作业优化模型及算法[J]. 铁道学报，1997，19 (3)：1-8.

[5] 何世伟，宋 瑞，胡安洲. 编组站阶段计划刚性与柔性优化的协调研究[J]. 铁道学报，1999，21 (4)：1-8.

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

[7] 薛 锋. 编组站调度系统配流协同优化理论与方法研究[D].成都：西南交通大学，2009.

[8] 王慈光. 编组站静态配流网络模型[J]. 交通运输工程与信息学报，2003，1 (2)：67-71.