考虑中转的高铁快运时空路径优化模型及拉格朗日松弛算法

Time-Space Path Optimization Model and Lagrangian Relaxation Algorithm for High Speed Railway Express Considering Transit

摘要

以提升运输方案与时变箱流需求间的耦合度为导向，基于既有载客动车组列车捎带运输模式，旨在对考虑箱流中转情形下的高铁快运方案进行优化。鉴于箱流运输方案对列车时空资源占用的双重依赖性，以列车及快运箱为研究对象，构建由4类节点与5类弧段构成的时空网络。在此基础上，以快运箱总运达时间最短为目标，考虑列车装载能力、箱流上车、中转及守恒等约束，构建运输方案时空网络优化模型。针对模型特性，设计拉格朗日松弛算法求解，将原问题分解为求解单个快运箱的最短运输路径子问题，并设计以消解违背列车能力约束冲突为核心的上界可行化算法。最后，以西安—兰州高速铁路为背景进行实例验证，研究结果表明，所提模型及算法可快速获得满意解，有效提升列车满载率。此外，与直达运输情形相比，考虑箱流中转可有效解决快运箱的滞留问题。

Abstract

To enhance the interconnectivity between the transportation scheme and the time-varying container flow demand, this paper optimized the transportation scheme of high speed railway express considering the container flow transit scenario by leveraging the piggyback transportation mode of existing passenger-carrying trains. In view of the dual dependence of the container flow transportation scheme on the occupation of train time and space resources, a time-space network consisting of four types of nodes and five types of arc segments was constructed, with the train and express container serving as the research objects. On this basis, this paper formulated a time-space network optimization model for the transportation scheme, with the objective of minimizing the total delivery time of express containers. Furthermore, the constraints of train loading capacity, container flow boarding, transit, and conservation were considered. According to the model characteristics, the paper designed a Lagrangian relaxation algorithm to solve the problem. By decomposing the original problem into a subproblem of determining the shortest transportation path of a single express container, the paper developed an upper-bound feasibility algorithm that focused on eliminating the conflict of violating the train capacity constraints. Lastly, the paper utilized the Xi'an-Lanzhou High Speed Railway as a case study for verification, and the results indicate that the proposed model and algorithm can rapidly generate an acceptable solution, effectively increasing the full load factor of the trains. Moreover, compared with the case of direct transportation, container flow transit can effectively address the congestion issue of express containers.

Graphical abstract

关键词

高铁快运 / 运输方案 / 箱流中转 / 时空网络 / 拉格朗日松弛

Key words

High Speed Railway Express / Transportation Scheme / Container Flow Transit / Time-Space Network / Lagrangian Relaxation Algorithm

0　引言

《新时代交通强国铁路先行规划纲要》明确指出：“发展快捷货运和高铁快运，强化铁路运输和两端配送有机衔接，完善枢纽快运集散服务功能”。高铁快运是以高速铁路动车组为载体，为客户提供指定服务范围、承诺运到时限的高端快运服务。大力发展高铁快运对于发挥高铁高质量运输服务能力和“溢出效应”、助力实现“公转铁”和“碳达峰”战略具有重要现实意义。

高铁快运目前仍处于局部试点和探索阶段，既有研究主要从高铁快运作业流程^[1-2]、货流需求预测^[3]及运输组织方案优化^[3-7]等层面分析了高铁快运的可行性及前景。然而，既有高铁快运运输组织方案依旧采用传统编制原则与人工经验相结合的方式，列车运输能力与箱流需求匹配性较差。列车时刻表作为高铁快运运输组织的核心，其决定了快捷货物的配装时间及途中运行时间，进而影响其对配装及接续车次的选择，如Niu等^[4]、Tian等^[8]及Gao等^[9]分别以时变客流为对象，研究了跨站模式、越行条件及新增列车运行线情形下的时刻表优化问题，并分别采用CPLEX求解器、列生成及ADMM算法求解，对高铁快运运输组织优化具有重要借鉴意义。此外，既有研究大多将运输方案优化问题分解为运输路径优化和流量分配2个子问题，如Wu等^[10]、Yang等^[11]、陈京亮等^[12]分别以应急车辆、高铁快运、铁路行包为研究对象，构建了考虑作业时间、箱流守恒、列车停站等约束的时空网络优化模型，为每个OD需求决策可行路径集合。Niu等^[13]、Xu等^[14]、Li等^[15]分别以公交路网、普速铁路、高速铁路网为背景，构建了考虑列车能力、车站能力以及中转次数等约束的时变客流分配模型，对快捷货物箱流分配方案优化具有重要参考价值。快捷货物运输路径生成及流量分配协同优化成为近期研究热点，如王泽等^[16]考虑到行包流与列车能力在时空上不匹配的问题，构建了行包流分配与路径生成综合优化模型，并设计拉格朗日松弛算法求解。刘勇等^[17]基于旅客列车运行图，考虑货运作业对旅客运输组织的影响，构建了行包运输组织方案优化模型。金伟等^[18]通过细分高铁快运产品种类，构建了高铁快运组织方案两阶段混合整数规划模型，并设计列生成算法，将原问题分解为求解单列车的广义最短路径问题，有效降低求解难度。

