考虑货物异质性和模糊需求的高速铁路货运组织优化方法

陈婉茹，张得志，秦 进，曹 健，徐光明，王 超

(1.中南大学 交通运输工程学院，湖南 长沙 410075；2.中国国家铁路集团有限公司 办公厅，北京 100044)

截至2021年底,我国高速铁路(以下简称“高铁”)运营里程突破4万km,然而,部分线路部分时段的运力和设施能力在实际运营中未能充分利用。与此同时,公路快运正面临着运能饱和和时效有限的双重压力[1]。2021年12月国务院颁布的《“十四五”现代综合交通运输体系发展规划》中明确指出:利用“八纵八横”的高铁网提供的线路条件和稳定货源[2],发挥高铁在中长距离运输方面成本低、容量大、速度快的突出优势,发展高铁快运等铁路快捷货运产品,是缓解公路运输压力,提升我国快捷货物运输效能的一大突破口[3]。然而,现阶段基于客运捎带和确认车运输的高铁快运干线组织模式存在节点功能不清晰、运输效率低、集散能力不足等问题[4]。结合国外铁路高速货运产品的发展经验,在夜间非天窗检修时段开行高铁货运专列,是加强高铁货运能力建设的关键。

2020年高速货运动车组就已下线,但其运输组织方案至今仍未明确。为解决该问题,金伟等[5]研究高铁快运组织方案优化问题,构建两阶段混合整数规划模型并基于列生成算法求解。高如虎等[6]以时变需求为导向,按分阶段优化的思路,研究快运专列时刻表和配装方案的综合优化方法。Hampaeyan等[7]以碳排放量最低为优化目标,构建混合整数非线性模型,确定城际单线双向铁路网中客货列车运行的最佳调度计划。Li等[8]在货运专列和客车捎带的组合服务模式下,以实现利润最大化为目标,优化列车时刻表和货物分配计划。以上研究遵循“按流开车”的基本原则,对列车径路、停站方案、开行频率等高铁货运专列开行方案的部分内容进行了定量优化,但忽略了其与服务网络和组织模式的相互关系,不利于指导生产实践。

为逐步扩大高铁货运专列的运行范围,稳步推进专列的成网开行,运输组织需要考虑高铁快运的网络特征和产品供需特点。高铁快运“轴-辐”式网络见图1,在高铁快运网络中,高铁站点被划分为一级枢纽和二级货运站,二级货运站依托高铁经由一级枢纽彼此相连,具有“轴-辐”式特征[9]。为实现规模效应,降低单位运输成本,二级货运站的待运货物依托一级枢纽间开行的高铁货运专列,实现由始发枢纽至货运站的疏运或由货运站至终到枢纽的集运,以直达或中转的组织模式送至目的地所在高铁站点[4]。除此之外,高铁货运专列的开行还应当考虑到如下现实特征:首先,受限于夜间的综合维修天窗,能够开行的专列数量有限;其次,高铁货运产品日益丰富,不再局限于单一快递包裹,在运输组织中需要考虑货物的异质性;此外,快运需求具有不确定性,计划需求和实际需求的差异将直接影响开行方案的服务质量。

图1 高铁快运“轴-辐”式网络

针对以上问题,本文面向高铁“轴-辐”式快运网络和高铁快运货物的集疏运需求,考虑高铁快运需求的异质性和不确定性特点,提出基于装载空间划分和需求拆分的异质货物协同运输策略,引入模糊集货需求下的机会约束,构建高铁货运专列开行方案和配载方案优化模型,设计并行改进变邻域搜索算法求解。最后,以京沪高铁货运专列的开行为例,验证上述模型和算法的有效性,探究决策者风险偏好对优化方案的影响,并给出相关建议。

1 模型构建

1.1 问题描述

