基于KSP和重路由机制的WDM光网络路由优化

针对波分复用(WDM)光网络中的传统路由和波长分配(RWA)算法不能有效降低阻塞率的问题,提出了一种基于K-最短路径(KSP)算法和顺序主动光路重路由(S-ALR)机制的路由优化方案。将WDM全光网络构建成一个由顶点、边和权重构成的图模型;当一个随机光路请求(RLD)到达时,先利用KSP算法寻找一条距离最短的路径和替代路径集合;当一个RLD离开时,相应的WDM通道被释放后启动重路由过程,调整现有RLD的路径以此充分利用空闲链路。仿真结果表明,提出的方案能够有效降低网络的阻塞率。

基于标记边的城市轨道交通网络KSP算法

城市轨道交通网络票务清分和客流分配都需要以路径搜索作为基础。由于城市轨道交通网络拓扑结构图不适用标记点的路径搜索算法,如对其拓展将导致路径搜索时间延长。为此,基于标记边的思想,考虑进出站时间对路径选择的影响,提出适用于城市轨道交通网络的K最短路径(KSP)搜索算法,以实现无须拓展网络的KSP搜索。在北京城市轨道交通网络上的应用结果表明,与传统的标记点Yen算法相比,该算法计算效率显著提高,在搜索同一OD对之间的KSP时能够节省至少一半时间。

基于偏离路径的煤矿水灾Yen-K最优路径算法

为矿井水灾提供最佳逃生路线,提高应急救援效率,首先引入当量长度,结合水流等巷道相关因素,求解到达安全地点的时间最短路径;其次根据一般矿井具有多个逃生出口的特性,提出一种基于偏离路径的煤矿水灾Yen-K最优路径算法,分别求出从源节点到每个目标节点的前k则最优路径;最后按照长度大小排序求得的所有路径,并结合矿井具体实例选取所需的前若干条逃生路线。在MATLAB环境下,对文章算法与传统的Dijkstra算法、K最短路径(KShortestPaths,KSP)算法进行仿真对比分析,结果显示改进后的算法在求解矿井水灾逃生最优路径时更具准确性和实用性。

K最短路径算法综述

为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。

基于D-K算法的煤矿水灾多最优路径研究

矿井水灾时选择合理的逃生路线,需要考虑水及巷道其他因素的影响,引入当量长度来求解到达逃生地点用时最短最安全的路径。Dijkstra算法可求解从源节点到目标节点的最短路径,K则最优路径算法可求解从源节点到某一目标节点的前N条最优路径,矿井水灾时,为了避免拥挤,同一地点工作的人员可选择多个逃生井口进行逃生,但从源节点到某一目标节点的前N条最优路径并不一定是到其他逃生井口的前N条最优路径,基于这种思路,在Dijkstra算法的基础上,提出一种从源节点到其他所有逃生节点的前N条最优路径的新方法,并结合矿井具体实例,与Dijkstra算法和K则最优路径算法比较,用MATLAB仿真实现。

国际航线网络中K条最短路径算法改进与仿真

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析,研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题,提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略,减少了产生候选航线路径的时间,从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真,实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时,与Yen算法相比,运算效率提升了75.19%以上,能够为航线路径优化提供决策支持。

K优路径的一种求解算法与实现

求解最优路径的算法已经比较成熟,但国内外求解K优路径的算法还未见到。在作战指挥中,通常需要人们能够根据战场情况提供部队行动路线的多个方案供指挥员决策。针对这一军事需求,论文提出了一种求解K优路径的算法,给出了相应的数据结构和算法实现,同时从实现的角度对Dijkstra算法进行了改进。

基于前K最短路径的输电断面搜索新算法

过载支路切除引起的潮流转移是导致连锁过载跳闸的重要原因。本文分析了过载支路切除后的潮流转移特征,引入了潮流转移系数(FTF)的概念,并给出了输电断面新的定义。根据潮流转移的路径特征,给出了一种快速搜索输电断面的新算法。该算法通过把实时的电力网络转化成拓扑图,基于动态规划理论,通过在一个以过载支路为中心的拓扑子图内快速搜索出过载支路两端点间的前K条最短路径,并最终找出受潮流转移影响较大的输电断面,把对整个系统的安全性分析缩小到一个输电断面内,极大地减少了进一步分析的工作量,有利于防止连锁过载跳闸的发生。中国电科院CEPRI36节点系统的仿真结果验证了该算法的有效性。

一个求解k短路径实用算法

求解k短路径问题在决策支持系统和咨询系统中具有广泛的用途,文章基于Dijkstra算法,给出了一个求解k短路径实用算法,并且分析了算法的时间复杂度和空间复杂度。

面向城市交通网络的K最短路径集合算法

