A routing algorithm for industrial wireless network based on ISA100.11a

ISA100.11 a industrial wireless network standard is based on a deterministic scheduling mechanism.For the timeslot delay caused by deterministic scheduling,a routing algorithm is presented for industrial environments.According to timeslot,superframe,links,channel and data retransmission of deterministic scheduling mechanisms that affect the design of the routing algorithm,the algorithm selects the link quality,timeslot delay and retransmission delay as the routing criteria and finds the optimum communication path by k shortest paths algorithm.Theoretical analysis and experimental verification show that the optimal paths selected by the algorithm not only have high link quality and low retransmission delay,but also meet the requirements of the deterministic scheduling.The algorithm can effectively solve the problem of packet loss and transmission delay during data transmission,and provide a valuable solution for efficient data transmission based on determinacy.

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

为矿井水灾提供最佳逃生路线,提高应急救援效率,首先引入当量长度,结合水流等巷道相关因素,求解到达安全地点的时间最短路径;其次根据一般矿井具有多个逃生出口的特性,提出一种基于偏离路径的煤矿水灾Yen-K最优路径算法,分别求出从源节点到每个目标节点的前k则最优路径;最后按照长度大小排序求得的所有路径,并结合矿井具体实例选取所需的前若干条逃生路线。在MATLAB环境下,对文章算法与传统的Dijkstra算法、K最短路径(KShortestPaths,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最短路径算法进行线网优化.首先运用道路空间资源要素和线路重复系数这2个约束条件实现对初始网络图中有效边的筛选,形成备选线路集合,其次将非直线系数和节点综合重要度这2个约束条件组成联合熵权,将该联合熵权作为现代有轨电车最优路径的判定参数,从而构建满足多约束条件下的现代有轨电车线网优化方法.最后,以南京河西新城现代有轨电车线网优化为例,验证了该方法的有效性,表明k最短路径算法是适用于现代有轨电车线网规划的有效方法,该方法可为现代有轨电车线网规划提供参考.

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

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

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

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

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

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

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

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

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

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

基于启发信息并行求解无环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条路径问题的求解算法研究

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

基于K路径算法的多无人机协同航迹规划

对于满足无人机团队中各机同时到达目标这样一个特定的协同要求,首先采用K路径算法实现了无人机的多航迹规划,然后采用速度控制和K路径算法相结合的办法实现了各无人机之间的时间协同。对整个协同航迹规划问题,采用一种分散式求解方法,把高维优化问题分解成低维、计算量小、通讯数据少的问题。

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

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

K最短路径算法与应用分析

为应对日趋庞大的网络规模和复杂的约束条件给解决k最短路径问题带来的挑战,同时给k最短路径在图书情报领域的研究提供建议,对研究现状和算法成果进行总结。首先,介绍k最短路径问题的基本概念。其次,对国内外k最短路径问题的算法思想和应用领域研究进展进行梳理,算法思想包括偏离路径算法、删除路径算法、标号算法、智能算法等,主要的应用领域有交通运输、通信网络、电力系统、图书情报领域等。最后总结k最短路径待解决的问题以及未来研究的方向。

基于机器学习算法的卷烟营销智能客户拜访策略研究

为提高卷烟行业客户经理的工作效率和服务质量,提出一种基于机器学习算法的卷烟营销智能客户拜访策略。在构建卷烟客户价值分类模型的基础上,利用K均值聚类机器学习算法对零售客户进行分类,合理设置LKH超启发算法和Dijkstra最短路径算法的参数,对客户经理拜访路径进行最优规划和智能导航。仿真结果表明,基于机器学习算法的卷烟营销智能客户拜访策略显著提高了客户经理人均拜访户数、商户满意度,大大缩减了户均在途时间和商户拜访服务覆盖周期。文中提出的策略有助于推动卷烟营销工作质量变革、效率变革和动力变革。

求解k最短路径问题的混合遗传算法

遗传算法求解问题的关键在于对问题的解进行编码,同时需要构造出适应度函数。结合k最短路径实际问题,重新定义了一种染色体编码方式,并且新构造了符合该问题的适应度函数。标准遗传算法采用固定的交叉率和变异率,在应用过程中存在收敛过慢、早熟及稳定性差的缺点。因此,提出了一种改进的自适应遗传算法,对交叉率和变异率采用自适应方式,构造了确定交叉率和变异率的公式,加快了算法收敛速度。同时结合模拟退火的Metropolis准则对子代个体的接收做出选择,克服了算法容易早熟的问题。仿真结果表明,改进后的混合遗传算法可以求解k最短路问题,并且在寻优精确度、时间效率、稳定性上均优于标准遗传算法。

基于扩展KMCSP的国际航线运价搜索模型及算法

为提升国际航线运价搜索效率,建立一个国际航线运价搜索的EKMCSP模型,该模型基于K条多约束最短路径(KMCSP)问题并进行扩展。国际航线运价搜索的各种因素被表示为EKMCSP模型中的变量、约束和目标;针对建立的国际航线运价搜索EKMCSP模型提出A*Level算法,结合国际航线运价搜索的特点,采用有限层搜索的思想,提高搜索效率并减小搜索规模。大量实验结果表明,该算法可实现国际航线运价搜索的EKMCSP问题的快速求解,且解集具有较高的正确率。

基于k短路径的兵力机动路线优化方法

由于传统Dijkstra算法只能求解最优路径,结合兵力机动路线选择的需要,将求解k短路径的实用算法引入到兵力机动路线优化问题中,给出了算法的数据结构和步骤。在道路权重的确定上,提出将路程、通行能力和安全性三项指标相结合的思想,并给出了综合权重的计算方法。仿真实验表明所提方法具有较强的实用性。