本文基于“轴-辐”式网络下快捷货物的集疏运需求,研究单条高铁线路某一方向货运专列开行方案和配载方案的联合优化问题。高铁快运货物的集疏运过程见图2,V为高铁线路站点集合,V={0,1,…,n,n+1},其中,0和n+1分别为始发和终到的一级枢纽,即所有列车均从枢纽0出发,最后返回枢纽n+1;N为线路途经二级货运站集合N={1,…,n}。以一天为一个计划期,K为线路在夜间非天窗检修时段所能开行的有限专列集合,即线路通过能力为|K|对/天。货物在一级枢纽和二级货运站间的集疏运过程描述如下:高铁货运专列从一级枢纽站0出发,装载OD为(0,i)的快运需求,将其运输到车站i(1≤i≤n),即完成了快运货物从起点至二级货运站i的疏运;接着,到达车站j(i≤j≤n)装载OD为(j,n+1)的快运需求,将其运输到枢纽n+1,即完成了快运货物从二级货运站j至终点的集运。

图2 高铁快运货物的集疏运过程

基于以上分析,本文所研究的集疏运需求OD具备以下特点:疏运需求均以一级枢纽车站0为起点,集运需求均以一级枢纽车站n+1为终点。本文需要解决的问题是合理开行高铁货运专列,并将不同类货物配载到不同专列上,满足一级枢纽和各二级货运站间的所有集疏运需求,具体内容包括优化高铁货运专列的开行对数、各高铁货运专列的停站方案及配载方案,使得总运营成本最低。

高铁快运产品主要针对商务文件、电商包裹、数码产品、生鲜等高附加值货物。这些货物对于运输环境的要求不同,具有特殊属性的货物(例如药品)不能与一般货物混装混运。但在已有研究中,货物的异质性被忽略,相同OD的货流被简单合并。本文考虑将货物依据相容性进行划分,H为所有货物种类构成集合,将列车内部空间划分为|H|个与货物种类一一对应的装载空间,以实现异质货物在空间上的分隔和时间上的同步运输,高铁货运专列装载空间划分见图3。值得注意的是,|H|是一个可以自定义的参数,可以根据具体的待运货物进行设置,而对应的装载空间可以根据货物的种类数和需求量预先灵活划分。当各二级货运站的所有集疏运需求由唯一专列一次停站全部满足时,所有专列共停站n次,可以最大限度减少停站作业成本。但异质货物协同运输时,不同装载空间的容量相互制约,可能会造成运力虚糜。因此,将二级货运站内的异质货物需求拆分,并通过停站方案实现不同站点异质货物需求的耦合,能够更好地利用专列的装载能力。

图3 高铁货运专列装载空间划分示意

由于快运货物具有小批量、多批次的特征,二级货运站i∈N对h∈H类货物的实际集运需求可能基于计划集运需求波动[6],实际集运需求更趋向于一个模糊区间[10],在制定专列开行方案时应当考虑上述不确定需求[11]。相比于一般模糊集,三角模糊变量对快运需求模糊现象的描述更为贴切[10],因此采用三角模糊变量描述集货需求的不确定性。不失一般性,将实际集运需求设定为对称三角模糊数[12],即

式中:pih为集运需求的期望;Lpih、Mpih分别为实际集运需求的下界和上界,且有Lpih=(1-ϑ)pih,Upih=(1+ϑ)pih,ϑ为集运需求的波动因子。

图4 模糊集运需求的概率密度函数

做出如下基本假设:

1)开行的有限专列能够满足线路上所有二级货运站的集疏运需求。

2)所有二级货运站的各类货物集疏运需求均不超过对应装载空间容量,可以被一次满足。

3)二级货运站内的不同类货物集疏运需求可拆分,并由不同专列满足;同类货物集疏运需求不可拆分,需由唯一专列一次满足。

4)仅以重量衡量专列的载运能力,不考虑货物体积对装载的影响,且货物运输过程中不允许混装。

决策变量见表1。

表1 决策变量

1.2 优化模型

模型以高铁快运专列的总运营成本最低作为优化目标,包括固定成本、变动成本和停站成本。固定成本由专列开行数量决定,变动成本由专列的走行距离决定,停站作业成本由专列停站作业次数决定,即

