基于改进TRG方法的管内零散货物快运列车开行方案研究

易晨阳，查伟雄，李 剑，张清雅，石俊刚

(1.华东交通大学 交通运输工程学院，江西 南昌 330013；2.广深铁路股份有限公司 广州车务段，广东 广州 510000)

2014年我国铁路开办了零散货物快运业务，是铁路新型零担运输产品，定位于高附加值但运量小的竞争性白货，采用区别于其他铁路快捷货运产品的新型运输组织模式，主要特点如下：①采用客车化的运输组织模式，货运列车具有固定的车次、径路与编组等，在沿线各站装卸；②零散货物快运由两部分构成，一个是将管内全部快运站与中心站相连的管内零散货物快运系统，另一个是将各路局中心站相连的直通零散货物快运系统，两个系统列车开行相对独立；③路局一般设1个中心站，在各中心站间开行点到点直达班列，实现货物直通运输，以中心站为绝大部分快运列车的首末站，在管内开行常态化的环线列车，实现货物管内运输。

目前，国内外与管内零散货物快运具有相似运输组织模式的列车开行方案编制研究极少。大宗货物运输以优化编组去向[1-4]为主，有大量成熟研究。Xiao等[1]研究单组与双组列车的编组计划优化模型，并提出一种将遗传算法和禁忌搜索相结合的混合求解算法。在基于点对点开行模式的货物快运列车开行方案研究中：易晨阳等[5]研究列车开行方案与货运方案的协同优化，模型借鉴编组去向的优化方法；李莅等[6]构建货运动车组列车开行方案优化模型。部分货物快运列车在运行途中设有停站，相关列车开行方案的编制研究主要采用构建备选集的方式；夏阳等[7]基于备选集构建快速集装箱列车开行方案的编制模型；郭玉华等[8]基于备选班列集合优化铁路中转班列开行方案；金伟等[9]采用列生成算法获得列车径路与停站方案的备选集，基于备选集来求解货流与列车流的耦合问题。备选集能有效缩小可行解范围，提升模型求解效率。然而，管内零散货物快运的起终点多为中心站，环线列车的可选径路多样，备选径路的筛选相对困难。无论是优化编组去向还是构建备选集，常用的列车开行方案优化方法难以直接用于管内零散货物快运。

考虑管内零散货物运输组织模式的特殊性，文献[10]借鉴车辆路径问题(Vehicle Routing Problem, VRP)的路径搜索方法，在此基础上提出列车径路组合生成 (Train Route Generation, TRG) 方法求解列车开行方案。VRP在国内外有大量成熟的研究，并发展出带服务时间窗、同时取送货等研究场景的VRP衍生问题[11-13]。但VRP主要解决货物配送问题，基本不考虑客户间的货运需求。而TRG方法是列车服务网络从满足中心站与快运站之间货运需求向快运站与快运站之间货运需求的延伸。文献[10]未考虑车站作业能力、线路通过能力等方面的限制，本文针对管内零散货物快运开行方案问题，构建考虑能力约束、大货流OD服务频率的新模型，其中，大货流OD服务频率的设计有利于提高列车运行计划在时变货流条件下的稳定性；同时改进TRG方法，将货运成本作为节点并入径路的判断依据，最终实现模型的高效求解。

1 LPRSEC模型

本文将构建的管内零散货物快运列车开行方案编制模型称为LPRSEC (Line Plan for Regional Scattered Freight Express with Capacity Constrains) 模型。LPRSEC模型需要解决的问题为：在管内零散货物快运网络上，以中心站为起终点，找到m条列车开行径路覆盖管内全部快运站，以区间通过能力、车站作业能力、货物运到期限等为约束，在运营成本最小的条件下实现最大的大货流OD服务频率，满足货物运输需求。

1.1 模型假设

(1)管内路网仅设有1个中心站，其为全部列车开行径路的首末站。

(2)货物仅在具备中转条件的快运站中转，且最多只能中转1次。

(3)相同OD货物有且只有一种运输方案，为可选的最短用时运输方案。

1.2 模型构建

(1)(V,L,U)为路网信息，变量符号及含义见表1。

表1 路网信息变量符号及含义

(2)(K,P,S,H,A,F,B)为径路方案，变量符号及含义见表2。

表2 径路方案变量符号及含义

(3)(Y1,Y2,L1,L2)为货运方案，变量符号及含义见表3。

表3 货运方案变量符号及含义

(4)其他符号释义见表4。

表4 其他变量符号及含义

1.2.1 上层规划模型

(1)目标函数：运营成本最小化。主要考虑列车运行成本与中转作业成本，即

(1)

(2)

(3)

式中：fk、bk由下层规划模型输出。

(2)径路与节点的服务关系约束。

(4)

(5)

(6)

(7)

