地铁线网末班列车时刻表协同编制优化

2020-12-04杨艳

山东交通学院学报 2020年4期

杨艳

广西交通技师学院，广西南宁 530001

0 引言

末班列车时刻表的编制方案是地铁系统运行组织工作的重要环节，其优劣直接影响整体线网的运营效率与安全性，相应优化问题越来越被国内外学术界和工程界重视[1]。国外研究多集中于城市轨道交通服务水平和运营指标的改善，并充分结合现有的实践策略和场景条件[2]。Kecman等[3]针对换乘限制条件设计了重分配优化方法，D′Ariano等[4]基于运营体系服务水平和乘客满意度提出了可变的列车时刻表方案，Corman等[5]在对服务区域进行多样化划分的基础上实现了列车调度和时刻表协同，Zhou等[6]分析了首班车和末班车之间的发车时刻影响。国内相关研究多侧重于修正建模和聚类建模方法，以组合优化特性分析作为问题领域的研究热点和重点[7]。徐文恺等[8]基于随机延误情景建立了城市轨道交通末班车时刻表调整模型，姚恩建等[9]考虑动态可达性对城市轨道交通末班车时刻表进行优化，陈垚等[10]分析了换乘站停站时间延长对末班列车时刻的影响，周玮腾等[11]提出了城市轨道交通网络时变路径搜索算法。此外，还有学者对末班列车时刻表的路径选址、能力限制等综合性因素进行了分析[12-14]。洪玲等[15]提出了基于换乘衔接的单线末班列车衔接方案优化方法，徐瑞华等[16]分析了城市轨道交通网络末班列车衔接方案的运营限制条件，宁丽巧等[17]研究了末班列车所处时段的可控影响因素，徐杰等[18]设计了对末班列车时刻表下的客流诱导系统。现有研究对线网系统衔接程度的分析不够深入，对优化计算方法的探索不够全面[19]。本文考虑末班列车衔接协同的实际因素，建立优化模型，提出基于粒子群算法的计算流程，改进衔接性能指标，实现对地铁末班列车时刻表编制方案的优化。

1 地铁末班列车时刻表协同优化模型

编制地铁末班列车时刻表应着重考虑各线路衔接的时间协同要求，采用规划模型形式明确目标函数、决策变量和限制条件，最大程度实现接续系统化的线路组织方案[20]。

本文的优化模型需考虑地铁线网中换乘衔接成功的线路组合数量最多，即目标函数为

(1)

式中：Xkmn为0-1二元变量，当线路m的末班列车与线路n的末班列车在站点k处衔接成功时，xkmn=1，否则，xkmn=0;K为地铁线网中站点集合；L为地铁线网中线路集合。

线路m的末班列车到达站点k的时刻

(2)

线路n的末班列车于站点k的发车时刻

(3)

地铁线网中的一对换乘接续线路对象

m≠n。

(4)

式(4)确保了两项原则成立：1)在模型定义中，以同一条地铁物理链路为载体实施运营的上行、下行及交路线路属于不同线路；2)模型的应用计算中，避免同一条线路的相关变量被重复计算[21]。

换乘衔接的成功场景定义为：

(5)

辅助决策变量定义为：

Xkmn∈{0,1}，

(6)

决策变量区间，即地铁线网中的末班列车运营时段范围为：

(7)

式中tmin和tmax分别为末班列车运营时段的下限控制点和上限控制点。

2 粒子群算法设计

考虑地铁末班列车时刻表编制问题的组合优化复杂性，为确保计算效率，本文采用粒子群算法(particle swarm optimization, PSO)求解所提出的模型。PSO对于最优化规划模型中涉及的函数性质特点没有特殊限制，可直接应用于启发式计算流程[22-23]。每一个粒子的位置为1×Γ矩阵编码形式，表示地铁线网中Γ个线路的始发时刻，即

pi=[t1t2…tΓ]，