( 1 )

式中:c1为专列开行的单位固定成本;c2为专列在区间行驶单位距离的平均开行成本;c3为专列的单位停站服务成本;r为始发终到枢纽间的线路里程。

1) 集疏运需求约束

所有集疏运需求都将被唯一服务,即

( 2 )

2) 停站约束

停站约束为

( 3 )

( 4 )

( 5 )

式中:M为一个足够大的正数。

式( 3 )表示当前专列不开行时,在任何途经站点都不停站。式( 4 )、式( 5 )保证专列停站时一定服务于站点的需求。

3) 载货能力约束

式( 6 )限制发车时各装载空间的装载量不超过其装载能力。

( 6 )

专列在途的货流量守恒约束为

∀i∈Nk∈Kh∈H

( 7 )

引入决策者的风险偏好值α,α∈[0,1],但一般不取0值,故有α∈(0,1][10]。限制专列服务完任意站点后各装载空间载重小于其装载能力的概率需大于等于预先设定的决策者风险偏好值α,即

( 8 )

( 9 )

4)决策变量取值约束

xk={0,1}k∈K

(10)

(11)

专列的载货量满足非负约束

(12)

2 求解算法

2.1 算法框架

构建的非线性混合整数规划模型,涉及多个多维决策变量,其组合数随着问题规模的增大将爆炸式增长,属于NP难问题。为了实现模型的高效求解,本文设计了基于并行改进变邻域搜索(Parallel Improved Variable Neighborhood Search, PIVNS)的启发式算法,总体框架见图5。

PIVNS算法基于3步后悔值插入算法[13]得到初始解;通过均衡扰动策略扩大搜索范围;采用变邻域下降[14]策略在给定邻域结构内嵌套寻优;达到最大迭代次数或最大不改进迭代次数时算法终止。

2.2 评价函数

对∀i∈N,h∈H,顺序编码站点i的h类货物需求,构成需求集合R={r1,r2,…,r|N|×|H|}。构造|K|个与专列一一对应的空数组,记录其服务需求和服务顺序。将∀ri∈R,i=1,2,…,|N|×|H|唯一指配给一列专列即构成一个解x。然而,并非所有解都能够满足载重约束,在评价解时需要对载重约束的违反施加惩罚,促使搜索朝着可行域的方向收敛[15]。因此,本文设计评价函数为

F(x)=f(x)+γiV1(x)+δiV2(x)

(13)

式中:f(x)为由式( 1 )计算得到的总成本;V1(x)和V2(x)分别为当前解中载重约束式( 6 )和式( 8 )的违背量;γi,δi为动态惩罚因子。若在第i-1次迭代后得到的局部最优解不违反约束式( 6 ),则在第i次迭代时置γi为γi-1的1/ρ倍,否则置其为γi-1的σ倍。同理,根据第i-1次迭代后得到的局部最优解是否违反约束式( 8 )更新δi。

2.3 初始解

基于3步后悔值插入[13]的方法生成初始解:对∀ri∈R计算3步后悔值R3(ri);以最佳服务顺序将argmax{R3(ri),ri∈R}指派给使得评价函数值最少增加的专列,最佳服务顺序指需求点插入当前专列对应数组时引起评价函数值增加最少的位置;更新R=R{ri};重复以上步骤直到R=∅。需求点ri的3步后悔值为

(14)

式中:fi,k为将需求ri以最佳的服务顺序指派给专列k所带来的评价函数值增量;xij为专列序号,当需求ri以最佳服务顺序指派给该专列时,评价函数值增量相较于指派其他专列是第j小的。

2.4 VNS算法

1)邻域结构

VNS算法涉及的邻域结构由如下算子产生:

inter-swap (n-n-n):如图6所示,该算子用以顺序交换三列专列所服务的连续n个需求点。

图6 inter-swap (n-n-n)算子示意