(8)

(9)

式(4)表示中心站为任意径路的起终点。式(5)表示中心站为任意径路的服务点。式(7)表示任意快运站至少被一条径路服务。式(8)表示除中心站外，任意径路至少服务一个快运站。式(9)表示径路上的途经点可不均为服务点。

(3)货运方案与运输时间的关系约束。

(10)

∀i,j∈Vu∈U

(11)

(12)

(13)

∀i,j∈Vk∈K

(14)

∀k∈Kr=1,2,…,N2(k)-1

(15)

∀k∈Kr=1,2,…,N2(k)-1

(16)

(4)货物运输时间约束。货物运输应满足运到期限的要求。由于实际运营中存在一些较难避免的时间延误，故在货物运输时间中预留延误时间。

ti,j+d1≤di,j∀i,j∈V

(17)

(18)

式(17)表示货物运输时间与延误时间之和不超过货物运到期限。式(18)表示货运方案与运输时间具有唯一性。

(5)中转能力约束。车站u的中转作业量不大于该站的中转作业能力，即

Gu≤a1u∀u∈U

(19)

1.2.2 下层规划模型

零散货运计划性不强，采用随到随办、敞开受理的方式，容易产生日常货流与列流不匹配的现象。OD服务频率表示OD间每日平均开行的列车数，是评价列车开行方案服务水平的重要指标。在能力约束的条件下，OD服务频率越大，列车运行计划在时变货流条件下的稳定性越好。铁路部门长期重视大宗、稳定货流，开展零散货物快运业务也重视保障大货流节点的运输需求。因此，设定下层规划目标为大货流OD服务频率最大，即

(20)

(21)

(22)

(1)货运需求与供给约束。

fk·bk≥Ek∀k∈K

(23)

(24)

(25)

bk=m2,m2+1，…，m1-1，m1∀k∈K

(26)

fk≥1且为整数 ∀k∈K

(27)

式(23)表示径路上实际开行的棚车数不小于需开行的棚车数。式(24)表示径路上需开行的棚车数取决于径路上的最大断面货流量。式(25)表示径路上各区段的货流量由径路货流分配获得。式(26)表示列车编组存在上下限。式(27)表示径路上每日至少开行一趟车。

(2)接发列车能力约束。车站接发列车的数量不大于其接发列车能力，即

(28)

(3)区段通过能力约束。区段通过的列车数量不大于其区段通过能力，即

(29)

下层规划模型中fk、bk均为需要求解的变量。由于上层规划目标含(fk·bk)且追求最小化，为实现模型求解，式(23)应实现fk·bk→Ek。考虑fk、bk的整数特性，构建fk、bk与Ek的关系为

bk=「Ek/fk⎤ ∀k∈K

(30)

由于「x⎤=x+γ,γ∈[0,1)，故式(26)结合式(30)可转化为

Ek/(m1-γ)≤fk≤Ek/(m2-γ) ∀k∈K

(31)

由于有Ek/m1≤Ek/(m2-γ)

Ek/m1≤fk

(32)

综上，下层规划可转化为决策变量是fk的整数线性规划。目标函数为式(20)，约束条件为式(28)、式(29)、式(32)。

2 改进的TRG方法

2.1 改进TRG方法思路

TRG是实现列车服务网络从满足快运站—中心站货运需求向快运站—快运站货运需求延伸的重要手段。改进TRG方法思路见图1，具体过程是：①通过快运站排序搜索初始径路组合PS(0)(P,S)，使m条径路串联起所有快运站，且任意快运站仅被1条径路服务，其保证了每个快运站均能直达中心站；②在PS(0)基础上，根据直达优先原则，将径路上的车站均临时赋予服务点属性，获得PS(1)；③在PS(1)的基础上，对任意不在径路上的快运站进行服务点并入判断，若允许并入则进一步扩展径路的服务点、途经点序列，见图2，获得PS(2)；④根据PS(2)及其货运方案(Y1,Y2,L1,L2)，删除径路上未被货流使用的服务点，获得最终径路组合PS(3)。

图1 改进的TRG方法思路

图2 车站并入径路示意

当管内零散货物快运网络中只存在直通零散货运需求时，初始径路组合PS(0)即可满足运输需求，无需计算PS(1)～PS(3)；当管内零散货物快运网络中同时存在直通与管内零散货运需求时，通过“服务点并入判断”，使管内零散货物的直达方案被逐步添加到货运方案集合中，实现最优径路组合的快速搜索。

因此，由服务点并入获得PS(2)是改进的TRG方法的关键环节。服务点并入判断的依据是其对运营成本(上层规划目标)的影响。LPRSEC模型上层规划目标函数的求解需要进行配流、求解下层规划，若每一次服务点并入判断均要求解上层规划目标值，则计算规模太大，耗时过长。故考虑简化的运营成本判断方法，为

