节拍式列车运行图具有规律性强、使用灵活及方便旅客出行与车站工作组织等优点,在日本、欧洲的一些国家得到广泛应用.PEETERS^[1]提出周期事件规划问题(periodic event scheduling problem,PESP)模型和周期性列车运行图编制(cycle periodicity formulation,CPF)模型; CAIMI等^[2]在此基础上提出周期运行图的弹性PESP模型; 汪波等^{[3- 4]}借助网络约束图及周期势差模型,以列车停站时间最少为目标,建立城际铁路与城轨周期运行图优化方法; 谢美全等^[5]考虑列车周期性运行约束,建立基于定序的周期性运行图优化方法; 贾晓秋等^[6]构建了高速铁路周期列车运行图的多目标模型,并设计基于job-shop的遗传算法; 李传宾^[7]基于矩阵表示和极大代数法设计高速铁路(即高铁)周期列车运行图优化方法.

周期列车运行图虽能提供旅客规律化的运行列车以方便旅客出行,然而在其编制过程中,通常是基于高峰期出行需求确定该时段列车时刻表,通过进一步复制和删除非高峰时段部分列车而获得全天列车运行图.如此一来,列车原本严格的等时间间隔周期运行规律将在一定程度上被破坏.为使列车运行具有严格的等间隔运行规律,能够使不同时段列车运行数量与出行需求量相适应,本研究基于列车多节拍协同运行方式,将具有相同起点、终点、停站方案以及速度等级的列车归为一个节拍单元.同节拍单元列车以严格的等时间间隔周期运行,而不同节拍单元列车可具有不同的运行时间间隔,进而协调优化各节拍单元列车运行的时间间隔及其车站到达与出发时间,由此获得的列车时刻表,不仅具有严格的等时间间隔运行规律,还能使不同时段的列车运行数量与出行需求量相适应.

考虑由K个车站与K-1个复线区间构成的高铁线路L=(S, E)上多节拍单元列车运行图优化问题,其中, S为线路车站序列; E为线路区间集.为简便起见,该问题研究基于以下假设.

假设1 车站简化为具有停车能力属性的节点,不考虑列车在车站运行路径,但要求车站同一时间内的停留列车数量不能超过该站停车能力.

假设2 线路仅运营多个节拍式运行列车,不包含非节拍运行列车.

假设3 同节拍单元列车采用相同的车底或动车组,所有同节拍列车具有相同定员.

给定线路运行的W个节拍单元列车,对于其中第w个节拍单元列车,其运行列车数量为m_w. 节拍单元w所有列车具有相同的起点站r_w∈S与终点站s_w∈S、 相同经由车站集S_w∈S及经由区间集E_w∈E; 且其所有列车在车站i∈S_w的最小停站时间为τ^w_i, 在区间(i, j)∈E_w的启动附加时分、纯运行时分及停止附加时分分别为qt^w_{i, j}, ct^w_{i, j}及tt^w_{i, j}. 图1给出由2个节拍单元列车组合运行构成的列车运行图,由实线和虚线表示的列车运行线分别属于2个具有不同运行间隔的节拍单元列车.其中,每个节拍单元可运行不同数量的同速度等级列车,但其列车应均具有相同运行路径与停站,即经由相同区间与车站、在相同车站停车.每个节拍单元列车均可采用不同运行时间间隔节拍式运行,实线为第1节拍单元列车以时间间隔60 min节拍式运行,虚线为第2节拍单元列车以运行时间间隔90 min节拍式运行.值得注意的是同一节拍单元列车不仅在始发站等时间间隔始发,且在其途经车站也等时间间隔到发.

这种多节拍组合运行方式能够使得各节拍单元列车严格按某固定时间间隔周期性运行,以方便旅客乘车出行,而且能够通过协调各节拍单元首列车始发时刻及其运行时间间隔,使得客流高峰期组织运行更多列车,而在客流低峰期运行少量列车以适应不同时期客流需求的变化.

图1 由2个运行节拍单元构成的列车运行图
Fig.1 A train schedule with two period-types of trains

多节拍单元列车运行图优化旨在优化各节拍单元列车运行时间间隔、以及各节拍单元列车在车站的到达与出发时刻,使其在满足各类运营与行车时间标准条件下,所有节拍单元列车总旅行时间达到最小.该优化问题所涉及到的相关参数符号定义如表1,决策变量与辅助变量的定义如表2.

以最小化所有节拍单元列车旅行时间之和为目标,实现多节拍列车组合运行时刻表优化,其具体模型为

min Z=∑^W_w=1{[∑_{(i, j)∈Ew}(d_{w, 1}(i, j)-a_{w, 1}(i, j))+

∑_{(i, j),(j, i')∈Ew}(a_{w, 1}(j, i')-d_{w, 1}(i, j))]×

m_w}(1)

该模型满足以下7组约束条件:

1)同节拍单元列车等间隔运行约束.

a_{w, f+1}(i, j)=a_{w, f}(i, j)+T_w, ∀w;

f=1,2,…,m_w-1;(i, j)∈E_w(2)

