基于Edmonds-Karp算法的输入排队调度

输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的。因而在调度算法理论研究中把应用了二部图最大匹配的MaximumSizeMatching和MaximumWeightMatching算法作为目前各种调度算法性能评价标准。Edmonds-Karp算法是图论中求解网络最大流的经典算法之一。该文介绍了如何使用Edmonds-Karp算法求解二部图的最大匹配问题,并且应用算法于输入排队调度算法仿真中,得出经典MSM和MWM算法的性能仿真曲线,为进一步研究调度算法打下了理论基础。

CTCS-3级列控系统车载设备测试序列优化生成方法

根据车载设备功能测试的需求,研究基于中国邮路算法优化生成CTCS-3级列控系统车载设备测试序列的方法。在分析测试序列构造方法的基础上,将测试序列的优化生成问题转换为求解1个具有多重弧的有向图的中国邮路问题。针对测试序列的特点,利用Edmonds-Johnson算法和LINGO建模工具对中国邮路问题进行求解,即通过构造容量网络、求解最小费用最大流、欧拉图寻迹等步骤,找出最优邮路。针对求解结果有可能导致测试序列过长的问题,提出1种有效的截短方法,实现了生成结果的二次优化。以CTCS-3级车载设备模式转换示意图为例,给出优化生成测试序列的具体过程。

采用“分区+搜索”模式的大电网最优解列断面搜索方法

针对大电网受到大扰动失稳后失步崩溃前应及时进行解列的问题,提出一种"分区+搜索"模式的最优解列断面搜索方法。该方法首先选择扰动前后各节点电压幅值和相角的变化量作为特征量,采用模糊C均值聚类算法将电网结构分为稳定区域、扰动区域和解列区域。然后以最小潮流冲击为目标函数,采用Edmonds-Karp算法和Dijkstra算法在解列区域求解出最优解列断面。该方法不需要对电网结构进行化简计算,且计算复杂度较低,可以在线获得最优解列断面。通过对IEEE 118节点系统和某实际大电网系统进行仿真计算,并与现有方法进行对比,证明了该方法的有效性和快速性。

网络化运营条件下城市轨道交通末班车时刻表优化研究

城市轨道交通成网运营后,列车运行计划编制问题也变得复杂。为统筹协调全运输网络内的换乘衔接,优化城市轨道交通末班车时刻表,针对城市轨道交通末班车的开行特点,以最大限度满足旅客需求为目标,构建末班车衔接方案的赋权有向图模型,提出一种结合客流需求的末班车到发时刻编制算法,即改进的Edmond算法,求解末班车衔接方案,并推算路网末班车时刻表。最后,通过算例对模型算法进行验算。结果表明,该算法可以根据需求产生相应方案,为城市轨道交通网络运营组织提供决策依据。