面向时变需求的高速铁路列车开行方案优化方法

面向时变需求的高速铁路列车开行方案优化方法苏焕银;史峰;邓连波;单杏花【摘要】Tomakethelineplanningforthehigh-speedrailwayfitwellwithtime-dependentdemand,atrainrunningschemeisintroduced.Thentraintimes(departuresandarrivals)areappliedinthelineplanningoptimization,whichavoidsthelarge-scalecomputationsofintegratedoptimizationwithtimetabling.AStackelbergGamemodelofthelineplanningforthehigh-speedrailwayconsideringtime-dependentdemandisproposedwiththeobjectiveofminimizingthetrainenginetimeandthepassengertraveltimewithweights.Constraintsincludesectionthroughcapacities,thestationcapacityoftraindepartingandthetraincapacity.Aschedule-basedassignmentmethodisusedtoevaluatethesolution.Asimulatedannealingalgorithmisusedinwhichsomestrategiesaredesignedtosearchneighborhoodsincludingreducingtrainformations,deletingtrains,addingtrains,splicingtrains,increasingtrainformationsandadjustingtraindeparturetimes.ThenumericalexperimentisconductedontheBeijing-Shanghaihigh-speedrailwaylineandtheresultsshowgoodevaluationindexes.Especially,theactualboardingtimesofpassengersmatchbetterwiththeexpecteddeparturetimesandthealgorithmholdshighefficiencyandwellconvergence.%为了使高铁列车开行方案与旅客时变需求相吻合，引入列车运行方案图，使列车开行方案优化中既能利用列车运行的时间信息，又能避免结合列车运行图综合优化的大规模计算。借助于基于时刻表的高铁客流分配方法，在区间通过能力、车站始发能力、列车载客能力等多种约束下，以列车运行时间与旅客出行时间加权和为优化目标，构建了时变需求下高铁列车开行方案优化的Stackelberg博弈模型。利用降低编组、删除列车、添加列车、拼接列车、提高编组和调整列车始发时间等邻域搜索策略，设计了求解模型的模拟退火算法。最后，针对京沪高速铁路进行算例分析，优化产生的列车开行方案具有良好的评价指标，特别是旅客上车时间与计划出发时间的偏差较小，具有较高的运算效率和收敛性。【期刊名称】《交通运输系统工程与信息》【年(卷)，期】2016(016)005【总页数】8页(P110-116,135)【关键词】铁路运输;高速铁路;列车开行方案;旅客时变需求;模拟退火算法【作者】苏焕银;史峰;邓连波;单杏花【作者单位】中南大学交通运输工程学院，长沙410075;中南大学交通运输工程学院，长沙410075;中南大学交通运输工程学院，长沙410075;铁道科学研究院电子计算技术研究所，北京100081【正文语种】中文【中图分类】U293.1高密度开行的高铁列车，在出行需求较高的时段可以开行更多列车，使旅客出行时变需求得到满足.列车开行数量及分布由列车开行方案和列车运行图确定，在一定服务水平下满足旅客出行需求，最小化铁路运行成本.列车开行方案确定列车运行区段(包括起讫车站和运行径路)、沿途停站、开行频率和编组等内容，很多学者对其优化方法进行了深入研究，多数以日客流量为基础，采用〃按流开车”的思想设计方案，如史峰等［1］，何宇强等［2］建立了旅客列车开行方案的双层规划模型，采用启发式算法求解；付慧伶等［3］建立基于备选集生成列车开行方案的混合整数规划模型，设计拉格朗日松弛启发算法求解；Fu等［4］根据列车停站方案设计分层次列车开行方案优化方法，采用启发式贪婪算法进行求解.由于上述研究没有列车运行时间信息，在客流分配中列车之间的换乘时间误差较大.为了解决这个问题，周文梁等［5］对列车开行方案和列车时刻表进行综合优化，但因没有有效解决基于时刻表的客流分配问题，仍然以日客流量为基础，求解效率有限.Kaspi等［6］在考虑旅客出行时变需求的基础上，假设列车无能力约束，以列车旅行时间和旅客旅行时间的综合加权为优化目标，对列车开行方案和列车时刻表综合优化.Kaspi关于列车无能力约束的假设虽然简化了问题求解，但与现实情况却存在较大的差异.为了解决基于时刻表的高铁客流分配问题，Su等［7］不认为高铁列车上存在拥挤，按照旅客购票顺序占用列车区段能力，在新的列车区段饱和之前，旅客的最小费用出行方案保持不变，在这个时段内，时变需求存在一个最优的离散划分，并可将离散划分后的出行需求进行全有全无分配，直至全部出行需求分配完毕.由于这样的分配过程模拟了旅客购票过程，只需一次性加载便可完成客流分配，不仅效率高，而且与实际情况相吻合.本文利用文献［7］的基于时刻表的高铁旅客出行时变需求分配方法，引入旅客列车运行方案图，以列车运行时间和旅客出行时间加权和为优化目标，基于列车候选集，构建优化高铁列车开行方案的铁路企业与出行旅客的Stackelberg博弈模型，并采用模拟退火算法进行优化求解.算例分析表明，优化方案的列车始发时间分布与客流时变需求吻合较好，算法运算效率较高，对提高高速铁路运营组织水平具有重要的应用价值.高速铁路网络为（V,E）,其中V为车站集，£为区间集•下面在旅客时变需求下，对列车开行方案优化问题展开分析，并提出解决方案.(1)时变需求的表示.高速铁路1天的运营时间为［tl,t2］，出行需求的OD集为RSVxV.对于给定的点对(r,s)ERS，时变需求可表示为关于计划出发时间x的一个强度分布函数.在实际应用中，通常将时变需求表示为每个时间段的出行需求(比如以小时为时段长度).根据2014年7月1日铁路售票数据统计，获得当日北京到上海的每小时出发的旅客出行需求分布如图1所示.(2)列车运行方案图的引入.当考虑旅客出行需求为时变需求时，优化列车开行方案存在两个难于处理的问题：第一个问题是客流分配问题，也就是如何针对时变需求进行客流分配，这个问题可以利用文献［7］来解决，文献中给出了基于时刻表的高铁客流分配方法；当然，要想利用文献［7］的方法进行客流分配，便引出了第二个问题，如何获得列车运行时间信息.自然地，我们想到列车开行方案与列车运行图综合优化，对于优化规模太大的问题，这显然不是一个理想的解决方案，这时我们注意到列车运行方案图.列车运行方案图是框架性列车运行图，包括列车始发、终到时间等框架性属性(但列车运行线之间可能存在冲突).我们认为将列车运行方案图引入到列车开行方案的优化过程中，一方面可以获得所需要的列车运行时间的估计值，以此进行时变客流分配；另一方面也不会增加太多的运算量.(3)列车候选集的确定.列车运行区段和沿途停站的组合称之为列车方案，我们将列车开行方案中可能采用的列车方案都汇集在列车候选集中以供选择，记列车候选集为L.列车候选集中的大部分列车方案可以从现行列车开行方案继承而来；由高铁网络结构和需求特征，还可以新增一些候选方案.候选集的生成方法与文献［3］类似，与文献［3］不同的是，列车编组没包含在列车方案中，每1列列车的编组将在优化模型中另行描述对于列车方案1UL,记，其中表示列车运行区段上第i个停站；h(l)表示列车方案1的停站个数.(4)列车开行方案的表示.按照上述思想，通过引入列车运行方案图，拓展了列车开行方案的概念，拓展后的列车开行方案为Q,对于列车TEQ，对应的列车方案为1T,则，也记，其中分别为列车T停站的到达时间序集和发车时间序集.列车T的编组(辆)和定员(人)分别记为BT和CT.因此，优化列车开行方案也就是讨论对的约束、评价和调整方法.车站veV，始发终到能力均为Cda()v;区间eeE,全天通过能力为；为了避免区间eeE的某一个时段内通过列车过于密集，设定单位时间长度At;将列车运营时段［tl,t2］划分为长度为At的(t2-t1)At个时段，通常取At为1h,每时段的区间通行能力为；考虑到按追踪时间运行时列车的密度较高，所以每时段的通过能力大于平均能力值；列车T的停站veVT，停站时间与启停附加时间之和记为tstop(v)；列车T的运行区段，列车运行时间记为.合理的列车开行方案Q必须满足相关约束条件，具体描述如下：(1)列车候选集约束.(2)列车载客能力约束.(3)列车到发时间约束.(4)全天和各时段区间通行能力约束.(5)车站发车到达能力约束和成对运行约束.列车开行方案的成本由铁路企业成本和旅客出行成本构成，借助于文献［6］的处理手法，将列车开行方案的成本表示为列车运行时间和旅客出行时间的线性组合.列车运行时间和旅客出行时间的求解方法如下.(1)列车运行时间.尽管1列16辆编组高铁列车的载客量约等于1列8辆编组高铁列车载客量的2倍，但前者成本远未达到后者成本的2倍，这一点可以从两者均只占用1条运行线看出.引入列车编组权值^:对于8辆编组列车，ZT=1；对于16辆编组列车，1<CT<2.注意到1列列车的运行时间等于列车终到时间与始发时间之差，利用列车编组权值，可获得所有列车的运行时间为(2)旅客出行时间.旅客出行时间包括出发时间偏差、乘车时间和换乘时间，其中出发时间偏差为旅客计划出发时间与实际上车时间的偏差.旅客出行时间可以表示为这3部分的线性组合.对于给定的列车开行方案Q，借助于文献［7］中提出的基于时刻表的高铁客流分配方法，对时变需求进行分配，获得已分配客流量的旅客出行总时间W2(Q).对于因能力受限而未分配客流量，引入一个充分大的惩罚因子，获得未分配客流量的惩罚费用W3(Q).客流分配过程还可以获得每1列列车的客座率，它是评价列车开行方案的重要指标，设计优化算法时是调整开行方案的重要依据.(3)优化模型.对于列车运行时间W1(Q)、旅客出行时间p2(Q)和惩罚费用p3(Q),引入加权参数a和B，组合生成列车开行方案的优化目标Z(Q)=ap1(Q)+B()p2(Q)+W3(Q).建立列车开行方案优化模型为s.t.式(1)~式(12)列车开行方案优化模型式(14)，式(1)~式(12)是一个Stackelberg博弈模型(主从博弈)，主体方为铁路企业，优化列车开行方案；从属方为出行旅客，针对铁路企业给定的列车开行方案选择出行，产生客流分配结果，获得旅客出行时间的W2(Q)和惩罚费用p3(Q).铁路企业根据列车运行时间W1(Q)、旅客出行时间W2(Q)和惩罚费用p3(Q),按照式(14)对列车开行方案进行综合评价.鉴于模拟退火算法适用性和鲁棒性较强的特性，我们采取模拟退火算法求解列车开行方案优化模型，算法框架如图2所示.下面仅介绍算法中初始解的构造和邻域解的搜索策略.（1）构造初始解.对于每个列车方案leL,在每个始发时段均开行1列无能力限制的列车，并在每个车站的每个时段内，均匀排列始发列车的发车时间.在不考虑能力约束的条件下进行客流分配，获得各列车区段上的客流量.根据每列列车各区段中的最大客流量，确定需要列车数量和编组.确定原则：除开行若干16辆编组满员列车外，若剩余客流量超过8辆编组列车定员，则再开行1列16辆编组列车；若在8辆编组列车定员的50%~100%之间，则再开行1列8辆编组列车；若不足8辆编组列车定员的50%，则不再开行列车.然后，在每个车站的每个时段内，均匀排列始发列车的发车时间.上述过程产生开行方案不满足约束条件时，按照客座率从低至高的顺序依次剔除，直至满足约束条件为止.（2）邻域解的搜索策略.降低编组.对于16辆编组的列车，若客座率低于某个阈值（比如45%），则降低为8辆编组.删除列车.对于8辆编组列车，若客座率低于某个阈值（比如50%），则将其删除.添加列车.对于剩余客流量，按照生成初始方案的方法添加列车.对于每个列车运行区段，若通过该区段的列车平均客座率达到某个阈值（比如80%），则添加1列列车，新添加列车的停站方案与客座率最高的列车相同，编组为8辆，始发时间安排在客座率最高且能力允许的时段内.拼接列车.对于运行方向相同、编组相同的列车A和B，若A的终到站与B的始发站相同，A的终到时间与B的始发时间之差不超过某个阈值（比如10min），且拼接后的运行区段仍然符合约束条件，则以一定概率将这2列列车拼接为1列列车，拼接后列车始发时间为列车A的始发时间，停站方案保持不变.提高编组.对于8辆编组的列车，若客座率高于某个阈值（比如90%），则以一定概率（比如10%）调整为16辆编组.调整列车始发时间.以一定概率（比如30%，并逐步降低）将列车始发时间提前或推迟一定时间（比如5min，并逐步降低）.5.1算例数据算例背景为京沪高速铁路，如图3所示，按下行方向将22个区间依次按序号编号.按照2014年7月1日的客流量优化列车开行方案，其中客流总量为167606人（篇幅所限，未列出OD时变客流信息）.线路的区间运行时间见文献［9］,划分时段的单位长度At=1h,对所有车站设置tstop（v）=6min.各区间全天通过能力均为230对列车，每小时通过能力为15对列车.借助于文献［6］和文献［8］的思想和大量计算结果分析，将目标函数权重设置为a=10000邛=1，旅客出行时间中的出发时间偏差、乘车时间和换乘时间的组合权值分别设置为3,1,2.5.2优化结果优化方案如图4所示，图中的实心点为列车的始发终到站，空心点为列车的中途停靠站.列车开行频率和编组如表1所示.结合表2可知，与初始方案相比，优化方案的列车运行时间降低5095min，旅客出行时间降低1.3x107min,列车总数减少22列，列车客座率提高9.17%，旅客出发时间偏差降低1min.表1中的实际方案是2014年7月1日运营的实际列车开行方案.两者对比可见，优化方案增加了13列8辆编组列车，减少了15列16辆编组列车，列车总数减少2列.将客流沿着铁路线推送加载，推送时间为所有列车的平均旅行时间，获得各线路区间各时段断面客流量（图5（a）.优化方案在各线路区间各时段运输能力（图5（b）略大于断面客流量，且整体变化趋势相似.由表2可见，优化方案的旅客平均出发时间偏差为31min，说明优化方案的列车分布与出行需求的时变性吻合较好.算法采用C#编程，程序运行时间大约为13min.算法收敛过程如图6所示，可以看出算法优化效果良好.由于高密度开行的高铁列车具有满足旅客出行时变需求的能力，所以高铁列车开行方案应该吻合旅客出行的时变需求，结合旅客出行时变需求优化高铁列车开行方案能够提高这种吻合程度.引入列车运行方案图优化列车开行方案，既能利用列车运行的时间信息，又能避免结合列车运行图综合优化的大规模计算.本文借助于基于时刻表客流分配方法所构建的高铁列车开行方案优化模型与算法贴切地表现了铁路企业与出行旅客的博弈关系，优化产生的列车开行方案具有良好的评价指标，特别是旅客上车时间与计划出发时间的偏差较小，算法具有较高的运算效率和收敛性.【相关文献】[1]史峰，邓连波，霍亮.旅客列车开行方案的双层规划模型和算法[J].中国铁道科学，2007,28(3):110-116.[SHIF,DENFLB,HUOL.Bi-levelprogrammingmodelandalgorithmofpassengertrainoperationplan[J].ChinaRailwayScience,2007,28(3):110-116.][2]何宇强，张好智，毛保华，等.客运专线旅客列车开行方案的多目标双层规划模型[J].铁道学报，2006,28(5):6-10.[HEYQ,ZHANFHZ,MAOBH.Multiobjectivebilevelprogrammingmodelofmakingtrainworkingplanforpassenger-onlyline[J].JournaloftheChinaRailwaySociety,2006,28(5):6-10.][3]付慧伶，聂磊，杨浩，等.基于备选集的高速铁路列车开行方案优化方法研究[J].铁道学报,,32(6):1-8.[FUHL,NIEL,YANGH,etal.Researchonthemethodforoptimizationofcandiate-train-setbasedtrainoperationplansforhigh-speedrailways[J].JournaloftheChinaRailwaySociety,2010,32(6):1-8.][4]FUHL,NIEL,MENGLY,etal.Ahierarchicallineplanningapproachforalarge-scalehighspeedrailnetwork:TheChinacase[J].TransportationResearchPartA,2015(75):61-83.[5]周文梁，史峰，陈彦，等.客运专线网络列车开行方案与运行图综合优化方法[J].铁道学报,,33(2):1-7.[ZHOUWL,SHIF,CHENY,