Optimization Model and Algorithm of Additional Trains Scheduling in High-Speed Railway Timetables Considering Passenger Demand
-
摘要:
在既有列车运行图中插入新增列车运行线是铁路运输企业编制每季度列车运行图和日计划中列车运行计划所常采用的方法，然而，传统人工编制手段效率低且难以保证列车运行图编制质量. 对此，本文以降低铁路运营和调度成本以及运输尽可能多的旅客等为优化目标，基于离散时空网络构建综合优化列车开行方案和新增列；车运行线的整数线性规划模型；针对模型特点，设计基于拉格朗日松弛的启发式求解算法，将原问题分解为列车开行方案优化子问题和一组为单列列车搜索费用最小的时空路径子问题；最后以京沪高速铁路为算例，验证模型的正确性和算法可行性. 研究结果表明：所提方法能快速自动生成新增列车运行线后的列车运行图，且求得的上界解质量相比顺序求解方法平均提升了4.58%.
Abstract:Objective: Railway operators enhance the alignment between transportation services and passenger demand by making quarterly adjustments to the basic train timetable and preparing next-day train operation plans based on it. However, the structural complexity of the basic timetable significantly complicates the generation of these two technical plans. To address this challenge within the framework of manually generated transport plans, railway operators commonly insert additional spatio-temporal train paths into the basic timetable while making reasonable adjustments to the original paths. Furthermore, incorporating passenger demand into the generation of these two technical plans can evidently result in train timetables that better meet market needs.Methods: To effectively utilize the remaining capacity of the basic timetable, two adjustment measures were applied to trains in the original train timetable: flexible adjustment of train stop patterns and time, including departure time at origin stations, and dwell time at intermediate stations. An integer linear programming model was developed for the integrated optimization of line planning and additional train scheduling problems based on a spatio-temporal network modeling framework. The objective function was formulated from the perspective of balancing the interests of both railway operators and passengers. The benefits of railway operators were represented by the total travel time of all trains and penalties imposed for adjusting stop patterns, as well as departure and dwell time of original trains, whereas passenger benefits were reflected in maximizing the number of passengers transported. The coefficients of the sub-objectives were determined based on practical operations and empirical experience. Moreover, practical constraints were considered, including the uniqueness of train stop patterns, train capacity, the relationship between passenger demand allocation decision variables and train stop pattern selection variables, minimum headway requirements, and the coupling of subproblems.Given the characteristics of the model, a Lagrangian relaxation-based heuristic algorithm was designed. By dualizing the headway requirements and coupling constraints into the objective function through Lagrangian multipliers, the original problem was decomposed into two independent subproblems: a line planning subproblem and an additional train scheduling subproblem. The algorithm iteratively solved subproblems by calling the commercial solver and a forward dynamic programming algorithm, respectively.Results: To evaluate the effectiveness of the proposed model and algorithm, a set of numerical experiments based on the Beijing–Shanghai high-speed railway corridor was conducted. Moreover, the same scenarios were also solved using a sequential solving approach commonly employed in practical operations, where the line planning problem was optimized first, followed by the generation of the train timetable. The efficiency of the proposed algorithm was more comprehensively evaluated by comparing the solution results of the two methods.In all scenarios, the proposed algorithm successfully obtained the optimal upper bound solution within the maximum number of iterations, with an average optimality gap of 3.21%. Compared to the sequential solving approach, the proposed model and algorithm improve the quality of the upper bound solutions by an average of 4.58%. This improvement is attributed to the fact that the sequential solving approach prioritizes higher-quality solutions in the line planning subproblem, which, in turn, leads to a more significant deterioration in the solution quality of the additional train scheduling subproblem. Besides, the proposed algorithm is able to achieve a feasible upper bound solution within the first 200 iterations, while further iterations can yield even better results.The optimized train timetable shows that approximately 5% of the original trains undergo time adjustments exceeding 10 minutes throughout their entire journey. Moreover, for around 10% of the original trains, significant adjustments have been made to certain timings along the journey, whereas their departure from origin stations and arrival time at destination stations remain unchanged. Both findings reflect the structural complexity of the timetable and its inherent robustness. Passenger demand allocation results indicate that over 10% of the trains have seat occupancy rates below capacity across three or more segments. However, compared to short-distance passengers, a larger proportion of long-distance passengers remains unserved.Conclusion: By considering passenger flow demand, integrating the additional train scheduling with the line planning can generate train timetables that provide higher overall system efficiency. To reduce the difficulty of basic timetable adjustments and train operation plan generation, spatio-temporal paths of additional trains should be scheduled in a way that maintains the arrival and departure time of higher-priority trains and minimizes changes to the overtaking relationships among trains. Additionally, to lower operational costs for railway operators and better meet passenger travel needs, priority should be given to accommodating long-distance passenger travel demand in daily operations. In future research, more practical factors should be incorporated into the modeling process, such as more detailed and accurate representations of the interests of railway operators and passengers, as well as time-varying passenger demand. Besides, the problem-solving framework should integrate other operational aspects, such as platform track allocation and rolling stock circulation plan, so as to further enhance the feasibility of the generated train timetables. -
在交通强国战略加快推进、交通运输领域基础设施建设逐步完善的背景下，隧道施工技术日趋成熟，长大隧道（长度超过1.00 km）不断涌现. 目前，我国已建成了世界最长的双洞高速公路隧道—秦岭终南山隧道（18.02 km）[1]，海拔
3000 m以上的世界最长隧道—新关角隧道（32.70 km）[2]，以及亚洲最长的单孔双线高速铁路隧道—秦岭天华山隧道（16.00 km）[3]. 面对隧道建设技术的持续革新和隧道需求的井喷式增长，我国隧道建设的规模和难度已位居世界第一，超长、超深隧道建设迎来新的发展机遇.在隧道建设过程中，地质条件复杂，视觉环境不良，施工作业难度大，具有一定的风险[4]. 因此，隧道施工期间的组织管理成为规避事故风险、保证施工效率的重要途径. Sousa等[5]研究了隧道施工过程中的事故案例，强调隧道组织管理在降低施工风险，减少施工事故方面的重要性. Zhu等[6]调查统计了我国2010年～2020年发生的重大隧道施工事故发现，低下的组织管理水平会导致施工过程中事故频发. 值得注意的是，施工车辆的运输组织管理已成为严重制约施工安全和施工效率的重点环节，隧道内的渣土运输、人员输送、交通物流配送等成为限制施工效率的瓶颈问题. 施工车辆在路况恶劣、能见度低的长大隧道内交通组织紊乱，不仅严重影响施工进度，还会增加运输安全隐患.
考虑到隧道内错综复杂的交通线路，科学的运输组织管理势在必行. 特别是长大隧道施工过程中对于施工交通流的合理组织和有效管控有利于提高施工效率，保障施工安全. 目前，国内外已有一些学者对隧道的运输组织管理进行了相关研究. Jiang等[7]通过VISSIM对隧道出入口车辆的运行情况进行仿真模拟，提出隧道施工期间隧道出入口及其周边的交通流组织优化方案. Liu等[8]在权衡施工车辆运输效率和安全性的基础上，建立了包含限高、限重、限速等约束条件的双目标车辆运输路径优化模型. 林杉等[9]提出了一种高速公路隧道交通瓶颈元胞自动机模型，为制定隧道内的交通流组织方案提供依据. 高壮[10]基于重载铁路的线路条件研究设计出 2 种隧道内无砟轨道施工物流组织方案，极大地提高了施工组织效率. 然而，现有的大多数研究都是从宏观的角度提出广泛的、借鉴性较强的交通物流组织方案，尚未有着眼于隧道内部交通冲突疏解的多工种施工车辆时刻表和运行路径的优化研究.
车辆时刻表和路径规划的协同优化问题在铁路开行方案和列车时刻表制定，公交循环计划，集装箱码头智能转运车路径、时刻规划以及智能机器人路径规划（避撞）等领域具有广泛的应用[11-14]. Zhang等[11]从宏观层面提出了一种基于扩展时空网络的列车运行周期表模型来得到最佳列车循环方案. 王志建等[12]根据公交车IC刷卡数据构建了多模式公交路网模型来设计满足乘客多种需求的路径规划方案. Cherif等[13]基于Peri网对自动化智能转运车在码头的时间调度和路径规划问题进行了研究. 徐翔斌等[14]将多自动引导车（AGV）的路径转化为离散时空网络下的路径，建立基于离散时空网络的路径优化模型. 由此可见，虽然车辆时刻表和路径的协同优化问题近年来受到了广泛关注，但是少有研究关注到隧道内部施工车辆的时刻表与运行路径的协同优化问题. 与一般隧道相比，长大隧道内道路线形差，施工车辆需求大，面临比上述领域更为棘手的难题. 如果不规定施工车辆的发车频率和路径时刻表，那么混乱、不均匀、不规律的发车会使车辆间产生过多的交通冲突，迫使车辆停止运行，进行掉头、避让、后退等操作，将严重影响施工效率.
在疏解冲突方面，Zhang等[15]针对自动导引车的离线路径规划问题，提出了一种无冲突路径规划方法. 李珣等[16]建立了基于元胞自动机的精细化车道模型，研究新的交通流模型在减少车辆堵塞方面的作用. 李英帅等[17]建立交通冲突预测模型，对直线式单泊位公交停靠站设置进行优化. 本文考虑到长大隧道内部的恶劣路况和复杂交通流促使多工种施工车辆间形成交通冲突的实际情况，对施工车辆的发车时刻表和运行路径的进行协同优化，实现交通冲突的有效消除，保证施工安全.
为解决上述难题，本文立足于施工车辆作业过程，构建路网层面的车辆时刻表和运行路径协同优化模型，并将模型重构为整数线性规划模型，利用GUROBI进行求解，制定施工车辆总运行时间最短的运输组织方案. 该优化方案能够有效疏解车辆间的交通冲突，协助调度员实施决策调度，使施工车辆在保证安全的前提下高效完成运输任务.
1. 问题描述
一般隧道的路况简单，施工过程中需求单一，多数研究侧重于其微观层面的组织管理. 而长大隧道内部道路狭长，路况复杂，需要从宏观层面对施工车辆的运输组织进行规划与管理. 在长大隧道施工作业的过程中，不同工种的施工车辆要求在指定需求点完成运渣、运材料、运人等任务.
1.1 隧道交通网络拓扑建模
长大隧道内的施工道路交通网络由正线、平导线、横洞等交错构成的复杂方格状道路网络，包含节点和路段2种基本要素. 其中，节点为路段间的交叉点，代表路段的交叉口. 交叉口按照交叉方式可分为“十字型交叉”和“T字型交叉”. 路段是连接节点的线段，代表供车辆行驶的道路，按照可供车辆行驶的方向数量分为单向路段和双向路段. 其拓扑结构如图1 所示.
图 1 隧道内部基本交通单元拓扑Figure 1. Topological diagram of basic traffic units inside the tunnel本文考虑了长大隧道内部的多样运输需求，包括运渣需求、运材料需求和运人需求. 因此，施工车辆由运渣车辆、运材料车辆和运人车辆组成，对应于不同类型的需求点. 施工车辆的作业流程包括：驶入隧道、到达需求点并完成指定运输任务、驶出隧道. 根据隧道内节点及路段间的物理连接关系，图2展示出了隧道内部的交通网络及其拓扑图.
由于隧道内部单、双向路段混合共存，行驶环境恶劣，且施工车辆本身体积大、运载质量大，其在运输过程中容易在交叉口和单向路段发生交通冲突，形成通行瓶颈，妨碍其他车辆正常通行. 根据产生原因可将交通冲突分为交叉冲突、相向冲突和赶超冲突，如图3所示. 交叉冲突是指车辆在很短的时间范围内到达同一交叉点而产生的冲突；相向冲突是指对向行驶的车辆在单向路段上相遇而产生的冲突；赶超冲突是指不同的速度的车辆在单向路段上同向行驶而产生的冲突.
2. 模型构建
在模型中，车辆时刻表的决策变量属于整数变量，车辆的运行路径由表示车辆是否经过某路段的一系列0-1变量决定.
2.1 模型假设
为了简化问题，方便后续模型的建立和求解，本文做出以下假设：
假设1. 施工车辆的运行路径分为去程和返程方向. 另外，为简化求解过程，指定车辆在去程和返程期间任意路段上的唯一可行方向，即简化车辆去程和返程方向上的有向弧集合.
假设2. 施工车辆的限速条件预先给定，其在路段上的运行时间范围由最高和最低限速确定.
假设3. 隧道内，同向行驶的车辆遵循先到先服务（FIFO）原则，即同向行驶的车辆中，先到达某路段的车辆先从该路段离开.
2.2 数学描述
隧道内的拓扑网络由有向网络${\mathcal{G}}=({\mathcal{N}}, {\mathcal{A}}) $表示，$ \mathcal{N} $为节点集合，$ \mathcal{A} $为路段集合，节点$ i, j \in \mathcal{N} $，有向弧$ (i, j) \in \mathcal{A} $，$ i \neq j $. $ \mathcal{U}=\{1,2\} $表示车辆的行驶方向集合，用$ t, u_{\mathrm{a}} \in \mathcal{U} $进行索引. 当$ u=1 $或$ u_{\mathrm{a}}=1 $时，车辆从隧道入口向需求点行驶，当$ t=2 $或$ u_{\mathrm{a}}={2} $时，车辆从需求点向隧道出口行驶. $ \mathcal{A}_{u} $表示$ u $方向上的路段集合，$ \mathcal{A}_{{\mathrm{s}}} $表示单向路段集合，$ \mathcal{K} $表示车辆集合，用$ k, k_{\mathrm{a}} \in \mathcal{K} $进行索引.
1） 车辆行驶路径的0-1决策变量：
xk,ui,j={1,若车辆k在u方向上经过路段(i,j)0,其他. 2） 车辆时刻表的决策变量：
$ h^{k} $为车辆$ k $的发车间隔.
3） 车辆到达和离开路段事件的相关变量：
$ a_{i,j}^{k,u} $为车辆$ k $在$ {u} $方向上到达路段$ (i, j) $的时刻，
$ d_{i,j}^{k,u} $为车辆$ k $在$ {u} $方向上离开路段$ (i, j) $的时刻.
2.3 目标函数和约束条件
隧道内多工种施工车辆的运输组织方案在保证系统安全的基础上，设计施工车辆的发车时刻表，合理安排运行路径，尽可能高效率地完成各项运输任务. 因此，模型以最小化所有车辆的运行（行驶）总时间为目标建立目标函数. 每辆车的行驶时长为$ \displaystyle\sum\limits_{\left( i,{{d}_{{\mathrm{s}}}} \right)\in \mathcal{A}}{d_{i,{{d}_{{\mathrm{s}}}}}^{k,2}}-\displaystyle\sum\limits_{\left( {{o}_{{\mathrm{s}}}},j \right)\in \mathcal{A}}{a_{{{o}_{{\mathrm{s}}}},j}^{k,1}}$，目标函数表示如式（1）所示.
minZ=∑k∈K(∑(i,ds)∈Adk,2i,ds−∑(os,j)∈Aak,1os,j), (1) 式中：$ o_{{\mathrm{s}}} $为隧道入口，即车辆去程方向上的起点$ o_{k, 1} $；$ d_{{\mathrm{s}}} $为隧道出口，即车辆返程方向上的终点$ d_{k, 2} $.
1） 车辆路径约束
车辆$ k $在$ {u} $方向上从起点$ o_{k, {u}} $出发，沿着路段驶过中间节点后到达终点$ d_{k,u} $，需满足所有车辆的路径均被规划（式（2）～（3））. 对于去程，车辆的起点为隧道入口，终点为相应需求点. 对于返程，车辆的起点为需求点，终点为隧道出口.
∑(ok,u,j)∈Auxk,uok,u,j=1,∀k∈K,u∈U, (2) ∑(i,dk,u)∈Auxk,ui,dk,u=1. (3) 2） 流量守恒约束
中间节点必须满足流量守恒约束，即节点流入等于节点流出，如式（4）所示.
∑(ia,i)∈Auxk,uia,i=∑(i,j)∈Auxk,ui,j,∀i∈N∖{ok,u,dk,u},k∈K,u∈U. (4) 3） 路径和时刻联系约束
只有车辆经过某一路段，才能得到其在该路段上的到达时刻和离开时刻，满足式（5）～（6）. 其中，$ M $是一个非常大的正数. 式（5）中，当车辆$ k $在方向$ {u} $上经过路段$ (i, j) $，即$ x_{i,j}^{k,u}=1 $时，$ 0 \leqslant a_{i, j}^{k, u} \leqslant M $，规定了$ a_{i, j}^{k, u} $的取值范围，强调了其非负特性，使$ a_{i, j}^{k,u} $具有实际意义. 而当车辆$ k $在$ {u} $方向上不经过路段$ (i, j) $，即$ x_{i, j}^{k, u}=0 $时，$ -M \leqslant a_{i, j}^{k,u} \leqslant 0 $，$ a_{i, j}^{k,u} $不具有实际意义. 式（6）中的$ d_{i,j}^{k,u} $同理.
(xk,ui,j−1)M⩽ak,ui,j⩽xk,ui,jM,∀(i,j)∈A,k∈K,u∈U, (5) (xk,ui,j−1)M⩽dk,ui,j⩽xk,ui,jM,∀(i,j)∈A,k∈K,u∈U. (6) 4） 发车间隔约束
在隧道中，受到技术条件和安全性能的限制，施工车辆需要满足一定的发车间隔要求，即满足式（7）.
hmin⩽hk⩽hmax,∀k∈K, (7) 式中：$ h_{\text {min }} $、$ h_{\max } $分别为给定的最小和最大发车间隔.
5） 路网进入时间约束
为保证车辆有序运行，车辆$ k $进入路网的时间由已出发车辆的发车间隔决定，满足式（8）.
∑(os,j)∈A1ak,1os,j=k∑ka=1hka,∀k∈K, (8) 式中：${\mathcal{A}_1} $为去程方向上的路段集合.
6） 路网运行时间约束
路网运行时间是指从第一辆车驶入路网开始直到最后一辆车驶出路网的总时间，即施工车队对于路网的使用周期. 路网存在一个最大的运行时间，在现实情况中可能是隧道内路段的最大工作时长或施工队的最长工时. 最后执行运输任务的车辆$ K $必须在到达路网的最大运行时间$ t_{\text{max}} $之前离开路网，即满足式（9）.
∑(i,ds)∈A2dK,2i,ds⩽tmax (9) 7） 路段运行时间约束
车辆在路段上的行驶时间范围取决于路段的长度和限速条件，满足式（10）.
τ(r)i,j,k⩾li,jvmaxk,∀(i,j)∈A,k∈K, (10) 式中：$ l_{i j} $为路段$ (i, j) $的长度，$ v_{\max {\mathrm{k}}} $为车辆$ k $的最大行驶速度，$ \tau_{i j, k}^{({\mathrm{r}})} $表示车辆$ k $在路段$ (i, j) $上的运行时间.
8） 路段到达和离开时刻约束
车辆离开某一路段的时刻等于到达该路段的时刻与路段上的行驶时间之和，即满足式（11）. 除了起始路段外，车辆到达某一路段的时刻等于离开上一路段的时刻，即满足约束条件（12）.
dk,ui,j=ak,ui,j+τ(r)i,j,k,∀(i,j)∈A,k∈K,u∈U (11) ak,ui,j=∑(ia,i)∈Audk,uia,i,∀(i,j)∈Au,i≠ok,u,i≠j,k∈K,u∈U. (12) 9） 去程和返程联系约束
对于车辆$ k $，其去程的终点和返程的起点相同，都为执行任务的需求点. 另外，车辆从返程起点出发的时刻等于离开去程终点的时刻与需求点服务时间之和，满足式（13）.
∑(ok,2,j)∈A2ak,2ok,2,j=∑(ia,dk,1)∈A1dk,1ia,dk,1+τ(w)dk,1,∀k∈K, (13) 式中：$ \boldsymbol{\tau}_{d_{k, 1}}^{({\mathrm{w}})} $表示需求点的服务时间.
10） 冲突疏解约束
为避免施工车辆间的碰撞、追尾事故，保障隧道内的运输安全，需要对车辆间的交叉冲突、相向冲突和赶超冲突进行疏解.
11） 交叉冲突疏解
若2辆车在短时间内到达同一交叉点，则会形成交叉冲突. 所以要求到达同一交叉口车流的时间间隔必须满足可保障安全的最低时间限制，满足式（14）.
|ak,uj,i−dka,uaia,j|+(1−xk,uj,i)M+(1−xka,uaia,j)M⩾τ(m)min,∀j∈N,(j,i)∈A,(ia,j)∈A,k,ka∈K,k≠ka,u,ua∈U, (14) 式中：$ \tau_{\mathrm{mim}}^{(\mathrm{m})} $表示最小会车时间间隔.
12） 相向冲突疏解约束
若2辆车在单向路段上相向而行，则会发生相向冲突. 为了避免这类情况的发生，需要保证先到达的车辆对于路段的优先使用权，满足式（15）.
(ak,ui,j−aka,uaj,i)(ak,ui,j−dka,uaj,i)+(1−xk,ui,j)M+(1−xka,uaj,i)M⩾1,∀(i,j)∈As,k,ka∈K,k≠ka,u,ua∈U. (15) 13） 赶超冲突疏解约束
若2辆车在单向路段上同向而行，由于速度不同，可能会发生赶超冲突. 在现实情况中，车辆一般遵守先到先服务的原则，满足式（16）.
(ak,ui,j−aka,uai,j)(dk,ui,j−dka,uai,j)⩾0,∀(i,j)∈As,k,ka∈K,k≠ka,u,ua∈U. (16) 14） 路段瓶颈约束
隧道内的每一路段都有通行能力限制. 当行驶车辆大于路段通行能力时，该路段成为瓶颈路段，路网安全性大幅度降低，所以需要满足式（17）.
∑k∈K∑u∈Uxk,ui,j⩽Ci,j,∀(i,j)∈A, (17) 式中：$ C_{i, j} $表示路段$ (i, j) $的最大通行能力.
15） 变量约束
车辆运行路径和时刻表的决策变量以及车辆到达和离开路段事件的相关变量满足式（18）.
{xk,ui,j∈{0,1},∀(i,j)∈A,k∈K,u∈U,ak,ui,j,dk,ui,j,hk⩾0且为整数,∀(i,j)∈A,k∈K,u∈U, (18) 3. 模型重构
本文建立的模型为整数非线性规划模型，为方便求解，结合假设1的简化条件对模型进行线性化处理，为接下来使用GUROBI求解模型做准备.
首先，通过引入$ M $，对式（11）和式（12）进行了线性化处理，得到式（19）和式（20）.
dk,ui,j⩾ak,ui,j+τ(r)i,j,k−M(1−xk,ui,j),∀(i,j)∈A,k∈K,u∈U (19) ak,ui,j⩾∑(ia,i)∈Audk,uia,i−M(1−xk,ui,j),∀(i,j)∈Au,i≠ok,u,i≠j,k∈K,u∈U (20) 根据假设1，简化后模型中去程和返程上的有向弧均为单向弧，则式（14）可简化为式（21）. 另外，由于GUROBI可对绝对值进行运算，不对式（14）进行线性化处理.
|∑u∈Uak,uj,i−∑u∈Udka,uia,j|+(1−∑u∈Uxk,uj,i)M+(1−∑u∈Uxka,uia,j)M⩾τ(m)min,∀j∈N,(i,j)∈A,(ia,j)∈A,k,ka∈K,k≠ka (21) 类似地，式（15）可简化为式（22）. 式（22）的线性化处理的结果如式（23）～（26）所示. 需要注意：$ \delta_{i, j, k, k_{\mathrm{a}}} $为0-1变量，用于辅助式（22）的线性化处理. 当$ \delta_{i, j, k, k_{\mathrm{a}}}=1 $时，式（23）和（25）的约束条件成立，式（24）和（26）的约束条件被放松，表明此时车$ k_{\mathrm{a}} $先进入路段，且在车$ k $进入路段之前就离开路段，保证不发生相向冲突. 同理，当$ \delta_{i, j, k, k_{\mathrm{a}}}=0 $时，式（24）和（26）的约束条件成立，式（23）和（25）的约束条件被放松，表明此时车$ k $先进入路段，且在车$ k_{\mathrm{a}} $进入路段之前就离开路段，保证不发生相向冲突.
(∑u∈Uak,ui,j−∑u∈Uaka,uj,i)(∑u∈Uak,ui,j−∑u∈Udka,uj,i)+(1−∑u∈Uxk,ui,j)M+(1−∑u∈Uxka,uia,j)M⩾1,∀(i,j)∈As,k,ka∈K,k≠ka, (22) ∑u∈Uak,ui,j−∑u∈Uaka,uj,i⩾1−(1−δi,j,k,ka)M−(2−∑u∈Uxk,ui,j−∑u∈Uxka,uj,i)M,∀(i,j)∈As,k,ka∈K,k≠ka (23) ∑u∈Uaka,uj,i−∑u∈Uak,ui,j⩾1−δi,j,k,kaM−(2−∑u∈Uxk,ui,j−∑u∈Uxka,uj,i)M,∀(i,j)∈As,k,ka∈K,k≠ka, (24) ∑u∈Uak,ui,j−∑u∈Udka,uj,i⩾1−(1−δi,j,k,ka)M−(2−∑u∈Uxk,ui,j−∑u∈Uxka,uj,i)M,∀(i,j)∈As,k,ka∈K,k≠ka, (25) ∑u∈Uaka,uj,i−∑u∈Udk,ui,j⩾1−δi,j,k,kaM−(2−∑u∈Uxk,ui,j−∑u∈Uxka,uj,i)M,∀(i,j)∈As,k,ka∈K,k≠ka. (26) 与式（15）的处理方式相同，式（16）可简化为式（27），线性化处理结果如式（28）、（29）所示. $ \xi_{i, j, k, k_{\mathrm{a}}} $为0-1变量. 当$ \xi_{i, j, k, k_{\mathrm{a}}}=1 $时，$ k $车先进入路段，先离开路段，保证不发生赶超冲突；当$ \xi_{i, j, k, k_{\mathrm{a}}}=0 $时，车$ k_{\mathrm{a}} $先进入路段，先离开路段，保证不发生赶超冲突.
(∑u∈Uak,ui,j−∑u∈Uaka,ui,j)(∑u∈Udk,ui,j−∑u∈Udka,ui,j)⩾0,∀(i,j)∈As,k,ka∈K, (27) −Mξi,j,k,ka⩽∑u∈Uak,ui,j−∑u∈Uaka,ui,j⩽(1−ξi,j,k,ka)M,∀(i,j)∈As,k,ka∈K, (28) −Mξi,j,k,ka⩽∑u∈Udk,ui,j−∑u∈Udka,ui,j⩽(1−ξi,j,k,ka)M,∀(i,j)∈As,k,ka∈K, (29) δi,j,k,ka,ξi,j,k,ka∈{0,1},∀(i,j)∈As,k2,ka∈K (30) 4. 案例分析
某长大隧道项目共有20辆施工车辆执行运渣、运材料、运人任务，包括12辆运渣车、4辆运材料车和4辆运人车. 隧道只有一个出入口，所有施工车辆均从该口驶入驶出隧道.
4.1 隧道网络拓扑
与一般隧道不同，长大隧道内部道路狭长，单双向路段混合，路网呈现纵横交错的结构. 本文将隧道抽象为近似3 × 5的网格结构，并对各节点进行编号，如图4所示. 其中，黄色节点为隧道出入口，绿色节点为运渣需求点，紫色节点为运材料需求点，红色节点为运人需求点，蓝色节点为中间节点. 可以看出，紫色节点，即运材料需求点也是隧道施工过程中的断点. 节点之间通过路段连接，有向双线箭头代表双向路段，有向单线箭头代表单向路段，路段上的数值代表节点间的距离. 根据假设1，对去程和返程方向上的有向弧进行简化，在去程方向上规定右行和下行有向弧，在返程方向上规定左行和上行的有向弧，如图5所示. 令Vq为图5中对应的节点. $q \in \{0,1,\cdots,16\} $.
图 5 去返程方向的隧道网络拓扑图Figure 5. Tunnel network topology diagram in inbound and outbound directions4.2 编制隧道交通组织方案
模型求解时，运行计算机硬件环境为Intel （R） Core （TM） i5-6200U CPU，主频2.40 GHz，内存8 GB；软件环境为Windows10系统，使用Python调用GUROBI求解器. 在该案例中，基于铁路隧道工程施工技术指南[18]，通过调查成兰铁路跃龙门隧道施工组织实际案例[19]，对各参数进行了规定和限制. 参考成兰铁路龙门隧道案例中车队的施工周期要求，规定路网的最大运行时间为100 min. 考虑到铁路隧道工程施工技术指南中提出的安全规范，结合成兰铁路跃龙门隧道案例涉及的车速限制，我们令运渣车（KM）和运材料车（KC）的最高限速为30 km/h，运人车（KP）的最高限速为40 km/h，车辆的最小和最大发车间隔分别为1 min和4 min，最小会车时间间隔和安全时间间隔均为1 min，单向路段和双向路段的最大通行能力分别为10辆和20辆车. 案例中20辆施工车辆根据最短行驶路径和最高行驶速度得到的施工运输组织初始方案，见表1. 然后本文使用GUROBI求解器，经过
1661 s后求解得到基于重构的整数线性规划模型的施工运输组织优化方案，见表2.表 1 施工运输组织初始方案Table 1. Initial construction organization scheme编号 车辆进入隧道运行方案 车辆离开隧道运行方案 始发时刻 运行路径 始发时刻 运行路径 KP1 0 0-1-2-5-8-11-14 13 14-11-8-5-4-1-0 KP2 1 0-1-4-5-8-11-14 14 14-11-8-5-2-1-0 KP3 2 0-1-4-5-8-11-14 15 14-11-8-5-2-1-0 KP4 3 0-1-4-5-8-11-14 16 14-11-8-5-2-1-0 KC1 4 0-1-2-3-6-9 15 9-6-3-2-1-0 KC2 5 0-1-2-3-6-9 16 9-6-3-2-1-0 KC3 6 0-1-2-3-6-9 17 9-6-3-2-1-0 KC4 7 0-1-2-3-6-9 18 9-6-3-2-1-0 KM1 8 0-1-4-7-10-13 23 13-10-7-4-1-0 KM2 9 0-1-4-7-10-13-14-16 27 16-14-13-10-7-4-1-0 KM3 10 0-1-4-5-8-11-14-15 27 15-14-11-8-5-2 1-0 KM4 11 0-1-4-7-10-13 26 13-10-7-4-1-0 KM5 12 0-1-4-7-10-13-14-16 30 16-14-13-10-7-4-1-0 KM6 13 0-1-4-5-8-11-14-15 30 15-14-11-8-5-2-1-0 KM7 14 0-1-4-7-10-13 29 10-7-4-1-0 KM8 15 0-1-4-7-10-13-14-16 33 16-14-13-10-7-4-1-0 KM9 16 0-1-4-5-8-11-14-15 33 15-14-11-8-5-2-1-0 KM10 17 0-1-4-7-10-13 32 13-10-7-4-1-0 KM11 18 0-1-4-7-10-13-14-16 36 16-14-13-10-7-4-1-0 KM12 19 0-1-4-5-8-11-14-15 36 15-14-11-8-5-2-1-0 表 2 施工运输组织优化方案Table 2. Optimization construction organization scheme编号 车辆进入隧道运行方案 车辆离开隧道运行方案 始发时刻 运行路径 始发时刻 运行路径 KP1 0 0-1-2-5-8-11-14 13 14-11-8-5-4-1-0 KP2 1 0-1-4-7-8-11-14 14 14-13-10-7-4-1-0 KP3 5 0-1-4-7-8-11-14 18 14-13-10-7-4-1-0 KP4 9 0-1-4-7-8-11-14 22 14-11-8-5-4-1-0 KC1 13 0-1-4-5-6-9 24 9-6-5-4-1-0 KC2 17 0-1-2-5-6-9 28 9-6-5-2-1-0 KC3 18 0-1-4-5-6-9 29 9-6-3-2-1-0 KC4 22 0-1-2-3-6-9 33 9-6-5-4-1-0 KM1 23 0-1-4-7-10-13 38 13-10-7-4-1-0 KM2 27 0-1-4-7-10-13-14-16 45 16-14-11-8-5-2-1-0 KM3 31 0-1-4-7-8-11-14-15 48 15-14-13-10-7-4-1-0 KM4 34 0-1-4-7-10-13 49 13-10-7-4-1-0 KM5 35 0-1-4-7-8-11-14-16 53 16-14-11-8-5-2-1-0 KM6 39 0-1-2-5-8-11-14-15 56 15-12-11-8-5-2-1-0 KM7 42 0-1-4-7-10-13 57 13-10-7-4-1-0 KM8 46 0-1-4-7-8-11-14-16 64 16-14-11-8-5-2-1-0 KM9 47 0-1-2-5-8-11-14-15 64 15-14-11-8-5-4-1-0 KM10 49 0-1-4-7-10-13 64 13-10-7-4-1-0 KM11 53 0-1-4-7-10-13-14-16 71 16-14-11-8-7-4-1-0 KM12 57 0-1-2-5-8-11-12-15 74 15-14-11-8-5-4-1-0 表1中加粗划线的节点表示车辆在该节点与其他车辆发生了交叉冲突. 易看出，优化前车辆KP1与KM3、KM9、KC2，KP2与KC3，KP3与KM9、KC4，KP4与KM6，KC1与KM12，KM1与KM10，KM2与KM11，KM3与KM7，KM6与KM10间发生了交叉冲突，甚至车辆KP2与KC3间存在3个交叉冲突点. 车辆KM3与KM9，车辆KM6与KM12在V14与V15间的路段发生了相向冲突. 对比表1和表2可以发现，优化前后施工车辆的时刻表发生了很大的变化. 车辆KP2、KC3、KM1、KM5、KM9与前车的发车间隔保持1 min没有变化，车辆KM10与前车的发车间隔从1 min增至2 min，车辆KM4、KM7与前车的发车间隔从1 min增加至3 min，剩下车辆与前车的发车间隔从1 min增加至4 min. 另外，优化前，对于需求点相同的车辆，其运行路径大多相同. 例如：需求点为V14的车辆KP2、KP3、KP4的运行路径
多数为V0→V1→V4→V5→V8→V11→V14→V11→V8→V5→V4→V1→V0；需求点为V9的车辆KC1、KC2、KC3、KC4的运行路径都为V0→V1→V2→V3→V6→V9→V6→V3→V2→V1→V0→V1. 这容易导致车辆对某路段的使用频率过高，从而产生冲突，例如：V1与V2间路段的高使用率导致V1与V2的交叉冲突点过多. 而优化后，对于需求点相同的车辆，其运行路径大多不同. 这是因为各个车辆需要尽量避免沿着相同路径行驶，减少某个路段的使用压力，规避交通冲突，保证安全行驶. 事实上，优化方案还可以在限速范围内改变车辆的行驶速度来调整车辆在路段上的运行时间，间接改变车辆的路径时刻表，达到延缓或提前到达某一节点的时刻来规避交通冲突，保证运行安全. 综上分析，本文所提出的优化方案主要从调整发车时刻表、改变车辆运行路径、调节路段行驶时间3个途径来减少交通冲突.
初始方案、优化方案的目标函数值和交通冲突数量如表3所示. 优化前后，目标函数值，即车辆的总运行（行驶）时间均为512 min，没有发生变化，交通冲突数量从21个减到0个. 因此，可以得出，对多工种施工车辆的时刻表和路径进行规划，可以在不增加车辆总运行（行驶）时间，即目标函数值（512 min）的基础上有效规避交通冲突，保证隧道内部施工期间车辆的行驶安全. 实际上，不同于理论计算结果，当隧道内部车辆间发生交通冲突时，车辆总运行时间不仅会大幅度增加，还可能引发严重的交通事故. 本案例的优化方案在不牺牲车辆理想运行（行驶）时间的条件下完全避免了交通冲突，保证了隧道内部施工车辆的畅通运行. 为进一步清晰直观地对比初始方案与优化方案的优劣，刻画2种方案优化前后的效果，我们绘制隧道运输组织初始方案和优化方案的时空轨迹图，如图6和图7所示. 图中的黑色五角星代表交叉冲突点，红色直线的交点代表相向冲突点. 优化后，图中的交通冲突点得以消除，各个车辆的路径时刻表从紧张危险、交错纵横的状态转变为疏散安全、平衡有序的状态. 另外，观察交通冲突的涉及对象和发生时刻可发现，车辆容易在去程方向上与其他返程方向上的车辆发生冲突. 这是因为去程方向和返程方向的目标方向不一致，车辆运行路径容易产生交叉相错. 初始方案的路径时刻表只能先保证去程方向上车辆的有序规律发车，难以进一步确保返程方向上车辆对于冲突的规避，而优化方案可以通过进一步调整路径时刻表来继续保证返程方向上车辆的有序安全运行. 由此可知，考虑交通冲突的长大隧道内部多工种施工车辆时刻表和运行路径的协同优化，使得隧道内部交通网络的安全性得到提高，车辆间的交通冲突得以疏解，施工任务能够高效安全完成，减少了意外事故发生的可能性.
表 3 初始和优化方案的目标函数值和交通冲突数量Table 3. Objective function values and number of traffic conflicts for initial and optimization schemes方案 目标函数值/min 交通冲突数量/个 交叉 相向 赶超 初始方案 512 19 2 0 优化方案 512 0 0 0 
图 6 隧道运输组织初始方案时空轨迹图Figure 6. Space-time trajectory map of initial scheme of tunnel transportation organization
图 7 隧道运输组织优化方案时空轨迹图Figure 7. Space-time trajectory map of optimization scheme of tunnel transportation organization综上分析，本文提出的考虑交通冲突的长大隧道内部多工种施工车辆的时刻表和运行路径系统优化模型及GUROBI求解方法具备可行性，能够在短时间内得到效果较好的优化方案，应用于隧道内部运输组织方案编制，可操作性强.
5. 结论与展望
1） 在隧道施工任务执行过程中，需求点相同的施工车辆容易发生交通冲突，不同目标方向（去程和返程）的车辆容易发生交通冲突. 本文所提出的优化方案主要从调整发车时刻表、改变车辆运行路径、调节路段行驶时间3个途径来减少交通冲突. 在案例中优化得到的多工种施工车辆运输组织方案不增加车辆的总运行（行驶）时间，即目标函数值（512 min），使车辆间的交通冲突数量从21个减为0个，提高了施工效率，保证了运输安全.
2） 本文提出的隧道内部多工种施工车辆的时刻表和运行路径协同优化模型可应用于各种隧道施工项目，也可以通过设置时间窗，考虑车辆装配过程，考虑车辆的循环运输计划等来进一步完善模型，扩大其应用场景，同时也是后续的重要研究方向.
-
图 1 在既有列车运行图中编制新增列车运行线示例
Figure 1. Illustration of scheduling additional trains into an original train timetable
图 2 不同调整策略条件下的新增列车运行线方案
Figure 2. Additional train scheduling results based on different adjustment measures
图 3 京沪高速铁路详细信息及开行的列车运行区间
Figure 3. Detailed information and train operation sections of Beijing–Shanghai High-Speed Railway
图 4 求解场景9时算法迭代过程收敛曲线
Figure 4. Convergence curves of algorithm’s iterative process for solving Scenario 9
表 1 时空弧费用
Table 1. Spatio-temporal arc costs
列车种类 弧类型 弧费用 既有列车 始发弧 $ {\beta _1} (\hat t - t + | {t - o_{{\mathrm{dep}},k}} |) $ 运行弧 $ {\beta _1} (\hat t - t) $ 终到弧 $ {\beta _1} (\hat t - t + | {\hat t - o_{{\mathrm{arr}},k}} |) $ 新增列车 所有弧 $ {\beta _2} (\hat t - t) $ 
下载: 导出CSV
表 2 各场景求解结果及求解质量指标
Table 2. Solution results and solution quality metrics for each scenario
对照参数 场景编号 参数设置 顺序求解方法 基于拉格朗日松弛的求解算法 下界解值 上界解值 计算时间/s Gap/% 下界解值 上界解值 计算时间/s egap/% Impr/% 1 7706.15 7976.93 678 3.51 7336.65 7532.89 1174 2.67 5.89 始发时间
窗长度2 40 min 7705.63 8037.93 678 4.31 7335.56 7664.90 1219 4.49 4.87 3 50 min 7706.35 7975.68 775 3.49 7336.60 7612.91 1069 3.77 4.77 客流需求 4 115270 5633.86 5806.79 614 3.07 5262.99 5491.79 1016 4.35 5.74 5 155958 9952.70 10142.33 603 1.91 9571.84 9902.13 2534 3.45 2.43 备选停站
方案数量6 短途 7868.33 8054.41 619 1.96 7473.63 7732.41 777 3.46 4.16 7 均匀 7617.67 7834.25 568 2.84 7256.33 7436.75 1520 2.49 5.35 运行区间 8 2 9076.02 9254.05 591 2.36 8707.45 8857.30 1190 1.72 4.48 9 4 8603.21 8741.14 813 2.76 8232.49 8439.19 869 2.51 3.58
下载: 导出CSV
-
[1] 鲁工圆,胡留洋,彭慧,等. 基于预发车的高速铁路列车出发追踪间隔时间压缩方法[J]. 西南交通大学学报,2024,59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064LU Gongyuan, HU Liuyang, PENG Hui, et al. Method for compressing departure tracking interval of high-speed trains based on pre-departure strategy[J]. Journal of Southwest Jiaotong University, 2024, 59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064 [2] INGOLOTTI L, BARBER F, TORMOS P, et al. An efficient method to schedule new trains on a heavily loaded railway network[C]//Advances in Artificial Intelligence – IBERAMIA 2004. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004: 164-173. [3] BURDETT R L, KOZAN E. Techniques for inserting additional trains into existing timetables[J]. Transportation Research Part B: Methodological, 2009, 43(8/9): 821-836. [4] CACCHIANI V, CAPRARA A, TOTH P. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B: Methodological, 2010, 44(2): 215-231. doi: 10.1016/j.trb.2009.07.007 [5] MEIRICH C, NIEßEN N. Calculating the maximal number of additional freight trains in a railway network[J]. Journal of Rail Transport Planning & Management, 2016, 6(3): 200-217. [6] LI S D, ZUO D J, LI W Q, et al. Freight train line planning for large-scale high-speed rail network: an integer Benders decomposition-based branch-and-cut algorithm[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192: 103750. 1-103750.28. doi: 10.1016/j.tre.2024.103750 [7] JIANG F, CACCHIANI V, TOTH P. Train timetabling by skip-stop planning in highly congested lines[J]. Transportation Research Part B: Methodological, 2017, 104: 149-174. doi: 10.1016/j.trb.2017.06.018 [8] 徐涵,聂磊,谭宇燕. 基于灵活接续的周期性列车运行图加线模型[J]. 铁道科学与工程学报,2018,15(9): 2439-2447.XU Han, NIE Lei, TAN Yuyan. The adding train paths model on cyclic timetable based on flexible connection[J]. Journal of Railway Science and Engineering, 2018, 15(9): 2439-2447. [9] 高如虎,牛惠民,江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报,2020,42(5): 1-8.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. [10] LIU Y T, CAO C X. A multi-objective train operational plan optimization approach for adding additional trains on a high-speed railway corridor in peak periods[J]. Applied Sciences, 2020, 10(16): 5554. 1-555.29. doi: 10.3390/app10165554 [11] 高如虎,牛惠民. 基于 ADMM 方法的新增列车条件下灵活的列车时刻表优化算法研究[J]. 铁道学报,2021,43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003GAO Ruhu, NIU Huimin. Study on additional train timetable algorithm in flexible manner based on ADMM approach[J]. Journal of the China Railway Society, 2021, 43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003 [12] 毛万华,陈亚茹. 高速铁路列车运行图新增列车运行线优化方法研究[J]. 铁道运输与经济,2021,43(11): 1-6,26.MAO Wanhua, CHEN Yaru. Research on optimization method of newly-added train paths based on train running diagram of high speed railways[J]. Railway Transport and Economy, 2021, 43(11): 1-6,26. [13] ZHAO J D, LI H Y, MENG L Y, et al. An optimization method of high-speed railway rescheduling to meet unexpected large passenger flow[J]. Journal of Advanced Transportation, 2022, 2022: 5964010. 1-5964010.16. [14] 曲云腾,姚向明,赵鹏,等. 考虑动车组接续的区域城际网运行图加线模型[J]. 铁道学报,2024,46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002QU Yunteng, YAO Xiangming, ZHAO Peng, et al. Model for inserting additional trains into existing timetable for intercity railway network considering EMU connections[J]. Journal of the China Railway Society, 2024, 46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002 [15] 赵日鑫,何世伟,张杰,等. 高铁枢纽环线公交化列车新增运行线优化方法[J]. 北京交通大学学报,2024,1-124-11-21]. ZHAO Rixin, HE Shiwei, ZHANG Jie, et al. Optimization method of adding extra train paths for mass transit type in high-speed railway hub loop[J]. Journal of Beijing Jiaotong University, 2024, 1-12[2024-11-21]. [16] 刘璐,孟令云,李新毅,等. 考虑旅客需求的停站方案与列车运行图一体化模型与算法[J]. 铁道科学与工程学报,2019,16(2): 518-527.LIU Lu, MENG Lingyun, LI Xinyi, et al. Integrated optimization of stopping pattern and train timetable for passenger demand[J]. Journal of Railway Science and Engineering, 2019, 16(2): 518-527. [17] HASSANNAYEBI E, ZEGORDI S H, AMIN-NASERI M, et al. Demand-oriented timetable design for urban rail transit under stochastic demand[J]. Journal of Industrial and Systems Engineering, 2016, 9(3): 28-56. [18] 赵子洪. 面向服务间隔时间的列车运行图优化方法研究[J]. 铁道运输与经济,2019,41(7): 33-39.ZHAO Zihong. A research on train diagram optimization method oriented to service interval time[J]. Railway Transport and Economy, 2019, 41(7): 33-39. [19] ALBRECHT T. Automated timetable design for demand-oriented service on suburban railways[J]. Public Transport, 2009, 1(1): 5-20. [20] FENG J J, LI X, SHI J G, et al. Joint optimization of metro train timetable and stopping plan for the first service period: an integrated energy-efficient and time-saving model[J]. International Journal of Transportation Science and Technology. (2024-10-06)[2024-12-10]. https://api.semanticscholar.org/CorpusID:273492667. [21] 李冰,任泽强,轩华. 考虑多编组站转场作业的铁路枢纽车流组织优化[J]. 西南交通大学学报,2023,58(03): 489-498,545.LI Bing, REN Zeqiang, Xuan Hua. Optimization of wagon flow assignment with transship work for multiple marshaling stations at railroad terminals[J]. Journal of Southwest Jiaotong University, 2023, 58(03): 489-498,545. -
下载:
下载:
点击查看大图
计量
- 文章访问数: 50
- HTML全文浏览量: 24
- PDF下载量: 6
- 被引次数: 0