首页 > 论文范文 > 工程工业论文 > 工业综合论文 > 公路运输论文 > 地铁线网末班列车编制时刻表优化方案研究

地铁线网末班列车编制时刻表优化方案研究

2020-12-08 261 上传者：管理员

摘要：以地铁线网为对象,为实现各线路末班列车换乘衔接最优,编制时刻表的优化方案,考虑实际运行的限制因素和必要条件,采用规划建模方法处理列车时刻表编制问题的组合优化;针对问题的复杂性和计算效率需求,采用粒子群算法求解新建模型。数值试验结果表明:该方法流程运算效率较高,原始时刻表的衔接指标在优化过程中改善幅度达66.7%。所建优化模型符合实际工程条件,算法准确有效,可为地铁线路运营领域提供理论依据和工程实践参考。

关键词：
地铁系统
地铁线路
时刻表
末班列车
粒子群算法
加入收藏

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

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

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

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

maxZ=∑k∈K∑m∈L∑n∈LXkmnmaxΖ=∑k∈Κ∑m∈L∑n∈LXkmn,(1)

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

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

tAkm=t0m+∑i=1k−1tRmi(i−1)+∑i=0k−1tRmitkmA=tm0+∑i=1k-1tmi(i-1)R+∑i=0k-1tmiR,(2)

式中:t0mm0为线路m的末班列车始发时刻,是决策变量;∑i=1k−1tRmi(i−1)∑i=1k-1tmi(i-1)R为线路m的末班列车到达站点k之前的途中总行驶时间,其中i为站点数;∑i=0k−1tRmi∑i=0k-1tmiR为线路m的末班列车到达站点k之前的途经站点总停驻时间。

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

tRkn=t0n+∑i=1k−1tRni(i−1)+∑i=0ktDWnitknR=tn0+∑i=1k-1tni(i-1)R+∑i=0ktniDW,(3)

式中:t0nn0为线路n的末班列车始发时刻,是决策变量;∑i=1k−1tRni(i−1)∑i=1k-1tni(i-1)R为线路n的末班列车到达站点k之前的途中总行驶时间;∑i=0ktDWni∑i=0ktniDW为线路n的末班列车于站点k发车前的途径站点总停驻时间。

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

m≠n。(4)

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

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

M(Xkmn−1)≤tDkn−tAkm−tTrakmn<MXkmnΜ(Xkmn-1)≤tknD-tkmA-tkmnΤra<ΜXkmn,(5)

式中:M为充分大的正数;tAkmkmA为线路m的末班列车到达站点k的时刻;tDknknD为线路n的末班列车于站点k的发车时刻;tTrakmnkmnΤra为乘客于站点k自线路m换乘至线路n所需时间。

辅助决策变量定义为:

Xkmn∈{0,1}Xkmn∈{0,1},(6)

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

tAkm,tDkn∈[tmin,tmax]tkmA,tknD∈[tmin,tmax],(7)

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

2、粒子群算法设计

考虑地铁末班列车时刻表编制问题的组合优化复杂性,为确保计算效率,本文采用粒子群算法(particleswarmoptimization,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<Zpb,则执行粒子个体历史最优位置更新ppb=ppc;②记录的粒子群体历史最优位置pgb对应适用性指标Zgb,令其与Zpc对比,若Zpc<Zgb,则执行粒子群体历史最优位置更新pgb=ppc。

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

vj+1pc=ωvjpc+c1R1(pjpc−pjpb)+c2R2(pjpc−pjgb)vpcj+1=ωvpcj+c1R1(ppcj-ppbj)+c2R2(ppcj-pgbj),(8)

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

粒子所在位置

pj+1pc=pjpc+vj+1pc,(9)

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

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

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

图1试验网络示意图

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

3、数值试验

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

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

表1(续)

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

注:u表示上行线路,d表示下行线路,1u-2d表示在站点x1处Line1上行线路与Line2下行线路衔接成功,表4、5类似。

注:u表示上行线路，d表示下行线路，1u-2d表示在站点x1处Line1上行线路与Line2下行线路衔接成功，表4、5类似。

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

采用C++语言编写粒子群算法,求解地铁末班列车时刻表优化模型。连续运算10次,最长运算时长为463s,最短运算时长为247s,平均运算时长为391s。同时,以地铁线网系统衔接程度最高为优化目标,运算得到的试验网络各线路末班列车时刻表的最佳优化方案如表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这一“瓶颈”站点。本文提出的优化方法采用双线路组合优化流程,在启发式算法中通过粒子个体的多维编码促进解的多样性。对比本文方法与传统方法的优化性能可知,本文优化方法接续改善幅度大,平均运算时间由499s缩减至341s,“瓶颈”站点由1个减至0。从整个地铁网络线路接续的改善幅度来看二者作用相同,但运算时间上本文方法具有优势,并且未出现“瓶颈”站点问题。

4、结语

针对地铁末班列车时刻表优化问题,考虑涉及的各类实际运行因素,创建优化模型以解析化描述问题。采用粒子群算法求解模型以获得地铁末班列车时刻表优化方案。数值试验结果表明:本文提出的方法实现了优化改进的目的,获得合理可行的末班列车时刻表编制方案。

在后续研究中可将模型的限制条件进一步细化,例如考虑乘客的安全预留时间和站内拥挤度的时间指标等,以充分反映真实条件下的计算结果和优化效果。

参考文献：

[1]温芳,柏赟,李宁海,等.考虑线网可达性的城市轨道交通末班车时刻表优化[J].铁道科学与工程学报,2019,16(6):1569-1576.

[7]袁振洲,魏来,吴玥琳,等.基于差异化换乘感知的轨道交通末班车衔接优化[J].北京交通大学学报,2020,44(1):12-19.

[8]徐文恺,赵鹏,宁丽巧,等.基于随机延误情景的城轨网络末班车时刻表调整模型[J].铁道学报,2018,40(8):28-33.

[9]姚恩建,刘文婷,刘莎莎,等.基于动态可达性的城轨末班车时刻表优化[J].华南理工大学学报(自然科学版),2018,46(1):58-65.

[10]陈垚,柏赟,冯旭杰,等.基于换乘站停站时间延长的城市轨道交通末班车时刻表优化[J].交通运输系统工程与信息,2017,17(6):228-234.

[11]周玮腾,韩宝明.城市轨道交通网络时变路径搜索算法[J].北京交通大学学报,2017,41(4):115-122.

[12]杜婷婷.城市轨道交通末班车条件下可达路径问题研究[D].北京:北京交通大学,2012.

[13]胡智敏.城市轨道交通末班车时刻表协调优化方法研究[D].北京:北京交通大学,2015.