在城市交通网络中,为了优化交通流,需要搜索到符合出行需求K最短路径,并将OD(Origin-Destination)交通流合理分配到这些路径上.本文主要对搜索符合出行需求的K最短路径搜索算法进行了研究,解决了已有算法仅能搜索出单条满足最短及K最短条件路径的问题.根据Wardrop第二原则及路段阻抗函数理论,分析了路径集合搜索方法对优化城市交通流的必要性,并定义了城市交通网络中K最短路径集合的概念及选择条件,提出了一种面向城市交通网络的具有多项式时间复杂度的K最短路径集合搜索算法.仿真结果表明,本文所提算法可以搜索出满足出行需求的所有K最短路径集合,在该路径集合上进行交通流分配的效果明显优于传统方法.

K(≤3)条渐次短路径搜索算法的研究

Dijkstra算法是经典的最短路径搜索算法。该文在Dijkstra算法的基础上,提出了在单限制多权值的条件下k(≤3)条渐次短路径的搜索算法。算法的实例表明,该算法切实有效。

基于K-最短路算法的云制造多粒度访问控制技术

在分析了云制造访问控制的特殊性基础上,提出云制造访问控制模型MGAC,分析了MGAC向有向图的转换方法,基于Dijkstra算法,研究了多目标下K-最短路求解算法,并通过示例验证了方法的可行性。最后,通过K变化下的顶点数、目标数与CPU运行时间关系分析及相关算法的对比测试,对算法性能进行了讨论,证明了算法的有效性。

复杂网络中最短K条路径问题的求解算法研究

以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了基于改进的A*算法求解复杂网络中最短K条路径问题的算法,并以城市交通为例,对算法进行了验证。实验结果表明所提出的算法可适用于一般多重图中最短K条路径问题的快速求解,具有广泛的应用价值。

基于k最短路径算法的负荷停电风险在线评估

传统负荷评估方法结果的准确性取决于故障假设的规模,并且相应负荷转供的计算量大,难以满足在线评估的快速性要求。针对传统方法的问题,首先对在线停电风险评估的相关概念进行详细阐述和定义。在此基础上,提出一种改进的k最短路径算法求取不含环路的所有负荷供电路径,再进行安全校验,进一步得出负荷的可行供电路径用以计算负荷停电概率和停电风险值。算例表明,所提方法准确、全面和高效,可以有效反映负荷的停电风险。

基于k最短路径的现代有轨电车线网优化

为科学合理地进行现代有轨电车线网的优化与改进,基于现代有轨电车线网优化的约束条件,引入k最短路径算法进行线网优化.首先运用道路空间资源要素和线路重复系数这2个约束条件实现对初始网络图中有效边的筛选,形成备选线路集合,其次将非直线系数和节点综合重要度这2个约束条件组成联合熵权,将该联合熵权作为现代有轨电车最优路径的判定参数,从而构建满足多约束条件下的现代有轨电车线网优化方法.最后,以南京河西新城现代有轨电车线网优化为例,验证了该方法的有效性,表明k最短路径算法是适用于现代有轨电车线网规划的有效方法,该方法可为现代有轨电车线网规划提供参考.

基于改进K次短路径算法的有效路径搜索算法及实现

为提高有效路径搜索效率,结合ArcGIS具有的路径分析功能,以K次短路径算法为基础,依据重叠惩罚算法的原理,提出基于改进K次短路径算法的有效路径搜索算法。以ArcGIS为平台,给出了算法的实现方法。经过对实际路网的可视化测试,验证了改进算法具有较高的运行效率,为有效路径相关理论在ArcGIS平台的应用提供了一种技术手段和方法。

基于启发信息并行求解无环K最短路径

引入适用于非负权图的启发函数评估潜在偏离节点的代价,优先产生代价低的节点对应的候选路径;在迭代计算过程中,当候选偏离节点的代价大于候选路径中K条路径长度时,结束本次候选偏离路径计算,从而避免产生大量无用的候选路径;采用压缩邻接链表、组合数组优化图和路径在GPU储存器中的存储,采取顶点并行和边并行方法将比较耗时的删除和恢复节点操作并行化,以及并行化Dijkstra算法,在CUDA平台上设计实现GPU并行求解无环K最短路径算法P_AStart Yen.实验结果表明,P_AStart Yen比同类的GPU并行算法P_Yen平均加速7.30倍、最高加速14.38倍,比串行算法NIYA平均加速349.19倍、最高加速615.03倍.

基于标号算法搜索过程的K最短路算法设计

K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的Dijkstra标号算法.该算法在搜索过程中得到一条最短路径的同时,获得了大量的临时标号信息;在此基础上,继续采用该算法利用这些临时标号信息进行标号,可以获得其他严密K最短路;将该算法与交叉口有延误的最短路径算法相结合,可方便的计算城市交通网络中交叉口有延误的K最短路径问题;该算法简化了K最短路的计算过程,提高了算法的计算效率.最后,利用一个简单网络介绍了该算法的计算过程.

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近邻查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络邻接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近邻查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。

一种应用于路由规划的实用无环K路算法

在对已有第K条最短路算法进行分析和比较的基础上提出了一种新的无环K路算法。该算法基于最短路计算，具有复杂度较低、收敛快以及无环等特点，在路由规划中的应用以及仿真分析都证明本算法是有效、实用的。