既有运输方案时空网络模型建模角度通常包含基于路径与基于节点-弧段2类，前者须以各箱流OD备选路径为基础，适用于大规模优化问题，可有效降低变量数量及求解规模；后者可同时实现箱流的运输路径生成和流量分配，同时体现时空网络中的点元素和弧元素，适用于小规模优化问题。因此，考虑到本研究问题规模适中，且考虑箱流中转情形，相较于直达运输而言箱流路径灵活多样，固化的箱流运输路径将严重影响最优解质量，故研究基于节点-弧段的建模角度进行时空网络模型构建。此外，在求解运输方案优化问题时，大部分学者通常采用启发式算法、列生成算法以及松弛或分解算法^[19]，当问题规模较小时，常采用商业求解器，如CPLEX等。考虑拉格朗日松弛算法具有良好的适应性与鲁棒性等特点，适用于求解大规模、多目标、强耦合的NP问题，故选用该算法对基于节点-弧段的时空网络优化模型进行精确求解。高铁快运相关文献比较如表1所示。

1　问题分析及说明

1.1　问题描述

鉴于当前高铁快运需求较小、站场设施配备不足、货运动车组尚处于试制阶段等发展现状，因此仅针对高速铁路载客动车组列车捎带模式下的高铁快运运输方案进行研究。以双线高速铁路线路单个方向为研究背景，以既有载客动车组列车运行图为依据，以全天运营时段内到达各站点的快运箱为研究对象，旨在为其决策最佳配装列车及配装时间。

此外，直达运输情形下高铁快运运输方案主要包括发送作业、在途运输、到达作业3个流程，其核心为合理调配列车运输能力，确定研究时段内快运箱的配装车次。然而，考虑到部分箱流运距过长，其运输过程需要相互衔接的动车组列车配合完成：在载客动车组列车的衔接点进行中转作业。少量快运箱可利用载客动车组列车的停站时间在中间站完成中转接续作业，大批量的快运箱只能在前序列车的终到站同时也是后续列车的始发站完成中转，箱流中转示意图如图1所示。因此，为提高运输方案服务质量，考虑箱流中转情形，确定快运箱在列车间的装卸计划及中转方案，为其指派中转车站及接续车次。

1.2　符号说明

为方便问题描述，所使用的集合、索引、参数、变量如下所示。

集合：U为车站集合；B为快运箱集合；I为列车集合；N为时空网络节点集合；A为时空网络弧段集合；T为研究时段内时间点集合。

索引：u,v为车站索引，u,v\in U；b为快运箱索引，b\in B；i，j为列车索引，i,j\in I；t，s为时间点索引，t,s\in T；(u,t;v,s)为从时空网络节点(u,t)到(v,s)的弧段索引，(u,t;v,s)\in A。

参数：c_b(u,t;v,s)为快运箱b占用弧段(u,t;v,s)的费用，b\in B，(u,t;v,s)\in A；C(u,t;v,s)为弧段最大装载能力，(u,t;v,s)\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}；T{d}_i^u为列车i在u站的发车时刻；T{a}_i^u为列车i在u站的到达时刻；T{r}_i^u为列车i从u站到u+1站的区间纯运行时间，min；T{s}_i^u为列车i在u站的停站时间，i\in I,u\in U，min；O_b,D_b分别为快运箱b的起始站和终到站，b\in B；O_i,D_i分别为列车i在运营区段内的首末站，i\in I；T_b^{\mathrm{m}\mathrm{i}\mathrm{n}},T_b^{\mathrm{m}\mathrm{a}\mathrm{x}}分别为快运箱b规定的最早和最晚运达时间限制，b\in B；T_b为快运箱b的待运时刻，b\in B；y_i^u为1表示列车i在u站停站，否则为0，i\in I,u\in U；l为快运箱最大中转次数，次。

变量：x_b(u,t;v,s)为1表示快运箱b占用时空网络弧段(u,t;v,s)，否则为0。

1.3　箱流出行时空网络构建

高铁快运运输方案优化的实质是快运箱在载客动车组列车运输网络上的配流问题^[13]，以载客动车组列车时刻表为依据，在满足快运箱上车时间约束、列车能力及箱流中转的条件下，将到达各站点的快运箱合理分配至各载客动车组列车，对时间具有强依赖性，故在箱流运输物理网络中引入时间维度，构建箱流选择的单层二维时空网络模型，将箱流需求与载客动车组列车间的关系图形化显示。时空网络图如图2所示。

