前言:
现时朋友们对“启发式求解”大概比较关切,姐妹们都需要剖析一些“启发式求解”的相关知识。那么小编在网络上网罗了一些对于“启发式求解””的相关知识,希望小伙伴们能喜欢,朋友们快快来学习一下吧!蒋燕 李彬重庆市轨道交通(集团)有限公司
摘 要:城市轨道交通不能全天运营,存在末班车无法换乘情况。为实现末班车可换乘客流量最大的目标,建立了以换乘客流需求为基础、线网末班车发车时间在一定范围、关键线路末班车发车时间固定的末班车衔接模型,并采用逐步寻优的启发式算法求解;基于末班车时刻表,提出了临界换乘方向概念及停站时间优化方法。通过重庆轨道交通线网末班车换乘衔接及优化进行案例验证,结果表明,所提出的模型能够有效增加末班车可换乘客流数量,具有较强实用性。
关键词:城市轨道交通;末班车;换乘衔接;停站时间优化;
作者简介:蒋燕(1991—),男,重庆丰都人,硕士,工程师,主要从事城市轨道交通运营管理;
0引 言
随着城市发展,多个城市轨道交通运营线路条数超过10条,线网规模扩大和换乘节点的增加,使得末班车协调变得更加复杂。末班车开行主要有统一和非统一发车时刻两种方式,由于城市结构呈现分散式布局,末班车统一发车时刻方式存在核心区线路运营时间不足、市郊区线路运营时间过长、重要换乘站换乘衔接不佳等问题,极易导致乘客投诉及运能浪费。因此,末班车非统一发车时刻的方式成为发展趋势,如何做好末班车换乘衔接,减少乘客出行不可达现象,对于乘客和运营企业都有着重要意义。
对末班车衔接研究主要可分为两类:一是构建末班车衔接关系模型,通过事先假定末班车衔接原则,如满足特定方向、特定线路的换乘需求等,从而推算网络末班车运行方案[1]。北京地铁以满足2#线(环线)换乘站的末班车换乘衔接为目标制定了线网末班车方案[2,3]。二是通过建立优化模型,设置不同的优化目标和采用不同算法进行求解。徐瑞华等[4,5,6]以能够换乘末班车乘客数量最多为目标,采用最小生成树的Kruskal算法进行求解;宁丽巧等[7]以换乘总等待时间最小为目标,利用CPLEX进行求解。
本文末班车换乘衔接分为时刻表生成和时刻表优化两个方面。
末班车时刻表生成,以末班车可换乘客流量最大、候车时间最小为目标,基于末班车发车时间固定的关键线路,采用逐步寻优的策略,逐个确定衔接线路方向及其末班车时刻表。
末班车时刻表优化,以生成的末班车时刻表为基础,识别该方案下末班车无法换乘、但换乘时间偏差在一定范围内的换乘方向(后文简称“临界换乘方向”);按照时刻表优化后可换乘客流更大的原则,对部分临界换乘方向进行优化,实现换乘衔接。
1末班车时刻表生成模型1.1 末班车换乘关系
如图1所示:线路LA中车站si的线路方向sdiid(d=1,上行;d=-1,下行)末班车到站时间为Tarrivesdisidarrive,发车时间为Tleavesdisidleave;Sdiid与线路LB中车站Sj的线路方向fgjjg的换乘关系为CsfJsdisidsJf(CsfJsdisidsJf=1表示可以换乘,否则CsfJsdisidsJf=0);sdiid换乘至sfjjf步行及乘车所需的最短时间为TsfJsdisidsJf;那么
sdiid换乘至sfjjf的末班车时间冗余RsfJsdisidsJf计算为:RsfJsdisidsJf=CsfJsdisidsJf×(Tleavesfjsjfleave-Tarrivesdisidarrive-TsfJsdisidsJf)。
sdiid换乘至sfjjf末班车换乘可行性XsfJsdisidsJf计算为:
,其中1表示换乘可达,0表示换乘不可达。
图1 换乘关系图 下载原图
由于线网运营存在方向性、空间性和时效性,在非24 h不间断运营的情况下,末班车衔接不可能满足每个换乘方向的换乘需求。图1中,假设线路LA方向sdiid末班车乘客能够换乘线路LB方向sfjjf末班车,考虑换乘步行时间因素,若不增加方向sdiid末班车停站时间,方向sfjjf乘客不可能换乘方向sdiid末班车,即末班车换乘成功方向的反向无法换乘。
1.2 末班车时刻表生成模型
不同时段乘客出行需求不同,早高峰以去往办公区为主,晚高峰以去往居住区、商业区为主,夜间以去往居住区为主。为尽可能减少乘客无法换乘末班车的情况,以换乘客流需求为基础,构建满足换乘成功客流量最大为目标的线网末班车时刻表生成模型。
sdiid换乘至sfjjf的末班车换乘客流量需求用FsfJsdisidsJf表示,单个方向成功换乘客流量为XsfJsdisidsJf×FsfJsdisidsJf。对于存在n个车站的线网而言,整个线网成功换乘最大客流量则为
maxFN=∑i=1:n∑J=1:n∑d=1,−1∑f=1,−1XsfJsdi×FsfJsdiFΝ=∑i=1:n∑J=1:n∑d=1,-1∑f=1,-1XsidsJf×FsidsJf
式中:假设末班车换乘客流需求FsfJsdisidsJf为定值,那么目标值FN的变化仅取决于不同线网末班车时刻表方案下换乘可行性XsfJsdisidsJf的变化。在不加其他约束条件情况下,最优解为每条线每天均24 h运营,所有的换乘站换乘方向均可以换乘,即可行域无上界,目标无法进行求解。
本文考虑末班车一方面应保证必须的服务质量,同时也需考虑设施设备检修和企业成本经济性等因素。因此,将末班车起点站最早、最晚发车时间作为约束条件,即[Tleaveearlistearlistleave,Tleaveeatesteatestleave]。
网络化运营条件下,线网线路条数、换乘站越多,在固定末班车时间范围内可开行方案数量越多。对于k条线路的路网,末班车发车时间范围限制时间t min,以1 min为间隔,单条线双向存在t2种末班车开行方案,整个线网则存在t2k种方案。在实际运营中,往往存在个别线路因运营里程长、客流量大、夜间检修施工要求高等因素导致其末班车发车时刻固定,本文称之为关键线路。
因此,本文对关键线路末班车时刻确定情况下的线网末班车时刻表方案进行求解。
1.3 模型求解
线网Gn中,已确定末班车时刻表的线路方向集合为Gsure,未确定末班车时刻表的线路方向集合Gunsure=Gn-Gsure。本文以Gsure为基础,采用逐步寻优的启发式算法,每次从Gunsure中确定一个线路方向Lf22f∈Gunsure及其最优末班车时刻表方案TLfw,最终实现对Gunsure中所有线路方向末班车时刻表进行求解。
具体每次确定线路方向Lfwwf及其最优末班车时刻表方案TLfw方法如下
Lfwwf与Gsure新增的最大可换乘客流量为FLfw;那么,存在Gunsure中除Lfwwf的任意线路方向Lfw¯¯¯¯∈(Gunsure−Lfw)Lwf¯∈(Gunsure-Lwf),均满足条件FLfw≥Lfw¯¯¯¯FLwf≥Lwf¯。
线路方向Lfwwf存在y种末班车方案,假设其最优时刻表方案TLfw为第m(其中m≤y)种方案,则最优末班车时刻表方案TLfw应满足与Gsure新增末班车可换乘客流量最大及换乘时间最少原则。具体为。
新增可换乘客流量最大原则:最优时刻表方案TLfw下,Lfwwf加入Gsure后,对于车站sgqqg∈Gsure、车站sfppf→sgqqg,单个换乘方向sgppg新增可换乘客流量表示为ssgqsfpspfsqg×Fsgqsfpspfsqg,因换乘具有双向性,Lfwwf与Gsure新增的可换乘客流量表示为:TLfw=∑sfp∈Lfw∑Lfw∈sgq(Xsgqsfp×Fsgqsfp)+∑Gsure∈sfs∑Gsure∈LfsXsfpsspΤLwf=∑spf∈Lwf∑Lwf∈sqg(Xspfsqg×Fspfsqg)+∑Gsure∈ssf∑Gsure∈LsfXspsspf。那么任意其他末班车时刻表方案,均满足FLfw≥FLfw(m)。
新增候车时间最短原则:最优时刻表方案TLfw下,车站sfppf的末班车到站时间为Tarrivesfpspfarrive,对于单个换乘方向sfppf→sgqqg新增末班车换乘候车时间为:Tleavesgqsqgleave-Tarrivesfpspfarrive-Tsgqsfpspfsqg,因换乘具有双向性,Lfwwf与Gsure新增的候车时间表示为:TLfwGsure=∑sfp∈Lfw∑sgq∈GsureXsgqsfp×(Tleavesgq−Tarrivesfp−Tsgqsfp)+∑sfp∈Lfw∑sgq∈GsureXsfpsfp×(Tleavesfp−Tarrivesfp−Tsfpsfp)ΤGsureLwf=∑spf∈Lwf∑sqg∈GsureXspfsqg×(Τsqgleave-Τspfarrive-Τspfsqg)+∑spf∈Lwf∑sqg∈GsureXspfspf×(Τspfleave-Τspfarrive-Τspfspf)。那么任意其他末班车时刻表方案,均满足TLf2GsureGsureL2f≥TLf2(m¯¯¯)GsureGsureL2f(m¯)。例如图2所示:L1、L2末班车发车时间已确定,换乘至线路L3在b站和c站的到站时间分别为23∶25和23∶35;线路L3在b、c站间运行时间10 min。按此L3在b站发车时间只需超过23∶25,均可以满足L1、L2→L3换乘,但是发车时间越晚,乘客候车时间越长,夜间施工作业时间也越短。因此,L3在b站最佳的发车时间为23∶25。
图2 简单网络示意图 下载原图
模型求解具体步骤如下。
Step1:初始化:(1)关键线路方向Ldlld起点s发车时间为Tleavesdsssdleave;(2)末班车发车限制时间为[Tleaveearlistearlistleave,Tleavelatestlatestleave]。
Step2:建立已确定末班车时刻表的线路集合Gsure,初始化Gsure={Ldlld}。建立未确定末班车时刻表的线路集合Gunsure,Gnsure=Gn-Gsure。
Step3:如果Gunsure≠∅,则计算Gunsure中各线路末班车时刻表。
Step3.1:以Gsure为基础,找到任意Lfwwf∈Gunsure的最优时刻表方案时间TLfw。具体方法如下。
(1)线路Lfwwf末班车起点发车时间限制范围[Tleaveearlistearlistleave,Tleavelatestlatestleave]存在y种方案,计算任意方案新增可换乘客流及增加候车时间;
(2)按照新增可换乘客流量最大、新增换乘时间最少原则对y种方案进行比选,找到lfwwf的最优时刻表方案时间TLfw。
Step3.2:从Funsure中比选出确定加入Gsure的线路方向Lfwwf,及其末班车时刻表方案TLfw。
Step3.3:将Lfwwf加入Gsure,Gsure=Gsure+Lfwwf;并同时将Lfwwf从Gunsure中移除,Gunsure=Gunsure-Lfwwf。
Step3.4:计算剩余线路末班车时刻表方案。重复Step3,直至Gunsure=∅。
Step4:将线网末班车时刻表方案标记为TGn,该方案下可换乘客流量记为FonGnGnon。
2末班车时刻表优化方法3.1 临界换乘方向
末班车换乘存在乘客换乘至目标线路时末班车刚好离站而无法实现换乘的情况。尤其是对于大客流方向换乘而言,此类情况的发生容易引起乘客投诉,有损企业形象。因此,本文将末班车换乘衔接不上、换乘时间冗余偏差在一定范围Tδ内、且换乘客流需求超过某一阈值Fσ的换乘方向,称之为“临界换乘方向”。即换乘方向sdiid→sfjjf满足条件{Rsfjsdisidsjf|-Tδ≤Rsfjsdisidsjf≤0,Fsfjsdisidsjf|Fsfjsdisidsjf≥Fσ}。本文以临界换乘方向为研究对象,进行时刻表优化。
3.2 优化原则
临界换乘方向时刻表优化,是为了更多的末班车乘客能够实现换乘;此外,乘客对于停站时间存在一定的可接受范围,过长的停站时间会引起乘客焦虑。因此,仅对满足以下条件的临界换乘方向末班车时刻表进行优化。
条件1:临界换乘方向时刻表优化后,线网末班车可换乘客流量>现可换乘客流量。
条件2:临界换乘方向时刻表优化后,末班车站台停站时间应不超过最大停站时间。
3.3 优化方法及步骤
为避免末班车时刻表优化对其他换乘方向可达性产生影响,优化采用增加换乘站临界换乘方向目标线路停站时间的方式,而普通车站停站时间不作调整。即:若sdiid→sfjjf为临界换乘方向,则增加sfjjf方向停站时间满足换乘衔接,其应增加的停站时间为Tleavesfjsjfleave=Tarrivesdisidarrive+Tsfjsdisidsjf-Tleavesfjsjfleave。
具体优化步骤如下。
Step1:初始化:(1)临界换乘方向判别客流阈值Fσ和时间阈值Tδ;(2)换乘站最大停站时间限制tmax;(3)现线网末班车时刻表方案TGn。
Step2:识别网络中可进行优化的所有临界换乘方向,记为TR。若sdiid→sfjjf为可优化的临界方向,应满足TR={TRsfjsdisidsjf|-Tδ<Rsfjsdisidsjf<0,Fsfjsdisidsjf≥Fσ,Tarrivesdisidarrive+Tsfjsdisidsjf-Tarrivesfjsjfarrive<tmin}。
Step3:若TR=∅,则执行以下步骤。
Step3.1:找出换乘需求最大的可优化临界方向,记为TRsfjsdisidsjf。
Step3.2:增加换入方向sfjjf及线路后续车站发车时间,数值为Tleavesfjsjfleave=Tarrivesdisidarrive+Tsfjsdisidsjf-Tleavesfjsjfleave。将更新后的线网末班车时刻表方案记为TnewGnGnnew。
Step3.3:计算新方案下的可换乘客流量记为Fon−newGnGnon-new。
Step3.4:对临界方向TRsfjsdisidsjf是否进行优化进行判断。
Step3.4.1:如果Fon−newGnGnon-new≤FonGnGnon,则不进行优化。将TRsfjsdisidsjf从TR中移出,即TR=TR-TRsfjsdisidsjf。
Step3.4.2:如果Fon−newGnGnon-new>FonGnGnon,则得到新的末班车时刻表方案及可换乘客流量,即TGn=TnewGnGnnew,FonGnGnon=Fon−newGnGnon-new,对该时刻表方案下的TR进行更新。
Step3.5:对更新后的TR,按Step3继续判别及优化。
Step4:TR=∅时,路网中不存在临界换乘方向,计算结束。此时最优的末班车时刻表方案为TGn,可换乘客流量为FonGnGnon。
3示 例3.1 重庆轨道运营基本概况
以重庆轨道交通末班车时刻表方案制定为例进行说明。截止2021年9月,目前已开通线路9条,运营369.49 km, 193座车站,其中换乘站22座,存在198个换乘方向。
现线网各线路末班车采用晚上22∶30从各线始发站发车,运行至终点站后回段结束运营的方式。从目前运营情况来看,大坪站、小什字站、两路口站、牛角沱站等主要换乘站及客流方向存在末班车无法换乘情况,且偏差超过40 min。
3.2 末班车时刻表生成
(1)客流基础。由于目前客流清分技术无法准确无误的对末班车的客流进行清分,本文考虑夜间乘客出行规律存在一定的相似性,因此,选取运营最后一小时换乘客流作为基础数据,反映末班车客流走向。
(2)关键线路的选取。重庆轨道交通3#线是重庆行车间隔最小,客流量最大的线路。由于列车运用数较多,线路较长,列车回库时间较晚,检修作业时间紧张。因此,从其客流量、夜间检修等分析,均适合作为关键线路。故将3#线下行末班车起点发车时间定为22∶30不变进行研究。
(3)末班车起点站发车限制时间。目前重庆长大线路单程运行时间时间为1.5 h左右,为避免列车回库过晚的情况,满足不低于4小时夜间施工作业时间要求。给定末班车最早发车时间为22∶30,与目前保持不变;最晚发车时间23∶30,较目前增加1 h。
(4)以5min为最小间隔,根据换乘客流需求,结合末班车时刻表生成模型,计算出线网末班车时刻表表1所示。
表1 线网末班车起点发车时刻表 导出到EXCEL
线路
1#线
2#线
3#线
4号线
5#线
6#线
10#线
环线
国博线
上行
22∶45
22∶45
22∶40
22∶30
22∶50
22∶40
22∶30
23∶00
22∶30
下行
23∶25
23∶25
22∶30
23∶05
23∶00
23∶05
23∶00
22∶45
23∶30
3.3 末班车时刻表优化
给定临界换乘方向判别客流阈值Fσ=100人次和时间阈值Tδ=3 min, 最大停站时间限制tmax=4 min。按此计算,首次优化时存在7个临界换乘方向,具体如表2所示。
表2 临界换乘方向表 导出到EXCEL
换乘站
换出
方向
换入
方向
换乘时间
冗余/s
客流需求
/人次
冉家坝
环线下行
6#线下行
-130
1 093
重庆北站南广场
3#线上行
环线上行
-110
715
冉家坝
环线上行
6#线下行
-10
429
重庆北站南广场
3#线下行
环线下行
-100
308
大龙山
5#线上行
6#线上行
-20
305
较场口
2#线上行
1#线下行
-80
243
红土地
6#线上行
10#线上行
-180
173
临界换乘方向时刻表优化。增加换乘站目标线路方向停站时间实现换乘可达。具体为:6#线下行冉家坝(+130 s)、环线上行重庆北站南广场(+110 s)、6#线大龙山上行(+20 s)、1#线下行较场口(+80 s)。
对临界换乘方向的优化后,除重庆北站南广场(3#线下行→环线下行方向)、红土地(6#线上行→10#线上行)2个临界换乘方向无法满足换乘外,新增5个可换乘方向。
3.4 结果对比
通过模型计算,最终实现可换乘方向97个,较目前22∶30统一末班车时刻方案,增加11个可换乘方向;可换乘方向客流54%,增加23%;其中,排名前10的换乘客流方向可达到7个(现为0个)。
4结 论
本文考虑城市轨道交通末班车开行最大程度满足客流方向换乘需求,提出一种末班车时刻表生成及临界换乘方向时刻表优化的衔接方法。并以重庆轨道交通末班车时刻表方案制定为例进行验证,有效提升了末班车出行可达性,满足了更多乘客夜间出行需求。针对夜间轨道交通发车间隔较大的问题,后期将从减少夜间乘客出行换乘候车时间方向开展研究。
参考文献
[1] 汪波,黄建玲,牛丰.城市轨道交通网络末班车衔接优化模型[J].城市轨道交通研究,2017(10).
[2] 汪波,李平,厉立,等.北京城市轨道交通路网末班车延误调整研究.现代城市轨道交通,2010.
[3] 汪波,李平,厉立,等.北京城市轨道交通路网末班车调整研究[J].现代城市轨道交通,2010(1):41-44.
[4] 徐瑞华,李璇.城市轨道交通网络末班车衔接方案的综合优化[J].同济大学学报(自然科学版),2012,40(10).
[5] 陈垚,柏赟,冯旭杰,等.基于换乘站停站时间延长的城市轨道交通末班车时刻表优化[J].交通运输系统工程与信息,2017,17(06):228-234.
[6] 禹丹丹,韩宝明,姚向明.基于灵活停站时间的轨道交通网络末班车接续优化[J].北京工业大学学报,2018,03(44):95-102.
[7] 宁丽巧,赵鹏,徐文恺,等.城市轨道交通末班车时段时刻表协同优化研究[J].交通运输系统工程与信息,2016(6).
声明:我们尊重原创,也注重分享。有部分内容来自互联网,版权归原作者所有,仅供学习参考之用,禁止用于商业用途,如无意中侵犯了哪个媒体、公司、企业或个人等的知识产权,请联系删除(邮箱:glyhzx@126.com),另本头条号推送内容仅代表作者观点,与头条号运营方无关,内容真伪请读者自行鉴别,本头条号不承担任何责任。
标签: #启发式求解