式中：i为粒子序号，i=1,2,3,…,N，N为群规模；Γ为地铁线网中的线路数量。

采用PSO的计算步骤为：

1)计算流程初始化。设置算法中粒子群的规模为N，粒子飞行的最大速度为vmax，计算中的最大迭代次数为φ，解更新过程的学习因子为c1、c2，惯性权重ω的计算参数为c1f、c2f、c1g、c2g、ωmin、ωmax。计算开始时，初始化设定粒子的位置和速度，每一个粒子初始的飞行速度为vi=vmaxδ，δ为区间(0,1]内的随机数。令迭代次数j=1。

2)粒子个体指标计算评定。对于当前群体中的每一个飞行粒子，判断是否在约束条件构成的解空间范围内，若符合，代入模型；若不符合，在解空间条件下继续随机生成新粒子个体。计算粒子对应的目标函数值，获得每一个飞行粒子个体的相应适用性指标。

3)更新粒子最优位置记录。①粒子个体当前位置ppc对应适用性指标Zpc，记录的粒子个体历史最优位置ppb对应适用性指标Zpb，若Zpc

4)更新粒子个体移动信息。粒子飞行速度

(8)

式中；R1、R2为区间[0,1]内的辅助随机数，c1=j(c1f-c1g)/φ+c1g，c2=j(c2f-c2g)φ+c2g。

粒子所在位置

(9)

根据式(8)(9)更新粒子个体的飞行速度、所在位置及粒子个体飞行的惯性权重参数

ω=ωmax-j(ωmax-ωmin)/φ,

ω及c1、c2随计算迭代过程线性减小[24]。

图1 试验网络示意图

5)更新迭代次数。令j=j+1，计算过程循环至步骤2)，停止条件为达到设定的最大迭代次数。

3 数值试验

试验网络如图1所示。由物理链路Line 1、Line 2、Line 3和Line 4组成，区分上下行方向，共计8条运行线路。图1中x1～x8为线路相关站点(上下行均停驻)，各链路旁箭头表示上行方向。该试验网络各线路末班列车时刻表的原始方案如表1所示，线路衔接效果如表2所示。

表1 试验网络末班列车时刻表原始方案

表1(续)

表2 原始末班列车时刻表对应的线路衔接效果

由表1、2可知：线路的衔接组合较少，x5和x7这两处站点存在明显的“瓶颈”问题。

采用C++语言编写粒子群算法，求解地铁末班列车时刻表优化模型。连续运算10次，最长运算时长为463 s，最短运算时长为247 s，平均运算时长为391 s。同时，以地铁线网系统衔接程度最高为优化目标，运算得到的试验网络各线路末班列车时刻表的最佳优化方案如表3所示，线路衔接效果如表4所示。

表3 试验网络末班列车时刻表优化方案

表3(续)

表4 优化后末班列车时刻表对应的线路衔接效果

对比表1～4可看出：线路的衔接组合由表2中的12组增加至表4中的20组，改善幅度达66.7%，优化效果明显。从微观单元看：x5和x7这两处站点的组合优化场景得到了充分改善，有效避免了系统最优原则下的“瓶颈”问题[25]。

传统的末班列车时刻表优化方法中以Zhou等[20]16为典型代表，即分析单一线路调控下的系统最优问题，应用CPLEX求解器求解线性整数规划模型。针对本文算例，应用传统方法进行优化计算，线路接续结果如表5所示。

表5 文献[20]的接续优化结果

由表5可以看出：传统方法下仍然存在x5这一“瓶颈”站点。本文提出的优化方法采用双线路组合优化流程，在启发式算法中通过粒子个体的多维编码促进解的多样性。对比本文方法与传统方法的优化性能可知，本文优化方法接续改善幅度大，平均运算时间由499 s缩减至341 s，“瓶颈”站点由1个减至0。从整个地铁网络线路接续的改善幅度来看二者作用相同，但运算时间上本文方法具有优势，并且未出现“瓶颈”站点问题。