表1 符号定义
Table 1 The definitions of all symbols

d_{w, f+1}(i, j)=d_{w, f}(i, j)+T_w,∀w;

f=1,2,…,(m_w-1);(i, j)∈E_w(3)

约束式(2)和(3)确保节拍单元w两相邻列车的到达(出发)时刻的时间间隔长度为T_w.

2)列车发车达到最低客座率约束.

a_{w, 1}(r_w, j)≥t^min_w, ∀w;(r_w, j)∈E_w(4)

表2 决策变量与辅助变量的符号定义
Table 2 The definitions of decision variables and auxiliary variables

a_{w, f+1}(r_w, j)-a_{w, f}(r_w, j)≥RT_w(a_{w, f}(r_w, j)),

∀w; f=1,2,…,m_w-1;(r_w, j)∈E_w(5)

由参数t^min_w的定义可知,只要约束式(4)使得节拍单元w首列列车在始发站的发车时刻不早于时刻t^min_w,便能保证列车达到最低客座率要求.由参数RT_w(t)定义可知,只要约束式(5)使得节拍单元w第f列与第f+1列列车在始发站的发车时刻间隔不小于时间间隔RT_w(t),第f+1列列车便能满足最低客座率要求.

3)区间运行时分标准与最小停站时间约束.

d_{w, 1}(i, j)-a_{w, 1}(i, j)=FT^w_{i, j}, ∀w;

(i, j)∈E_w(6)

a_{w, 1}(j, i')-d_{w, 1}(i, j)≥ST^w j, ∀w;

(i, j),(j, i')∈E_w(7)

约束式(6)与(7)分别确保节拍单元w首列列车区间运行时间与车站停站时间分别不低于其相应的最小值.

4)列车间最小安全到达与出发时间间隔约束.

a_{w, f}(i, j)+(1-φ^{w, f}_{w', f'}(i, j))×M≥

a_{w', f'}(i, j)+AT_{i, j},

∀[w, f]≠[w', f'];(i, j)∈E_w∩E_w'(8)

d_{w, f}(i, j)+(1-φ^{w, f}_{w', f'}(i, j))×M≥

d_{w', f'}(i, j)+DT_{i, j},

∀[w, f]≠[w', f'];(i, j)∈E_w∩E_w'(9)

约束式(8)保证节拍单元w第f列列车与节拍单元w'第f'列列车进入区间(i, j)的时间间隔不小于最小安全间隔AT_{i, j},离开区间(i, j)的时间间隔不小于最小安全间隔DT_{i, j}.

同理,约束式(9)确保节拍单元w第f列列车与节拍单元w'第f'列列车离开区间的时间间隔不小于最小安全间隔DT_{i, j}.

5)车站最大同时停留列车数约束,即车站停车能力约束.

∑∀w|j∈Sw∑Mwf=1θw, f(j, t)≤capj,

∀j∈S; t=1,2,…,T(10)

约束式(10)保证了车站j在任意时刻t停留的列车总数不会超过其停车能力cap_j.

6)列车到发时间取值范围约束.

1≤a_w,f(i, j)≤T, ∀w;

f=1,2,…,m_w;(i, j)∈E_w(11)

1≤d_w,f(i, j)≤T, ∀w;

f=1,2,…,m_w;(i, j)∈E_w(12)

约束式(11)和(12)分别使得列车进入和离开区间的时间均在列车运营时间1～T以内.

7)决策变量间一致性约束.

φ^{w, f}_{w', f'}(i, j)+φ^{w', f'}_{w, f}(i, j)=1,

∀[w, f]≠[w', f'];(i, j)∈E_w∩E_w'(13)

1-(d_{w, f}(i, j))/t≤ρ_{w, f}(i, j, t)≤

(d_{w, f}(i, j)-T)/(t-T), ∀w;

f=1,2,…,m_w; t=1,2,…,T;(i, j)∈E_w(14)

