重载组合站列车组合方案随机机会规划模型及算法

董世鑫，魏玉光，张进川

(北京交通大学 交通运输学院，北京 100044)

以大秦线为代表，我国重载铁路在铁路网中相对独立，重载线路两端衔接路网中其他线路，车流来源与去向较为复杂，从而形成了半封闭式重载铁路。由于重载线路与其所衔接集疏线路牵引质量标准不一致，为充分利用重载线路能力，半封闭式重载线路在装车端单独设置列车组合站进行重车车列的组合作业和空车车列的分解作业[1]。重载铁路装车端组合站在重载运输集疏运系统中发挥着极其重要的作用。

与我国不同，国外重载铁路一般为专线运输，普遍采用低密度、大载重、固定车底循环的运输模式，线路利用率低，能力富裕，因此对于重载运输组织的研究较少。国内学者从不同角度对重载铁路运输组织进行了研究。在重载铁路车流组织方面，文献[2]以组合时间最短、重载通道重车流量最大为目标，建立重载铁路装车端车流组织的多目标规划模型，并从宏观角度结合路网结构将其抽象成最小费用最大流问题求解。文献[3]对重载铁路装车域的重车车流组合方案进行优化研究，以组合列车在总组合时间及走行时间最小为目标，建立多目标规划模型。文献[4]综合考虑重载铁路装车端和卸车端空车回送，以空车空驶时间最短为目标，建立重载铁路空车调整的规划模型，并利用动态规划方法求解。

在车站工作组织方面，文献[5]以编组站为研究对象，引入“代价”的概念将编组站静态配流问题转换为运输问题，并采用表上作业法求解。文献[6]对湖东站的车流组织形式展开分析，构建湖东站重车流调整的0-1规划模型，并利用网络流算法求解模型。文献[7]以在站停留时间和前方站分解时间最小为目标，构建确定环境下重载组合站的列车组合方案规划模型，并设计表格法求解。然而在车站系统内存在诸多不确定因素，如列车到发时刻、车流信息以及各种作业时间等，为提高计划的可靠性，有必要研究不确定条件下的计划方案编制。文献[8]运用随机规划方法，研究列车解编时间随机变动情况下编组站阶段计划的优化编制问题。文献[9]将编组站解编作业时间作为模糊变量，在给定置信水平下用变量的悲观值表示不确定环境下的解编作业时间。

综上，目前针对重载组合站的阶段计划优化研究较少且存在不足之处。由于组合方式的多样化以及车站系统的不确定因素，重载列车的组合作业时间有所差异且存在不确定性，这时需要对不确定条件下的车流接续约束作具体讨论，既有研究中仅考虑编组站阶段计划编制这一方面；另外，到发线数量约束以及重载列车的发车间隔调整等重载组合站应特殊讨论的问题在既有研究中均未涉及。

在上述研究的基础上，本文结合重载组合站组合作业特点引入组合模式变量，以组合列车在站停留时间和前方站分解作业时间最少为优化目标，在考虑组合规则、到发线数量、发车时间间隔调整以及不确定性条件下的车流接续等约束的基础上，构建相应的随机机会约束规划模型，并借鉴行生成方法的优化思想，优先分解复杂的到发线数量约束，以解决到发线数量约束导致模型求解困难的问题，从而提高模型求解效率。

1 重载组合站组合作业特点分析

重载铁路装车端组合站以列为单位办理重载列车组合作业和回送空车的分解作业，与既有线编组站“到、解、集、编、发”的作业流程存在较大差异。在重车方向，由于装车点装车能力限制和衔接集疏线路牵引质量标准差异，到达组合站的列车多为牵引质量相对较小的单元列车，如万吨单元列车；同时也有少量到达的其他列车，如0.5万t列车和2万t组合列车。

由于衔接线路众多，到达组合站的重载列车数量较多且去向多样，而组合站发车能力及重载线路通过能力有限，无法单独将所有列车发出。为充分挖掘重载线路潜力，提高重载运输能力，一般将小编组列车组合成大编组组合列车发出，而大编组列车则无需进行组合作业，在到发线上完成必要的技术作业后，直接选择适当列车运行线上线运行。