高铁快运箱被运至对应的装车站后有多辆列车可供其选择，即对应多条运输路径。在时间维度上，列车需在快运箱对应装车站的发车时刻晚于其待运时刻且满足其最晚运达期限；在空间维度上，列车需在快运箱的起始站和终到站均停站或者满足其箱流中转接续条件，快运箱才有可能被分配至该列车。如图1所示，在满足时空约束的条件下，快运箱b对应3条运输路径，其运达时间由始发弧、运行弧、停站弧、中转弧及终到弧时间费用组成，不同弧段的选择对应不同的运达时间。因此，研究的核心是在满足列车能力及时空约束的基础上为各快运箱决策运达时间最短所对应的网络弧段。箱流选择时空网络G= (N，A)为由4类节点与5类有向弧构成的有向图，其构建过程如下。

1.3.1　时空网络节点集合

（1）将车站节点拓展为到达层和出发层，对于任意列车i\in I，其时空节点N_i包括列车i到达车站节点(u,t=T{a}_i^u)\in R^u和从车站出发节点(u,t=T{d}_i^u)\in W^u。

（2）对于任意快运箱b\in B，其均具有相应的始发站、终到站、待运时刻及最晚运达时刻属性，故为其添加始发时空点(u=O_b,t=T_b)\in \overline{W^u}和终到时空点(u=D_b,t=T_b^{\mathrm{m}\mathrm{a}\mathrm{x}})\in \overline{R^u}，其中\overline{W^u}为快运箱b的始发时空点集合，\overline{R^u}为终到时空点集合。

因此，高铁快运时空网络节点分别由列车的出发和到达时空节点集合W^u,R^u与快运箱的始发和终到时空节点集合\overline{W^u},\overline{R^u}组成，即N=W^u\bigcup R^u\cup \overline{W^u}\bigcup \overline{R^u}。

1.3.2　时空网络弧段

（1）添加列车运行弧：连接列车在相邻车站出发节点与到达节点的弧段，(u,t;v,s)\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}，其中(u,t)\in W^u,(v,s)\in R^u，表示列车i于T{d}_i^u时刻出发并于T{a}_i^{u+\mathrm{1}}时刻到达u+1站，其费用表示列车在相邻站间的运行时间。

A_{}^{\mathrm{r}\mathrm{u}\mathrm{n}}=\{(u,t;v,s)|(u,t)\in W^u,(v,s)\in R_{}^u,v=u+\mathrm{1},s=t+T{r}_i^u,u\ne d_i\}⑴

（2）添加列车停站弧：连接列车在同一车站到达节点与出发节点的弧段，(u,t;v,s)\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}，其中(u,t)\in R^u,(v,s)\in W^u，表示列车i于T{a}_i^u时刻到达u站并于T{d}_i^u时刻出发，其费用表示列车在u站的停站时间。

A_{}^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}=\{(u,t;v,s)|(u,t)\in R_{}^u,(v,s)\in W_{}^u,s=t+T{s}_i^u,u\ne o_i,d_i\}⑵

（3）添加快运箱始发弧：连接快运箱始发节点与列车在该站出发节点的弧段，(u,t;v,s)\in A^{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{a}\mathrm{r}\mathrm{d}}，其中(u,t)\in \overline{W^u},(v,s)\in W^u，表示待运时刻为T_b的快运箱在O_b站于时刻T{d}_i^{O_b}的始发过程，其费用表示快运箱在其始发站的等待时间。

⑶

（4）添加快运箱终到弧：连接快运箱终到节点与列车在该站到达节点的弧段，(u,t;v,s)\in A^{\mathrm{u}\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}，其中(u,t)\in \overline{R^u},(v,s)\in R^u，表示最晚运达时刻T_b^{\mathrm{m}\mathrm{a}\mathrm{x}}的快运箱在D_b站于时刻T{a}_i^{D_b}的终到过程，其费用表示快运箱运到期限的惩罚值。

⑷

（5）添加箱流中转弧：连接快运箱在同一车站满足接续关系列车间中转的弧段，(u,t;v,s)\in A^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}，其中(u,t)\in R^u,(v,s)\in W^u，表示配装至列车i的快运箱b在u站中转至列车j。对于列车i和列车j而言，二者需在u站满足中转接续条件，即列车i与列车j的中转站须为同一车站，即u=v，且列车i在u站的到达时间T{a}_i^u需早于列车j在u站的发车时间T{d}_j^u，即。其费用表示快运箱在u站的箱流中转时间。

⑸

因此，高铁快运时空网络弧段A分别由列车运行弧A^{\mathrm{r}\mathrm{u}\mathrm{n}}、列车停站弧A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}和快运箱始发弧A^{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{a}\mathrm{r}\mathrm{d}}、快运箱终到弧A^{\mathrm{u}\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}以及箱流中转弧A^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}共同组成。