1-insert:将一列专列所服务的一个需求点重新指派给另一专列。

2-insert:将一列专列所服务的连续两个需求点重新指派给另一专列。

Inter swap 1-1:交换一列专列所服务的一个需求点与另一专列所服务的一个需求点。

Inter swap 2-2:交换一列专列所服务的连续两个需求点与另一专列所服务的连续两个需求点。

Intra 2-opt:将一列专列所服务的连续两个需求点以不同的服务顺序重新指派给当前专列。

Intra swap:交换一列专列所服务的两个需求点的服务顺序。

Shift:将一列专列所服务的一个需求点以不同的服务顺序重新指派给当前专列。

2)扰动

为了扩大搜索范围,需要扰动当前解,即从定义的邻域结构中选择一个解输入局部搜索。3个扰动邻域结构基于算子inter-swap (n-n-n)产生。不妨设C1,C2,C3分别为三列专列所服务需求的数量,表2给出邻域结构κ对应的算子最大操作长度nmax。nmax的设置在保证n不超过扰动路径长度的同时,给出n的上界。邻域中n的取值是随机的。

表2 抖动邻域结构

3)局部搜索

局部搜索指在给定邻域结构NK(x)内搜索改进解以更新当前解的过程。7个局部搜索邻域结构由算子1-insert,2-insert,Inter swap 1-1,Inter swap 2-2,Intra 2-opt,Intra swap,Shift依次生成。研究表明,最佳改进搜索策略能更好地平衡算法的求解质量和运行时间[16]。设当前解x的邻域结构NK(x)中包含解x1,…,xn,xi=F(xi)-F(x)。若xi≥0,∀xi∈NK(x),则不更新当前解x;否则以argmin{xi,xi∈NK(x)}更新x。若在邻域结构NK(x)中更新当前解,则搜索回到邻域N1;否则搜索邻域NK+1。当K>7时,本次迭代中的局部搜索结束。

2.5 IVNS算法

2.6 PIVNS算法

图7 并行局部搜索示意

3 算例仿真与分析

3.1 算例设计及参数

本文以京沪高铁为例进行仿真分析,线路示意见图8。

图8 京沪线高速铁路线路示意

假定线路的专列通过能力为6对/d[18],|H|=2且两类货物需求相当,8节编组专列被均分为两个由4

节车厢组成的装载空间,单节车厢最大载重为143.75 kN。单位固定成本c1为42万元/列,单位可变成本c2为0.07万元/km,单位停站成本c3为5万元/次[5]。二级货运站i∈N对h∈H类货物集疏运需求pih、dih见表3。设置算法最大迭代次数和最大不改进迭代次数分别为2 000和150,动态惩罚因子控制参数ρ,σ均为100。所有算法通过Matlab 2020a编程实现,计算机参数配置为Intel Core i5-9500,3.0 GHz,8 GB RAM。各算例下算法的测试结果均基于10次运算。

表3 算例详细信息表

3.2 算法对比分析

当ϑ=0.25时,对比VNS算法、IVNS算法和PIVNS算法在偏好值α∈(0,1]按0.1增时的求解结果,以验证PIVNS算法的有效性和稳定性。表4给出各算法求得的最优解Bbest、平均值Aavg、平均值Aavg相对于Bbest的误差比率Ggap和与Bbest对应的最佳运行时间T。

表4 PIVNS算法和VNS算法、IVNS算法的求解结果对比

Ggap=(Aavg-Bbest)/Bbest×100%

(15)

由表4可知,PIVNS算法求得所有偏好值下的当前最优解,IVNS算法求得其中7个,VNS算法仅求得3个,说明改进策略的加入能增强算法的全局搜索能力,一定程度上避免算法陷入局部最优;在求解时间方面,PIVNS算法的计算时间均要明显少于VNS算法和IVNS算法,说明并行策略的加入能大大提升算法的运行的效率;在求解稳定性方面,VNS的算法的平均Ggap为3.11%,IVNS算法的平均Ggap为2.57%,PIVNS算法的平均Ggap最小,仅为1.87%,说明PIVNS算法的求解较为稳定。