通过分析重载组合站组合作业特点，列举各种组合模式及其特点，见表1。其中m为组合模式；am、bm、cm为组合模式m下0.5、1.0、2.0万t重载小列数量。

表1 组合模式表

表1中组合模式1、4、7为组合站常见的组合作业形式；组合模式3、5、6由于组合作业复杂，组合时间过长，在实际生产作业中已不再采用；组合模式2、8实际上并没有进行组合作业，而是万吨以上重载列车到达车站后进行必要的技检作业后直接上线发车；组合模式9则为抽象意义上的组合模式，表示列车编入本阶段站存车，因此重载小列数及组合大列质量均不确定。

不同于编组站在编组场进行编组作业，重载组合站的列车组合作业直接在到发线上进行，且一般不进行转线作业。重载组合站到发线也相对特殊，到发线有效长较长，两条到发线间夹一条机走线构成“三线一束”的形式，且到发线与机走线间设有腰岔。

对于列车占用到发线的起讫时间，需结合组合方案及各列车实际到发时间确定，如某出发列车占用到发线的时间段为编入该出发列车的单元小列中最早到站时刻起至该出发列车实际出发时刻止。在描述到发线数量对组合方案的影响时，本文以出发列车为研究对象，讨论其占用到发线的时间冲突，同时为简化列车之间占用到发线起讫时刻不同而产生的约束，引入时间片[10]的概念。

时间片定义：将本阶段的时间划分为几段, 每段时间被多列车占用, 且这几列车在占用到发线的时间上存在着交叉干扰, 不能使用同一条到发线，则每段时间就称为一个时间片。时间片的划分算法在文献[10]中有详细解释，本文不再赘述。

2 模型构建

2.1 问题描述及模型假设

给定组合站到达单元重载列车的数量、编组内容、到达时刻信息，和出发组合列车的数量、出发时刻信息，以及组合站到发线类型及数量、各项技术作业时间标准等，重载组合站重载列车组合方案优化问题旨在合理分配到达单元列车，确定各重载列车单元的组合方案，同时保证所有重载列车在站停留时间及在前方站分解时间最少，加速机车车辆周转。

本文基于如下假设：①组合站重车到达方向接车能力满足要求；②机车设备供应充足，机车出入段不受影响；③列检组能力充足。

2.2 符号与变量

2.3 约束条件

∀i∈Dj∈F1m∈M1

(1)

式中：α为置信水平。

(2)组合规则约束。除站存车外，对于出发列车j，选择不同的组合模式时，其所需的各类型重载小列数量需满足表1中的关系，即

(2)

(3)

(4)

式中：am，bm和cm取值见表1。

(3)列车归属唯一约束。对于到达列车i，只能编入一列出发列车。

(5)

(4)组合模式唯一约束。对于出发列车j，只能选择一种组合模式，且站存车f+1 只能选择组合模式9。

(6)

(5)站存车组合约束。本文讨论的在站组合作业均为本线组合，即列车到达组合站后无需转线作业，因此上阶段末的站存车之间无法组合编入同一出发列车。

pii′j=0 ∀i,i′∈D0i≠i′ ∀j∈F1

(7)

(8)

(9)

(10)

(11)

(12)

(8)到发线数量约束。在本阶段任意时刻，重载列车占用各类型到发线的数量，不大于组合站可提供作业的各类型到发线数量。而通过引用前面时间片的概念，可将任意时刻描述为任一时间片内，从而简化该约束。

(13)

(14)

(15)

(16)

式(14)～式(16)表示在第k个时间片内3种类型组合列车占用到发线数量不得超过可提供的相应类型到发线数量。

(9)逻辑约束。根据上述决策变量的定义，决策变量之间需满足一系列的逻辑约束。

(17)

pii′j=xijxi′j∀i∈D∀j,j′∈F1