列车从其运营区段的始发站运行至终到站的过程对应了时空网络中的时空路径，该时空路径反映了列车在其沿途各站的到发时刻信息。对于任意快运箱b\in B而言，时空网络中存在多条运输路径可供其选择，快运箱对于不同网络弧段的占用对应了不同的总运达时间，因此，各弧段费用至关重要，其构成如下所示。

c_b(u,t;v,s)=\left\{\begin{array}{l}\begin{array}{c}T{a}_i^{u+\mathrm{1}}-T{d}_i^u(u,t;v,s)\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}\\ T{d}_i^u-T{a}_i^u(u,t;v,s)\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}\end{array}\\ \begin{array}{c}T{d}_i^{O_b}-T_b(u,t;v,s)\in A^{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{a}\mathrm{r}\mathrm{d}}\\ \mathrm{0}(u,t;v,s)\in A^{\mathrm{u}\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}\\ T{d}_j^u-T{a}_i^u(u,t;v,s)\in A^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}\end{array}\end{array}\right.⑹

2　模型构建

2.1　目标函数

为提高高铁快运运达时效性，提高其产品市场竞争力，以研究时段内快运箱总运达时间最短为优化目标。通过时空网络的构建，将快运箱的运输过程转化为对网络弧段的占用，故目标函数为快运箱占用时空资源最小。

\mathrm{m}\mathrm{i}\mathrm{n}Z=\sum _{b\in B}\sum _{(u,t;v,s)\in A}{c}_b(u,t;v,s)\times x_b(u,t;v,s)⑺

2.2　约束条件

（1）箱流守恒约束。流平衡约束是时空网络优化问题中最基本的约束。通过构建时空网络，将箱流运输转化为对各类网络弧段的占用，对任意快运箱而言，都需保证仅有一条时空路径被其占用，且该时空路径必须在时间和空间维度上保证连通性。

\sum _{(u,t):(u,t;v,s)\in A}{x}_b(u,t;v,s)-\sum _{(u,t):(v,s;u,t)\in A}{x}_b(v,s;u,t)=\left\{\begin{array}{l}-\mathrm{1}(v,s)\in \overline{W^u}，\forall b\in B\\ \mathrm{1}(v,s)\in \overline{R^u}，\forall b\in B\\ \mathrm{0}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}，\forall b\in B\end{array}\right.⑻

（2）列车能力约束。对于任意列车而言，都应保证在其经停站出发时装载的快运箱数量不大于列车最大装载能力。对应到时空网络中，即对于任意列车运行弧而言，其被占用的总次数均应保证不大于列车最大装载能力。

\sum _{b\in B}{x}_b(u,t;v,s)\le C(u,t;v,s)\forall (u,t;v,s)\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}⑼

（3）箱流上车选择约束。对于任意快运箱而言，其对于既有运行列车的选择均应满足以下约束。公式⑽确保快运箱占用的网络弧段费用总和应在其运到期限内，否则不能选择该条时空路径。到达各站点的快运箱均有相对应的运到时间，公式⑾保证仅当列车到达快运箱起始站的时间晚于其运到时间，该快运箱才能被配装至该列车。对于选择直达方式的快运箱而言，公式⑿保证仅当列车在该快运箱的起始站和终到站均停站时，快运箱才可被配装至该列车。

T_b^{\mathrm{m}\mathrm{i}\mathrm{n}}\le \sum _{(u,t;v,s)\in A_{}}c(u,t;v,s)\times x_b(u,t;v,s)\le T_b^{\mathrm{m}\mathrm{a}\mathrm{x}}\forall b\in B⑽

x_b(u,t;v,s)\times s\ge T_b\forall b\in B,\forall (u,t;v,s)\in A^{\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{a}\mathrm{r}\mathrm{d}}⑾

x_b(u,t;v,s)\le \frac{\mathrm{1}}{\mathrm{2}}(y_i^{o_b}+y_i^{d_b})\forall b\in B，\forall (u,t;v,s)\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}⑿

（4）箱流中转约束。对于各快运箱而言，若没有直达列车供其选择时，则可通过2列车间的中转配送至其终到站。公式⒀确保快运箱选择的中转弧可行，即该中转弧连接的2列车i,j\in I均需在中转站u站停车，即y_i^u=y_j^u=\mathrm{1}，且该中转站u站必须为快运箱运达过程的中间站。此外，对于中转的快运箱而言，公式⒁为最大中转次数限制，即保证快运箱无法无限中转，从而缩短运达时间。

x_b(u,t;v,s)\le \frac{\mathrm{1}}{\mathrm{2}}(y_i^u+y_j^u)\forall b\in B,u\in U;\forall (u,t;v,s)\in A_{}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}⒀

\sum _{(u,t;v,s)\in A_{}^{transfer}}{x}_b(u,t;v,s)\le l\forall b\in B⒁