(a_{w, f}(j, i')-t)/(T-t)+[ρ_{w, f}(i, j, t)-1]×M≤

θ_{w, f}(j, t)<(a_{w, f}(j, i'))/t+

[1-ρ_{w, f}(i, j, t)]×M,∀w;

f=1,2,…,m_w; t=1,2,…,T;

(i, j),(j, i')∈E_w(15)

θ_{w, f}(j, t)≤ρ_{w, f}(i, j, t), ∀w;

f=1,2,…,m_w; t=1,2,…,T;(i, j)∈E_w(16)

约束式(13)保证列车[w, f]只有在列车[w', f']之前或者之后进入区间(i, j)两种情形.即φ^{w, f}_{w', f'}(i, j)=1, φ^{w', f'}_{w, f}(i, j)=0或者φ^{w, f}_{w', f'}(i, j)=0, φ^{w', f'}_{w, f}(i, j)=1. 约束式(14)确保列车到达车站j的时间(离开区间(i, j)的时间)d_{w, f}(i, j)早于时刻t, 即时d_{w, f}(i, j)≤t, ρ_{w, f}(i, j, t)=1; 否则, ρ_{w, f}(i, j, t)=0.

约束式(15)和(16)共同确保仅当列车[w, f]在车站j的到发时间满足d_{w, f}(i, j)≤t<a_{w, f}(j, i')时,该列车在时刻t停留车站j, 即θ_{w, f}(j, t)=1; 否则, θ_{w, f}(j, t)=0. 表4给出列车到发时间与时刻t不同大小关系下,参数θ_{w, f}(j, t)在约束式(15)与(16)作用下的取值以及最终取值.

考虑由6个车站、5个复线区间线路,运营时间为[1,180] min,且各区间最小安全出发、到达间隔为3 min.所有列车均从线路端点站出发到达另一端点站,停车随机确定,且最小停车时间为1 min.

图4 算法计算时间CT与Gap随节拍单元数量的变化关系
Fig.4 The change relation of CT and Gap with the number of period-types

图4(a)与(b)分别给出当节拍单元平均列车数为3～7列时,算法计算时间(CT)与目标函数与最优值相对差距(Gap)随节拍数量增加的变化.显然,CT呈先慢后快增长趋势.如在平均列车数为4时,节拍单元数量从2增至4,计算时间增幅较小,但之后却大幅增加.另外,节拍单元平均列车数越少,计算时间增速反而较大,主要原因是在平均列车数量较少时,每个节拍单元列车可搜索的路径范围与时间间隔值均较多,导致更多的计算时间.由图4(b)可知,随节拍单元数量增加,算法基本能搜索到最优解,仅在平均列车数为7列、节拍单元为4时,没有搜索到最优解,此时Gap约为10%.

图5 算法计算时间CT与Gap随节拍单元平均列车的变化关系
Fig.5 The change relation of CT and Gap with the increase of average train number of period-types

图5(a)与(b)分别给出不同节拍单元数量时,CT与Gap随着节拍单元平均列车数增加的变化关系.由图5(a)可知,随着节拍单元平均列车数量的增加,CT反而下降.主要原因是算法并不需要为同节拍单元列车逐列搜索路径,而只需寻找具有开行间隔属性的出行路径,反而节拍单元平均列车数越少,首列列车路径的搜索时间范围与对应的列车运行间隔范围越大,计算时间越多.由图5(b)可知,在节拍单元平均列车数较少时,Gap均为0,但当继续增加至6以后,Gap具有一定的波动性,最大值接近18.0%.

图6(a)与(b)分别给出当节拍单元平均列车数为3～6列时,CT与Gap随高、中速节拍单元数量之比增加的变化关系.由图6(a)可知,在节拍单元平均列车数为5列或6列时,高、中速节拍单元数量之比变化对计算时间影响较大,但当节拍单元平均列车数为3列或4列时,算法计算时间变化范围相对较小.由图6(b)可知,在节拍单元平均列车数较少时,Gap一直保持为0; 而当节拍单元平均列车数为6列时,Gap达到最大值29.6%、最小值1.4%.由此可见,在节拍平均开行列车数量较少时,高、中速节拍单元列车混行对CT与Gap影响均较小; 但当节拍平均列车数量较大时,将导致CT与Gap增加.

图6 算法计算时间CT与Gap随高、中速节拍单元数量比的变化关系
Fig.6 The change relation of CT and Gap with the rate increase of high-speed to middle-speed period-type

以京沪高铁线路为例,仅考虑北京南至上海虹桥的节拍列车,暂不考虑其他非节拍列车.假定共有5个节拍单元列车,其列车数量及停站序列见表3,运营时间为07:00—24:00,且在各区间的最小安全出发、到达时间间隔分别为5 min和6 min.

表3 各运行节拍单元列车停站序列以及运行数量
Table 3 The number of trains and stop sequences of each period-type train

为方便记忆列车运行时刻,以10 min的整倍数作为列车运行时间间隔的可能取值.经4.31 h的计算后,获得列车运行图如图7,此时,Gap为6.8%.

由图7可知,每个节拍单元列车均按所确定的时间间隔等间隔运行,通过协调各节拍单元列车最早发车时间与时间间隔使得全天不同时段具有不同数量的列车,以满足不同时段旅客需求.经比较发现,具有较多数量列车节拍单元的运行时间间隔相对较小,反之相对较大,从而使列车尽可能分散到全天运营时间范围内,避免列车集中运行.

本研究以最小化列车总旅行时间为目标,构建多节拍单元列车协同运行时刻表优化模型.在定义主路径、从路径及路径间隔等概念的基础上,将交互熵原理与多路径组合搜索算法相结合,设计了时刻表优化的元启发式算法.

本模型与算法暂未考虑客流因素,今后研究需进一步将客流因素反映到模型与算法中.此外,关于车站到发数量、车站路径选择限制的考虑、以及将本方法推广到小规模轨道网络同样是需要进一步研究的内容.

图7 07:00—24:00以10 min的整数倍为运行间隔的多节拍列车运行图
Fig.7 The multi-periodic train timetable based on setting train operation period as the integer multiples of 10 min during 07:00 to 24:00