(18)

∀i∈Dj∈F1m∈M1

(19)

2.4 目标函数

为加快重载机车车辆周转，降低运营成本，提高运输质量，在满足上述约束条件下，模型的优化目标为：

一是重载列车在组合站总停留时间最小，考虑到不同重载列车车辆数差异，引入车辆权重更好地阐述列车在站停留时间。

(20)

式中：wi为到达列车i的车辆数权重，1万t、1.5万t、2万t重载列车的车辆数权重分别为1.0、1.5及2.0。

二是去向不同的单元小列组合而成的重载组合列车在前方卸车端分解站的分解作业时间最小。

(21)

式中：aii′为0-1变量，若单元小列i与i′的去向不同，则aii′=1；否则为0；t分解为重载组合列车在前方分解站的分解作业时间，min。

2.5 随机机会约束和非线性约束处理

(1)随机机会约束转换为确定性约束

本文将随机机会约束转换为其相应等价的确定性约束[11]。

定理：令ξ为随机变量，其分布函数为Φ，若g(x)可表示为g(x,ξ)=h(x)-ξ，则Pr[g(x,ξ)≥0]≥α，当且仅当h(x)≥Kα，其中Kα=inf[K|K=Φ-1(α)]。

证明：由条件可知，Pr[g(x,ξ)≥0]≥α可表示为Pr[h(x)≥ξ]≥α；同时对于任意的α必然存在Kα使得Pr(Kα≥ξ)=α,即Φ(Kα)=α。则当且仅当h(x)≥Kα时，Pr[h(x)≥ξ]≥α可转换为Pr(Kα≥ξ)=α，此时Kα=inf[K|K=Φ-1(α)]。

∀i∈Dj∈F1m∈M1

(22)

(2)线性化转换

式(17)和式(18)为非线性约束，可将其转换为等价线性约束

∀i∈Dj∈Fm∈M1

(23)

pii′j≤xijpii′j≤xi′jpii′j≥xij+xi′j-1

∀i,i′∈D∀j∈F1

(24)

(25)

(26)

Tij≥-M·xij∀i∈Dj∈F1

(27)

综合考虑，总目标函数为：

(28)

由此得到重载组合站组合方案优化模型Md1,包括目标函数式(28)，约束式(2)～式(16)、式(19)、式(22)～式(24)和式(26)～式(27)。

3 基于行生成的模型分解算法

从模型性质分析，模型Md1为非线性混合整数规划模型，其中到发线数量约束涉及到时间维度上的占用冲突，为模型中的复杂约束，严重限制求解效率及精准度。

借鉴行生成[12]的思想，先松弛到发线数量约束式，得到子问题Md2，此时子问题松弛为线性混合整数规划模型，可调用商业求解器GUROBI求解，求解子问题并判断该解是否满足到发线数量约束，若不满足，则添加相应约束，从而减少原问题约束的数量与复杂度，最终求得较优解。基于前面分析，算法流程如下：

Step1S为模型Md1中到发线数量约束，C为其他所有约束，暂不考虑模型中到发线数量约束，令S=∅，得到子问题Md2(C,S)。

Step2调用求解器求解子问题Md2(C,S)，如果不可行，则原问题不可行，终止算法；否则输出组合方案和列车到发时刻，转下一步。

Step3根据组合方案和列车到发时刻，求得每列出发列车占用到发线时间段，并结合时间片划分算法[11]，将本阶段划分为多个时间片，转下一步。

Step4依次检查各个时间片内列车数量是否满足约束式(14)～式(16)，其中各时间片内下阶段站存车按重量类型分配至1.5万t或2万t到发线。一旦存在某个时间片不满足，则将该时间片对应约束添加至S，转Step2。

Step5若不存在到发线占用冲突，则输出结果，终止算法。

4 算例分析

(1)参数说明及原始数据