（5）变量域约束。

x_b(u,t;v,s)\in \{\mathrm{0,1}\}\forall b\in B，\forall (u,t;v,s)\in A⒂

3　拉格朗日松弛算法

3.1　原问题分解

从时空资源角度出发，高铁快运箱箱流分配方案可被看作快运箱在时空网络维度上的最短路径集合，每个快运箱的最短路径对应了其在沿途各站的到发时刻信息。若将各快运箱单独考虑，求解其在时空网络上的最短路径，便可快速获得优化的高铁快运箱配装方案。然而，由于列车能力有限，快运箱彼此之间存在排他性和关联性，为了得到可行的配装方案，需要消解各快运箱路径间的潜在冲突。研究所建模型中的列车能力约束⑼为唯一的快运箱耦合约束，会导致快运箱之间彼此影响。下面利用拉格朗日松弛算法对快运箱配装方案模型进行松弛和分解。具体地，对于每条运行弧段a\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}引入非负的拉格朗日乘子\lambda (a)，将模型中的耦合条件松弛，形成拉格朗日松弛模型。

\mathrm{m}\mathrm{i}\mathrm{n}{Z}_{LR}=\sum _{b\in B}\sum _{a\in A}{c}_b(a)\times x_b(a)+\sum _{a\in A_{}^{run}}\lambda (a)\times (\sum _{b\in B}{x}_b(a)-C(a))⒃

拉格朗日函数可转换为

\mathrm{m}\mathrm{i}\mathrm{n}{Z}_{LR}=\sum _{b\in B}\sum _{a\in A}{c}_b(a)\times x_b(a)+\sum _{b\in B}\sum _{a\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}}\lambda (a)\times x_b(a)-\sum _{a\in A_{}^{run}}\lambda (a)\times C(a)⒄

移除公式⒄中的常数项，拉格朗日松弛问题可进一步分解为单个快运箱的子问题。

\mathrm{m}\mathrm{i}\mathrm{n}{Z}_{L{R}_b}=\sum _{a\in A}\overline{c_b}(a)\times x_b(a)⒅

s.t.式⑻，⑽至⒂

其中，\overline{c_i}(a)表示转换后的列车i占用弧段a的拉格朗日费用。