(33)

在这个环节中，当节点r0作为服务点并入径路k*，一方面会增加部分OD的备选直达方案，另一方面由于径路延长使得原经由径路k*直达的运输方案可能不再是最优方案。因此，分析货运方案可能会发生变化的OD如下：

(1)节点r0到径路k*上原货运方案为中转送达的节点。这一类OD的货运方案由中转变为径路k*直达。

(2)节点r0到径路k*上原货运方案经由其他径路直达的节点。这一类OD因备选直达方案的增加，最优方案可能会发生变化。

(3)原货运方案由径路k*直达，且r0的插入位置在装车站、卸车站之间的OD。这一类OD可能会由于径路k*延长使其用时最短直达方案发生变化，且其装、卸车站在新径路上的位置编号发生改变。

(4)原货运方案经由径路k*中转运输，且r0的插入位置在装车站→中转站或中转站→卸车站之间的OD。这一类OD可能会因径路k*延长导致用时最短的中转方案发生变化。

搜索上述4类OD，并置于集合X1、X2、X3、X4。可推知：第1、2类OD有ΔCr0,k*≤0,∀(i,j)∈X1∪X2；第3、4类OD有ΔCr0,k*≥0,∀(i,j)∈X3∪X4。故第1、2类OD对服务点能否并入径路存在关键作用。

2.2 TRG新径路方案模型

新增变量的符号及含义见表5。

表5 新增变量符号及含义

图3 插入点与前后节点位置关系示意

(34)

(35)

(36)

(37)

节点r0的插入位置要使径路k*的长度增长最少，即

r=2,3,…,N2(k*)

(38)

新径路上列车离开r0站及前方车站的时刻，为上一站的离站时刻加上新增的列车区间运行时间与停站时间，即

(39)

(40)

新径路上列车离开r0站及前方车站时的累计运行里程，是在上一站的累计运行里程加上新增的路径距离，即

(41)

(42)

2.3 TRG新货运方案模型

∀i∈sk*

(43)

∀i∈sk*

(44)

∀i,j∈sk*

(45)

∀i,j∈V且i,j≠r0

(46)

∀i,j∈Vk∈K

(47)

∀i,j∈Vk∈K

(48)

(49)

(50)

(51)

∀i,j∈V

(52)

(53)

(54)

∀i,j∈V

(55)

(56)

∀i,j∈V

(57)

∀(i,j)∈X4u∈Uk1=l1i,uk2=l1u,j

(58)

式(53)、式(54)分别为4类OD新的直达、中转方案。k′为X2、X3中OD最优直达方案的经由径路，u′为X4中OD最优中转方案的中转站。式(55)、式(56)为新货运方案下任意OD的运距。式(57)表示X2、X3中OD选择最短用时的径路k′直达。其中，X2中OD仅需比较经由原径路l1i,j与新径路k*所需的直达运输时间，X3中OD需比较经由其他径路与新径路k*的直达运输时间。式(58)为X4中OD选择运输时间最短方案对应的中转站u′中转。

计算新货运方案下减少的货物中转量Q*。只有X1中OD由中转变为直达，不再耗费中转作业成本，即

(59)

2.4 改进TRG算法步骤

改进TRG算法的主要步骤如下：

(1)初始径路组合PS(0)生成。详见3.1。

(2)服务点扩充，生成PS(1)。扩充方法为

(60)

将PS(0)中的所有途经点赋予服务点属性。

(3)服务点并入判断，生成PS(2)。

Step1基于PS(1)计算原货运方案(Y1,Y2,L1,L2) (详见文献[10])，转Step2。

Step4判断是否遍历了全部径路k，否则转Step2，是则结束运算并输出PS(2)。

(4)服务点删除判断，生成PS(3)。

3 LPRSEC模型求解与算例分析

3.1 求解算法

LPRSEC模型采用结合改进TRG方法的单亲遗传算法求解。种群个体的编码方式见图4。x基因段为不重复的快运站编号排序(不含中心站)，y基因段为PS(0)中各径路上的服务点数量。种群个体解码可获得PS(0)：①在被y基因分隔的x基因段首末加上中心站编号，例如：已知n=5,m=2，中心站编号为“0”，个体基因为“124331”，可将其分解为 “0-1-2-4-0”与“0-3-0”；②用Dijkstra算法求取以上相邻节点间的最短路径，组成完整径路，获得PS(0)。之后通过改进的TRG方法将PS(0)转化为PS(3)。

图4 编码方式

PS

(3)

(61)

(62)

式中：Z1为上层规划的目标函数值；ρ为下层规划解的输出形式，ρ=1为下层规划模型无可行解，反之ρ=0；κ为惩罚系数(κ>0)，取极大值M。