3.3 结果分析

基于提出的PIVNS算法,对比分析ϑ=0、ϑ=0.25且偏好值α∈(0,1]按0.1递增时不同运输策略下的优化方案。其中,MCSD为装载空间划分且需求拆分策略,MC为装载空间划分但需求不拆分策略,SC为不划分装载空间且需求不拆分策略。SC策略中始发站配备分别用于运输两类货物的专列各|K|/2列。当前偏好值下各策略组织方案总成本Bbest和当前策略Bbest相对于MCSD策略的误差比率Ggap见表5。

表5 不同波动因子下不同策略的求解结果

(16)

1)异质物协同配送策略

ϑ=0时各策略优化方案见图9。在开行对数方面,SC策略和MC策略的开行对数均为6列,而MCSD策略为5列。在停站方案方面,MC策略停站次数最少,MCSD策略次之,SC策略停站次数最多。相较于MC策略,MCSD策略通过牺牲部分停站成本实现了固定成本和变动成本的大幅下降。为了更加直观地对比不同运输策略下配载方案的优劣,表6给出各策略方案的区间平均装载率,装载率为实际载货量和专列最大装载能力的比值。

图9 ϑ=0时各策略下的优化方案

表6 各策略下确定模型优化方案的区间装载率 %

由表6可知,高铁货运专列的在途载货量是动态变化的。在装载空间容量约束下,为满足全部集疏运需求,SC策略中V2和V4专列的运力大量虚糜,平均区间装载率为64.71%。MC策略中不同装载空间的容量互相制约同样导致V5和V6专列的运力大量虚糜,平均区间装载率为66.36%。多类货物协同运输的MCSD策略能够优化整体方案,平均区间装载率为77.66%。

2)模糊需求下决策者偏好的影响

α的大小反应决策者在模糊环境下对待风险的态度。α越小,决策者越冒险,希望当前专列可以服务更多需求,而服务失败的概率也越大,会对客户满意度造成负面影响;α越大,决策者越保守,更重视线路可行性安排,虽然服务失败的风险低,但会导致运力资源浪费。需要注意的是,专列可服务的需求点数量受到配货需求的硬性约束,并不会随着偏好的减小而一直增加。

偏好值的设置可以参考ϑ=0时的求解结果,即确定计划需求下的运输组织方案。在当前算例中,当α取0.5～0.7时,既不会因为决策者的保守而带来较大的浪费,也预留了部分运力用以满足波动的集货需求,是较为合适的。此外,动态设置偏好值能够有效规避固定偏好值设置不合理而导致的问题,即在不同周期的决策内,根据当前货物的实际波动情况,设置不同的偏好值,以更好地安排运力。

4 结论

本文针对需求不确定的异质快运货物在高铁货运“轴-辐”式网络中的集疏组织问题,研究高铁货运专列开行方案和配载方案的联合优化方法。以运营成本最低为优化目标,构建基于模糊需求的混合整数非线性规划模型,设计并行改进变邻域搜索(PIVNS)算法进行求解。以京沪高速铁路为背景的仿真实验结果表明:

1)PIVNS算法的求解有效且稳定,提出的均衡扰动策略能够增强算法的全局搜索能力,采用的并行局部搜索策略能够减少算法运行时间。

2)基于专列装载空间划分和站点需求拆分的异质货物协同运输策略能够优化方案的开行对数,合理安排列车停站,有效提高专列在区间的装载率,降低配送成本。

3)决策者对待模糊需求的风险偏好会直接影响组织方案,偏好值的设置应当以确定计划需求下的组织方案为基准,并结合货物需求的实际波动情况,在不同计划周期内动态设置。

本文的研究为相关部门实现高铁干线集疏运的智能组织调度提供有力支撑。未来的研究将围绕提高算法效率及多组织模式下高铁快运专列的成网运行展开。