以湖东站某阶段计划编制为例，除站存车外，重载列车到达技术作业时间和出发技术作业时间均为30 min，组合列车在前方站分解作业时间为45 min，重载车辆在站最大停留时间为240 min，本阶段编制结束时刻为07:00，重载列车包括A、B、C、D和E 5个去向，1.0、1.5、2.0万t重载列车到发线数量分别为3、6、8条。

假定重载组合站不同组合模式下的组合作业时间服从正态分布，见表2，取置信水平α为0.90。

表2 不同组合模式下组合时间

到达列车车流数据见表3，编号1和2的到达列车为上阶段末的站存车，其到达时刻取本阶段编制开始时刻；出发列车图定出发时刻见表4，编号18的出发列车为本阶段末的站存车，其出发时刻取本阶段编制结束时刻。

表3 到达列车车流数据

表4 出发列车图定出发时刻

(2)优化求解

在Core 2.30 GHz & RAM 8 GB & Windows 10个人计算机上，采用Matlab2016b编程计算，调用GUROBI求解器对模型进行求解，得到子问题Md2初次优化的组合方案，根据组合方案确定各列车占用到发线起讫时间，由此得到时间片划分结果见表5。

表5 子问题初次优化时间片划分结果

由表5可知，时间片A1(与A2)明显不满足到发线数量约束，需要添加时间片A1(与A2)所对应的到发线数量约束到子问题Md2中，之后继续迭代求解，直至得到满足到发线数量约束的最终优化解，总求解耗时在10 min以内，迭代优化过程见表6。

最终优化组合方案见表7，编号18的出发列车为本阶段站存车，包括1列0.5万t和1列1万t重载小列，本阶段重载列车在站停留时间为5 457.5 min，在前方卸车站需要进行2次分解作业，总时间消耗为5 547.5 min。

根据各列车占用到发线起讫时间，时间片划分结果见表8，此时各时间片内列车均满足到发线数量约束。

表6 迭代优化过程对比

表7 重载组合站最终优化组合方案

表8 最终优化方案时间片划分结果

(3)结果分析

分析上述结果可知，在迭代过程中列车总时间消耗与站存车数量逐步增加，最终优化组合方案与子问题初次优化结果对比，重载列车总时间消耗增加72 min，站存车增加1列0.5万t重载小列。

究其原因，在不考虑到发线数量约束的情况下，为实现在站停留时间最小的目标，重载列车尽可能以2万t的大载重组合方式组合发车，但由于组合站2万t到发线数量的限制，因此必须对组合方案进行调整。而迭代优化过程实际即为调整部分组合列车的组合顺序，通过牺牲部分重载列车在站停留时间，或者减少本阶段出发车辆数，尽可能地减少本阶段2万t组合列车数量，以满足到发线数量约束。

现场工作基于组合站“先到先组，先到先发”的原则尽管能确定可行的组合方案，但组合列车需在前方站进行10次分解作业，总时间消耗增加到5 999 min；同时未能考虑到发线数量的限制，导致列车组合方案不够均衡，致使部分重载列车被迫晚点到站。相比于现场“先到先组，先到先发”的作业原则，优化组合方案使得重载列车总时间消耗降低7.5%，且组合方案更加均衡，能更好地适应重载运输需求。

5 结束语

基于随机规划理论，考虑车流接续、发车时间间隔调整和到发线数量等约束，构建包含随机机会约束的重载组合站组合方案优化模型，并借鉴行生成算法的思路求解模型，为重载组合站组合方案编制提供指导意义。

本文利用基于行生成的模型分解方法处理到发线数量约束时，在合理的限制时间内，可获得接近于最优解的满意解，在组合站复杂多变的作业环境下，满意解也能够满足作业要求。同时，未考虑本阶段组合方案对后续阶段计划的影响，以及车流不准确等随机因素，因而得到的组合方案可靠性仍有待提升，而在实际生产作业中，为提高方案可靠性，可动态地更新车流信息以进行组合方案实时调整更新。此外，针对到发线数量约束的其他处理方式以及列车到达时间和车流信息的不确定性，后续笔者将作进一步的研究。