式(62)表示当下层规划模型有可行解时，输出(fk,bk)并计算Z1；无可行解时Z1=M。

根据适应值对种群个体(对应PS(0))进行繁殖与基因重组操作[14]。其中，父代采用杂草算法繁殖机制[14]，子代基因根据IPGA重组方式生成[15]。

据此，LPRSEC模型求解算法步骤如下：

Step1种群初始化[10]，计算ξi,j与初代种群P(t=0)适应度，转Step2。

Step2迭代终止判断：迭代次数t大于或等于规定次数则输出结果，否则转Step3。

Step3对种群P(t)开展繁殖与基因重组操作，获得新一代种群P(t+1)，计算新种群适应度。t=t+1，转Step2。

3.2 算例分析

以南昌局管内路网为参照，构建管内零散货物快运网络，见图5。圆圈内数字为车站编号，连接边括号内的数字表示站间距离，km，括号外的数字表示从左至右、从上到下的区段编号，例如区段“1-3”、“3-1”的编号分别为“1”和“-1”。节点1为中心站，中转站集合U={1,5,7,11}，能力参数a1～a3见表6～表8，其他参数见表9。随机生成测试货流集合{Qi,j}，货流量总计6 386 t/d。

图5 管内零散货物快运网络(n=15)

表6 中转站作业能力a1

表7 车站接发车能力a2

表8 区间通过能力a3

表9 参数取值

目前各路局管内零散货物快运的列车开行径路数量为2～6条，平均4条。据此，测试m分别取{3,4,5,6}时的运算结果，并判定最优的列车开行方案。算法用MATLAB R2019a实现，下层规划采用其内置函数intprog求解。测试种群规模与迭代次数，发现取种群规模200、迭代200次时运算结果相对稳定，能较快、较好地趋近最优解。测试不同列车开行径路数量m条件下的模型最优解，每组经15次运算测试，获得不同m条件下最优解的收敛情况，见图6，计算结果见表10所示。当m=5时，管内零散货物快运的运营成本最小，为141.68万元；m=4,6时，运营成本与其相近，分别为143.03、144.75万元。但m=5,6时，大货流OD服务频率最小，为1.6；m=4时，大货流OD服务频率较大，为1.97。

图6 不同m取值的收敛曲线图

表10 不同m取值的模型最优解

综合上、下层目标函数值，取m=4为最优方案，见表11。径路全长最大2 662 km，最小1 158 km。由于管内零散货物快运为棚车编组，可加挂宿营车，故该列车径路长度是可行的。径路1、2的列车开行数量为3列/d，编组分别为7车/列、6车/列；径路3、4的列车开行数量为2列/d，编组分别为6车/列、9车/列。部分径路列车开行数量较小是受区间通过能力较小、大货流OD较少等因素的综合限制。

表11 管内零散货物快运列车开行方案(m=4)

列车开行径路与区段流量(m=4)见图7。图中连接边旁的数字为线路区段上的货流量，t，括号外为编号是正数的区段流量，括号内为编号是负数的区段流量。其中，1—11、11—1、1—5、5—1、5—7为最繁忙区段，这是因为大量货物在中心站集散，进而呈现出货流向中心站聚集或由中心站向路网发散的特点。节点5、11作为介值较大、具有中转站属性的节点，也承担了大量货物的集散工作。

图7 列车开行径路与区段流量示意图(m=4)

4 结束语

本文主要研究工作如下：①在LPRSE模型的基础上，新增了区间通过能力、车站接发列车能力、中转作业能力三种能力约束，以管内零散货物快运的运营成本最小为上层目标，大货流OD服务频率最大为下层目标构建了LPRSEC模型。大货流OD服务频率的设计，有利于减少零散货流到站时间分布不均衡带来的负面影响，提高列车运行计划在时变货流条件下的稳定性。②设计改进的TRG方法，通过判断服务点并入径路前后对货运成本的影响，使管内零散货物的直达方案被逐步添加到货运方案集合中，最终实现最优径路组合的快速搜索，提高了模型求解效率。同时，通过删除径路上未被OD使用的服务点，减少径路上的服务点数量，实现列车停站优化。③将下层规划转化为整数线性规划，将解的形式融入适应值函数，结合改进的TRG方法与单亲遗传算法，设计LPRSEC模型求解算法。④以南昌局管内零散货物快运网络为参照进行算例分析，分别测试了不同列车开行径路数量条件下的运算结果，得到了最优的列车开行方案。

综上，论文研究成果对于管内零散货物快运的运输组织优化具有一定的理论意义和应用价值。此外，研究还可进一步改进：结合零散货物到达发站的时间分布规律，可引入服务时间窗属性，以实现日常运营中更好的车流与货流配合。这是论文后续的研究方向。