\overline{c_b}(a)=\left\{\begin{array}{l}{c}_b(a)+\lambda (a)a\in A^{\mathrm{r}\mathrm{u}\mathrm{n}}\\ c_b(a)\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.⒆

拉格朗日乘子采用次梯度法更新。

{\lambda }_i^{k+\mathrm{1}}(a)=\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{0},{\lambda }^k(a)+\frac{Z_{IP}^{\mathrm{\text{'}}}(q)-Z_{LD}(q)}{||s^q||}{\beta }^q(\sum _{b\in B}{x}_b(a)-C(a))\}⒇

其中，{\beta }^{k+\mathrm{1}}={\beta }^q·{\mathrm{e}}^{-\mathrm{0.5}{p}^{{(k)}^{\mathrm{2}}}},p^{(k)}=\mathrm{0.15}k/\mathrm{20}。

显然，子问题为求解单个快运箱在时空网络中的最短路径问题，即在满足约束⑻，⑽至⒂条件下，为各快运箱决策最佳配装列车及配装时间。由于中转会导致作业难度增强及快运箱运达时间增长等问题，故优先选择直达运输，当快运箱无可选择的直达列车时，需进行列车间的中转。中转弧的生成步骤为：对任意快运箱b而言，若列车i到达快运箱b的起始站时间晚于其到达该站时间且列车i在快运箱b运达途中的车站u停站，同时，存在后续列车j在快运箱b的终到站停站且列车j在u站停站，则快运箱b可被配装至列车i，运行至u站后中转至列车j。下界生成算法流程如下所示。

步骤1：计算各列车占用各类弧段的时间费用c_b(u,t;v,s)，作为输入参数。

步骤2：初始化快运箱b占用列车i的时空路径费用矩阵time\_cum(b,i)=+\mathrm{\infty }。

步骤3：对于快运箱b，判断列车i是否满足快运箱b直达运输条件，若不满足，则判断快运箱b是否可通过列车i进行中转，更新快运箱b占用列车i的时空路径费用time\_cum(b,i)。

步骤4：判断列车i是否遍历结束，若是则更新快运箱为b=b+1，否则更新列车为i=i+1。返回至步骤3，直至遍历完所有快运箱。

步骤5：得到所有快运箱的初始时空路径费用矩阵time\_cum\_initial(b,i)，对费用矩阵各行求最小值，得到各快运箱b的最佳配装列车i及对应的最小时空路径费用time\_cum\_best(b,i)。在此基础上，求得列车i的运行弧a占用次数矩阵arc\_load(i,a)。

3.2　构造原问题的可行解

由于在求解原问题的下界解时将列车能力约束进行了松弛，故得到的拉格朗日对偶解可能不可行，即部分列车装载的快运箱超过了其最大装载能力。因此，需要通过设计专门的启发式算法，消解快运箱间违背列车能力的冲突，上界生成算法步骤如下。

步骤1：将求得的下界解中的最小时空路径费用time\_cum\_best(b,i)、初始时空路径费用矩阵time\_cum\_initial(b,i)、运行弧占用次数矩阵arc\_load(i,a)作为输入参数。

步骤2：根据运行弧占用次数矩阵arc\_load(i,a)，求得违背列车能力约束的列车列表vehicle\_sel(i)及对应的车站列表station\_sel(i)。

步骤3：判断列车列表长度len(vehicle\_sel(i))是否为0，若是，循环结束，输出当前可行解；否则，转步骤4。

步骤4：更新初始时空路径费用矩阵，若运行弧占用次数矩阵arc\_load(i,a)大于等于列车最大通过能力，则其他可占用该运行弧的快运箱不能再占用，令其为无穷大。

步骤5：对于快运箱b，判断其是否通过列车vehicle\_sel(i)配装，若是，则令其时空路径费用为无穷大，即重新为快运箱b寻找配装列车，转步骤6；否则，更新快运箱为b=b+1。

步骤6：运行弧占用次数矩阵arc\_load(i,a)，返回步骤2。

步骤7：输出可行解，包括：运行弧占用次数矩阵、快运箱配装列车、箱流中转矩阵。

3.3　拉格朗日松弛算法流程

拉格朗日松弛算法流程如图3所示。

步骤1：初始化。输入列车时刻表、快运箱OD及到站时间、列车最大装载能力、最大中转次数等信息，初始化迭代次数k= 0，拉格朗日乘子{\lambda }_i^{(k)}(a) = 0，步长{\beta }^{(k)} = 0.05，最优上界UB=+\mathrm{\infty }，最优下界LB=-\mathrm{\infty }。

步骤2：计算并更新下界。利用3.1节方法求解拉格朗日对偶子问题，更新最优下界为LB=\mathrm{m}\mathrm{a}\mathrm{x}\{LB,L{B}^{(k)}\}。

步骤3：计算并更新上界。利用3.2节方法将拉格朗日对偶解转换为可行解，更新上界为UB=\mathrm{m}\mathrm{a}\mathrm{x}\{UB,U{B}^{(k)}\}。

步骤4：计算GAP值。GAP=(UB-LB)/UB。

步骤5：更新拉格朗日乘子。采用公式⒇方法对拉格朗日乘子{\lambda }_i^{(k)}(a)进行更新。

步骤6：终止条件。若当前循环满足以下任意一条，则算法终止。①k > K，K为最大迭代次数；②GAP\le \epsilon，\epsilon为最小GAP值；③次梯度向量的模长||s^{(k)}|| = 0；④迭代步长{\beta }^{(k)}\le \delta，采用公式⒇更新，否则，转步骤2。

步骤7：输出。输出各列车配装的快运箱、快运箱中转列车及对应车站、快运箱最短时空路径费用。

4　实例测算

西兰高速铁路(西安北—兰州西)作为徐兰高速铁路(徐州东—兰州西)的一部分，全长约650 km，途经定西、天水、宝鸡等重要节点城市，被誉为西北地区交通运输和经济发展的大动脉。由于其建设时间较晚且货运需求较大，故其预留了高铁快运作业基地，从而方便高铁快运业务的开展。选取西兰高速铁路为背景，以该线全天运营的26列快运动车组列车为载运工具，采用载客动车组列车捎带运输模式，列车运行区段示意图如图4所示。假定列车装载能力均为100，某日各站点快运箱需求共2 675个(箱流需求数据可能与实际存在偏差，但并不影响模型与算法的验证)，根据其待运时间及OD站点将其依次编号，为其决策最佳的配装列车及配装时间。

4.1　运输方案分析

选用Python编程语言实现拉格朗日松弛算法，算法运行环境为一台CPU为AMD R7-6800H 3.20 GHz内存16 GB的个人计算机。算法运行时长为772.497 s，迭代次数为16次，拉格朗日对偶解为368 776 min，可行解为371 794 min，优化GAP值为0.008 1，考虑箱流中转的迭代结果如图5所示。到达各站点的快运箱全部被载客动车组列车配送至其目的站点，无快运箱滞留。

（1）列车装载量及满载率分析。根据求解结果，计算得到各列车在其运营区段内所服务的快运箱数量及其平均满载率，列车装载量及满载率如表2所示。兰州—西安区段内运营列车所装载的快运箱数量及其满载率均为最高，而兰州—天水与宝鸡—西安区段内运营列车装载的快运箱数量与满载率则处于较低水平，说明研究时段内载客动车组列车的运能供给与箱流需求匹配程度不高。由于采用载客动车组列车捎带运输模式，其列车时刻表及停站方案均已给定，兰州—西安区段内运营列车数量与停站次数较多，快运箱有更多的运输路径供其选择，从而提升了该区段内运营列车的满载率。

（2）箱流分配情况分析。选取研究时段内的载客动车组列车D2690与D8918对快运箱运输方案进行分析，其发车时间分别为11：47与20：25，高铁快运运输方案如图6所示。动车组列车D2690服务的快运箱OD为1—5、1—6、6—10、7—10，动车组列车D8918服务的快运箱OD为3—5、3—6。其中，由于动车组列车D2690在5站不停站通过，故OD为1—5的44个快运箱需在3站发生箱流中转，换由动车组列车D8918进行服务。

4.2　不考虑箱流中转的运输方案分析

研究考虑了箱流中转的高铁快运运输方案优化，为便于体现考虑箱流中转对运输方案的影响，将仅考虑直达运输条件下的配装方案时空网络优化模型定义为M1，目标函数仍为快运箱总运达时间最短，则M1模型为

\mathrm{M}\mathrm{1}=\left\{\begin{array}{c}\mathrm{m}\mathrm{i}\mathrm{n}Z=\sum _{b\in B}\sum _{(u,t;v,s)\in A}\sum _{i\in I}{c}_b(u,t;v,s)\times x_b(u,t;v,s)\\ \mathrm{s}.\mathrm{t}.\mathrm{式}\mathrm{⑻}\mathrm{至}\mathrm{⑿},\mathrm{⒂}\end{array}\right.

以西兰高速铁路为背景对模型M1进行测试，直达运输迭代结果如图7所示。考虑到直达运输条件下部分箱流可能发生滞留，故通过添加虚拟列车对该问题进行处理，即将选择虚拟列车进行配送的快运箱视为滞留，其他算例数据保持不变。求解结果对比如表3所示。

对表3进行分析，当快运箱不允许发生中转时，部分箱流由于其待运时刻晚于其可选择的直达列车或者受限于列车最大装载能力，导致其发生滞留。在直达运输条件下，仅考虑被既有载客动车组列车服务的快运箱的运达时间，不考虑被虚拟列车服务的快运箱(滞留量)的运达时间，从而导致其求解结果相比于考虑箱流中转条件下更小。

5　结论

针对载客动车组列车捎带模式的高铁快运运输方案进行优化，考虑到载客动车组列车的时空特性，通过构建点-弧时空网络优化模型，以便同时获取快运箱的路径规划与箱流分配方案。基于运输方案时空网络模型规模庞大、求解困难等特性，设计了拉格朗日松弛算法，将原问题分解为求解单个快运箱的最短运输路径问题，并给出了消解违背列车能力约束冲突的上界可行化算法。最后，以西兰高速铁路为背景进行实例分析，研究结果表明以下几点。

（1）相较于直达运输模式，考虑箱流中转的高铁快运运输方案可服务更多的快运箱数量，减少箱流滞留现象，从而提高高铁快运的运达时效性。

（2）研究设计的拉格朗日松弛算法可快速求得满意解，最优GAP值仅为0.8%。此外，设计的可行解算法可有效化解列车能力冲突。

（3）点-弧时空网络优化模型可同时获得快运箱的路径规划与箱流分配方案，从而有效提升求解质量。

参考文献

[1] 周红云. “高铁极速达” 快运产品发展策略研究[J]. 铁道运输与经济，2018，40(7)：23-27.

[2] ZHOU Hongyun. A Research on the Development Strategy of High Speed Railway Immediate Delivery Service[J]. Railway Transport and Economy，2018，40(7)：23-27.

[3] 张　诚，郭侠如，严利鑫. 客货共运模式下高铁快运输送方案设计[J]. 铁道运输与经济，2023，45(6)：8-14.

[4] ZHANG Cheng， GUO Xiaru， YAN Lixin. Design of HSR Express Transportation Scheme under Passenger and Freight Co-Transportation Mode[J]. Railway Transport and Economy，2023，45(6)：8-14.

[5] 陈星瀚，周培宇，郎茂祥，等. 需求变动下高铁快运货流分配与组织模式优化[J]. 交通运输系统工程与信息，2022，22(5)：174-186.

[6] CHEN Xinghan， ZHOU Peiyu， LANG Maoxiang，et al. High Speed Railway Express Cargo Flow Allocation and Operation Organization Optimization under Varying Demand[J]. Journal of Transportation Systems Engineering and Information Technology，2022，22(5)：174-186.

[7] 晁宇宏，高如虎，牛惠民. 基于备选集的高铁快运专列开行方案优化[J]. 铁道科学与工程学报，2022，19(12)：3505-3514.

[8] CHAO Yuhong， GAO Ruhu， NIU Huimin. Optimization of Train Plan on High Speed Railway Immediate Delivery Based on Candidate Train Set[J]. Journal of Railway Science and Engineering，2022，19(12)：3505-3514.

[9] NIU H M， ZHOU X S， GAO R H. Train Scheduling for Minimizing Passenger Waiting Time with Time-Dependent Demand and Skip-Stop Patterns：Nonlinear Integer Programming Models with Linear Constraints[J]. Transportation Research Part B：Methodological，2015，76：117-135.

[10] 曹佳峰. 高铁快运运输组织策略研究[J]. 铁道货运，2022，40(2)：6-10.

[11] CAO Jiafeng. Study of the Transportation Organization Strategy for High Speed Rail Express[J]. Railway Freight Transport，2022，40(2)：6-10.

[12] 张云逸，刘文歌. 高铁快运物流运输组织优化研究[J]. 铁道货运，2020，38(4)：1-5.

[13] ZHANG Yunyi， LIU Wenge.A Study on the Strategies to Improve High Speed Rail Express Logistics Organization[J].Railway Freight Transport，2020，38(4)：1-5.

[14] TIAN X P， NIU H M. Optimization of Demand-Oriented Train Timetables under Overtaking Operations：A Surrogate-Dual-Variable Column Generation for Eliminating Indivisibility[J]. Transportation Research Part B：Methodological，2020，142：143-173.

[15] GAO R H， NIU H M. A Priority-Based ADMM Approach for Flexible Train Scheduling Problems[J]. Transportation Research Part C：Emerging Technologies，2021，123：102960.

[16] WU J M， KULCSÁR B，AHN S，et al. Emergency Vehicle Lane Pre-Clearing：From Microscopic Cooperation to Routing Decision Making[J]. Transportation Research Part B：Methodological，2020，141：223-239.

[17] YANG Z H， SONG R. Transport Scheme Design for Emergency Supplies Carried by High Speed Passenger Trains[C]//2020 IEEE 5th International Conference on Intelligent Transportation Engineering (ICITE). September 11-13，2020，Beijing，China. IEEE，2020：551-555.

[18] 陈京亮. 铁路行包装运方案编制方法的研究[J]. 中国铁道科学，2012，33(1)：108-112.

[19] CHEN Jingliang. Research on the Compilation Method for the Shipping Scheme of Railway Luggage and Parcel[J]. China Railway Science，2012，33(1)：108-112.

[20] NIU H M， ZHOU X S， TIAN X P. Coordinating Assignment and Routing Decisions in Transit Vehicle Schedules：A Variable-Splitting Lagrangian Decomposition Approach for Solution Symmetry Breaking[J]. Transportation Research Part B：Methodological，2018，107：70-101.

[21] XU G M， LIU W， YANG H. A Reliability-Based Assignment Method for Railway Networks with Heterogeneous Passengers[J]. Transportation Research Part C：Emerging Technologies，2018，93：501-524.

[22] LI X J， LI D W， HU X T，et al. Optimizing Train Frequencies and Train Routing with Simultaneous Passenger Assignment in High Speed Railway Network[J]. Computers & Industrial Engineering，2020，148：106650.

[23] 王　泽，潭宇燕，魏玉光. 基于拉格朗日松弛的铁路行包运输方案编制方法研究[J]. 铁道学报，2021，43(11)：8-17.

[24] WANG Ze， TAN Yuyan， WEI Yuguang. Method of Development of Railway Package Transportation Scheme Based on Lagrangian Relaxation[J]. Journal of the China Railway Society，2021，43(11)：8-17.

[25] 刘　勇，朱晓宁，闫柏丞，等. 基于既有运行图的高铁行包运输方案优化[J]. 武汉理工大学学报(交通科学与工程版)，2016，40(6)：1038-1042.

[26] LIU Yong， ZHU Xiaoning， YAN Baichen，et al. Express Freight Transportation Plan Optimization Based on Existed High Speed Railway Timetable[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering)，2016，40(6)：1038-1042.

[27] 金　伟，李夏苗，周凌云，等. 基于列生成算法的高速铁路快捷货运组织方案优化研究[J]. 铁道学报，2020，42(9)：26-32.

[28] JIN Wei， LI Xiamiao， ZHOU Lingyun，et al. Research on Optimization of High Speed Railway Freight Transportation Organization Scheme Based on Column Generation Algorithm[J]. Journal of the China Railway Society，2020，42(9)：26-32.

[29] 高如虎，牛惠民，江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报，2020，42(5)：1-8.

[30] GAO Ruhu， NIU Huimin， JIANG Yuxing. Train Timetable Rescheduling Based on a Time-Station-Track Multi-Dimensional Network under Condition of Running Extra Trains for High Speed Railway[J]. Journal of the China Railway Society，2020，42(5)：1-8.