任禹谋1,2,张琦2,袁志明2,王涛2,丁舒忻2,李智2
(1.中国铁道科学研究院 研究生部,北京 100081;2.中国铁道科学研究院集团有限公司 通信信号研究所,北京 100081)
摘要:
针对高速铁路车站到发线运用计划编制问题,提出了一种基于分时段多目标的到发线运用优化模型和改进的快速非支配排序遗传算法（non-dominated sorting genetic algorithm Ⅱ,NSGA-Ⅱ）。首先,考虑咽喉区进路与到发线的耦合关系,根据列车到发分布特征对研究时段进行划分,以到发线利用均衡、计划鲁棒性强和客运服务质量为优化目标,应用整数规划方法构建到发线运用优化模型。然后,引入约束支配原则,设计了带精英策略的改进算法。最后,以京沪高铁某车站的实际运行数据为例进行仿真验证。计算结果表明,在平峰时段,到发线占用费用比原方案降低了16.98%,有效提升了客运服务质量；在高峰时段,到发线占用时间方差和总冲突系数比原方案降低了48.57%和29.81%,明显提高了车站的设备利用率和到发线运用计划的鲁棒性；与整体优化方法相比,分时段优化方法能更有针对性地降低各项优化目标的函数值。因此,充分考虑列车到发分布因素对到发线运用问题的影响,可以有效改善优化指标,为制定不同繁忙程度下的车站作业方案提供决策支持。
关键词: 铁路运输 到发线运用 改进的快速非支配排序遗传算法（NSGA-Ⅱ） 多目标优化 列车到发分布
DOI：10.11918/202102026
分类号:U292.15
文献标识码:A
基金项目:国家自然科学基金高铁联合基金(U1834211); 中国铁道科学研究院集团有限公司基金(2020YJ225)
Optimization of train platform utilization at high-speed railway stations based on arrival and departure distribution of trains
REN Yumou1,2,ZHANG Qi2,YUAN Zhiming2,WANG Tao2,DING Shuxin2,LI Zhi2
（1.Postgraduate Department, China Academy of Railway Sciences, Beijing 100081, China; 2.Signal & Communication Research Institute, China Academy of Railway Sciences Co. Ltd., Beijing 100081, China）
Abstract:
To solve the problem of the arrival-departure track utilization planning for high-speed railway stations, an optimization model of train platform utilization based on time segment and multi-objective optimization and an improved fast non-dominated sorting genetic algorithm Ⅱ(NSGA-Ⅱ) were proposed. First, considering the coupling relationship between the arrival-departure tracks and the routes in the throat area, the study period was divided according to the arrival and departure distribution characteristics of the trains. Taking the utilization balance of the train platform, strong planning robustness, and passenger service quality as the optimization objectives, an optimization model of train platform utilization was established by integer programming method. Then, an elite strategy with feasible solutions was designed by introducing constraint domination principle. At last, the actual operation data of a station on the Beijing-Shanghai high-speed railway was taken as an example for simulation verification. Calculation results show that the occupancy cost of the train platform was reduced by 16.98% compared with the original scheme in the normal peak period, which significantly improves the quality of passenger service. During the rush hour, the variance of the occupation time of the platform and the total conflict coefficient were reduced by 48.57% and 29.81% compared with the original scheme, which significantly improves the equipment utilization rate and the robustness of the arrival-departure track utilization plan. In comparison with the overall optimization method, the time segment optimization method could be more targeted in reducing the function value of the optimization objectives. Therefore, considering the influence of train arrival and departure distribution factors on the train platform utilization, it can effectively improve the optimization factors and provide support for making station operation plans during different busy periods.
Key words: railway transportation utilization of arrival-departure tracks improved fast non-dominated sorting genetic algorithm Ⅱ(NSGA-Ⅱ) multi-objective optimization distribution of arrival and departure trains
任禹谋, 张琦, 袁志明, 王涛, 丁舒忻, 李智. 基于列车到发分布的高速铁路车站到发线运用优化[J]. 哈尔滨工业大学学报, 2021, 53(8): 137-143. DOI: 10.11918/202102026.
REN Yumou, ZHANG Qi, YUAN Zhiming, WANG Tao, DING Shuxin, LI Zhi. Optimization of train platform utilization at high-speed railway stations based on arrival and departure distribution of trains[J]. Journal of Harbin Institute of Technology, 2021, 53(8): 137-143. DOI: 10.11918/202102026.
基金项目 国家自然科学基金高铁联合基金(U1834211);中国铁道科学研究院集团有限公司基金(2020YJ225) 作者简介 任禹谋(1990—)，男，博士研究生;
张琦(1968—)，男，研究员，博士生导师 通信作者 张琦，gorgeous@139.com 文章历史 收稿日期: 2021-02-06
Abstract Full text Figures/Tables PDF
基于列车到发分布的高速铁路车站到发线运用优化
任禹谋1,2, 张琦2
, 袁志明2, 王涛2, 丁舒忻2, 李智2 1. 中国铁道科学研究院 研究生部，北京 100081;
2. 中国铁道科学研究院集团有限公司 通信信号研究所，北京 100081
收稿日期: 2021-02-06
基金项目: 国家自然科学基金高铁联合基金(U1834211);中国铁道科学研究院集团有限公司基金(2020YJ225)
作者简介: 任禹谋(1990—)，男，博士研究生; 张琦(1968—)，男，研究员，博士生导师
通信作者: 张琦，gorgeous@139.com
摘要: 针对高速铁路车站到发线运用计划编制问题，提出了一种基于分时段多目标的到发线运用优化模型和改进的快速非支配排序遗传算法(non-dominated sorting genetic algorithm Ⅱ, NSGA-Ⅱ)。首先，考虑咽喉区进路与到发线的耦合关系，根据列车到发分布特征对研究时段进行划分，以到发线利用均衡、计划鲁棒性强和客运服务质量为优化目标，应用整数规划方法构建到发线运用优化模型。然后，引入约束支配原则，设计了带精英策略的改进算法。最后，以京沪高铁某车站的实际运行数据为例进行仿真验证。计算结果表明，在平峰时段，到发线占用费用比原方案降低了16.98%，有效提升了客运服务质量；在高峰时段，到发线占用时间方差和总冲突系数比原方案降低了48.57%和29.81%，明显提高了车站的设备利用率和到发线运用计划的鲁棒性；与整体优化方法相比，分时段优化方法能更有针对性地降低各项优化目标的函数值。因此，充分考虑列车到发分布因素对到发线运用问题的影响，可以有效改善优化指标，为制定不同繁忙程度下的车站作业方案提供决策支持。
关键词: 铁路运输 到发线运用 改进的快速非支配排序遗传算法(NSGA-Ⅱ) 多目标优化 列车到发分布
Optimization of train platform utilization at high-speed railway stations based on arrival and departure distribution of trains
REN Yumou1,2, ZHANG Qi2
, YUAN Zhiming2, WANG Tao2, DING Shuxin2, LI Zhi2 1. Postgraduate Department, China Academy of Railway Sciences, Beijing 100081, China;
2. Signal & Communication Research Institute, China Academy of Railway Sciences Co. Ltd., Beijing 100081, China
Abstract: To solve the problem of the arrival-departure track utilization planning for high-speed railway stations, an optimization model of train platform utilization based on time segment and multi-objective optimization and an improved fast non-dominated sorting genetic algorithm?(NSGA-?) were proposed. First, considering the coupling relationship between the arrival-departure tracks and the routes in the throat area, the study period was divided according to the arrival and departure distribution characteristics of the trains. Taking the utilization balance of the train platform, strong planning robustness, and passenger service quality as the optimization objectives, an optimization model of train platform utilization was established by integer programming method. Then, an elite strategy with feasible solutions was designed by introducing constraint domination principle. At last, the actual operation data of a station on the Beijing-Shanghai high-speed railway was taken as an example for simulation verification. Calculation results show that the occupancy cost of the train platform was reduced by 16.98% compared with the original scheme in the normal peak period, which significantly improves the quality of passenger service. During the rush hour, the variance of the occupation time of the platform and the total conflict coefficient were reduced by 48.57% and 29.81% compared with the original scheme, which significantly improves the equipment utilization rate and the robustness of the arrival-departure track utilization plan. In comparison with the overall optimization method, the time segment optimization method could be more targeted in reducing the function value of the optimization objectives. Therefore, considering the influence of train arrival and departure distribution factors on the train platform utilization, it can effectively improve the optimization factors and provide support for making station operation plans during different busy periods.
Keywords: railway transportation utilization of arrival-departure tracks improved fast non-dominated sorting genetic algorithm Ⅱ(NSGA-Ⅱ) multi-objective optimization distribution of arrival and departure trains
现有铁路运输体系中，大型高速铁路车站作业交叉干扰是限制列车运行图能力的重要因素，其中到发线资源对此尤为敏感。编制高水平到发线运用计划能够满足列车正点出发和车站作业不冲突的要求，提高设备资源的利用率和抗干扰性，为车站调度员提供决策支持，具有重要的实际意义。
到发线运用优化问题是一个典型的半结构化问题，模型构建繁琐，且与到发线相连的咽喉区进路结构错综复杂，进一步加剧了问题的求解难度[1]。Cacchiani等[2]从列车到发时间和到发线选择两个角度详细阐述车站作业问题，并为之提供通用模型和解决方案。Cardillo等[3]首次提出采用增量约束着色图模型解决列车到发时间不能改变的车站径路使用问题。Sels等[4]为了解决无法排列全部列车进路的情况，在构建的到发线模型中提出了虚拟站台的概念并应用于比利时铁路系统，最大限度地增加了可以在无冲突站台通行的列车数量。Petering等[5]构建了列车时刻表和到发线作业组合优化的混合整数规划模型，并采用CPLEX求解器求解实际问题进行验证。近年，国内学者更多地考虑现场因素，并将启发式算法应用于求解过程，降低问题的求解难度[6]。Zhang等[7]对车站到发线时空资源进行微观描述，并建立数学规划模型后用模拟退火算法进行求解。赵鹏等[8]将到发线和咽喉区进路作为整体问题综合研究，完善了到发线运用模型。鲁工圆等[9]以进路冲突图为基础构建赋时有色Petri网仿真模型解决车站作业计划建模过程复杂的问题，有效提高了建模效率。也有部分学者从客运服务质量[10]、车站作业计划鲁棒性[11]、到发线利用均衡程度[12-13]等角度出发，详细分析车站的优化方向以解决到发线运用问题。
既有研究在解决到发线运用优化问题时，通常采用加权的方式将多个优化目标合并为单个优化目标求解，并未以多目标的视角考虑不同方案的适用性，并且在现实中几乎不可能精确测定各优化目标的先验权重。因此，到发线运用优化问题的解应该是一组从不同角度计算分析得出的Pareto解，供调度员决策备用。同时既有研究在目标制定过程中，往往忽略了列车到发分布特征的影响，采用固定化的优化目标，这样难以有针对性地解决车站通过能力与鲁棒性之间存在的矛盾。因此，在满足列车安全运行约束的条件下，针对列车到发分布特征，提出一种基于分时段多目标的到发线运用整数规划模型，并设计改进的NSGA-Ⅱ算法求解，为车站列车调度工作提供策略支持。
1 问题描述与建模 1.1 问题描述到发线运用优化问题可以描述为: 对于即将进站的列车集合和车站到发线集合，已知列车的图定到发时间和车站站场布置，在满足多个作业约束的情况下，求出一个使问题所有目标均尽可能为优的合理到发线分配方案，以达到降低列车晚点传播风险、提高车站作业能力和安全运营的目的。高速铁路车站作业过程主要包含出段作业、入段作业、接车作业、发车作业、通过作业和折返作业等，每项作业对应由列车在站内走行进路完成，这些进路又可以分为接车进路和发车进路。在编制到发线运用计划时，根据列车到发时间、出入段时间和其他作业时间标准，有序安排到发线的占用，减少空费时间，并预留一定的时间裕度，便于突发事件发生时计划的调整[14]。同时合理利用咽喉区的列车进路，避免作业间的冲突，保证车站的作业效率和安全性。
1.2 模型假设1) 假设列车到发时间和车站站场布置均为已知条件；
2) 假设车站作业过程完成时间均严格参照作业时间标准；
3) 假设列车在接发车时只选择基本进路，且所有到发线均能停靠列车；
4) 不考虑列车进路的分段解锁，只采用一次性解锁；
5) 假设折返列车不变更到发线，并采用顺接反发的进出站方式。
1.3 符号定义1) 集合。I为到站列车集合，i和h为列车的序号，n为到站列车的总数；J为车站到发线集合，j和l为到发线的序号，m为到发线的总数；Rj为连接到发线j的接车进路集合，rjs为集合中的接车进路，s为集合中接车进路的序号，a为集合中包含的接车进路总数；Pj为连接到发线j的发车进路集合，pjg为集合中的发车进路，g为集合中发车进路的序号，d为集合中包含的发车进路总数。
2) 参数。tiarr为列车i占用到发线的开始时刻；tidep为列车i占用到发线的结束时刻；Tmin为同一到发线相邻作业最小安全间隔时间；M为一足够大的正数；c为到发线占用费用矩阵。当cij=M时，表示列车i不能接入到发线j，当cij≠M时，表示列车i接入到发线j所产生的费用；oih为0-1辅助变量，表示列车i和h在开行方案中的折返关系，若两车在站接续，则oih=1，否则oih=0；wihj为0-1辅助变量，表示到达同一到发线j的相邻列车位置关系，若列车i比h先到达，则wihj=1，否则wihj=0；usk为0-1辅助变量，表示咽喉区接车进路rjs和rlk之间的空间关系，该参数只与车站的拓扑结构图有关。若任意两条接车进路包含相同道岔，则usk=1，否则usk=0；ugq为0-1辅助变量，表示咽喉区发车进路pjg和plq之间的空间关系，该参数只与车站的拓扑结构图有关。若任意两条发车进路包含相同道岔，则ugq=1，否则ugq=0；usq为0-1辅助变量，表示咽喉区接车进路rjs和发车进路plq之间的空间关系，该参数只与车站的拓扑结构图有关。若任意接车进路和发车进路包含相同道岔，则usq=1，否则usq=0；ρih为0-1辅助变量，表示任意两列车占用咽喉区的时间关系，该参数与列车的到发时间和作业时间有关，若两个列车的咽喉区进路占用时间窗存在重叠，则ρih=1，否则ρih=0。
3) 决策变量。xij为0-1决策变量，当xij=1时表示列车i占用到发线j，否则xij=0；yijs为0-1决策变量，当yijs=1时表示列车i占用到发线j选择第s条接车进路，否则yijs=0；zijg为0-1决策变量，当zijg=1时表示列车i占用到发线j选择第g条发车进路，否则zijg=0。
1.4 到发线运用分时段优化模型构建高速铁路车站接发列车的分布特征较为明显，分为高峰时段和平峰时段，从定量的角度可以界定两类时段对应的列车密集程度，进而制定差异化的优化目标。定义车站接发列车的分布特征参数为θ，设车站一天中单个小时最大接发列车数为M, 则高峰和平峰时段对应的接发列车数量范围分别为[0, θM]和(θM, M]。平峰时段，在保证到发线作业鲁棒性的同时，仍需考虑到发线固定作业方式等多方面影响因素；高峰时段，不仅要满足到发线作业鲁棒性的要求，更要提升到发线的利用效率。对于到发线运用优化问题的鲁棒性[15]，首先引入“冲突系数”的概念，即相邻两列车占用相同到发线时间间隔的倒数，用列车总冲突系数描述鲁棒性；到发线利用效率可通过到发线占用时间方差衡量；到发线固定作业方式和乘客便捷乘降等影响因素折算成到发线占用费用来表征。到站列车分布特征与优化目标的关系见图 1。
Fig. 1
图 1 列车分布特征与优化目标关系 Fig. 1 Relation between train distribution characteristics and optimization objectives 模型为：
$\begin{aligned}\min f_{1}=& \frac{1}{m} \sum\limits_{j=1}^{m}\left(\sum\limits_{i=1}^{n}\left(t_{i}^{\mathrm{dep}}-t_{i}^{\mathrm{arr}}\right) \cdot x_{i j}-\right.\\&\left.\frac{1}{m} \sum\limits_{i=1}^{n}\left(t_{i}^{\mathrm{dep}}-t_{i}^{\mathrm{arr}}\right)\right)^{2}\end{aligned}$ (1)
$\min f_{2}=\sum\limits_{j=1}^{m} \sum\limits_{i=1}^{n} \sum\limits_{h=i+1}^{n} \frac{1}{w_{i h j}\left(t_{h}^{\mathrm{arr}}-t_{i}^{\mathrm{dep}}\right)+M\left(1-w_{i h j}\right)}$ (2)
$\min f_{3}= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} c_{i j} x_{i j}$ (3)
$\text { s.t. } \quad \sum\limits_{j=1}^{m} x_{i j}=1, \forall i \in I$ (4)
$\sum\limits_{j=1}^{m} \sum\limits_{s=1}^{a} y_{i j s}=1, \forall i \in I$ (5)
$ \sum\limits_{j=1}^{m} \sum\limits_{g=1}^{d} z_{i j g}=1, \forall i \in I$ (6)
$x_{i j}=\sum\limits_{s=1}^{a} y_{i j s}, \forall i \in I ; j \in J $ (7)
$x_{i j}=\sum\limits_{g=1}^{d} z_{i j g}, \forall i \in I ; j \in J$ (8)
$\begin{gathered}w_{i h j}\left(t_{h}^{\mathrm{arr}}-t_{i}^{\mathrm{dep}}\right)+M\left(1-w_{i h j}\right) \geqslant T_{\min } \\\forall i \neq h, i, h \in I ; j \in J\end{gathered}$ (9)
$u_{s k} \rho_{i h}\left(y_{i j s}+y_{h l k}\right) \leqslant 1, \forall i, h \in I ; j, l \in J ; s \in R_{j} ; k \in R_{l}$ (10)
$u_{g q} \rho_{i h}\left(z_{i j g}+z_{h l q}\right) \leqslant 1, \forall i, h \in I ; j, l \in J ; g \in P_{j} ; q \in P_{l}$ (11)
$u_{s q} \rho_{i h}\left(y_{i j s}+z_{h l q}\right) \leqslant 1, \forall i, h \in I ; j, l \in J ; s \in R_{j} ; q \in P_{l}$ (12)
$\sum\limits_{j=1}^{n} x_{i j} x_{h j} \geqslant o_{i h}, \forall i \neq h, i, h \in I$ (13)
$x_{i j}, y_{i j s}, z_{i j g} \in\{0,1\}$ (14)
式(1)针对高峰时段到站列车，表示最小化到发线占用时间方差；式(2)针对所有时段的到站列车，表示列车总冲突系数；式(3)针对平峰时段到站列车，表示最小化到发线占用费用；式(4)为到发线指派的唯一性约束；式(5)和式(6)为接发车进路指派的唯一性约束；式(7)和式(8)为到发线和咽喉区进路的连通性约束；式(9)为同一到发线的占用时间间隔约束；式(10)~(12)为咽喉区进路冲突约束，分别表示接车进路之间、发车进路之间以及接发车进路之间在时间和空间上不能存在共同的交集；式(13)为列车折返约束。
2 算法设计到发线运用问题是典型的多目标约束优化问题，采用进化多目标优化算法可以求出一组Pareto最优解集供决策者针对不同的条件制定对应的方案。进化算法中的NSGA-Ⅱ可以有效解决多目标优化问题，但其在进行支配排序时仅通过适应度函数选择，并未考虑解的可行性，如果在进化全过程周期中加入约束限制则会导致解的搜索区域急剧减小，最后陷入局部最优[16]。因此在进化的后期加入约束准则改进NSGA-Ⅱ算法中的个体选择策略，既能在进化前期保持种群的多样性，又能在进化后期提高种群的收敛性。基本步骤如下：
Step 1??编码。采用自然数编码方式，染色体长度等于研究时段内到站列车的数目，基因位置代表列车到站的顺序，基因所对应内容则为到发线编号。
Step 2??种群初始化。随机生成一组规模为N的初始种群作为初代父代种群E(s)，s=0，s为迭代次数。
Step 3??非支配排序。针对已经生成的种群，计算每个个体对应不同目标函数的值，然后根据个体间是否存在支配关系对种群内所有个体进行分层，层级越小的解越优秀，再对同一层内的解计算拥挤距离，计算公式如下
$Z_{D}=\sum\limits_{b=1}^{B}\left(\left|f_{b}^{D+1}-f_{b}^{D-1}\right|\right)$ (15)
式中：ZD为拥挤度距离，fbD+1和fbD-1分别为个体D+1和个体D-1的第b个子目标的大小，B为目标函数的个数。拥挤距离代表种群的多样性，因此拥挤距离越大的解在该层级内越优秀。继续执行Step 5。
Step 4??约束准则排序。引入约束违反度[17]概念，并根据约束支配原则对种群内个体进行排序，有效改善NSGA-Ⅱ进化后期可行解不足的问题。定义如果以下任何一个条件成立，则种群中任意两个解比较时解1约束支配解2。
1) 解1为可行解，解2为不可行解；
2) 解1和解2都是不可行解，但解1的约束违反度小；
3) 解1和解2都为可行解，且解1优于解2，使用Step 3中拥挤距离的计算规则来解决。
约束违反度值计算公式如下
$G(\boldsymbol{X})=\sum\limits_{e=1}^{10}\left\langle g_{e}(\boldsymbol{X})\right\rangle$ (16)
式中：G(X)为约束违反度，X为决策向量，ge(X)为模型中的10个约束条件。当ge(X)≤0, 〈ge(X)〉返回其绝对值，否则返回0。由此可知当X为可行解时约束违反度值为0，当X为不可行解时，约束违反度值大于0。
Step 5??遗传操作。将父代种群E(s)执行传统遗传算法中的交叉和变异操作，生成一个规模为N的子代种群F(s)。
Step 6??选择算子和精英策略。将父代E(s)和子代F(s)混合得到规模为2N的种群，然后判断若
3 算例分析 3.1 数据准备以京沪高速铁路某车站为例进行仿真验证。车站从3个方向接发列车，并与一个动车所相连通，站型图见图 2，站内共有10个到发线，48条基本接发车进路，8条入段进路和8条出段进路，车站作业时间标准见表 1。对该站某日全天接发列车数量进行统计，单小时最大接发车数量M为20，到站列车的分布特征参数θ取0.85，则平峰和高峰时段对应的接发列车数量范围分别为[0, 17]和(17, 20]。综合考虑方便旅客乘降和到发线固定作业方式的影响，制定到发线占用费用矩阵，见表 2。选取16:00~18:00内的进站列车作为研究对象，16:00~17:00接发列车16列，处于平峰时段，17:00~18:00接发列车20列，处于高峰时段，取种群大小N=200，最大进化代数Smax=300，交叉概率为0.9，变异概率为0.2，分别对两种列车分布状态下的到发线运用问题进行建模计算。
Fig. 2
图 2 某高速铁路车站平面站型 Fig. 2 Layout of a high-speed railway station 表 1
表 1 作业时间标准 Tab. 1 Operating time standard? min项目 作业过程占用咽喉区时间 始发列车到发线停留时间 终到列车到发线停留时间 安全作业时间间隔
接车 发车 通过 出入段
列车接发 4 3 3 3 17 12 5
表 1 作业时间标准 Tab. 1 Operating time standard?
表 2
表 2 到发线占用费用矩阵 Tab. 2 Occupancy cost matrix of train platform 到发线 1 2 3 4 V VI 7 8 9 10 上行 10 000 10 000 10 000 10 000 10 000 1 3 3 4 5
下行 5 5 4 3 1 10 000 10 000 10 000 10 000 10 000
表 2 到发线占用费用矩阵 Tab. 2 Occupancy cost matrix of train platform
3.2 仿真结果验证16:00~17:00平峰时段，计算结果在进化至220代时逐渐收敛于Pareto前沿，共得到5组解，方案见表 3。列车总冲突系数与到发线占用费用见图 3。可以看出，方案之间均不存在支配关系，且列车总冲突系数的减少需要以增加到发线占用费用为代价。全部可行方案中列车总冲突系数最低至0.007 4，到发线占用费用最小为44。该时段到站列车数量未达峰值，从客运服务角度来看，优先满足旅客乘降便捷和客运员固定到发线接发列车，则选择方案2，对比原计划方案，总冲突系数降低了12.62%，到发线占用费用降低了16.98%；从车站调度安全角度来看，优先提升到发线作业鲁棒性，选择方案1，进一步考虑同一到发线相邻列车最小间隔时间可能成为限制计划强壮性的瓶颈因素，验证方案1的最小间隔时间为11 min，该值同样是5个方案中的最大值，符合要求，对比原计划方案，总冲突系数降低了33.82%，到发线占用费用降低了5.66%。
表 3
表 3 16:00~17:00平峰时段到发线分配方案 Tab. 3 Train platform utilization scheme during normal peak period 16:00—17:00 方案 列车 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
原计划方案 V 3 VI 4 8 1 7 9 10 V 8 7 4 1 2 V
方案1 V 3 VI 4 8 1 7 9 10 V 8 VI 4 1 3 V
方案2 V 3 VI 4 7 2 VI 9 8 4 7 VI V 3 4 V
方案3 V 3 VI 4 8 1 VI 7 9 V 8 VI 4 1 3 V
方案4 V 3 7 4 8 1 VI 7 9 V 8 VI 4 1 3 V
方案5 V 3 VI 4 8 1 7 9 8 4 7 VI V 1 3 4
表 3 16:00~17:00平峰时段到发线分配方案 Tab. 3 Train platform utilization scheme during normal peak period 16:00—17:00
Fig. 3
图 3 16:00~17:00到发线运用方案的Pareto解分布 Fig. 3 Pareto front distribution in train platform utilization scheme during 16:00—17:00 17:00~18:00高峰时段，仿真计算共得到4组Pareto解，种群进化至250代时趋于收敛，限于篇幅，只展示各方案中列车分配不同的到发线，见表 4。各方案目标函数对比结果见图 4。与平峰时段分配方案对比发现，4个方案中只有40%列车分配的到发线有区别，说明到站列车密集，满足约束的可行性方案不多，同时各方案的最小间隔时间均为3 min，且该瓶颈时间位于列车19和24之间。方案1到发线使用效率最高，到发线占用时间方差104.85，比原计划方案降低48.57%，总冲突系数也降低了18.71%，明显提高了车站设备的利用效率；方案4在总冲突系数比原计划方案降低了29.81%的同时，到发线使用效率基本与方案1持平，既保证了车站的通过效率，又提高了到发线运用计划的鲁棒性。
表 4
表 4 17:00~18:00高峰时段到发线分配方案(部分) Tab. 4 Train platform utilization scheme during rush hour 17:00—18:00 (part) 方案 列车 19 22 23 27 28 30 33 35
原计划方案 VI 2 7 2 9 3 4 7
方案1 7 2 8 2 9 3 4 7
方案2 VI 2 7 4 8 2 3 7
方案3 VI 4 7 2 9 3 4 8
方案4 7 4 8 2 9 3 4 7
表 4 17:00~18:00高峰时段到发线分配方案(部分) Tab. 4 Train platform utilization scheme during rush hour 17:00—18:00 (part)
Fig. 4
图 4 17:00~18:00到发线运用方案的Pareto解分布 Fig. 4 Pareto front distribution in train platform utilization scheme during 17:00—18:00 与此同时，为了研究分时段优化与传统优化方法的区别，本文对全部研究时间段内36列列车的三目标整数规划模型进行计算生成了整体优化方案，从解的Pareto前沿中均匀选取与分时段优化方案等量的解进行对比，见图 5，方法1和方法2分别代表本文方法和整体优化方法。可以看出，平峰时段整体优化和分时段优化方法在到发线占用费用方面比较接近，但列车总冲突系数方面却明显降低，两种方法同一到发线相邻列车间隔时间的最小差值为19 min，说明在车站作业不紧张时分时段优化方案能够在保证到发线合理选择的同时有效提高到发线作业的鲁棒性；高峰时段，整体优化方法中到发线占用时间方差和列车总冲突系数均有较大波动，且两个目标函数值变化趋势相同，分时段优化方法则情况相反，分析原因可知，整体优化主要考虑了到发线空间上的运用均衡性，分时段优化则进一步将分段时间内的到发线占用时间均匀分布，使得列车总冲突系数也可以保持在较低水平。当突发事件发生, 导致列车晚点时，同一到发线列车间的时间间隔越长表示吸收晚点时间的能力越强，说明分时段优化方法能够增强车站的抗干扰能力，具有一定的优越性。
Fig. 5
图 5 全部研究时段整体和分时段优化方法结果对比 Fig. 5 Comparison of results of overall and segment optimization methods throughout the period of study 为检验改进算法的求解效率和质量，以高峰时段2 h车站数据为例，将改进算法与文献[6]中标准NSGA-Ⅱ算法进行对比实验，结果见表 5。实验结果表明本文的改进NSGA-Ⅱ算法可以获得更多的可行解，目标值有一定程度的优化，同时改进算法的求解时间降低了48.17%。改进后NSGA-Ⅱ算法在解的质量和求解效率方面均有提升，说明该算法具有良好的适应性和有效性。
表 5
表 5 本文算法与对比算法的比较结果 Tab. 5 Comparison of results of the proposed algorithm and the comparison algorithm 使用算法 解的数量 到发线占用时间方差平均值 列车总冲突系数平均值 求解时间/s 本文算法 22 152.4 0.015 48.11
NSGA-Ⅱ 17 190.8 0.016 92.83
表 5 本文算法与对比算法的比较结果 Tab. 5 Comparison of results of the proposed algorithm and the comparison algorithm
4 结论在考虑列车到发分布特征，分时段差异化制定目标的基础上，构建了一种到发线运用多目标优化模型，并设计了包含约束处理的改进NSGA-Ⅱ算法进行求解。与整体优化方法相比，分时段优化方法从车站资源利用的角度增加了目标的针对性和多样性，引入列车总冲突系数加强了到发线运用计划的抗干扰性。实验结果表明，相比整体优化方法，分时段优化方法的目标值有大幅降低，说明该方法有更好的鲁棒性和有效性，同时本文算法在解的质量和求解效率方面比NSGA-Ⅱ算法均有所提升，说明该模型和算法可以适用于不同时段车站到发线运用计划制定过程，对提升车站的抗干扰能力和客运服务质量具有重要意义。
参考文献
[1] 朱昌锋. 铁路大型客运站到发线分配耦合优化及时域调整研究[D]. 兰州: 兰州交通大学, 2014
ZHU Changfeng. Research on coupling optimization of arrival and departure track scheduling for railway large-scale passenger station and its receding horizon adjustment[D]. Lanzhou: Lanzhou Jiaotong University, 2014
[2] CACCHIANI V, GALLI L, TOTH P. A tutorial on non-periodic train timetabling and platforming problems[J]. EURO Journal on Transportation and Logistics, 2015, 4(3): 285. DOI:10.1007/s13676-014-0046-4
[3] CARDILLO D D L, MIONE N. k L-list λ coloring of graphs[J]. European Journal of Operational Research, 1998, 106(1): 160. DOI:10.1016/S0377-2217(98)00299-9
[4] SELS P, CATTRYSSE D, VANSTEENWEGEN P. Automated platforming & routing of trains in all Belgian railway stations[J]. Expert Systems with Applications, 2016, 62(15): 302. DOI:10.1016/j.eswa.2016.05.042
[5] PETERING M E H, HEYDAR M, BERGMANN D R. Mixed-integer programming for railway capacity analysis and cyclic, combined train timetabling and platforming[J]. Transportation Science, 2016, 50(3): 892. DOI:10.1287/trsc.2015.0652
[6] 刘杰, 殷勇, 甘志良. 高速铁路车站咽喉区与到发线综合运用优化[J]. 交通运输系统工程与信息, 2018, 18(1): 193.
LIU Jie, YIN Yong, GAN Zhiliang. Comprehensive optimization for utilization of arrival-departure tracks and throat area in high-speed railway station[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 193. DOI:10.16097/j.cnki.1009-6744.2018.01.029
[7] ZHANG Yongxiang, ZHONG Qingwei, YIN Yong, et al. A fast approach for reoptimization of railway train platforming in case of train delays[J]. Journal of Advanced Transportation, 2020, 2020: 5609524. DOI:10.1155/2020/5609524
[8] 赵鹏, 宋文波, 陈霞, 等. 大型铁路客运站到发线与咽喉区综合运用优化[J]. 北京交通大学学报, 2015, 39(6): 1.
ZHAO Peng, SONG Wenbo, CHEN Xia, et al. Comprehensive optimization for utilization of arrival-departure tracks and throat area in large railway passenger station[J]. Journal of Beijing Jiaotong University, 2015, 39(6): 1. DOI:10.11860/j.issn.1673-0291.2015.06.001
[9] 鲁工圆, 闫海峰, 徐进. 基于TCPN的铁路客运站作业组合仿真模型[J]. 西南交通大学学报, 2013, 48(4): 694.
LU Gongyuan, YAN Haifeng, XU Jin. Railway passenger station operation combined simulation model based on TCPN[J]. Journal of Southwest Jiaotong University, 2013, 48(4): 694. DOI:10.3969/j.issn.0258-2724.2013.04.016
[10] 陈佳瑞. 大型客运站进路选择与股道运用协调优化研究[D]. 兰州: 兰州交通大学, 2017
CHEN Jiarui. Coordination optimization study of route selection and track utilization in large railway passenger station[D]. Lanzhou: Lanzhou Jiaotong University, 2017
[11] 郭彬, 周磊山, 唐金金, 等. 高速铁路大站作业计划鲁棒性链式优化研究[J]. 铁道学报, 2017, 39(7): 10.
GUO Bin, ZHOU Leishan, TANG Jinjin, et al. Study on robustness improvement of high-speed railway station operation plan based on operational chain optimization[J]. Journal of the China Railway Society, 2017, 39(7): 10. DOI:10.3969/j.issn.1001-8360.2017.07.002
[12] 雷定猷, 王栋, 刘明翔. 客运站股道运用优化模型及算法[J]. 交通运输工程学报, 2007, 7(5): 84.
LEI Dingyou, WANG Dong, LIU Mingxiang. Optimization model and algorithm of utilization of arrival and departure tracks in railroad passenger station[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 84.
[13] 刘伟. 非常态下的大型客站咽喉利用与到发线分配优化研究[D]. 北京: 北京交通大学, 2017
LIU Wei. Optimizing the bottleneck sections and track allocation problems for large railway passenger stations under abnormal conditions[D]. Beijing: Beijing Jiaotong University, 2017
[14] 王保山. 客运专线车站作业计划优化编制方法研究[D]. 北京: 北京交通大学, 2015
WANG Baoshan. Optimization model for station operational schemes on passenger dedicated lines[D]. Beijing: Beijing Jiaotong University, 2015
[15] DEWILDE T, SELS P, CATTRYSSE D, et al. Improving the robustness in railway station areas[J]. European Journal of Operational Research, 2014, 235(1): 276. DOI:10.1016/j.ejor.2013.10.062
[16] 顾清华, 莫明慧, 卢才武, 等. 求解约束高维多目标问题的分解约束支配[J]. 控制与决策, 2020, 35(10): 2466.
GU Qinghua, MO Minghui, LU Caiwu, et al. Decomposition-based constrained dominance principle NSGA-Ⅱ for constrained many-objective optimization problems[J]. Control and Decision, 2020, 35(10): 2466. DOI:10.13195/j.kzyjc.2019.0116
[17] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182. DOI:10.1109/4235.996017
