基于累积流变量的列车图优化模型

基于累积流变量的列车图优化模型

运行图是铁路运行方法的基础。制定和优化运行图是铁路运输组织领域的一个经典问题。对此,各国专家学者建立目标和约束条件各异的优化模型,并根据模型特点,设计不同的求解算法。但利用数学规划方法对列车运行图进行优化,精确的算法只能求解小规模算例,对于大规模问题必须采取不同的策略将原问题分解或简化,以求降低问题的规模,如国外CAR-EY列车运行图优化,无论是既有线上以旅客列车总旅行时间最短、货物列车开行数量最多,还是客运专线上以列车服务频次高、旅行时间短等为目标,本质均是有限时空资源分配的组合优化问题,尽管当前计算机运算速度和储存空间有较大发展,但是列车运行图的组合规模决定人们依然难以使用传统的方法直接求解大规模问题。因此,目前解决这类问题的思路主要分为两大类:一类为采用模拟人工编图的启发式算法或遗传算法、模拟退火算法等智能优化算法;另一类为将复杂的原问题分解为相对容易求解的子问题,进而获得原问题的较优解。国外有研究采用拉格朗日松弛算法求解列车运行图问题本文针对列车运行图的大规模有限时空资源分配本质问题,结合拉格朗日松弛算法对资源约束问题良好的分解效果及优化程度可评估的特点,以列车对“行车资源”的占用代替传统列车追踪间隔时间表示通过能力约束,考虑实际运营中的列车运行图要素(起停车附加时分、停站时间和各种追踪间隔时间),构建基于累积流变量的双线铁路列车运行图优化模型;构造拉格朗日松弛算法框架,建立“时间-空间-状态网络”以求解拉格朗日松弛子问题。最后通过实际运营中的列车运行图编制算例验证算法的效率与优化质量。1基于累积流变量的流程图优化模型1.1模型编码及计算为更好地研究影响列车运行图求解算法性能的关键要素,现对列车运行图问题进行适当的抽象和假设。假设列车在双线铁路网上运行,不考虑列车在站内的进路与到发线安排;行车闭塞方式为自动闭塞,追踪间隔时间固定且已知;列车在各区间的纯运行时分、起停附加时分已知且固定;列车的数量、起讫点、径路、停站方案已知;运行图的编制不考虑车底的运用。模型输入为:列车的等级、不同等级列车的区间纯运行时分、车站起动及停车附加时分、列车追踪间隔时分;列车运行径路,列车始发(接入)时间窗(在始发站或接入站的最早出发时刻至最晚出发时刻之间的时间段)、在各站的最小停站时分以及列车的权重。模型输出为列车在径路上各站的到达和出发时刻。据文献1.2列车追踪间隔时间对双线铁路,某车站某衔接方向同一时间内最多只能为某一列车办理到达或出发作业,只能依次为各列车单独办理到达或出发进路。从开始办理进路至进路解锁时间段内,其他列车不能办理相应的作业。因此可将车站某衔接方向用于办理到达或出发作业的时间看作待分配的时空资源。本文定义车站上列车占用的“行车资源”为各站列车到达与出发作业在时空上的占用许可,见图1,称为“接车资源”和“发车资源”。列车的到达(或通过)作业需要占用的行车资源自开始办理到达进路时开始,至到达进路解锁时止,见图2(a)。列车出发(或通过)作业需要占用的行车资源自开始办理出发进路时开始,至出发进路解锁时止,见图2(b)。当有列车办理到达(或出发)作业时,接车资源(或发车资源)被占用,否则接车资源(或发车资源)空闲。传统的列车追踪间隔时间设置目的是为了保证前后行列车占用同一线路资源,在时间上不冲突,追踪间隔时间的值可根据办理列车进路各环节的时间组成计算得到,与本文提出的“行车资源”占用是等价的。因此,可用列车对“行车资源”的占用时间分配刻画列车的追踪间隔,具体的分析为:列车在车站办理到达或出发进路主要分为3个阶段:当列车在本站停站时,占用时间根据以下起止时刻确定:t上述占用时空资源要根据列车速度、车站轨道电路结构、接发车进路情况确定。列车出发追踪间隔时间包括:(1)前行列车从车站出发至完全离开车站进入区间的时刻;(2)与后行列车办理出发作业时间的组合。若前后两列车均从车站起动出发,则I列车到达追踪间隔包括:(1)前行列车到达车站时刻起至到达进路解锁的时间;(2)办理后行列车到达作业时刻起至该列车到达车站的时间。若前后两车均到达停车,则I列车通过追踪间隔包括:(1)前行列车通过车站时刻起至列车完全离开车站进入区间的时刻;(2)前行列车出清出发方向第一离去区段后办理后行列车通过作业时刻,至后行列车通过车站的时刻止的时间。I以上分析说明,列车车站追踪间隔时间可用列车占用车站“行车资源”组合等价表示。车站的到达、出发追踪间隔时间一般是列车追踪间隔时间的决定性因素,但对于长大闭塞分区等区间追踪间隔时间是决定性因素的情况,可通过数据预处理,将列车在区间追踪间隔的最大值用该区间前方站的出发间隔时间或后方站的到达间隔时间表示,以统一使用列车的车站行车资源表示追踪间隔。1.3基于累积流变量的列车全负荷建模定义路网中车站节点集合为V,区间弧段集合为E,车站节点标号为i,j,k;列车集合F,集合中各列车标号为f。在列车运行图的时间维度上,采用累积流变量(CumulativeFlowVariables)的建模方法。累积流变量是在时间轴上,将时间按照固定的单位长度进行离散化,并使用一组0-1变量表示某参量在每个离散时刻的状态。对于列车到发时刻,传统建模方法使用连续变量例如图6(b)中,列车在t=5时离开车站i,则t<5时,d定义接车资源与发车资源的占用0-1变量分别为y式中:T列车越行问题本质是列车在区间的运行顺序在某车站发生交换。由于车站接车方向与发车方向的行车资源是分别定义的,二者相互独立。当列车发生越行对于越行站是同一对前后行列车占用接车资源与发车资源的占用顺序发生交换。若车站衔接多方向,可对每个衔接方向的线路各定义一组出发与到达行车资源,当不考虑车站内进路冲突的前提假设下,使模型能够适应多方向情况。使用累积流变量方法建模可使用线性方程刻画列车对行车资源占用的过程以及行车资源状态随时间变化的过程,即将线性优化与离散系统仿真融合在一起,为轨道交通运输组织优化中引入复杂要素提供手段;其次,用该方法建立的模型,重点在于列车对行车资源的占用关系,而非传统运行图优化模型中的列车与列车运行间隔时间关系,便于对原问题进行分解,实现复杂问题求解的目标。1.4基于op的基于约束的列车状态变化模型对于列车运行图编制的目标,有列车总旅行时间最短、旅客换乘时间最少等。本文研究的重点在于可接受的求解时间内提升列车运行图求解的质量,而导致问题难以获得最优解的原因在于复杂的约束条件,目标函数可以根据不同的编制目标进行改进。因此,选取目标中最具有代表性的加权总旅行时间最短为目标,对于有特定目标的编图问题,目标函数可以在此基础之上扩充。列车运行图优化模型的目标函数是加权总旅行时间最短为式中:o模型约束条件为(1)列车到达、出发事件状态约束该组约束保证对于表示列车f在车站上作业的同一组累积流变量随着时间的推移最多只能发生1次变化,且只能从0向1变化,保证列车进入弧段或离开弧段事件从“尚未发生”到“已经发生”的状态转变最多只能发生1次。(2)区间进出先后顺序约束该约束保证列车进入区间的时刻不得晚于离开本区间的时刻。(3)出发时间窗式中:EST设置出发时间窗约束,可以保证列车在规定的时间范围内出发,尤其是接入到本区段的列车,需要以衔接区段交出列车的时刻作为本区段列车运行图编制的输入条件。同时设置出发时间窗也可以减小问题的解空间,缩小搜索的范围。(4)车站最小客运业务停站时间式中:w(5)区间运行时分约束式(12)~式(14)中:x式(12)、式(13)将列车的停车标记x(6)列车占用行车资源标记约束式中:(7)能力约束每个行车资源被占用的次数是有限的,同一行车资源仅能被一列车占用。2添加罚项类型拉格朗日松弛原理是将问题中的难约束松弛,并将其作为惩罚项添加到目标函数中,使约束条件简化。通过求解拉格朗日松弛问题,可以获得原问题的最优边界,同时通过不断迭代更新拉格朗日乘子,使得松弛问题的解逐渐逼近原问题的最优解2.1效率约束目标函数基于累积变量的列车运行图优化模型中,通常认为制约模型求解效率的约束是能力约束目标函数为式中:ρ通过对上述目标函数式进行恒等变换,可得到式中:2.2时空网络中控制变量的确定在拉格朗日对偶问题ZD()中,由于松弛约束式(17),使用式(6)~式(16)刻画单个列车运行过程中的时空逻辑,使各列车之间的关联被解除,而目标函数是各列车时空路径的目标函数LR由于约束中包含列车是否停站的决策变量x(1)列车的时空逻辑起点和逻辑终点表示列车在时空网络中的生成与消失;(4)通过节点表示通过列车的到达与出发作业。在上述的节点上根据列车的作业类型不同构建弧段,正确地表示车站起停附加时分和列车间隔时间。时空网络中有3类弧段:(1)起止弧表示列车从逻辑起点进入时空网络,以及列车从时空网络离开前往终止节点的弧段;(2)运行弧表示列车在两个车站间的运行;(3)停站弧表示列车在某车站内从到达至出发的状态转变。通过模型中各种约束建立每列车对应的所有可选时空路径构成1个完整的时空网络,通过求解该时空网络的最短路径可求得问题LR2.3拉格朗日乘子的调整在2.1节中,拉格朗日松弛对偶问题ZD()在给定拉格朗日乘子时其解是一定的,为使拉格朗日对偶问题的解逐渐逼近原问题的最优解,要通过迭代更新拉格朗日乘子的值。迭代过程中,采用次梯度方法对拉格朗日乘子进行更新,为式中:q为当前的迭代次数,式(20)表示新的拉格朗日乘子与当前的拉格朗日乘子及本次迭代求解得到的时空资源占用次数有关,在当前拉格朗日乘子的基础上,根据本次求解中列车对该资源的占用次数,对拉格朗日乘子进行调整。在拉格朗日松弛问题中,拉格朗日乘子的现实含义是“时空资源费用”,即列车占用“时空资源”的代价,更新拉格朗日乘子的次梯度法则是根据本次迭代中列车对资源的竞争结果情况对“时空资源费用”进行动态更新。将列车对时空资源的请求看作“需求”,将线路能力看作“供给”,将拉格朗日乘子的值看作“价格”。各次列车首先根据时间效益最大的路径,独立地向时空资源发出占用请求,各时空资源根据所有列车的占用请求与自身能力的匹配情况,使用次梯度法更新拉格朗日乘子值,即根据“供需关系”对各资源“定价”,从而影响下次迭代中各列车在时空网络中的路径选择。通过“资源定价”与“路径选择”过程的不断迭代,从而解决运行图优化的核心问题———有限时空资源的优化分配。2.4启发式求解方法由于使用拉格朗日松弛方法将原问题分解后,得到的解可能是不可行解。因此需要提供高效获得原问题可行解的方法。现使用启发式算法,即把拉格朗日松弛求解得到的结果作为启发信息,按照一定的顺序逐个列车进行规划,从而求得可行解。该启发式方法在本质上是滚动式求解方法,关键是如何确定进入规划列车的顺序。采用按照列车的LRPLRP铺画过程中,使用与求解拉格朗日松弛问题同样的最短路径方法进行求解,并同时对占用进行标记。算例验证中,如果该启发式方法不能获得可行解,即有列车不能被规划,则调整这些规划失败列车的优先级,优先铺画前次规划失败的列车。3计算机软件仿真将京广高速铁路武汉—广州南区段(共18座车站)作为算例对模型与算法的可行性和求解效率进行分析。使用ILOGCPLEXV12.3软件求解原问题与线性松弛问题,拉格朗日松弛算法框架在VisualStudio2012平台上使用C#语言实现,算法运行环境为1台CPU为IntelXeonE55202.27GHz×2,8GB内存的台式计算机。首先采用武汉—长沙南区段7座车站对算法的可行性和性能进行初步验证。算例设置求解总时间长度为180min,时间离散化后的铺画时间单位为1min,列车出发时间窗为全时间域(0~180min),列车权重均设为相等,测试随着列车数量增加求解质量与求解时间的变化。实验首先使用CPLEX分别计算模型的最优解与线性松弛解(下界)。针对相同实验数据集,再次利用拉格朗日松弛算法框架进行200次迭代计算。求解结果表明,随着列车数量增大,CPLEX求最优解变得越来越困难,当列车数增加到8列时,在设定时间内(7200s)不能完成求解过程,但将原问题进行线性松弛后,CPLEX能够较快地求解出问题的下界。与CPLEX求解出的线性松弛生成的下界相比,求解8列车时,拉格朗日松弛算法得到的下界质量有11.13%的提升。进一步分析CPLEX与拉格朗日松弛算法在求解问题下界方面的效率,当列车数量较少时,CPLEX求解速度比使用拉格朗日松弛算法快,但是当列车数量增多(大于32列)时,拉格朗日松弛算法具有明显的效率优势。使用拉格朗日松弛算法时,上下界间隔将随着列车的数量增加而增加,见图9。以武汉—广州南全线下行方向为背景测试模型和算法的性能。设定全天(1440min)下行方向开行110列车,时间离散化后的铺画时间单位为1min,为每列车设置30min的始发站出发时间窗,并根据列车的等级、停站数量、旅行时间设置权重。利用拉格朗日松弛算法进行200次迭代,总耗时10448s,收敛的上下界间隔为0.19%,见图10。4车分解算法优化根据我国双线铁路列车运行图编制特点,考虑列车起停附加时分和列车追踪间隔等关键要素,构建基于累积流变量的列车运行图0-1整数规划模型。针对运行图优化问题求解困难的问题,结合模型特点提出拉格朗日松弛算法框架,对问题按照列车分解,针对子问题特点,提出改进的列车运行时空状态网络并设计子问