铁路行车调度03.16.doc

高速铁路单个列车运行冲突消解研究高速铁路单个列车运行冲突消解研究摘要：为研究高速铁路列车运行冲突消解问题，提出了各类列车运行冲突单个冲突的消解策略。分析了平移运行线、交换运行线、变更停站和越行方案以及数学规划方法等4种冲突策略的含义。根据冲突消解代价计算的方法，以最小冲突消解代价为优化目标，研究了高速铁路到达间隔时间冲突和出发间隔时间冲突、区间冲突、到发线运用冲突运用平移运行线、交换运行线、变更停站和越行方案等三种策略进行冲突消解的方法和过程。关键词：高速铁路，列车运行，冲突冲突，消解代价，单个冲突铁路行车调度的主要任务是按照一定的优化目标消解列车之间的冲突，确定合理的列车运行顺序，对列车运行图进行优化调整。列车运行冲突消解是一个对冲突列车占用运输资源的次序和时间的重新确定问题。不同的列车运行冲突消解方案，将带来不同的列车运行调整效果，影响行车指挥质量。因此，列车运行冲突消解方案的好坏直接影响行车指挥的效果。列车运行冲突的消解是通过变更列车运行次序和到发时间来消除列车之间对运输资源占用时间的重叠或使相关技术设备的运用满足列车的技术作业要求。对于铁路列车运行冲突消解策略的研究，国内外专家和学者近年来开展了大量的研究工作，并取得了一定的研究成果。D .ArianoA提出了三种冲突解决的方法：简单调度规则( 列车先到先发和列车先到后发) ；基于选择图的启发式算法；基于分枝定界算法的定速度列车运行优化方案，并运用分枝定界方法确定了总体列车的排序和局部列车径路解决了列车间的实时冲突消解问题1,2。MMazzarello 提出了一种分布式智能算法进行冲突解决，基于区域行车指挥中心数据进行全局优化，并通过两个实例进行了验证3。Rodriguez 利用约束规划模型解决节点处列车运行径路计划时将列车间冲突作为模型的一个约束条件进行考虑，得到了一个无冲突的径路安排计划4。Maree Lake通过运用局部搜索、禁忌搜索算法和仿真技术，利用维修作业与资源利用短期计划的协同优化解决了列车运行和固定设备维修之间的冲突。C W Tsang利用遗传算法研究了铁路衔接点的冲突消解问题并通过仿真手段对算法的效果进行了验证6。周磊山提出了疏解冲突的一般方法是采用错开冲突事件的发生时机，它包括两个方面的含义：一是根据冲突类型和冲突性质，确定两冲突事件的放行顺序，二是根据放行顺序确定待避事件的滞后量。周伟提出了列车运行调整过程中简单冲突和组合冲突的解决方法框架和思路。史峰等提出了单线铁路冲突的形式及化解的方案及最早冲突优化算法。上述研究工作主要是利用复杂的数学规划方法和现代求解算法研究并试图消解列车运行冲突，对列车运行冲突的消解机理及策略研究缺乏，且冲突消解的对象主要是静态冲突和当前冲突，在实际应用中具有较大的局限性。高速铁路列车运行冲突的消解是对单个列车运行冲突消解方案的全局综合优化，单个冲突消解是全局优化的基础。提出高速铁路列车运行冲突消解的四种策略，以最小冲突消解代价为依据，考虑冲突消解的后效性，对各类车站间隔时间冲突、区间冲突、到发线运用冲突等常见冲突的消解策略进行了研究并给出了各类冲突消解效果评价的标准。1 冲突消解策略概述列车运行调整的列车运行线自我恢复阶段仅是列车运行冲突消解的辅助手段，在列车受到随机干扰后通过充分运用运行图冗余时间，可以在一定程度上吸收随机干扰延误时间，减少冲突发生的可能性，但对冲突消解起决定性作用的还是平移运行线、交换运行线、变更停站和越行方案以及数学规划方法四种策略：1.1策略 平移运行线当列车技术作业间隔时间小于相关作业标准而发生列车运行冲突时，通过合理平移冲突点相关运行线，使列车技术作业时间间隔大于等于相关作业时间标准。例如：当两列车存在1min的发车间隔时间冲突时，采用将后行列车向后平移1min，则可消除发车间隔时间冲突；又如在Sn1站发现具有大量换乘旅客的列车i在Sn站与旅客需换乘列车j的出发时刻之间存在接续时间冲突，则可行的方法有：如果列车i在Sn1站可以左移，则左移列车i，将列车i的出发时刻提前；如果列车i在Sn1站不能左移，而列车j在sn站的出发时刻可以右移，则右移列车j；前两种方法组合运用。1.2策略 交换运行线当已经发生或即将发生列车运行冲突时，通过交换相关列车运行线在车站的出发顺序以消除相应的冲突。例如：列车i和列车j依次离开Sn1站，由于前行列车i的晚点延误及后行列车j的速度标准高于列车i，导致两列车在区间qn1将存在区间冲突的可能，为了消除此冲突，在Sn1站采取交换两列车出发顺序的措施，从而消除该潜在的冲突。1.3策略 变更停站和越行方案该策略是通过改变列车的停靠车站、停站数以及列车的待避和越行点来改变列车运行次序，进而达到消除列车运行冲突的目标，它是策略的拓展。例如：对于策略所提到的例子，如果两列车均为在Sn1站通过，但为了消除列车i和列车j潜在的潜在区间冲突，可令本该在Sn1站不停车的列车i停车避让列车j，以消除潜在的区间冲突。又如列车j计划在Sn站越行列车i，但为了消除区间qn1的潜在冲突，而将该越行更改为在Sn1站进行。1.4策略 数学规划方法根据一定的冲突消解和列车运行调整目标，利用数学规划方法寻求列车运行冲突的组合优化，从全局角度制定冲突消解方案。例如：基于晚点列车数最少或正点率最高的列车运行调整目标，建立相应的数学优化模型求解冲突的消解方案，确定各列车的运行顺序。高速铁路列车运行冲突的消解策略可分为简单冲突消解和组合冲突消解两步。简单冲突消解是对单个冲突进行消解，其消解的目标仅是针对单个冲突，消解冲突的主要策略为前三种。组合冲突消解是站在全局优化的高度研究多个冲突的整体消解，利用数学规划方法进行组合冲突消解方案的确定，但具体的冲突消解策略依然是平移运行线、交换运行线、变更停站和越行方案三种。平移运行线、交换运行线、变更停站和越行方案等三种消解策略均需要使列车运行线产生一定的平移量，其往往是以部分列车的晚点运行为代价，在具体选择冲突消解策略时，首先分别计算冲突列车在一定平移量下的冲突消解时间代价及后效冲突，再计算冲突消解代价，选择所有列车冲突消解代价总和最小的方案为最终方案。2 列车运行冲突消解代价计算冲突消解过程分为两步：首先通过计算冲突消解的时间代价确定合理的列车运行偏移量，再以列车运行冲突消解的后效冲突为冲突消解方案的评价依据，计算各消解方案的冲突消解代价，从全局角度考虑高速铁路列车运行冲突消解方案的合理性并最终选择合理的冲突消解方案。选取列车正点水平、列车等级、列车在站停车裕度、列车旅程完成度、列车区间运行裕度等5个指标作为评估冲突列车运行状态指标，记冲突列车运行状态的评估指标值为Vi(ar)、各评估指标的权重记为(ar)，则用列车运行特征值表征列车可调整余地大小，表征冲突列车的运行优先级，将其作为冲突消解方案制定及确定列车运行次序的依据，具有较大列车运行特征值的冲突列车具有较高优先级10。定义1 列车运行特征值Tij冲突列车i在j站的运行状态，其值等于列车i各运行状态指标属性值与各指标权重的加权： （1）由于列车运行状态指标属性的取值均不小于1，因此恒有： （2）定义2 冲突消解时间代价若将列车运行特征值作为冲突列车时间平移的单位时间代价，则令其与相应消解策略下所得方案的列车运行时间平移量的乘积为冲突消解时间代价。一般情况下，冲突消解是将列车运行线向右平移。如果在冲突消解时允许运行线向左平移，则该列车的冲突消解时间代价为负值。若列车i与列车k在j站冲突，冲突消解方案Rj下列车i，k在j站的平移量分别为Tij和Tkj，两列车在j站的列车运行特征值分别为Tij和Tkj，则列车i和k的冲突消解时间代价为： （3） （4）冲突消解策略对应冲突方案的冲突消解时间代价越大，其冲突消解的效果越差，在冲突消解时需将具有大冲突消解时间代价值的列车优先保证，如果PijPkj，则列车i的运行秩序应优先保障。根据冲突消解时间代价确定冲突列车的运行次序，只能保证当前冲突在一定的消解要求下是可行的或较优的，但却不能保证冲突消解后对列车自身后续列车活动及其他列车的后续列车活动的影响程度最小，即此时的冲突消解仅能保证列车运行调整的局部较优，而不能保证全局最优。通过计算冲突消解后不同消解方案下后续列车活动的冲突可能性，从而对冲突消解方案的效果进行校验，将这个冲突可能性作为当前冲突消解的反馈信息及衡量冲突消解方案优劣的依据，这样便考虑了列车运行冲突消解的后效性，体现了从全局角度消解列车运行冲突和进行列车运行调整的思想。定义3 后效冲突在j站消解列车i的冲突后，列车未来各类列车运行冲突可能性的总和称为冲突消解方案的后效冲突，记为Vij，且有： （5）在已知列车当前活动时间的情况下，根据列车未来顺序执行的各活动作业环节、作业时间标准，可以实现对高速铁路未来行车作业与维修作业时间冲突、动车组接续时间冲突、列车运行与旅客换乘时间冲突、跨线列车跨线时间后效冲突的计算，记为，s =1，2，3，4，表示上述四类冲突类型。在已知列车当前活动时间的情况下，根据列车未来各活动作业环节、作业时间标准，可以实现对车站间隔时间和到发线运用情况的考察，从而实现对列车未来区间线路、到发线等运输资源的占用时间和次序后效冲突的计算，记为，t=1，2；表示区间冲突和到发线运用冲突类型。n为区段终端车站序号。冲突消解的后效冲突对于评估列车运行的状态演变、列车运行调整策略及调整效果具有重要的意义。以当前或即将发生的列车运行冲突消解后的冲突可能性作为评价冲突消解方案效果的评价标准，能够对各冲突消解方案下列车未来运行质量的比较，较基于当前冲突消解的列车运行调整方法更具有优越性和科学性。后效冲突考虑了未来各列车活动发生时刻的不确定性，以未来各列车活动冲突可能性为反馈信息调整冲突消解方案的方法能够在一定程度上减少未来冲突发生的可能性，是一种立足于全局的冲突消解和列车运行调整方法。将冲突消解方案的后效冲突作为列车运行冲突消解效果的评价依据，能够满足全局冲突消解的要求。由冲突消解方案的后效冲突的极性可以知道，后效冲突越大，说明消解方案越不合理。因此，将冲突消解方案的后效冲突作为冲突消解时间代价的惩罚因子加以考虑，即将各列车的后效冲突值作为乘子分别乘以其冲突消解时间代价，并将此值作为最终的列车运行冲突消解代价。定义4 列车运行冲突消解代价 列车i与列车k在j站冲突，冲突消解方案Rj下列车i，k在j站的平移量分别为Tij和Tkj，两列车的后效冲突值分别为Vij和Vkj，则列车i和k的冲突消解代价为 （6） （7）Rj的冲突消解代价为： （8）为了实现列车运行效果的最优，在进行冲突消解时，总是优先选择冲突消解代价最小的方案。欲追求所有列车冲突消解代价最小的方案，对于列车运行特征值大、后效冲突大的列车，需要认真制定其列车运行调整计划，降低其与其他列车的冲突，否则将对其他列车的运行产生巨大影响，为了实现此目标，则需使该列车的平移量趋于最小，这符合重点列车重点保障的列车运行调整原则。3 单个冲突消解策略3.1车站间隔时间冲突消解车站间隔时间冲突的消解又细分为到达间隔时间冲突和出发间隔时间冲突的消解。3.1.1到达间隔时间冲突消解当两列车发生如图1所示的冲突时，运用策略、策略和策略进行冲突消解。在tk时刻考察列车下一阶段的运行情况，由于列车i1晚点从s(j2)站出发，导致两列车在s(j)站的到达间隔时间TzId，要将该列车运行冲突消解，则需使两列车在s(j)站的TzId。采用策略消解冲突时，需将列车i2向右平移即可，将列车i2向右平移的平移量为T1i2=IdTz，为了满足列车i1的出发间隔时间标准，列车i1也需向右平移，平移量Ti1=T1i2。采用策略消解冲突时，则需要将列车i1平移至列车i2的右边，其平移量以保障两列车从s(j2)站出发的时刻满足发车时间标准，且由于列车i1晚点运行，可利用冗余时间吸收和消除晚点时间。采用策略消解冲突时，列车i2越行列车i1的车站由s(j)改为s(j1)，列车i1的平移量需保障两列车从s(j1)出发的时刻满足发车时间标准，且由于列车i1晚点运行，可利用冗余时间吸收晚点时间，平移量为：T3i1=di2(sj1)+If+minti1q(j1，j)+Imindi1(sj)。则各策略下列车运行冲突消解代价分别为： （9） （10） （11）选择最终消解策略及确定消解方案的依据为使冲突消解代价最小。3.1.2出发间隔时间冲突消解由于列车i1晚点从s(j2)出发，导致两列车在s(j)的出发间隔时间TzIf，要将该列车运行冲突消解，则需使两列车在s(j)的TzIf。采用策略消解冲突时，需将列车i2向右平移即可，将列车i2在区间q(j1，j)的运行线向右平移，平移量为T1i2=IfTz。采用策略消解冲突时，则需要在q(j1，j)将列车i1平移至列车i2的右边，列车的平移量为：T2i1=If+Tz。在采用策略的同时，也运用了策略，将两列车在s(j1)无越行作业改为有越行作业。两种策略下列车运行冲突消解代价分别为： (12)取min 对应的冲突消解策略为列车出发间隔时间冲突消解策略。3.2到发线运用冲突消解某站到发线运用冲突的消解是在到发线运用不足的情况下确定合理的列车占用到发线顺序，以使冲突消解代价最小。即在tk时刻有nj(njN+，nj1)列车申请s(j)的到发线，而s(j)此时的可用到发线数mjnj(mjN)。则此时必存在至少一列车需等待s(j)的到发线空闲，设等待时间为Ti，则到发线运用冲突消解代价等于所有冲突列车的列车运行特征值、后效冲突与各自等待s(j)到发线空闲时间乘积的加和。使到发线运用冲突消解代价最小的方案即是使各列车等待到发线空闲的代价最小。3.3其他冲突消解行车作业与维修作业冲突、列车运行与旅客换乘时间冲突、动车组接续时间冲突和跨线列车跨线时间冲突均是高速铁路不常见及为数不多的冲突，他们一般仅发生在特定的时间和地点，且这些冲突多为车站间隔时间冲突、区间冲突和到发线运用冲突消解并产生一定的列车运行延误后导致列车运行至特定地点或特定的时间内不能满足行车要求而产生的。因此，这些冲突是前述冲突消解的后效冲突需要在冲突发生站或区间之前的若干个车站提前消解，这些冲突的消解均是通过对车站间隔时间冲突、区间冲突和到发线运用冲突的合理消解来实现的，而不专门研究这些冲突的消解策略。4 结论高速铁路列车运行冲突消解是一个由大量单个冲突组合而成的复杂问题，本文研究是列车运行冲突全局优化的基础，以最小冲突消解代价为优化目标的列车运行冲突消解数学规划方法将另文阐述。（1）分析了平移运行线、交换运行线、变更停站和越行方案以及数学规划四种冲突消解策略的含义（2）重点研究了运用平移运行线、交换运行线、变更停站和越行方案等三种冲突消解策略在以列车运行冲突消解代价最小为消解目标时高速铁路到达间隔时间冲突和出发间隔时间冲突、区间冲突、到发线运用冲突等单个冲突的消解过程。 参考文献1 DAriano A，Corman F，Pacciarelli D，et alReal-time train conflict detection and resolution: global sequencing and local reroutingIn:van Zuylen H J ( ed) Proceedings 9th TRAIL congress，selected pa-persDelft University Press，Delft，2006: 7792.2 DAriano A，Pacciarelli D，Pranzo MA branch and bound algorithmfor scheduling trains in a railway network Eur J Oper Res，2007; 183( 2) : 643657 3 Mazzarello M，Copello R Conflict resolution in railway traf